Opened 4 years ago
Closed 3 years ago
#27859 closed enhancement (fixed)
Implementing the Yen's algorithm and its improved versions
Reported by:  Rajat Mittal  Owned by:  Rajat Mittal 

Priority:  major  Milestone:  sage8.9 
Component:  graph theory  Keywords:  gsoc19 
Cc:  David Coudert  Merged in:  
Authors:  Rajat Mittal  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  fcfa3e6 (Commits, GitHub, GitLab)  Commit:  fcfa3e661e0840adba52a7e7f4a5b692450a8bad 
Dependencies:  Stopgaps: 
Description
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.
Change History (164)
comment:1 Changed 4 years ago by
Keywords:  gsoc19 added 

comment:2 Changed 4 years ago by
Authors:  → Rajat Mittal 

Branch:  → u/ghrajat1433/27859_yen_algorithm_improved 
comment:3 Changed 4 years ago by
Commit:  → ac4ff86c1def01ca30d08bf20312ff3fbca664f7 

comment:4 Changed 4 years ago by
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.
comment:5 Changed 4 years ago by
Commit:  ac4ff86c1def01ca30d08bf20312ff3fbca664f7 → b31f288dc0a9663d5088ab065abf14d3a9c9f471 

Branch pushed to git repo; I updated commit sha1. New commits:
b31f288  added one line

comment:6 Changed 4 years ago by
Status:  new → needs_review 

comment:7 Changed 4 years ago by
Commit:  b31f288dc0a9663d5088ab065abf14d3a9c9f471 → 9da448297268b41bcd1df703969fb407cf664a68 

Branch pushed to git repo; I updated commit sha1. New commits:
9da4482  removed all_paths

comment:8 Changed 4 years ago by
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 ?
comment:9 Changed 4 years ago by
Commit:  9da448297268b41bcd1df703969fb407cf664a68 → 3ca1945f5fe323afbd5f26d5efe9a7f478ca1f68 

comment:10 followup: 11 Changed 4 years ago by
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]]
comment:11 Changed 4 years ago by
Replying to ghrajat1433:
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.
comment:12 Changed 4 years ago by
Commit:  3ca1945f5fe323afbd5f26d5efe9a7f478ca1f68 → 70e86c1c6935b53b0097c0ed908e1c37dd96a020 

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

comment:13 Changed 4 years ago by
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.
comment:14 Changed 4 years ago by
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)
comment:15 Changed 4 years ago by
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.
comment:16 Changed 4 years ago by
+ 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)
comment:17 Changed 4 years ago by
Commit:  70e86c1c6935b53b0097c0ed908e1c37dd96a020 → 481ea41cda6b7ef1b4d697a89d8bd0b97b6ec958 

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

comment:18 Changed 4 years ago by
Commit:  481ea41cda6b7ef1b4d697a89d8bd0b97b6ec958 → 5b14b84b95851cc07991e35fdf42c2d7f5dcd7e3 

Branch pushed to git repo; I updated commit sha1. New commits:
5b14b84  improved method name and description

comment:19 followup: 25 Changed 4 years ago by
 In fact,
exclude_vertices
andexclude_edges
could be any kind of iterable containers since we turn them directly to something else.
 You can do:
 if exclude_vertices:  exclude_vertices_int = set()  for u in exclude_vertices:  exclude_vertices_int.add(self.get_vertex(u)) + cdef set exclude_vertices_int = {self.get_vertex(u) for u in exclude_vertices} + cdef set exclude_edges_int = {(self.get_vertex(u), self.get_vertex(v)) for u, v in exclude_edges}
 You may also define
cdef bint exclude = exclude_vertice or exclude_edges
and then do a simpler testif not exclude
...
 Note that the set of vertices and edges that you exclude is sometimes called
forbidden
.
 pep8
in fact the error message could be
 raise LookupError("No path between %s and %s" % (x, y)) + raise LookupError("no path between %s and %s" % (x, y))
no path from/to an excluded vertex
or something like that.
 in Yen's algorithm, could you document the code
 I think that case
if not prev_path:
should be done before the while loop and that the while loop should bewhile heap_paths:
.
comment:20 Changed 4 years ago by
Commit:  5b14b84b95851cc07991e35fdf42c2d7f5dcd7e3 → 5164f340947cdfaca8d635f0d6e930df4a409e3b 

Branch pushed to git repo; I updated commit sha1. New commits:
5164f34  changes in c_graph.pyx

comment:21 Changed 4 years ago by
I have made the container description as an iterable and made the improvements in c_graph file in the above commit.
I think the positioning of if not prev_path: is correct still I will check it, I will be documenting the Yen's code soon in my next commit.
comment:22 Changed 4 years ago by
Commit:  5164f340947cdfaca8d635f0d6e930df4a409e3b → d22322cf4dfe6a4a9fd249dc03f64bec2f0bc46b 

Branch pushed to git repo; I updated commit sha1. New commits:
d22322c  documenting the yen's algorithm

comment:23 Changed 4 years ago by
Commit:  d22322cf4dfe6a4a9fd249dc03f64bec2f0bc46b → 55c187c22e02b665a97d301a8ddff9b20f31fe04 

Branch pushed to git repo; I updated commit sha1. New commits:
55c187c  documenting the yen's algorithm

comment:24 Changed 4 years ago by
Commit:  55c187c22e02b665a97d301a8ddff9b20f31fe04 → beb67d67e2153ca1f700b91f1d70c2d9f13ac55e 

Branch pushed to git repo; I updated commit sha1. New commits:
beb67d6  documenting the yen's algorithm

comment:25 Changed 4 years ago by
Replying to dcoudert:
 in Yen's algorithm, could you document the code
Done
If any improvement is possible let me know.
 I think that case
if not prev_path:
should be done before the while loop and that the while loop should bewhile heap_paths:
.
The thing is that it will enter this if statement only once and that too at the start. So it can be placed outside the while loop but placing it inside seems to give a kind of structure and avoid redundancy as the part after if else condition(line 16097) will be redundant if it is placed outside the while loop so I place it inside the while(True) loop.
comment:26 Changed 4 years ago by
Owner:  set to Rajat Mittal 

comment:27 Changed 4 years ago by
You must reorder the blocks like that:
# will enter here for the first time to compute the shortest path between source and target if by_weight: path = shortest_path_func(source, target, weight_function=weight_function) ... heap_paths.add(hash_path) # adding the path to the heap_paths set while heap_paths: (cost, path1) = heappop(heap_sorted_paths) # extracting the next best path from the heap hash_path = tuple(path1) ... prev_path = path1 exclude_vertices = [] exclude_edges = [] for i in range(1, len(prev_path)): # deviating from the previous path to find the candidate paths root = prev_path[:i] # root part of the previous path ....
comment:28 Changed 4 years ago by
Commit:  beb67d67e2153ca1f700b91f1d70c2d9f13ac55e → 353b3c368a322ad4cc2d40435cd3a6259a750fb7 

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

comment:29 followup: 34 Changed 4 years ago by
For feng's algorithm should I implement it here in this ticket or create a new ticket ? Actually Feng's algorithm is only for directed graphs so this algorithm in this tkt is important for undirected graphs and will be used to compare timings with Feng's algorithm. So I guess its best to implement a new method.
comment:30 Changed 4 years ago by
Commit:  353b3c368a322ad4cc2d40435cd3a6259a750fb7 → 0528edc5e690836abaf3cd366004ce4bfbc14563 

Branch pushed to git repo; I updated commit sha1. New commits:
0528edc  added tests

comment:31 followup: 32 Changed 4 years ago by
Commit:  0528edc5e690836abaf3cd366004ce4bfbc14563 → 20515f95fcb2cbf273de57718496e24a0a01caad 

Branch pushed to git repo; I updated commit sha1. New commits:
20515f9  revert back to set

comment:32 Changed 4 years ago by
comment:33 Changed 4 years ago by
Commit:  20515f95fcb2cbf273de57718496e24a0a01caad → f7abe8489de91ad8b0cbf745bb1001db85ae84b1 

Branch pushed to git repo; I updated commit sha1. New commits:
f7abe84  added more tests

comment:35 Changed 4 years ago by
I am planning to include some new parameters like
1.) include_vertices in shortest path functions
2.) reduced cost dictionary to shortest path functions
first one is for finding the all yellow node path in the graph as per the feng's algorithm since these number will be less as compared to exclude_vertices so this seemed a suitable parameter.
second one can be avoided but that will require to make a duplicate copy of the graph with the edge weights as reduced weights but not sure if it is good to make a copy of the graph is ok or not but using this parameter can help us in retrieving the edge weights.
Any suggestions on if anything above can be done in a better way will be helpful.
comment:36 Changed 4 years ago by
I'm reluctant to add new parameters to the shortest path methods. The methods will become more complicated and difficult to maintain, and can be slow down.
An alternative is to create a new .pyx file dedicated to paths enumerations, and to put inside specialized shortest paths methods that are needed.
comment:37 Changed 4 years ago by
Commit:  f7abe8489de91ad8b0cbf745bb1001db85ae84b1 → 64f2a8c7dddd2b67de194ed1e9ec7d423f72c0e8 

Branch pushed to git repo; I updated commit sha1. New commits:
64f2a8c  improved the code

comment:38 Changed 4 years ago by
Commit:  64f2a8c7dddd2b67de194ed1e9ec7d423f72c0e8 → b49d8f16bbcfa0fe1cc6c5de125a962bf9827058 

Branch pushed to git repo; I updated commit sha1. New commits:
b49d8f1  implementation of feng's algorithm

comment:39 Changed 4 years ago by
In c_graph file there are 2 new shortest path methods as a helper fn to yen's as well as feng's algorithm:
 bidirectional_dijkstra_special
 shortest_path_special
which can be moved to separate file or remain here whatever seems appropriate.
In generic_graph file :
 yen_k_shortest_simple_paths [original YEN] [completed]
 yen_k_shortest_simple_paths_directed [Feng's implementation]
the feng's implementation is not fully completed yet there are few improvements and corner cases to be considered which I will be doing shortly but its still functional and can be tested.
comment:40 Changed 4 years ago by
Status:  needs_review → needs_work 

comment:41 Changed 3 years ago by
Commit:  b49d8f16bbcfa0fe1cc6c5de125a962bf9827058 → ce0ca22addd85a311f6de06f2f345d6569c0ef0d 

Branch pushed to git repo; I updated commit sha1. New commits:
ce0ca22  documented and improved the code

comment:42 Changed 3 years ago by
Commit:  ce0ca22addd85a311f6de06f2f345d6569c0ef0d → 5a5750379dbcc2e8c9a27848d3b6e1f1fdb7334a 

Branch pushed to git repo; I updated commit sha1. New commits:
5a57503  improved the code and covered some corner cases

comment:43 Changed 3 years ago by
Status:  needs_work → needs_review 

comment:44 Changed 3 years ago by
Commit:  5a5750379dbcc2e8c9a27848d3b6e1f1fdb7334a → 1e1fb83766e0fcb281612f5fd0a1ab42ef8bdda7 

Branch pushed to git repo; I updated commit sha1. New commits:
1e1fb83  Merge branch 'develop' into u/ghrajat1433/27859_yen_algorithm_improved

comment:46 Changed 3 years ago by
Milestone:  sage8.8 → sage8.9 

comment:47 Changed 3 years ago by
shortest_path_special
 you could add a text explaining that this method is an extension of
shortest_path
enabling to exclude vertices/edges from the search
 add doctests
contatiner
>container
 the case
if x == y:
should depend ondistance_flag
: return either 0 or[x]
(or[]
). You can take the opportunity to correct other methods for the same issue
 assign default values to
exclude_vertices_int
andexclude_edges_int
elif self._cg_rev is not None: # Sparse
add an extra space before#
. This is pep8 same for
# Dense
bidirectional_dijkstra_special
 same comments as above
 I suggest to move the definition of the priority queue (
cdef priority_queue[...
) just beforepq.push(...
I still have to review the implementation of Yen's algorithm. One concern is that these method should better fit in a new file gathering all methods related to the enumeration of paths. We could then let in generic_graph
, and/or in graph.py
and digraph.py
, methods for selecting the algorithm to use.
comment:48 Changed 3 years ago by
Commit:  1e1fb83766e0fcb281612f5fd0a1ab42ef8bdda7 → ac2786898c8822e2c3b0b4af3780dc2cc70a6056 

comment:49 Changed 3 years ago by
I have improved the code in shortest_path methods and added the doctests.
comment:50 Changed 3 years ago by
Commit:  ac2786898c8822e2c3b0b4af3780dc2cc70a6056 → f3f5dc6c6766db77cd8ca32046d8cc3f79656921 

Branch pushed to git repo; I updated commit sha1. New commits:
f3f5dc6  applied Lawler's modification to make yen's algorithm faster

comment:51 Changed 3 years ago by
In the previous commit I applied the Lawler's modification (in which duplicates path are not calculated as opposed to the original algorithm where they are calculated and then discarded when they are found to be duplicates) to Yen's algorithm to improve its performance.
comment:52 followup: 53 Changed 3 years ago by
You should add a check of weights. See G._check_weight_function??
sage: g = digraphs.DeBruijn(2, 3) sage: g.vertices() ['000', '001', '010', '011', '100', '101', '110', '111'] sage: print(g.edges()) [('000', '000', '0'), ('000', '001', '1'), ('001', '010', '0'), ('001', '011', '1'), ('010', '100', '0'), ('010', '101', '1'), ('011', '110', '0'), ('011', '111', '1'), ('100', '000', '0'), ('100', '001', '1'), ('101', '010', '0'), ('101', '011', '1'), ('110', '100', '0'), ('110', '101', '1'), ('111', '110', '0'), ('111', '111', '1')] sage: for p in g.yen_k_shortest_simple_paths_directed('000', '111', by_weight=True): ....: print(p) ....:  TypeError Traceback (most recent call last) <ipythoninput1020beb2396f59> in <module>() > 1 for p in g.yen_k_shortest_simple_paths_directed('000', '111', by_weight=True): 2 print(p) 3 /Users/dcoudert/sage3/sage/local/lib/python3.7/sitepackages/sage/graphs/generic_graph.py in yen_k_shortest_simple_paths_directed(self, source, target, weight_function, by_weight) 16314 for e in self.edge_iterator(): 16315 if e[0] in dist and e[1] in dist: > 16316 reduced_cost[(e[0], e[1])] = weight_function(e) + dist[e[1]]  dist[e[0]] 16317 exclude_vert_set = set(self)  set(dist.keys()) 16318 # finding the parent information from successor TypeError: unsupported operand type(s) for : 'str' and 'str'
Also, is it possible (via specific parameters) to get edges instead of vertices ? the weight of each path ?
comment:53 followup: 54 Changed 3 years ago by
Replying to dcoudert:
You should add a check of weights. See
G._check_weight_function??
Will do that soon...
Also, is it possible (via specific parameters) to get edges instead of vertices ? the weight of each path ?
Yes it is surely possible I guess. So should it be like a tuple of weight and corresponding path when report_weight is true?
I can add parameter like report_edges, report_weight as I did in all_simple_paths and all_paths method previously.
comment:54 Changed 3 years ago by
So should it be like a tuple of weight and corresponding path when report_weight is true?
yes
I can add parameter like report_edges, report_weight as I did in all_simple_paths and all_paths method previously.
yes
comment:55 Changed 3 years ago by
Also, try to avoid the multiplication of comments like
c = 0 # c is ...
. Prefer putting comments on a different line.
comment:56 followup: 58 Changed 3 years ago by
for _check_weight_function it seem to be typecasting the string part of edge_label of g = digraphs.DeBruijn?(2, 3) to float.
So I was thinking to modify _check_weight_function to accept only float as weights and not the strings? Will be better to do it in another ticket I guess if you agree?
comment:57 Changed 3 years ago by
Commit:  f3f5dc6c6766db77cd8ca32046d8cc3f79656921 → 721b8c7ee436df766aaae217f626e194d56e3c12 

Branch pushed to git repo; I updated commit sha1. New commits:
721b8c7  fix bugs in c_graph

comment:58 Changed 3 years ago by
Replying to ghrajat1433:
for _check_weight_function it seem to be typecasting the string part of edge_label of g = digraphs.DeBruijn?(2, 3) to float.
So I was thinking to modify _check_weight_function to accept only float as weights and not the strings? Will be better to do it in another ticket I guess if you agree?
For sure in another ticket. Such modification must be done with a lot of care.
comment:59 Changed 3 years ago by
Commit:  721b8c7ee436df766aaae217f626e194d56e3c12 → 5b15cfb6cddaa7c55cab821d098e28098398d1e7 

comment:60 Changed 3 years ago by
Commit:  5b15cfb6cddaa7c55cab821d098e28098398d1e7 → f5d43456c5a86c48bea3e85cb9526fd210fe0c51 

Branch pushed to git repo; I updated commit sha1. New commits:
f5d4345  added examples in docs abt usage of various parameters

comment:61 Changed 3 years ago by
Commit:  f5d43456c5a86c48bea3e85cb9526fd210fe0c51 → c176c941c39faaa778304b659260168900657f3a 

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

comment:62 Changed 3 years ago by
I performed the speed tests to compare the results of the original Yen's and the Yen's modified version i.e. Feng's which I have implemented under yen's shortest path_directed.
sage: g = DiGraph() sage: for i in range(120): ....: g.add_edge(i,i+1,i%5) ....: sage: for i in range(30, 40, 1): ....: g.add_edge(i,120,i%2) ....: ....: ....: sage: %timeit list(g.yen_k_shortest_simple_paths_directed(0, 120, by_weight=True ....: )) 100 loops, best of 3: 6.4 ms per loop sage: sage: %timeit list(g.yen_k_shortest_simple_paths(0, 120, by_weight=True)) 100 loops, best of 3: 17.4 ms per loop
So I guess now I can merge both the methods (calling the second one inside the first if the graph is directed).
Also should I move the shortest_paths_special methods which are currently in c_graph.pyx inside a separated .pyx file.
comment:63 Changed 3 years ago by
Speed test: the graph you use is very specific. You could try other graphs
Merge: yes, you can merge the methods
separate file: let's try to move all methods in it. It should be easier to maintain. You can add that the method is an adaptation of methods in c_graph.pyx
.
comment:64 Changed 3 years ago by
Can you suggest some directed graphs if you have any in mind?
Or may be I can construct some graphs which maybe random or like a grid graph having many paths between 2 nodes?
[UPDATE]: Looks like i found them: http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/digraph_generators.html
comment:65 Changed 3 years ago by
Yes, digraphs.<TAB>
. For instance the tests you did are for subgraphs of tournaments.
If you try with tournaments, the number of paths will be huge. So instead of listing all of them, you can restrict to 1000 for instance [g.yen_.... for _ in range(1000)]
.
The same if you use a DiGraph(graphs.Grid2dGraph(10, 10))
and search for paths from (0, 0)
to (9, 9)
.
comment:66 Changed 3 years ago by
Commit:  c176c941c39faaa778304b659260168900657f3a → bb6ecb6d852facc1ab208be3e48f2ed483caa619 

Branch pushed to git repo; I updated commit sha1. New commits:
bb6ecb6  fixed the bugs discovered

comment:67 followup: 70 Changed 3 years ago by
Speed Tests on more graphs:
Grid Graph
sage: g = DiGraph(graphs.Grid2dGraph(10, 10)) sage: p = g.yen_k_shortest_simple_paths((0, 0), (9, 9)) sage: %timeit [p.next() for i in range(1000)] 1 loop, best of 3: **1.34 s** per loop sage: p = g.yen_k_shortest_simple_paths_directed((0, 0), (9, 9)) sage: %timeit [p.next() for i in range(1000)] 1 loop, best of 3: **864 ms** per loop sage: def weight_function(e): ....: return 3 sage: p = g.yen_k_shortest_simple_paths((0, 0), (9, 9), weight_function=weight_function, by_weight=True) sage: %timeit [p.next() for i in range(1000)] 1 loop, best of 3: **2.3 s** per loop sage: p = g.yen_k_shortest_simple_paths_directed((0, 0), (9, 9), weight_function=weight_function, by_weight=True) sage: %timeit [p.next() for i in range(1000)] 1 loop, best of 3: **773 ms** per loop
Paley Graph
sage: g = digraphs.Paley(19) sage: p = g.yen_k_shortest_simple_paths(0, 18) sage: %timeit [p.next() for i in range(1000)] 1 loop, best of 3: 554 ms per loop sage: p = g.yen_k_shortest_simple_paths_directed(0, 18) sage: %timeit [p.next() for i in range(1000)] 1 loop, best of 3: 421 ms per loop sage: p = g.yen_k_shortest_simple_paths(0, 18) sage: %timeit [p.next() for i in range(5000)] 1 loop, best of 3: 13.2 s per loop sage: p = g.yen_k_shortest_simple_paths_directed(0, 18) sage: %timeit [p.next() for i in range(5000)] 1 loop, best of 3: 1.97 s per loop
It can be seen directed_graphs algorithm by Feng's is indeed faster and our implementation is backing this fact.
comment:68 Changed 3 years ago by
Commit:  bb6ecb6d852facc1ab208be3e48f2ed483caa619 → b231b5ce0fbdbd150a8f5f4ee210e27b774912ef 

Branch pushed to git repo; I updated commit sha1. New commits:
b231b5c  merging both methods and improvements

comment:69 Changed 3 years ago by
In c_graph,
Since currently shortest_path_special and bidirectional_dijkstra_special are methods of CGraphBackend class.
I am not sure how to move them to a separate file.
Should I define the method declaration in C_graph and its definition in separate file or is there any other way round?
comment:70 Changed 3 years ago by
It can be seen directed_graphs algorithm by Feng's is indeed faster and our implementation is backing this fact.
Good.
Can you do an extra test: check that you obtain the same paths. You have to be careful has the order in which paths are returned might differ.
Since currently shortest_path_special and bidirectional_dijkstra_special are methods of CGraphBackend class. I am not sure how to move them to a separate file.
Right. So let them in c_graph.pyx
.
We have to choose a good name for the new file. So far I have only in mind shortest_paths.pyx
but you may have better proposals.
comment:71 Changed 3 years ago by
Just to be clear we wish to move yen_k_shortest_simple_paths and yen_k_shortest_simple_paths_directed from generic_graph into the new file(path_enumeration.pyx) and use cython data structures?
comment:72 Changed 3 years ago by
Yes. And other methods like all_paths
and all_simple_paths
could be moved in it as well.
comment:73 Changed 3 years ago by
 Can you do an extra test: check that you obtain the same paths. You have to be careful has the order in which paths are returned might differ.
sage: g = digraphs.Paley(19) sage: p = g.yen_k_shortest_simple_paths(0, 18) sage: l1 = [p.next() for i in range(385)] sage: l1[1] [0, 17, 15, 13, 18] sage: q = g.yen_k_shortest_simple_paths_directed(0, 18) sage: l2 = [q.next() for i in range(385)] sage: c=0 sage: for p in l1: ....: if p in l2: ....: c = c + 1 ....: sage: c 385
comment:75 Changed 3 years ago by
Commit:  b231b5ce0fbdbd150a8f5f4ee210e27b774912ef → 6c8b7d02f3e259855d203a1658be4d5ae5eb4c38 

Branch pushed to git repo; I updated commit sha1. New commits:
6c8b7d0  moved to path_enumeration.py

comment:76 Changed 3 years ago by
I haved moved the yen's algorithms and all_paths and all_paths iterators to path_enumeration.py while still maintaining the mehtod definition to call them.
But the same examples and tests at two place seems to be redundant.
Also further this path_enumeration.py can be transformed to path_enumeration.pyx for further speed up.
comment:77 followup: 78 Changed 3 years ago by
The file should be .pyx, as further improvements will come.
You should make a frontend method (in this file) k_shortest_paths
with a parameter algorithm=...
to choose between Yen, Feng, Sage, etc. I think that yen_k_...
, should not be seen in generic_graph.py
.
Also, restrict the new methods to iterators. Old methods returning lists can stay like that, but for new methods, iterators is a better design.
In generic_graph
, instead of having a frontend method here, you can use aliases to methods defined in other modules. See the block # Aliases to functions defined in other modules
. This way, doctests will be performed only in path_enumeration.pyx
.
comment:78 Changed 3 years ago by
Replying to dcoudert:
You should make a frontend method (in this file)
k_shortest_paths
with a parameteralgorithm=...
to choose between Yen, Feng, Sage, etc. I think thatyen_k_...
, should not be seen ingeneric_graph.py
.
As Feng is for directed graphs only and we already use it inside yen for directed graphs. And also the Sage function all_paths
return the list of all the simple paths between src and target for unweighted graphs, so it should not be included as an algorithm if we plan to make k_shortest_paths
kind of function. According to me it will be best to keep k shortest paths without any parameter algorithms and use yen for undirected graphs and feng's for directed graphs.
If you have any better idea let me know.
comment:79 Changed 3 years ago by
Commit:  6c8b7d02f3e259855d203a1658be4d5ae5eb4c38 → ac823735bb8792d150f9b077c5cb7d42e3009d9f 

comment:80 Changed 3 years ago by
Commit:  ac823735bb8792d150f9b077c5cb7d42e3009d9f → 91da250916962ff20ead33c452890c097acb811c 

Branch pushed to git repo; I updated commit sha1. New commits:
91da250  transition to path_enumeration.pyx

comment:81 Changed 3 years ago by
 methods starting with
_
are not displayed in the html documentation. So there is no need to add_all_paths_iterator
to the table
 We should not expose
yen_k_shortest_simple_paths
to generic graph, but a frontend method, likeshortest_simple_paths
performing some tests and calling the right method. This method can have parameteralgorithm
to force the selection of the algorithm. Another choice could also be to extendall_simple_paths
.
 Also, could you push the code to a new branch in
public/
likepublic/graphs/27859_enumerate_paths
. This way I can edit the branch directly. It is sometimes faster than listing necessary changes. But of course I will not do all the work for you ;)
comment:82 Changed 3 years ago by
Commit:  91da250916962ff20ead33c452890c097acb811c → acdc3b97e89de7a6fcedf86f1de1c17e7db58aaa 

Branch pushed to git repo; I updated commit sha1. New commits:
acdc3b9  improving the path_enumeration.pyx

comment:83 Changed 3 years ago by
Commit:  acdc3b97e89de7a6fcedf86f1de1c17e7db58aaa → d9aea14762598997d4d084d62baeb14e9e558b55 

Branch pushed to git repo; I updated commit sha1. New commits:
d9aea14  updating the reference

comment:84 Changed 3 years ago by
Commit:  d9aea14762598997d4d084d62baeb14e9e558b55 → 6d69868025940e62a3f8f25bc89a8d46b12b4be5 

Branch pushed to git repo; I updated commit sha1. New commits:
6d69868  correcting spaces

comment:85 Changed 3 years ago by
Branch:  u/ghrajat1433/27859_yen_algorithm_improved → public/graphs/27859_enumerate_paths 

Commit:  6d69868025940e62a3f8f25bc89a8d46b12b4be5 
comment:86 Changed 3 years ago by
Commit:  → b5fae2661a81b6588ffa5cb24f5e74f0a9ebd6ff 

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
6c8b7d0  moved to path_enumeration.py

98b04f1  improved the comments

1a773d8  improved the comments

f307c81  minor improvements

ac82373  placed all path enumeration into path_enumeration.py

91da250  transition to path_enumeration.pyx

acdc3b9  improving the path_enumeration.pyx

d9aea14  updating the reference

6d69868  correcting spaces

b5fae26  made public and rebase on 8.9beta1

comment:87 Changed 3 years ago by
I guess the next steps are to make a front end in generic_graph file and create a section of algorithm in the methods and mentioning the references. And further also we can improve the cython things in path_enumeration file.
comment:88 followup: 89 Changed 3 years ago by
We have 2 options here:
 add parameters to methods
all_paths
andall_simple_paths
in order to enumerate paths by increasing lengths / weights using weight functions (similar to what is done in shortest paths methods. You then call Yen / Feng when the parameters are appropriate  make a frontend method for
shortest_simple_paths
May be the first option is enough, no ?
extra cythonization can be done after, possibly in another ticket as this one is already very big.
comment:89 Changed 3 years ago by
Replying to dcoudert:
We have 2 options here:
 add parameters to methods
all_paths
andall_simple_paths
in order to enumerate paths by increasing lengths / weights using weight functions (similar to what is done in shortest paths methods. You then call Yen / Feng when the parameters are appropriate make a frontend method for
shortest_simple_paths
Problem with first approach is that both the methods all_paths
and all_simple_paths
return lists not iterator so it will change the functionality of these which I am not sure is a good idea. Also a common method for undirected and directed graph seems more better which is the second option. So I think second one is more appropriate.
comment:90 Changed 3 years ago by
Right. I think you can implement the method inside path_enumeration.pyx
. Then you add an alias in generic_graph.py
.
comment:91 Changed 3 years ago by
Commit:  b5fae2661a81b6588ffa5cb24f5e74f0a9ebd6ff → b362e51224f72bbeee7b2026a1e7581d05789f72 

Branch pushed to git repo; I updated commit sha1. New commits:
b362e51  improved docs and added front_end method shortest_simple_paths

comment:92 Changed 3 years ago by
I have added the front_end shortest_simple_paths method, but I am not able to build the documnetation.
I am getting the following error.
rajat@rajatInspiron3537:~/new_version/sage8.7.beta6$ make doccleanmake build/make/Makefile stop make[1]: Entering directory '/home/rajat/new_version/sage8.7.beta6' make[1]: 'build/make/Makefile' is up to date. make[1]: Leaving directory '/home/rajat/new_version/sage8.7.beta6' build/bin/sagelogger \ "cd build/make && ./install 'docclean'" logs/install.log make[1]: Entering directory '/home/rajat/new_version/sage8.7.beta6/build/make' make[1]: Leaving directory '/home/rajat/new_version/sage8.7.beta6/build/make' *** ALL ENVIRONMENT VARIABLES BEFORE BUILD: *** CLUTTER_IM_MODULE=xim CMAKE_PREFIX_PATH=/opt/ros/kinetic:/opt/jderobot COMPIZ_CONFIG_PROFILE=ubuntu CONFIGURED_CC=gcc CONFIGURED_CXX=g++ std=gnu++11 CONFIGURED_FC=gfortran CONFIGURED_OBJC=gcc CONFIGURED_OBJCXX=g++ DBUS_SESSION_BUS_ADDRESS=unix:abstract=/tmp/dbusnBmi6MiTdV DEFAULTS_PATH=/usr/share/gconf/ubuntu.default.path DESKTOP_SESSION=ubuntu DISPLAY=:0 GDM_LANG=en_US GDMSESSION=ubuntu GNOME_DESKTOP_SESSION_ID=thisisdeprecated GNOME_KEYRING_CONTROL= GNOME_KEYRING_PID= GPG_AGENT_INFO=/home/rajat/.gnupg/S.gpgagent:0:1 GTK2_MODULES=overlayscrollbar GTK_IM_MODULE=ibus GTK_MODULES=gail:atkbridge:unitygtkmodule HOME=/home/rajat IM_CONFIG_PHASE=1 INSTANCE= JDEROBOT_CONFIG_PATHS=/home/rajat/jderobot_conf:/opt/jderobot/share/jderobot/conf JDEROBOT_GLADE_PATH=/opt/jderobot/share/jderobot/glade JOB=dbus LANG=en_IN LANGUAGE=en_IN:en LD_LIBRARY_PATH=/opt/ros/kinetic/lib:/opt/ros/kinetic/lib/x86_64linuxgnu:/opt/jderobot/lib LESSCLOSE=/usr/bin/lesspipe %s %s LESSOPEN= /usr/bin/lesspipe %s LOGNAME=rajat LS_COLORS=rs=0:di=01;34:ln=01;36:mh=00:pi=40;33:so=01;35:do=01;35:bd=40;33;01:cd=40;33;01:or=40;31;01:mi=00:su=37;41:sg=30;43:ca=30;41:tw=30;42:ow=34;42:st=37;44:ex=01;32:*.tar=01;31:*.tgz=01;31:*.arc=01;31:*.arj=01;31:*.taz=01;31:*.lha=01;31:*.lz4=01;31:*.lzh=01;31:*.lzma=01;31:*.tlz=01;31:*.txz=01;31:*.tzo=01;31:*.t7z=01;31:*.zip=01;31:*.z=01;31:*.Z=01;31:*.dz=01;31:*.gz=01;31:*.lrz=01;31:*.lz=01;31:*.lzo=01;31:*.xz=01;31:*.bz2=01;31:*.bz=01;31:*.tbz=01;31:*.tbz2=01;31:*.tz=01;31:*.deb=01;31:*.rpm=01;31:*.jar=01;31:*.war=01;31:*.ear=01;31:*.sar=01;31:*.rar=01;31:*.alz=01;31:*.ace=01;31:*.zoo=01;31:*.cpio=01;31:*.7z=01;31:*.rz=01;31:*.cab=01;31:*.jpg=01;35:*.jpeg=01;35:*.gif=01;35:*.bmp=01;35:*.pbm=01;35:*.pgm=01;35:*.ppm=01;35:*.tga=01;35:*.xbm=01;35:*.xpm=01;35:*.tif=01;35:*.tiff=01;35:*.png=01;35:*.svg=01;35:*.svgz=01;35:*.mng=01;35:*.pcx=01;35:*.mov=01;35:*.mpg=01;35:*.mpeg=01;35:*.m2v=01;35:*.mkv=01;35:*.webm=01;35:*.ogm=01;35:*.mp4=01;35:*.m4v=01;35:*.mp4v=01;35:*.vob=01;35:*.qt=01;35:*.nuv=01;35:*.wmv=01;35:*.asf=01;35:*.rm=01;35:*.rmvb=01;35:*.flc=01;35:*.avi=01;35:*.fli=01;35:*.flv=01;35:*.gl=01;35:*.dl=01;35:*.xcf=01;35:*.xwd=01;35:*.yuv=01;35:*.cgm=01;35:*.emf=01;35:*.ogv=01;35:*.ogx=01;35:*.aac=00;36:*.au=00;36:*.flac=00;36:*.m4a=00;36:*.mid=00;36:*.midi=00;36:*.mka=00;36:*.mp3=00;36:*.mpc=00;36:*.ogg=00;36:*.ra=00;36:*.wav=00;36:*.oga=00;36:*.opus=00;36:*.spx=00;36:*.xspf=00;36: MAKEFLAGS= V=1 MAKELEVEL=1 MAKE=make MAKE_TERMERR=/dev/pts/2 MAKE_TERMOUT=/dev/pts/2 MANDATORY_PATH=/usr/share/gconf/ubuntu.mandatory.path MFLAGS= PATH=/home/rajat/new_version/sage8.7.beta6/build/bin:/home/rajat/new_version/sage8.7.beta6/src/bin:/home/rajat/new_version/sage8.7.beta6/local/bin:/opt/ros/kinetic/bin:/home/rajat/bin:/home/rajat/.local/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/snap/bin:/opt/jderobot/bin PKG_CONFIG_PATH=/opt/ros/kinetic/lib/pkgconfig:/opt/ros/kinetic/lib/x86_64linuxgnu/pkgconfig:/opt/jderobot/lib/pkgconfig PWD=/home/rajat/new_version/sage8.7.beta6/build/make PYTHONPATH=/home/rajat/new_version/sage8.7.beta6/local QT4_IM_MODULE=xim QT_ACCESSIBILITY=1 QT_IM_MODULE=ibus QT_LINUX_ACCESSIBILITY_ALWAYS_ON=1 QT_QPA_PLATFORMTHEME=appmenuqt5 ROS_DISTRO=kinetic ROS_ETC_DIR=/opt/ros/kinetic/etc/ros ROS_MASTER_URI=http://localhost:11311 ROS_PACKAGE_PATH=/opt/ros/kinetic/share ROS_ROOT=/opt/ros/kinetic/share/ros ROS_VERSION=1 SAGE_CONFIGURE_GMP=withgmp=/home/rajat/new_version/sage8.7.beta6/local SAGE_CONFIGURE_MPC=withmpc=/home/rajat/new_version/sage8.7.beta6/local SAGE_CONFIGURE_MPFR=withmpfr=/home/rajat/new_version/sage8.7.beta6/local SAGE_CONFIGURE_NTL=withntl=/home/rajat/new_version/sage8.7.beta6/local SAGE_EXTCODE=/home/rajat/new_version/sage8.7.beta6/local/share/sage/ext SAGE_GMP_INCLUDE=/home/rajat/new_version/sage8.7.beta6/local/include SAGE_GMP_PREFIX=/home/rajat/new_version/sage8.7.beta6/local SAGE_LOCAL=/home/rajat/new_version/sage8.7.beta6/local SAGE_LOGS=/home/rajat/new_version/sage8.7.beta6/logs/pkgs SAGE_MPC_PREFIX=/home/rajat/new_version/sage8.7.beta6/local SAGE_MPFR_PREFIX=/home/rajat/new_version/sage8.7.beta6/local SAGE_NTL_PREFIX=/home/rajat/new_version/sage8.7.beta6/local SAGE_ORIG_PATH=/opt/ros/kinetic/bin:/home/rajat/bin:/home/rajat/.local/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/snap/bin:/opt/jderobot/bin SAGE_ORIG_PATH_SET=True SAGE_PYTHON_VERSION=2 SAGE_ROOT=/home/rajat/new_version/sage8.7.beta6 SAGE_SHARE=/home/rajat/new_version/sage8.7.beta6/local/share SAGE_SPKG_INST=/home/rajat/new_version/sage8.7.beta6/local/var/lib/sage/installed SAGE_SRC=/home/rajat/new_version/sage8.7.beta6/src SAGE_VERSION=8.9.beta1 SESSION_MANAGER=local/rajatInspiron3537:@/tmp/.ICEunix/1726,unix/rajatInspiron3537:/tmp/.ICEunix/1726 SESSIONTYPE=gnomesession SESSION=ubuntu SHELL=/bin/bash SHLVL=3 SSH_AUTH_SOCK=/run/user/1000/keyring/ssh TERM=xterm256color UPSTART_SESSION=unix:abstract=/com/ubuntu/upstartsession/1000/1321 USER=rajat _=/usr/bin/env VTE_VERSION=4205 WINDOWID=85983242 XAUTHORITY=/home/rajat/.Xauthority XDG_CONFIG_DIRS=/etc/xdg/xdgubuntu:/usr/share/upstart/xdg:/etc/xdg XDG_CURRENT_DESKTOP=Unity XDG_DATA_DIRS=/usr/share/ubuntu:/usr/share/gnome:/usr/local/share:/usr/share:/var/lib/snapd/desktop XDG_GREETER_DATA_DIR=/var/lib/lightdmdata/rajat XDG_MENU_PREFIX=gnome XDG_RUNTIME_DIR=/run/user/1000 XDG_SEAT_PATH=/org/freedesktop/DisplayManager/Seat0 XDG_SEAT=seat0 XDG_SESSION_DESKTOP=ubuntu XDG_SESSION_ID=c2 XDG_SESSION_PATH=/org/freedesktop/DisplayManager/Session0 XDG_SESSION_TYPE=x11 XDG_VTNR=7 XMODIFIERS=@im=ibus *********************************************** make[1]: Entering directory '/home/rajat/new_version/sage8.7.beta6/build/make' cd "/home/rajat/new_version/sage8.7.beta6/src/doc" && make clean make[2]: Entering directory '/home/rajat/new_version/sage8.7.beta6/src/doc' rm rf en/reference/*/sage rm rf en/reference/*/sagenb rm rf en/reference/sage rm rf en/reference/sagenb rm f common/*.pyc make[2]: Leaving directory '/home/rajat/new_version/sage8.7.beta6/src/doc' rm rf "/home/rajat/new_version/sage8.7.beta6/local/share/doc/sage" make[1]: Leaving directory '/home/rajat/new_version/sage8.7.beta6/build/make' real 0m0.057s user 0m0.042s sys 0m0.009s Sage build/upgrade complete! rajat@rajatInspiron3537:~/new_version/sage8.7.beta6$ ./sage b && ./sage docbuild reference html cd . && export \ SAGE_ROOT=/doesnotexist \ SAGE_SRC=/doesnotexist \ SAGE_SRC_ROOT=/doesnotexist \ SAGE_DOC_SRC=/doesnotexist \ SAGE_BUILD_DIR=/doesnotexist \ SAGE_PKGS=/home/rajat/new_version/sage8.7.beta6/build/pkgs \ && sagepython23 u setup.py nousercfg build install Discovering Python/Cython source code.... Discovered Python/Cython sources, time: 0.02 seconds. running build Generating autogenerated sources Building interpreters for fast_callable running build_cython Enabling Cython debugging support Updating Cython code.... Finished Cythonizing, time: 3.37 seconds. running build_py running build_ext Executing 0 commands (using 1 thread) Time to execute 0 commands: 0.11 seconds. Total time spent compiling C/C++ extensions: 0.17 seconds. running install running install_lib running install_egg_info Removing /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage8.9.beta1py2.7.egginfo Writing /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage8.9.beta1py2.7.egginfo Cleaning up stale installed files....  cleaning /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages  cleaning build/lib.linuxx86_642.7 Finished cleaning, time: 0.15 seconds. if [ "$UNAME" = "CYGWIN" ]; then \ sagerebase.sh "$SAGE_LOCAL" 2>/dev/null; \ fi real 0m4.854s user 0m4.159s sys 0m0.601s [manifolds] building [html]: targets for 63 source files that are out of date [manifolds] updating environment: 63 added, 0 changed, 0 removed [manifolds] loading cross citations... looking for nowoutdated files... none found [manifolds] /home/rajat/new_version/sage8.7.beta6/src/doc/en/reference/manifolds/index.rst:4: WARNING: undefined label: tensorsonfreemodules (if the link has no caption the label must precede a section header) [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/chart.py:docstring of sage.manifolds.chart:20: WARNING: citation not found: Lee2011 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/chart.py:docstring of sage.manifolds.chart:21: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/continuous_map.py:docstring of sage.manifolds.continuous_map:12: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/continuous_map.py:docstring of sage.manifolds.continuous_map:13: WARNING: citation not found: Lee2011 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/affine_connection.py:docstring of sage.manifolds.differentiable.affine_connection:13: WARNING: citation not found: Lee1997 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/affine_connection.py:docstring of sage.manifolds.differentiable.affine_connection:14: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/affine_connection.py:docstring of sage.manifolds.differentiable.affine_connection:15: WARNING: citation not found: ONe1983 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/automorphismfield_group.py:docstring of sage.manifolds.differentiable.automorphismfield_group:24: WARNING: citation not found: God1968 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/chart.py:docstring of sage.manifolds.differentiable.chart:19: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/curve.py:docstring of sage.manifolds.differentiable.curve:19: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/curve.py:docstring of sage.manifolds.differentiable.curve:20: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/diff_form.py:docstring of sage.manifolds.differentiable.diff_form:27: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/diff_form.py:docstring of sage.manifolds.differentiable.diff_form:28: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/diff_form_module.py:docstring of sage.manifolds.differentiable.diff_form_module:20: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/diff_form_module.py:docstring of sage.manifolds.differentiable.diff_form_module:21: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/diff_map.py:docstring of sage.manifolds.differentiable.diff_map:16: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/diff_map.py:docstring of sage.manifolds.differentiable.diff_map:17: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/differentiable_submanifold.py:docstring of sage.manifolds.differentiable.differentiable_submanifold:21: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/euclidean.py:docstring of sage.manifolds.differentiable.euclidean:1: WARNING: citation not found: Ber1987 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/euclidean.py:docstring of sage.manifolds.differentiable.euclidean:396: WARNING: citation not found: Ber1987 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/levi_civita_connection.py:docstring of sage.manifolds.differentiable.levi_civita_connection:12: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/levi_civita_connection.py:docstring of sage.manifolds.differentiable.levi_civita_connection:13: WARNING: citation not found: Lee1997 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/levi_civita_connection.py:docstring of sage.manifolds.differentiable.levi_civita_connection:14: WARNING: citation not found: ONe1983 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:1: WARNING: citation not found: Ser1992 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:1: WARNING: citation not found: Ber2008 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:418: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:419: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:420: WARNING: citation not found: Huy2005 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:421: WARNING: citation not found: Ser1992 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:422: WARNING: citation not found: Ber2008 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:423: WARNING: citation not found: BG1988 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold.DifferentiableManifold:3: WARNING: citation not found: Ser1992 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold.DifferentiableManifold:3: WARNING: citation not found: Ber2008 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/manifold_homset.py:docstring of sage.manifolds.differentiable.manifold_homset:30: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/manifold_homset.py:docstring of sage.manifolds.differentiable.manifold_homset:31: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/metric.py:docstring of sage.manifolds.differentiable.metric:14: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/metric.py:docstring of sage.manifolds.differentiable.metric:15: WARNING: citation not found: Lee1997 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/metric.py:docstring of sage.manifolds.differentiable.metric:16: WARNING: citation not found: ONe1983 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/multivector_module.py:docstring of sage.manifolds.differentiable.multivector_module:20: WARNING: citation not found: BG1980 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/multivector_module.py:docstring of sage.manifolds.differentiable.multivector_module:21: WARNING: citation not found: Mar1997 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield:23: WARNING: citation not found: BG1980 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield:24: WARNING: citation not found: Mar1997 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorField.bracket:47: WARNING: citation not found: Mar1997 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorField.bracket:47: WARNING: citation not found: Kos1985 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorField.bracket:47: WARNING: citation not found: Nij1955 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorField.bracket:47: WARNING: citation not found: Lic1977 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorField.bracket:47: WARNING: citation not found: Vai1994 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorFieldParal.bracket:47: WARNING: citation not found: Mar1997 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorFieldParal.bracket:47: WARNING: citation not found: Kos1985 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorFieldParal.bracket:47: WARNING: citation not found: Nij1955 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorFieldParal.bracket:47: WARNING: citation not found: Lic1977 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorFieldParal.bracket:47: WARNING: citation not found: Vai1994 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/pseudo_riemannian.py:docstring of sage.manifolds.differentiable.pseudo_riemannian:254: WARNING: citation not found: ONe1983 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/pseudo_riemannian.py:docstring of sage.manifolds.differentiable.pseudo_riemannian:255: WARNING: citation not found: Lee1997 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/pseudo_riemannian_submanifold.py:docstring of sage.manifolds.differentiable.pseudo_riemannian_submanifold:153: WARNING: citation not found: ONe1983 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/pseudo_riemannian_submanifold.py:docstring of sage.manifolds.differentiable.pseudo_riemannian_submanifold:154: WARNING: citation not found: Lee1997 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/real_line.py:docstring of sage.manifolds.differentiable.real_line:12: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/scalarfield.py:docstring of sage.manifolds.differentiable.scalarfield:21: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/scalarfield.py:docstring of sage.manifolds.differentiable.scalarfield:22: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/scalarfield.py:docstring of sage.manifolds.differentiable.scalarfield:23: WARNING: citation not found: ONe1983 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/scalarfield_algebra.py:docstring of sage.manifolds.differentiable.scalarfield_algebra:15: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/scalarfield_algebra.py:docstring of sage.manifolds.differentiable.scalarfield_algebra:16: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/scalarfield_algebra.py:docstring of sage.manifolds.differentiable.scalarfield_algebra:17: WARNING: citation not found: ONe1983 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/tangent_space.py:docstring of sage.manifolds.differentiable.tangent_space:11: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/tangent_vector.py:docstring of sage.manifolds.differentiable.tangent_vector:11: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/tensorfield.py:docstring of sage.manifolds.differentiable.tensorfield:32: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/tensorfield.py:docstring of sage.manifolds.differentiable.tensorfield:33: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/tensorfield.py:docstring of sage.manifolds.differentiable.tensorfield:34: WARNING: citation not found: ONe1983 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/tensorfield_module.py:docstring of sage.manifolds.differentiable.tensorfield_module:20: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/tensorfield_module.py:docstring of sage.manifolds.differentiable.tensorfield_module:21: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/tensorfield_module.py:docstring of sage.manifolds.differentiable.tensorfield_module:22: WARNING: citation not found: ONe1983 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/tensorfield_paral.py:docstring of sage.manifolds.differentiable.tensorfield_paral:32: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/tensorfield_paral.py:docstring of sage.manifolds.differentiable.tensorfield_paral:33: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/tensorfield_paral.py:docstring of sage.manifolds.differentiable.tensorfield_paral:34: WARNING: citation not found: ONe1983 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/vectorfield.py:docstring of sage.manifolds.differentiable.vectorfield:41: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/vectorfield.py:docstring of sage.manifolds.differentiable.vectorfield:42: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/vectorfield.py:docstring of sage.manifolds.differentiable.vectorfield:43: WARNING: citation not found: ONe1983 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/vectorfield.py:docstring of sage.manifolds.differentiable.vectorfield:44: WARNING: citation not found: BG1988 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/vectorfield_module.py:docstring of sage.manifolds.differentiable.vectorfield_module:21: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/vectorfield_module.py:docstring of sage.manifolds.differentiable.vectorfield_module:22: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/vectorfield_module.py:docstring of sage.manifolds.differentiable.vectorfield_module:23: WARNING: citation not found: ONe1983 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/differentiable/vectorframe.py:docstring of sage.manifolds.differentiable.vectorframe:30: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/manifold.py:docstring of sage.manifolds.manifold:307: WARNING: citation not found: Lee2011 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/manifold.py:docstring of sage.manifolds.manifold:308: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/manifold.py:docstring of sage.manifolds.manifold:309: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/manifold.py:docstring of sage.manifolds.manifold:310: WARNING: citation not found: Huy2005 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/manifold_homset.py:docstring of sage.manifolds.manifold_homset:13: WARNING: citation not found: Lee2011 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/manifold_homset.py:docstring of sage.manifolds.manifold_homset:14: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/point.py:docstring of sage.manifolds.point:14: WARNING: citation not found: Lee2011 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/point.py:docstring of sage.manifolds.point:15: WARNING: citation not found: Lee2013 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/scalarfield.py:docstring of sage.manifolds.scalarfield:21: WARNING: citation not found: Lee2011 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/scalarfield.py:docstring of sage.manifolds.scalarfield:22: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/scalarfield_algebra.py:docstring of sage.manifolds.scalarfield_algebra:15: WARNING: citation not found: Lee2011 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/scalarfield_algebra.py:docstring of sage.manifolds.scalarfield_algebra:16: WARNING: citation not found: KN1963 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/subset.py:docstring of sage.manifolds.subset:14: WARNING: citation not found: Lee2011 [manifolds] /home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage/manifolds/topological_submanifold.py:docstring of sage.manifolds.topological_submanifold:27: WARNING: citation not found: Lee2013 [manifolds] The HTML pages are in local/share/doc/sage/html/en/reference/manifolds. [manifolds] Exception occurred: [manifolds] File "/home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/os.py", line 157, in makedirs [manifolds] mkdir(name, mode) [manifolds] OSError: [Errno 17] File exists: '/home/rajat/new_version/sage8.7.beta6/local/share/doc/sage/html/en/reference/manifolds/_static' [manifolds] The full traceback has been saved in /tmp/sphinxerr9g_nLJ.log, if you want to report the issue to the developers. [manifolds] Please also report this if it was a user error, so that a better error message can be provided next time. [manifolds] A bug report can be filed in the tracker at <https://github.com/sphinxdoc/sphinx/issues>. Thanks! Error building the documentation. Traceback (most recent call last): File "/home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/runpy.py", line 174, in _run_module_as_main "__main__", fname, loader, pkg_name) File "/home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/runpy.py", line 72, in _run_code exec code in run_globals File "/home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage_setup/docbuild/__main__.py", line 2, in <module> main() File "/home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 1733, in main builder() File "/home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 550, in _wrapper build_many(build_ref_doc, L) File "/home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/sitepackages/sage_setup/docbuild/__init__.py", line 288, in _build_many ret = x.get(99999) File "/home/rajat/new_version/sage8.7.beta6/local/lib/python2.7/multiprocessing/pool.py", line 572, in get raise self._value OSError: /home/rajat/new_version/sage8.7.beta6/src/doc/en/reference/manifolds/index.rst:4: WARNING: undefined label: tensorsonfreemodules (if the link has no caption the label must precede a section header)
comment:93 Changed 3 years ago by
Which version of Sagemath are you using ? I hope it is not 8.7.beta6 as the path suggest...
Can you build the doc without this ticket ? Try make docclean && make
.
comment:94 Changed 3 years ago by
I am using sage 8.9 beta 1. I am in process of merging it with beta 2 to get rid of patchbot errors. And
make docclean && make
worked and the documentation is building nicely.
comment:95 Changed 3 years ago by
Commit:  b362e51224f72bbeee7b2026a1e7581d05789f72 → f74c014f142777ce9d8e596c0e44541f508ee7be 

Branch pushed to git repo; I updated commit sha1. New commits:
f74c014  trac #27859 merged with 8.9beta2

comment:96 Changed 3 years ago by
Commit:  f74c014f142777ce9d8e596c0e44541f508ee7be → 8254b0dfe3888160203f5d0dcd99c533d2009224 

Branch pushed to git repo; I updated commit sha1. New commits:
8254b0d  Algorithm description added for Yen and Feng

comment:97 Changed 3 years ago by
Commit:  8254b0dfe3888160203f5d0dcd99c533d2009224 → e84d80279b530c87bd831b3adb4f34e823885a61 

Branch pushed to git repo; I updated commit sha1. New commits:
e84d802  algorithm desciption completed

comment:98 Changed 3 years ago by
Commit:  e84d80279b530c87bd831b3adb4f34e823885a61 → 6731354ad10cfcdf0c7bd4902dfefacfb65e7fab 

Branch pushed to git repo; I updated commit sha1. New commits:
6731354  correct doc method pointer

comment:99 Changed 3 years ago by
Commit:  6731354ad10cfcdf0c7bd4902dfefacfb65e7fab → 4eb0c142e5e9a2013683e5d219e696cc4eab9fc7 

comment:100 followup: 101 Changed 3 years ago by
I did several corrections in the code. The main one is to rename the method for directed graphs feng_k_shortest_simple_paths
. Please check.
There is room for speed up improvements, in particular really using Cython. However, I prefer to finalyze first these methods, even if slow. We can latter work on speed up improvements.
Please also check if we really need to import _all_paths_iterator
in generic_graph.py
or if it can be a local method in path_enumeration.pyx
. Note the methods starting with _
are not shown in the html documentation. So we don't need to add this method to the top table.
comment:101 Changed 3 years ago by
Replying to dcoudert:
Please also check if we really need to import
_all_paths_iterator
ingeneric_graph.py
or if it can be a local method inpath_enumeration.pyx
. Note the methods starting with_
are not shown in the html documentation. So we don't need to add this method to the top table.
I think you meant to import _all_paths_iterator
in digraph.py
.
The difference between _all_paths_iterator
and all_paths_iterator
is that former one takes single vertex as a starting vertex and latter one takes a list of starting vertices. These two methods were already present inside digraph.py
. So if somebody was already using specifically _all_paths_iterator
method can continue using since we have imported that method from path_enumeration.pyx to digraph.py otherwise the user will have to first import it from path_enumeration file. I am not sure if someone uses this method specifically, but this method also offers simple
option if set to false useful for non simple paths. So maybe we can import it inside digraph.py module, so as to offer the same functionality as before.
I have gone through the changes you made and the methods and documentation has been improved a lot. Thanks for the review and it looks good to me.
comment:102 Changed 3 years ago by
Right, it's in digraph.py
and I agree it's safer to let the functionality.
There is something wrong. Feng and Yen should give the same results...
sage: G = digraphs.DeBruijn(2, 4) sage: for i, p in enumerate(G.shortest_simple_paths('0000', '1111', by_weight=False, algorithm='Feng')): ....: print(i, p) ....: 0 ['0000', '0001', '0011', '0111', '1111'] 1 ['0000', '0001', '0010', '0101', '1011', '0111', '1111'] 2 ['0000', '0001', '0010', '0100', '1001', '0011', '0111', '1111'] 3 ['0000', '0001', '0011', '0110', '1101', '1011', '0111', '1111'] 4 ['0000', '0001', '0011', '0110', '1101', '1010', '0101', '1011', '0111', '1111'] 5 ['0000', '0001', '0010', '0100', '1001', '0011', '0110', '1101', '1011', '0111', '1111'] 6 ['0000', '0001', '0011', '0110', '1100', '1001', '0010', '0101', '1011', '0111', '1111'] 7 ['0000', '0001', '0010', '0100', '1001', '0011', '0110', '1101', '1010', '0101', '1011', '0111', '1111'] 8 ['0000', '0001', '0011', '0110', '1101', '1010', '0100', '1001', '0010', '0101', '1011', '0111', '1111'] sage: for i, p in enumerate(G.shortest_simple_paths('0000', '1111', by_weight=False, algorithm='Yen')): ....: print(i, p) ....: 0 ['0000', '0001', '0011', '0111', '1111'] 1 ['0000', '0001', '0010', '0101', '1011', '0111', '1111'] 2 ['0000', '0001', '0010', '0100', '1001', '0011', '0111', '1111'] 3 ['0000', '0001', '0011', '0110', '1101', '1011', '0111', '1111'] 4 ['0000', '0001', '0010', '0101', '1010', '0100', '1001', '0011', '0111', '1111'] 5 ['0000', '0001', '0011', '0110', '1101', '1010', '0101', '1011', '0111', '1111'] 6 ['0000', '0001', '0010', '0100', '1001', '0011', '0110', '1101', '1011', '0111', '1111'] 7 ['0000', '0001', '0010', '0101', '1011', '0110', '1100', '1001', '0011', '0111', '1111'] 8 ['0000', '0001', '0011', '0110', '1100', '1001', '0010', '0101', '1011', '0111', '1111'] 9 ['0000', '0001', '0010', '0100', '1001', '0011', '0110', '1101', '1010', '0101', '1011', '0111', '1111'] 10 ['0000', '0001', '0010', '0101', '1010', '0100', '1001', '0011', '0110', '1101', '1011', '0111', '1111'] 11 ['0000', '0001', '0010', '0101', '1011', '0110', '1101', '1010', '0100', '1001', '0011', '0111', '1111'] 12 ['0000', '0001', '0011', '0110', '1101', '1010', '0100', '1001', '0010', '0101', '1011', '0111', '1111']
comment:103 Changed 3 years ago by
Commit:  4eb0c142e5e9a2013683e5d219e696cc4eab9fc7 → 9749101ec8b9443943e3293b43bbeede4980f465 

Branch pushed to git repo; I updated commit sha1. New commits:
9749101  fixed a bug

comment:104 Changed 3 years ago by
It was due to I forgot to update include_vertices as in above commit (took me a long time to realize that ;) )
I guess now its fixed.
sage: G = digraphs.DeBruijn(2, 4) sage: s = set() sage: sage: for i, p in enumerate(G.shortest_simple_paths('0000', '1111', by_weight=False, al ....: gorithm='Yen')): ....: ....: s.add(tuple(p)) sage: k = set() sage: sage: for i, p in enumerate(G.shortest_simple_paths('0000', '1111', by_weight=False, al ....: gorithm='Feng')): ....: ....: k.add(tuple(p)) sage: k==s True
comment:105 Changed 3 years ago by
Commit:  9749101ec8b9443943e3293b43bbeede4980f465 → 3845829a32fe3b64dc29eb857acfe37eca724c3c 

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

comment:107 Changed 3 years ago by
Status:  needs_review → needs_work 

This is not enough to fix the code. In this example, the last path reported with Feng is not simple (vertex (1,0) visited twice). More errors with larger grids.
sage: G = DiGraph(graphs.Grid2dGraph(3,3)) sage: for i, p in enumerate(G.shortest_simple_paths((0, 0), (0, 1), by_weight=False, algorithm='Feng')): ....: print(i, p) ....: 0 [(0, 0), (0, 1)] 1 [(0, 0), (1, 0), (1, 1), (0, 1)] 2 [(0, 0), (1, 0), (1, 1), (1, 2), (0, 2), (0, 1)] 3 [(0, 0), (1, 0), (2, 0), (2, 1), (1, 1), (0, 1)] 4 [(0, 0), (1, 0), (1, 1), (2, 1), (2, 2), (1, 2), (0, 2), (0, 1)] 5 [(0, 0), (1, 0), (2, 0), (2, 1), (1, 1), (1, 2), (0, 2), (0, 1)] 6 [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (1, 1), (0, 1)] 7 [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 1)] 8 [(0, 0), (1, 0), (1, 1), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 1)] sage: for i, p in enumerate(G.shortest_simple_paths((0, 0), (0, 1), by_weight=False, algorithm='Yen')): ....: print(i, p) ....: 0 [(0, 0), (0, 1)] 1 [(0, 0), (1, 0), (1, 1), (0, 1)] 2 [(0, 0), (1, 0), (1, 1), (1, 2), (0, 2), (0, 1)] 3 [(0, 0), (1, 0), (2, 0), (2, 1), (1, 1), (0, 1)] 4 [(0, 0), (1, 0), (1, 1), (2, 1), (2, 2), (1, 2), (0, 2), (0, 1)] 5 [(0, 0), (1, 0), (2, 0), (2, 1), (1, 1), (1, 2), (0, 2), (0, 1)] 6 [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 1)] 7 [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (1, 1), (0, 1)]
comment:108 Changed 3 years ago by
Commit:  3845829a32fe3b64dc29eb857acfe37eca724c3c → 0cedd3147b17d93ce57affc2c0c146d137eb6de3 

comment:109 Changed 3 years ago by
Commit:  0cedd3147b17d93ce57affc2c0c146d137eb6de3 → df8fe320c442c22815b21106d180a905174917d7 

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

comment:110 Changed 3 years ago by
Status:  needs_work → needs_review 

I guess I forgot to exclude the vertices on the prefix previously which has been fixed now.
sage: G = DiGraph(graphs.Grid2dGraph(3, 3)) sage: s = set() sage: for i, p in enumerate(G.shortest_simple_paths((0, 0), (0, 1), by_weight=False, algorithm='Feng')): ....: s.add(tuple(p)) sage: k = set() sage: for i, p in enumerate(G.shortest_simple_paths((0, 0), (0, 1), by_weight=False, algorithm='Yen')): ....: k.add(tuple(p)) sage: s==k True
comment:111 Changed 3 years ago by
 sage: s==k + sage: s == k
This might be better
 for j in range(dev_idx+1):  if j != dev_idx:  exclude_vertices.add(prev_path[j])  # coloring red  color[prev_path[j]] = 1 + for j in range(dev_idx): + exclude_vertices.add(prev_path[j]) + for j in range(dev_idx + 1): + # coloring red + color[prev_path[j]] = 1
comment:112 Changed 3 years ago by
Commit:  df8fe320c442c22815b21106d180a905174917d7 → f91e0259adb6ad606a1d3642f2799c30ae2eb024 

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

comment:113 Changed 3 years ago by
Commit:  f91e0259adb6ad606a1d3642f2799c30ae2eb024 → 6eb771d1c81ecba28eeca1ed2d9b3ccf59f2ff43 

Branch pushed to git repo; I updated commit sha1. New commits:
6eb771d  merge conflict solved

comment:114 Changed 3 years ago by
Commit:  6eb771d1c81ecba28eeca1ed2d9b3ccf59f2ff43 → 8a22e2ecfd3be1a739340ba5d2d4d45589243e4a 

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

comment:116 Changed 3 years ago by
Another issue.
sage: G = DiGraph('SL{Sa??B[??iSOBIgA_K?a?@H??aGCsc??_oGCC__AA?H????c@_GA?C@?A_?_C???a?') sage: for i, p in enumerate(G.shortest_simple_paths(0, 1, by_weight=False, algorithm='Yen')): ....: print(i, p) 0 [0, 2, 1] 1 [0, 3, 2, 1] ... 388 [0, 18, 9, 3, 7, 16, 15, 8, 17, 6, 4, 12, 10, 19, 14, 11, 5, 2, 1] sage: sage: for i, p in enumerate(G.shortest_simple_paths(0, 1, by_weight=False, algorithm='Feng')): ....: print(i, p) 0 [0, 2, 1] 1 [0, 5, 2, 1] ... 7164 [0, 18, 9, 3, 13, 0, 2, 5, 11, 14, 19, 10, 12, 4, 6, 17, 8, 15, 16, 7, 0, 2, 1]
Please continue to track bugs.
comment:117 Changed 3 years ago by
Status:  needs_review → needs_work 

comment:118 Changed 3 years ago by
Commit:  8a22e2ecfd3be1a739340ba5d2d4d45589243e4a → eab8dba6a8cdda67f1a296b415a6734d89c8a0bd 

Branch pushed to git repo; I updated commit sha1. New commits:
eab8dba  removed bugs, worked on a copy of original graph, added a doctest

comment:119 Changed 3 years ago by
That was a good test case, I realized that I missed the part of Feng's algorithm where he mentions about removing the incoming edges of source and outgoing edges of the target node. But since it will be bad to permanently delete those things on our input graph that is why I created a copy of the original graph and worked on it.
+ G = self.copy()
+ # removing the incoming edges to source and outgoing edges from target as
+ # they do not contribute towards the k shortest simple paths
+ incoming = G.neighbors_in(source)
+ for i in incoming:
+ G.delete_edge(i, source)
+ outgoing = G.neighbors_out(target)
+ for o in outgoing:
+ G.delete_edge(target, o)
Now
sage: G = DiGraph('SL{Sa??B[??iSOBIgA_K?a?@H??aGCsc??_oGCC__AA?H????c@_GA?C@?A_?_C???a?') sage: s = set() sage: for i, p in enumerate(G.shortest_simple_paths(0, 1, by_weight=False, algorithm='Yen')): ....: s.add(tuple(p)) sage: t = set() sage: for i, p in enumerate(G.shortest_simple_paths(0, 1, by_weight=False, algorithm='Feng')): ....: t.add(tuple(p)) sage: s == t True
I see that copy function has parameters like sparse but not sure if we require to use it here.
comment:120 Changed 3 years ago by
Status:  needs_work → needs_review 

comment:122 followup: 124 Changed 3 years ago by
Have you tried other random (di)graphs, possibly with multiple edges and various edge weights ? For small graphs, you can enumerate all paths. For large graphs, you can for instance enumerate 100 or 1000 paths. The more tests you do, the less bugs remains ;)
comment:123 Changed 3 years ago by
Commit:  eab8dba6a8cdda67f1a296b415a6734d89c8a0bd → 32d1bc8a1923a684513af083652499a864d58d9f 

Branch pushed to git repo; I updated commit sha1. New commits:
32d1bc8  added exclude vertices

comment:124 Changed 3 years ago by
Replying to dcoudert:
Have you tried other random (di)graphs, possibly with multiple edges and various edge weights ? For small graphs, you can enumerate all paths. For large graphs, you can for instance enumerate 100 or 1000 paths. The more tests you do, the less bugs remains ;)
Right. I guess I found some more, working on improving it.
comment:125 Changed 3 years ago by
Status:  needs_review → needs_work 

comment:126 Changed 3 years ago by
Commit:  32d1bc8a1923a684513af083652499a864d58d9f → fbc0faa48aff86dc64b3ad1b682903dd681e8e89 

Branch pushed to git repo; I updated commit sha1. New commits:
fbc0faa  fix bugs in feng

comment:127 Changed 3 years ago by
Status:  needs_work → needs_review 

comment:128 Changed 3 years ago by
Status:  needs_review → needs_work 

Another issue with Feng when there is no path from source to target. The answer of Yen is good.
sage: G = DiGraph(graphs.PathGraph(2) * 2) sage: for i,p in enumerate(G.shortest_simple_paths(0, 2, by_weight=False, algorithm='Yen')): ....: print(i, p) ....: 0 [] sage: for i,p in enumerate(G.shortest_simple_paths(0, 2, by_weight=False, algorithm='Feng')): ....: print(i, p) ....:  LookupError Traceback (most recent call last) <ipythoninput438f520f4e49ee> in <module>() > 1 for i,p in enumerate(G.shortest_simple_paths(Integer(0), Integer(2), by_weight=False, algorithm='Feng')): 2 print(i, p) 3 /Users/dcoudert/sage3/sage/local/lib/python3.7/sitepackages/sage/graphs/path_enumeration.pyx in shortest_simple_paths (build/cythonized/sage/graphs/path_enumeration.c:5131)() 489 raise ValueError("Feng's algorithm works only for directed graphs") 490 > 491 yield from feng_k_shortest_simple_paths(self, source=source, target=target, 492 weight_function=weight_function, 493 by_weight=by_weight, report_edges=report_edges, /Users/dcoudert/sage3/sage/local/lib/python3.7/sitepackages/sage/graphs/path_enumeration.pyx in feng_k_shortest_simple_paths (build/cythonized/sage/graphs/path_enumeration.c:12389)() 1097 1098 # compute the shortest path between the source and the target > 1099 path = shortest_path_func(source, target, exclude_vertices=exclude_vert_set, 1100 weight_function=weight_function, reduced_weight=reduced_cost) 1101 length = length_func(path) /Users/dcoudert/sage3/sage/local/lib/python3.7/sitepackages/sage/graphs/base/c_graph.pyx in sage.graphs.base.c_graph.CGraphBackend.bidirectional_dijkstra_special (build/cythonized/sage/graphs/base/c_graph.cpp:21062)() 2385 raise LookupError("%s and %s are excluded vertices" % (x, y)) 2386 elif x_excluded: > 2387 raise LookupError("no path from an excluded vertex %s" % (x)) 2388 elif y_excluded: 2389 raise LookupError("no path to an excluded vertex %s" % (y)) LookupError: no path from an excluded vertex 0
comment:129 Changed 3 years ago by
Commit:  fbc0faa48aff86dc64b3ad1b682903dd681e8e89 → ced65d454a7c1c97d0c321bb5ecef9988e5da3de 

Branch pushed to git repo; I updated commit sha1. New commits:
ced65d4  fix case of no paths bw vertices in Feng

comment:130 Changed 3 years ago by
Currently both Yen's and Feng's ignores the multiedges present in a graph as shown thru below examples.
Considering this, for Feng's it may be a little bit difficult to handle, it becomes a little tricky when the graph is weighted and we want shortest paths according to its edge weights. As we have used exclude_vertices approach it may be diffcult to handle. I think it will be better to handle this in another ticket but still during the gsoc period as #28220 is waiting for this tkt to be commited on top of it. Currently we can say its not implemented for multigraphs.
sage: g = DiGraph([(0, 1, 'a'), (0, 1, 'b'), (1, 2,'c'), (1, 2,'d')], multiedges=True) sage: g.all_simple_paths(starting_vertices=[0], ending_vertices=[2], use_m ....: ultiedges=True, report_edges=True, labels=True) [[(0, 1, 'b'), (1, 2, 'd')], [(0, 1, 'b'), (1, 2, 'c')], [(0, 1, 'a'), (1, 2, 'd')], [(0, 1, 'a'), (1, 2, 'c')]] sage: sage: for i,p in enumerate(g.shortest_simple_paths(0, 2, by_weight=False, ....: algorithm='Yen')): ....: ....: print(i, p) ....: (0, [0, 1, 2]) sage: from sage.graphs.path_enumeration import feng_k_shortest_simple_paths sage: list(feng_k_shortest_simple_paths(g, 0, 2, report_edges=True, report_weigh ....: t=False, labels=False)) [[(0, 1), (1, 2)]] sage: list(feng_k_shortest_simple_paths(g, 0, 2, report_weight=False, labels=Fal ....: se)) [[0, 1, 2]] sage: list(feng_k_shortest_simple_paths(g, 0, 2, report_edges=True, report_weigh ....: t=False, labels=True)) [[(0, 1, 'a'), (1, 2, 'c')]]
comment:131 Changed 3 years ago by
Status:  needs_work → needs_review 

comment:132 Changed 3 years ago by
Commit:  ced65d454a7c1c97d0c321bb5ecef9988e5da3de → dc98836129bdfcf6fe2268698613aa11050312b9 

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

comment:133 Changed 3 years ago by
Commit:  dc98836129bdfcf6fe2268698613aa11050312b9 → 362ff4beda260691e046505435d56b5ec2c56841 

Branch pushed to git repo; I updated commit sha1. New commits:
362ff4b  based on #28221

comment:134 Changed 3 years ago by
Dependencies:  → #28221 

comment:135 Changed 3 years ago by
Dependencies:  #28221 

comment:136 Changed 3 years ago by
Commit:  362ff4beda260691e046505435d56b5ec2c56841 → f02d6e584155bde2aa34f4cce714504bdc2ec859 

Branch pushed to git repo; I updated commit sha1. New commits:
f02d6e5  trac #27859 merged with 8.9beta4

comment:137 Changed 3 years ago by
Status:  needs_review → needs_work 

I think we are almost done here.
 use latex (twice)
 Time complexity is `O(kn(m+nlogn))` where `n` is the number of vertices and + Time complexity is `O(kn(m+n\log{n}))` where `n` is the number of vertices and
 it might be nicer to do like that:
 sage: g = Graph([(1, 2, 1), (2, 3, 1), (3, 4, 1), (4, 5, 2), (5, 6, 100), (4, 7, 3), (7, 6, 4), (3, 8, 5), (8, 9, 2), (9, 6, 2), (9, 10, 7), (9, 11, 10), (11, 6, 8), (10, 6, 2)]) + sage: g = Graph([(1, 2, 1), (2, 3, 1), (3, 4, 1), (4, 5, 2), + ....: (5, 6, 100), (4, 7, 3), (7, 6, 4), (3, 8, 5), + ....: (8, 9, 2), (9, 6, 2), (9, 10, 7), (9, 11, 10), + ....: (11, 6, 8), (10, 6, 2)])
 issue with corner case (Yen, Feng, etc.). I assume that when source=target and
report_edges=True
, we expect the empty path, and possibly a path with a loop if self loops are allowedsage: g = DiGraph([(1, 2, 20), (1, 3, 10), (1, 4, 30), (2, 5, 20), (3, 5, 10), (4, 5, 30)]) sage: list(g.shortest_simple_paths(1, 1, by_weight=True, report_edges=True, report_weight=True, labels=True)) [[1]]
 if loops / multi edges are forbidden, you can start with
self._scream_if_not_simple()
. If only ignored, it must be clearly documented and you can useG.to_simple(to_undirected=False, keep_label='min', immutable=False)
to reduce the size of the graph to consider. Currently, the weights are not smallest possible and not consistent with reported paths.sage: G = digraphs.DeBruijn(2, 3) sage: for u,v in G.edges(labels=False): ....: G.set_edge_label(u, v, 1) ....: sage: G.allow_multiple_edges(True) sage: for u,v in G.edges(labels=False): ....: G.add_edge(u, v, 2) ....: sage: list(G.shortest_simple_paths('000', '111')) [['000', '001', '011', '111'], ['000', '001', '010', '101', '011', '111']] sage: list(G.shortest_simple_paths('000', '111', by_weight=True)) [['000', '001', '011', '111'], ['000', '001', '010', '101', '011', '111']] sage: list(G.shortest_simple_paths('000', '111', by_weight=True, report_weight=True)) [(6, ['000', '001', '011', '111']), (9, ['000', '001', '010', '101', '011', '111'])] sage: list(G.shortest_simple_paths('000', '111', by_weight=True, report_weight=True, report_edges=True, labels=True)) [(6, [('000', '001', 1), ('001', '011', 1), ('011', '111', 1)]), (9, [('000', '001', 1), ('001', '010', 1), ('010', '101', 1), ('101', '011', 1), ('011', '111', 1)])]
comment:138 Changed 3 years ago by
Commit:  f02d6e584155bde2aa34f4cce714504bdc2ec859 → 5839ca6051a1c53fb39840ac728bfa35815013b4 

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

comment:139 Changed 3 years ago by
Status:  needs_work → needs_review 

comment:140 Changed 3 years ago by
These are methods, not booleans
 if self.has_loops or self.allows_multiple_edges: + if self.has_loops() or self.allows_multiple_edges():
comment:141 Changed 3 years ago by
Commit:  5839ca6051a1c53fb39840ac728bfa35815013b4 → 99d8fa7c6c1a6d0c445682e96600fc94c432d5a7 

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

comment:142 Changed 3 years ago by
FYI, I opened ticket #28309 to slightly speed up method to_simple
by improving method allow_multiple_edges
.
Actually, it might be a good idea to pass the weight_function
to method to_simple
.
comment:143 Changed 3 years ago by
Status:  needs_review → needs_work 

Another issue:
sage: def my_test(G, u, v, n=100): ....: it_yen = G.shortest_simple_paths(u, v, by_weight=True, report_weight=True, report_edges=True, labels=True, algorithm='Yen') ....: it_feng = G.shortest_simple_paths(u, v, by_weight=True, report_weight=True, report_edges=True, labels=True, algorithm='Feng') ....: for i,(p,f) in enumerate(zip(it_yen, it_feng)): ....: print(i, p, f) ....: if p[0] != f[0]: ....: print("Something goes wrong !") ....: break ....: if i == n: ....: break sage: sage: G = DiGraph(weighted=True) sage: G.add_edges([(0, 5, 8), (0, 6, 2), (0, 16, 10), (0, 19, 4), (1, 4, 9), (1, 5, 9), (1, 10, 1), (1, 12, 2), (1, 13, 1), (1, 14, 8), (1, 16, 3), (2, 1, 8), (2, 4, 7), (2, 5, 4), (2, 10, 7), (2, 12, 4), (2, 13, 10), (2, 16, 6), (3, 4, 8), (3, 9, 4), (3, 13, 3), (3, 14, 5), (3, 18, 4), (4, 0, 9), (4, 5, 5), (4, 7, 1), (4, 8, 1), (4, 9, 2), (4, 10, 9), (4, 13, 9), (4, 18, 8), (5, 3, 4), (5, 7, 1), (5, 8, 2), (5, 10, 10), (5, 12, 4), (5, 13, 9), (5, 15, 7), (6, 0, 8), (6, 2, 7), (6, 4, 6), (6, 5, 8), (6, 12, 5), (6, 16, 1), (7, 0, 10), (7, 1, 2), (7, 5, 6), (7, 6, 9), (7, 9, 8), (7, 13, 3), (7, 15, 1), (8, 0, 3), (8, 9, 10), (8, 10, 1), (9, 0, 9), (9, 1, 1), (9, 8, 8), (9, 11, 9), (9, 13, 3), (9, 16, 5), (10, 3, 10), (10, 8, 3), (10, 9, 9), (10, 13, 8), (10, 17, 1), (10, 18, 2), (10, 19, 6), (11, 2, 7), (11, 6, 9), (11, 7, 6), (11, 8, 9), (11, 10, 9), (11, 13, 8), (11, 16, 4), (11, 17, 8), (12, 1, 5), (12, 2, 4), (12, 6, 10), (12, 9, 3), (12, 16, 7), (12, 17, 5), (12, 18, 10), (13, 1, 4), (13, 14, 1), (13, 15, 6), (13, 18, 10), (13, 19, 7), (14, 0, 7), (14, 3, 8), (14, 5, 8), (14, 7, 6), (14, 9, 6), (15, 6, 4), (15, 9, 6), (15, 12, 8), (15, 16, 10), (15, 17, 4), (16, 0, 8), (16, 2, 9), (16, 3, 8), (16, 4, 6), (16, 8, 9), (16, 13, 5), (16, 14, 7), (17, 6, 2), (17, 8, 1), (17, 14, 7), (17, 16, 6), (18, 1, 2), (18, 3, 1), (18, 5, 3), (18, 6, 7), (18, 7, 4), (18, 9, 1), (18, 12, 2), (18, 13, 7), (19, 0, 6), (19, 1, 7), (19, 4, 1), (19, 9, 1), (19, 11, 3), (19, 16, 10), (19, 17, 8), (19, 18, 8)]) sage: sage: my_test(G, 17, 8) 0 (1, [(17, 8, 1)]) (1, [(17, 8, 1)]) 1 (9, [(17, 6, 2), (6, 4, 6), (4, 8, 1)]) (9, [(17, 6, 2), (6, 4, 6), (4, 8, 1)]) 2 (10, [(17, 6, 2), (6, 16, 1), (16, 4, 6), (4, 8, 1)]) (10, [(17, 6, 2), (6, 16, 1), (16, 8, 9)]) 3 (12, [(17, 6, 2), (6, 5, 8), (5, 8, 2)]) (10, [(17, 6, 2), (6, 16, 1), (16, 4, 6), (4, 8, 1)]) Something goes wrong !
I found that case by taken a digraphs.RandomDirectedGNP(20, .3)
, assigning random weights in 1..10
, and randomly selecting source and destination.
comment:144 Changed 3 years ago by
A smaller example (8 vertices) where you can check that the weight of the path is not properly computed with Feng. The second reported path has weight 14 (=5 + 9), not 13. The third path must be reported before the second.
sage: G = DiGraph([(0, 1, 9), (0, 3, 1), (0, 4, 2), (1, 6, 4), (1, 7, 1), (2, 0, 5), (2, 1, 4), (2, 7, 10), (3, 1, 7), (3, 2, 4), (3, 4, 2), (4, 0, 8), (4, 1, 10), (4, 3, 3), (4, 7, 10), (5, 2, 5), (5, 4, 9), (6, 2, 9)], weighted=True) sage: my_test(G, 2, 1) 0 (4, [(2, 1, 4)]) (4, [(2, 1, 4)]) 1 (13, [(2, 0, 5), (0, 3, 1), (3, 1, 7)]) (13, [(2, 0, 5), (0, 1, 9)]) 2 (14, [(2, 0, 5), (0, 1, 9)]) (13, [(2, 0, 5), (0, 3, 1), (3, 1, 7)]) Something goes wrong !
comment:145 Changed 3 years ago by
Commit:  99d8fa7c6c1a6d0c445682e96600fc94c432d5a7 → 7871701cd23f8a693d36771c2a2e4c422e672782 

comment:146 Changed 3 years ago by
sage: G = DiGraph(weighted=True) sage: G.add_edges([(0, 5, 8), (0, 6, 2), (0, 16, 10), (0, 19, 4), (1, 4, 9), (1, 5, 9), (1, 10, 1), (1, 12, 2), (1, 13, 1), (1, 14, 8), (1, 16, 3), (2, 1, 8), (2, 4, 7), (2, 5, 4), (2, 10, 7), (2, 12, 4), (2, 13, 10), (2, 16, 6), (3, 4, 8), (3, 9, 4), (3, 13, 3), (3, 14, 5), (3, 18, 4), (4, 0, 9), (4, 5, 5), (4, 7, 1), (4, 8, 1), (4, 9, 2), (4, 10, 9), (4, 13, 9), (4, 18, 8), (5, 3, 4), (5, 7, 1), (5, 8, 2), (5, 10, 10), (5, 12, 4), (5, 13, 9), (5, 15, 7), (6, 0, 8), (6, 2, 7), (6, 4, 6), (6, 5, 8), (6, 12, 5), (6, 16, 1), (7, 0, 10), (7, 1, 2), (7, 5, 6), (7, 6, 9), (7, 9, 8), (7, 13, 3), (7, 15, 1), (8, 0, 3), (8, 9, 10), (8, 10, 1), (9, 0, 9), (9, 1, 1), (9, 8, 8), (9, 11, 9), (9, 13, 3), (9, 16, 5), (10, 3, 10), (10, 8, 3), (10, 9, 9), (10, 13, 8), (10, 17, 1), (10, 18, 2), (10, 19, 6), (11, 2, 7), (11, 6, 9), (11, 7, 6), (11, 8, 9), (11, 10, 9), (11, 13, 8), (11, 16, 4), (11, 17, 8), (12, 1, 5), (12, 2, 4), (12, 6, 10), (12, 9, 3), (12, 16, 7), (12, 17, 5), (12, 18, 10), (13, 1, 4), (13, 14, 1), (13, 15, 6), (13, 18, 10), (13, 19, 7), (14, 0, 7), (14, 3, 8), (14, 5, 8), (14, 7, 6), (14, 9, 6), (15, 6, 4), (15, 9, 6), (15, 12, 8), (15, 16, 10), (15, 17, 4), (16, 0, 8), (16, 2, 9), (16, 3, 8), (16, 4, 6), (16, 8, 9), (16, 13, 5), (16, 14, 7), (17, 6, 2), (17, 8, 1), (17, 14, 7), (17, 16, 6), (18, 1, 2), (18, 3, 1), (18, 5, 3), (18, 6, 7), (18, 7, 4), (18, 9, 1), (18, 12, 2), (18, 13, 7), (19, 0, 6), (19, 1, 7), (19, 4, 1), (19, 9, 1), (19, 11, 3), (19, 16, 10), (19, 17, 8), (19, 18, 8)]) sage: lis=[] sage: it_yen = G.shortest_simple_paths(17, 8, by_weight=True, report ....: _weight=True, report_edges=True, labels=True, algorithm='Yen') sage: for i in range(300): ....: a = it_yen.next() ....: lis.append(a) ....: sage: fis=[] sage: it_feng = G.shortest_simple_paths(17, 8, by_weight=True, repor ....: t_weight=True, report_edges=True, labels=True, algorithm='Feng') sage: for i in range(300): ....: a = it_feng.next() ....: fis.append(a) ....: sage: for i in range(300): ....: if lis[i][0]!=fis[i][0]: ....: print("error") ....:
comment:147 Changed 3 years ago by
It took me quite a while to debug the problem , so I went through the algorithm step by step and made changes to make sure it does not break or causes error. Now I think it works and report weights properly.
comment:148 Changed 3 years ago by
Status:  needs_work → needs_review 

comment:149 Changed 3 years ago by
Commit:  7871701cd23f8a693d36771c2a2e4c422e672782 → 3ae912dd544e9b4aa21dc1a084f6efb2faf19430 

comment:150 Changed 3 years ago by
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 ;)
comment:151 Changed 3 years ago by
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
comment:152 Changed 3 years ago by
Commit:  3ae912dd544e9b4aa21dc1a084f6efb2faf19430 → 82015e22bcd6a345456b3f1c9644cb4c27547559 

Branch pushed to git repo; I updated commit sha1. New commits:
82015e2  made feng faster

comment:153 Changed 3 years ago by
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
comment:154 Changed 3 years ago by
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
comment:155 Changed 3 years ago by
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....
comment:156 Changed 3 years ago by
Commit:  82015e22bcd6a345456b3f1c9644cb4c27547559 → 3a2aca351d2952a6fd573ec8b4ddea41f8942c45 

comment:157 Changed 3 years ago by
I did some minor edits in Yen and Feng.
In Feng, why are you adding/removing edges ? can't we avoid that ?
comment:158 Changed 3 years ago by
Commit:  3a2aca351d2952a6fd573ec8b4ddea41f8942c45 → 034cb7f12ef01704732ae3d044cff43eecd84aaa 

comment:159 Changed 3 years ago by
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.
comment:160 Changed 3 years ago by
Status:  needs_review → positive_review 

I agree. So I propose to let speedup improvements of the algorithms to future tickets.
Good to go.
comment:161 Changed 3 years ago by
Commit:  034cb7f12ef01704732ae3d044cff43eecd84aaa → fcfa3e661e0840adba52a7e7f4a5b692450a8bad 

Status:  positive_review → needs_review 
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
fcfa3e6  removing extra newline

comment:162 Changed 3 years ago by
@dcoudert I guess due to above change you have to positive review it again ;)
comment:163 Changed 3 years ago by
Status:  needs_review → positive_review 

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.).
comment:164 Changed 3 years ago by
Branch:  public/graphs/27859_enumerate_paths → fcfa3e661e0840adba52a7e7f4a5b692450a8bad 

Resolution:  → fixed 
Status:  positive_review → closed 
Branch pushed to git repo; I updated commit sha1. New commits:
yen's algorithm implementation
improved
revert