Implementing the Yen's algorithm and its improved versions

[rajat1433]

This ticket aims at implementing the Yen's algorithm and its improved version for k shortest simple path enumeration between the source and the target. The implementation will be compared to the original yen's algorithm.

CC: @dcoudert

Component: graph theory

Keywords: gsoc19

Author: Rajat Mittal

Branch/Commit: fcfa3e6

Reviewer: David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/27859

[dcoudert]

Changed keywords from none to gsoc19

[rajat1433]

Author: Rajat Mittal

[rajat1433]

Branch: u/gh-rajat1433/27859_yen_algorithm_improved

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

2afbaef	yen's algorithm implementation
ede0d00	improved
ac4ff86	revert

[sagetrac-git]

Commit: ac4ff86

[rajat1433]

comment:4

This is the implementation of original yen's algorithm for k shortest paths which the method will return as an iterator. This will be compared with the improved yen's(Feng) algorithm which will be implemented shortly.

shortest_path methods are also enhanced by adding exclude_vertices and exclude_edges parameter which are required for Yen's or improved Yen's algorithm. If some improvements are possible please let me know so I can improve the above method.

[sagetrac-git]

Changed commit from ac4ff86 to b31f288

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b31f288

added one line

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9da4482

removed all_paths

[sagetrac-git]

Changed commit from b31f288 to 9da4482

[dcoudert]

comment:8

I'm a bit reluctant to the changes you did in shortest_path and bidirectional_dijkstra as it will slowdown these methods when exclude_edges and exclude_vertices are false. A significant effort has been put in optimizing these methods, so slowing them is not clever.

You must try to have the minimum possible impact on them. For instance do:

if not exclude_edges and not exclude_vertices:
    neighbors = nbr
else:
    neighbors = []
    for w in nbr:
        ...

you could also create exclude_vertices_int and exclude_edges_int to avoid code like
(self.vertex_label(u), self.vertex_label(w)) not in exclude_edges.

Is method yen_k_shortest_paths only for undirected graphs ?

[sagetrac-git]

Changed commit from 9da4482 to 3ca1945

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b7a49b4	improved the shortest_paths
3ca1945	removed xtra line

[rajat1433]

comment:10

I have made the changes in shortest_paths methods to have a minimal effect of exclude_edges and exclude_vertices.

yen_k_shortest_paths is for both the directed as well as undirected graphs as evident from the examples in the method.

            sage: g = DiGraph([(1, 2, 20), (1, 3, 10), (1, 4, 30), (2, 5, 20), (3, 5, 10), (4, 5, 30)])
            sage: list(g.yen_k_shortest_paths(1, 5, by_weight=True))
            [[1, 3, 5], [1, 2, 5], [1, 4, 5]]
            sage: list(g.yen_k_shortest_paths(1, 5))
            [[1, 2, 5], [1, 3, 5], [1, 4, 5]]
            sage: list(g.yen_k_shortest_paths(1, 1))
            [[1]]

            sage: g = Graph([(1, 2, 20), (1, 3, 10), (1, 4, 30), (2, 5, 20), (3, 5, 10), (4, 5, 30), (1, 6, 100), (5, 6, 5)])
            sage: list(g.yen_k_shortest_paths(1, 6, by_weight = True))
            [[1, 3, 5, 6], [1, 2, 5, 6], [1, 4, 5, 6], [1, 6]]
            sage: list(g.yen_k_shortest_paths(1, 6))
            [[1, 6], [1, 2, 5, 6], [1, 3, 5, 6], [1, 4, 5, 6]]

[dcoudert]

comment:11

Replying to @rajat1433:

I have made the changes in shortest_paths methods to have a minimal effect of exclude_edges and exclude_vertices.

you were too fast. You still have if not exclude_edges and not exclude_vertices: inside the for w in nbr:. Also, check if the order of the other tests could be improved.

yen_k_shortest_paths is for both the directed as well as undirected graphs as evident from the examples in the method.

The first lines of description are not clear. That's why I asked.

Plus it would be better to have a single line of description.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

70e86c1

improved

[sagetrac-git]

Changed commit from 3ca1945 to 70e86c1

[rajat1433]

comment:13

Oops! I have made the description more clear and also concised the checks and removed "if not exclude_edges and not exclude_vertices:" these from wherever unnecessary.

If there is further any improvement possible please let me know.

[dcoudert]

comment:14

What about:

-                        if exclude_edges and ((out == 1 and (u, w) not in exclude_edges_int) or (out == -1 and (w, u) not in exclude_edges_int)):
-                            if not exclude_vertices or (exclude_vertices and w not in exclude_vertices_int):
-                                neighbors.append(w)
-                        elif not exclude_edges and exclude_vertices and w not in exclude_vertices_int:
-                            neighbors.append(w)
+                        if exclude_vertices and w not in exclude_vertices_int:
+                            neighbors.append(w)
+                        elif (exclude_edges and 
+                              ((out == 1 and (u, w) not in exclude_edges_int) or 
+                               (out == -1 and (w, u) not in exclude_edges_int))):
+                            neighbors.append(w)

[rajat1433]

comment:15

I think there may be a problem in that, consider that w is not in exclude_vertices(there are other vertices though) but (u,w) is present in exclude_edges then w will be appended as a neighbor, but it should be not appended.

[dcoudert]

comment:16

+                        if exclude_vertices and w in exclude_vertices_int:
+                            continue
+                        if (exclude_edges and 
+                              ((out == 1 and (u, w) in exclude_edges_int) or 
+                               (out == -1 and (w, u) in exclude_edges_int))):
+                            continue
+                        neighbors.append(w)

[sagetrac-git]

Changed commit from 70e86c1 to 481ea41

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

481ea41

improvedcode

[sagetrac-git]

Changed commit from 481ea41 to 5b14b84

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

5b14b84

improved method name and description

[sagetrac-git]

Changed commit from 7871701 to 3ae912d

[dcoudert]

comment:150

I rebased on last beta and fixed merge conflicts. Then I added a test on random digraphs.

I have not yet identified new issues, and I hope I will not find any ;)

[dcoudert]

comment:151

I did the following test and I don't understand why Feng is significantly slower than Yen. Do you have any idea of the parts that must be improved ?

sage: def my_run(G, algo):
....:     i = 0
....:     for u in G:
....:         for v in G:
....:             if u == v:
....:                 continue
....:             it = G.shortest_simple_paths(u, v, by_weight=True, algorithm=algo)
....:             for p in it:
....:                 i += 1
....:     return i
....: 
sage: G = digraphs.RandomDirectedGNP(15, 0.1)
sage: while not G.is_strongly_connected():
....:     G = digraphs.RandomDirectedGNP(15, 0.1)
....:     
sage: for u, v in list(G.edges(labels=False, sort=False)):
....:     G.set_edge_label(u, v, randint(1, 10))
....:     
sage: %time my_run(G, 'Yen')
CPU times: user 623 ms, sys: 2.41 ms, total: 626 ms
Wall time: 626 ms
5841
sage: %time my_run(G, 'Feng')
CPU times: user 2.36 s, sys: 5.73 ms, total: 2.37 s
Wall time: 2.37 s
5841

[sagetrac-git]

Changed commit from 3ae912d to 82015e2

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

82015e2

made feng faster

[rajat1433]

comment:153

sage: g = DiGraph(graphs.Grid2dGraph(10, 10))
sage: sage: from sage.graphs.path_enumeration import feng_k_shortest_simple_path
....: s
....: sage: from sage.graphs.path_enumeration import yen_k_shortest_simple_paths
....: 
....: 
sage: q = feng_k_shortest_simple_paths(g, (0, 0), (9, 9))
sage: %timeit [q.next() for i in range(1000)]
1 loop, best of 3: 833 ms per loop
sage: %timeit [q.next() for i in range(1000)]
1 loop, best of 3: 906 ms per loop
sage: p = yen_k_shortest_simple_paths(g, (0, 0), (9, 9))
sage: %timeit [p.next() for i in range(1000)]
1 loop, best of 3: 1.31 s per loop

sage: sage: def weight_function(e):
....: ....: ....:     return 3


sage: g = DiGraph(graphs.Grid2dGraph(10, 10))
sage: sage: p = yen_k_shortest_simple_paths(g, (0, 0), (9, 9),weight_function=we
....: ight_function)
sage: sage: %timeit [p.next() for i in range(1000)]
1 loop, best of 3: 3.35 s per loop

sage: q = feng_k_shortest_simple_paths(g, (0, 0), (9, 9),weight_function=weight_
....: function)
sage: %timeit [q.next() for i in range(1000)]
1 loop, best of 3: 1.31 s per loop

[rajat1433]

comment:154

sage: sage: def my_run(G, algo):
....: ....:     i = 0
....: ....:     for u in G:
....: ....:         for v in G:
....: ....:             if u == v:
....: ....:                 continue
....: ....:             it = G.shortest_simple_paths(u, v, by_weight=True, algor
....: ithm=algo)
....: ....:             for p in it:
....: ....:                 i += 1
....: ....:     return i
....: 
sage: sage: G = digraphs.RandomDirectedGNP(15, 0.1)
....: sage: while not G.is_strongly_connected():
....: ....:     G = digraphs.RandomDirectedGNP(15, 0.1)
....:     
sage: sage: for u, v in list(G.edges(labels=False, sort=False)):
....: ....:     G.set_edge_label(u, v, randint(1, 10))
....:     
sage:  %time my_run(G, 'Yen')
CPU times: user 69.7 ms, sys: 157 µs, total: 69.9 ms
Wall time: 66.5 ms
405
sage: %time my_run(G, 'Feng')
CPU times: user 176 ms, sys: 7.98 ms, total: 184 ms
Wall time: 177 ms
405

[rajat1433]

comment:155

Though I have improved the speed of Feng's significantly from the version just before but still in some cases Yen is faster and in some cases Feng is faster.
Will look into more optimizations possible into Feng without breaking the algorithm....

[sagetrac-git]

Changed commit from 82015e2 to 3a2aca3

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

fabe87b	trac #27859: review edit in Yen
3a2aca3	trac #27859: review edit in Feng

[dcoudert]

comment:157

I did some minor edits in Yen and Feng.

In Feng, why are you adding/removing edges ? can't we avoid that ?

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4bdbe63	some improvement
034cb7f	Merge branch 'public/graphs/27859_enumerate_paths' of git://trac.sagemath.org/sage into public/graphs/27859_enumerate_paths

[sagetrac-git]

Changed commit from 3a2aca3 to 034cb7f

[rajat1433]

comment:159

Adding and Removing edges in Feng's is required when we find express edges so that we can update the head node of express edges directly to the target. (This is done because the cost of the path between the head of express edge and the target becomes zero as per the cost function defined by Feng in his paper.) And when we move to the next vertex for deviation of the current path we update the express edges and also remove the additional edges of some vertices we introduced previously which are no longer valid. Though I have tried not to remove the vertices and nodes in the graph by using exclude_vertices and exclude_edges set so that we don't have to remove and add again and again, but adding the edges from head of express edge to target was a necessity as described in the algorithm.

[dcoudert]

comment:160

I agree. So I propose to let speed-up improvements of the algorithms to future tickets.

Good to go.

[sagetrac-git]

Changed commit from 034cb7f to fcfa3e6

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

fcfa3e6

removing extra newline

[rajat1433]

comment:162

@dcoudert
I guess due to above change you have to positive review it again ;)

[dcoudert]

comment:163

Please don't do that. Such kind of modification can be postpone to another ticket.
We only reopen a ticket when something critical has to be done (fixing a bug, etc.).

[vbraun]

Changed branch from public/graphs/27859_enumerate_paths to fcfa3e6