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: sage-8.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:

Status badges

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 David Coudert

Keywords: gsoc19 added

comment:2 Changed 4 years ago by Rajat Mittal

Authors: Rajat Mittal
Branch: u/gh-rajat1433/27859_yen_algorithm_improved

comment:3 Changed 4 years ago by git

Commit: ac4ff86c1def01ca30d08bf20312ff3fbca664f7

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

2afbaefyen's algorithm implementation
ede0d00improved
ac4ff86revert

comment:4 Changed 4 years ago by Rajat Mittal

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 git

Commit: ac4ff86c1def01ca30d08bf20312ff3fbca664f7b31f288dc0a9663d5088ab065abf14d3a9c9f471

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

b31f288added one line

comment:6 Changed 4 years ago by Rajat Mittal

Status: newneeds_review

comment:7 Changed 4 years ago by git

Commit: b31f288dc0a9663d5088ab065abf14d3a9c9f4719da448297268b41bcd1df703969fb407cf664a68

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

9da4482removed all_paths

comment:8 Changed 4 years ago by David Coudert

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 git

Commit: 9da448297268b41bcd1df703969fb407cf664a683ca1945f5fe323afbd5f26d5efe9a7f478ca1f68

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

b7a49b4improved the shortest_paths
3ca1945removed xtra line

comment:10 Changed 4 years ago by Rajat Mittal

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 in reply to:  10 Changed 4 years ago by David Coudert

Replying to gh-rajat1433:

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

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

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

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

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

comment:12 Changed 4 years ago by git

Commit: 3ca1945f5fe323afbd5f26d5efe9a7f478ca1f6870e86c1c6935b53b0097c0ed908e1c37dd96a020

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

70e86c1improved

comment:13 Changed 4 years ago by Rajat Mittal

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 David Coudert

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 Rajat Mittal

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 David Coudert

+                        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 git

Commit: 70e86c1c6935b53b0097c0ed908e1c37dd96a020481ea41cda6b7ef1b4d697a89d8bd0b97b6ec958

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

481ea41improvedcode

comment:18 Changed 4 years ago by git

Commit: 481ea41cda6b7ef1b4d697a89d8bd0b97b6ec9585b14b84b95851cc07991e35fdf42c2d7f5dcd7e3

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

5b14b84improved method name and description

comment:19 Changed 4 years ago by David Coudert

  • In fact, exclude_vertices and exclude_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 test if not exclude...
  • Note that the set of vertices and edges that you exclude is sometimes called forbidden.
  • pep8
    -            raise LookupError("No path between %s and %s" % (x, y))
    +            raise LookupError("no path between %s and %s" % (x, y))
    
    in fact the error message could be 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 be while heap_paths:.

comment:20 Changed 4 years ago by git

Commit: 5b14b84b95851cc07991e35fdf42c2d7f5dcd7e35164f340947cdfaca8d635f0d6e930df4a409e3b

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

5164f34changes in c_graph.pyx

comment:21 Changed 4 years ago by Rajat Mittal

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 git

Commit: 5164f340947cdfaca8d635f0d6e930df4a409e3bd22322cf4dfe6a4a9fd249dc03f64bec2f0bc46b

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

d22322cdocumenting the yen's algorithm

comment:23 Changed 4 years ago by git

Commit: d22322cf4dfe6a4a9fd249dc03f64bec2f0bc46b55c187c22e02b665a97d301a8ddff9b20f31fe04

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

55c187cdocumenting the yen's algorithm

comment:24 Changed 4 years ago by git

Commit: 55c187c22e02b665a97d301a8ddff9b20f31fe04beb67d67e2153ca1f700b91f1d70c2d9f13ac55e

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

beb67d6documenting the yen's algorithm

comment:25 in reply to:  19 Changed 4 years ago by Rajat Mittal

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 be while 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 Rajat Mittal

Owner: set to Rajat Mittal

comment:27 Changed 4 years ago by David Coudert

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 git

Commit: beb67d67e2153ca1f700b91f1d70c2d9f13ac55e353b3c368a322ad4cc2d40435cd3a6259a750fb7

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

353b3c3reordered

comment:29 Changed 4 years ago by Rajat Mittal

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 git

Commit: 353b3c368a322ad4cc2d40435cd3a6259a750fb70528edc5e690836abaf3cd366004ce4bfbc14563

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

0528edcadded tests

comment:31 Changed 4 years ago by git

Commit: 0528edc5e690836abaf3cd366004ce4bfbc1456320515f95fcb2cbf273de57718496e24a0a01caad

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

20515f9revert back to set

comment:32 in reply to:  31 Changed 4 years ago by Rajat Mittal

Replying to git:

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

20515f9revert back to set

I hv reverted back to set here as there can be multiple instances of same edges and vertices in exclude_edges and exclude_vertices.

comment:33 Changed 4 years ago by git

Commit: 20515f95fcb2cbf273de57718496e24a0a01caadf7abe8489de91ad8b0cbf745bb1001db85ae84b1

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

f7abe84added more tests

comment:34 in reply to:  29 Changed 4 years ago by David Coudert

So I guess its best to implement a new method.

Yes, go for it.

comment:35 Changed 4 years ago by Rajat Mittal

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 David Coudert

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 git

Commit: f7abe8489de91ad8b0cbf745bb1001db85ae84b164f2a8c7dddd2b67de194ed1e9ec7d423f72c0e8

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

64f2a8cimproved the code

comment:38 Changed 4 years ago by git

Commit: 64f2a8c7dddd2b67de194ed1e9ec7d423f72c0e8b49d8f16bbcfa0fe1cc6c5de125a962bf9827058

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

b49d8f1implementation of feng's algorithm

comment:39 Changed 4 years ago by Rajat Mittal

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 Rajat Mittal

Status: needs_reviewneeds_work

comment:41 Changed 3 years ago by git

Commit: b49d8f16bbcfa0fe1cc6c5de125a962bf9827058ce0ca22addd85a311f6de06f2f345d6569c0ef0d

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

ce0ca22documented and improved the code

comment:42 Changed 3 years ago by git

Commit: ce0ca22addd85a311f6de06f2f345d6569c0ef0d5a5750379dbcc2e8c9a27848d3b6e1f1fdb7334a

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

5a57503improved the code and covered some corner cases

comment:43 Changed 3 years ago by Rajat Mittal

Status: needs_workneeds_review

comment:44 Changed 3 years ago by git

Commit: 5a5750379dbcc2e8c9a27848d3b6e1f1fdb7334a1e1fb83766e0fcb281612f5fd0a1ab42ef8bdda7

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

1e1fb83Merge branch 'develop' into u/gh-rajat1433/27859_yen_algorithm_improved

comment:45 Changed 3 years ago by Rajat Mittal

Merged with latest develop SageMath version 8.8.rc1

comment:46 Changed 3 years ago by Rajat Mittal

Milestone: sage-8.8sage-8.9

comment:47 Changed 3 years ago by David Coudert

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 on distance_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 and exclude_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 before pq.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 git

Commit: 1e1fb83766e0fcb281612f5fd0a1ab42ef8bdda7ac2786898c8822e2c3b0b4af3780dc2cc70a6056

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

a41a714improved the code in c_graph
ac27868added the doctest in c_graph for special shortest paths

comment:49 Changed 3 years ago by Rajat Mittal

I have improved the code in shortest_path methods and added the doctests.

comment:50 Changed 3 years ago by git

Commit: ac2786898c8822e2c3b0b4af3780dc2cc70a6056f3f5dc6c6766db77cd8ca32046d8cc3f79656921

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

f3f5dc6applied Lawler's modification to make yen's algorithm faster

comment:51 Changed 3 years ago by Rajat Mittal

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.

Reference: https://en.wikipedia.org/wiki/Yen%27s_algorithm

comment:52 Changed 3 years ago by David Coudert

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)
<ipython-input-10-20beb2396f59> 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/site-packages/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 in reply to:  52 ; Changed 3 years ago by Rajat Mittal

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 in reply to:  53 Changed 3 years ago by David Coudert

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 David Coudert

Also, try to avoid the multiplication of comments like c = 0 # c is .... Prefer putting comments on a different line.

comment:56 Changed 3 years ago by Rajat Mittal

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 git

Commit: f3f5dc6c6766db77cd8ca32046d8cc3f79656921721b8c7ee436df766aaae217f626e194d56e3c12

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

721b8c7fix bugs in c_graph

comment:58 in reply to:  56 Changed 3 years ago by David Coudert

Replying to gh-rajat1433:

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 git

Commit: 721b8c7ee436df766aaae217f626e194d56e3c125b15cfb6cddaa7c55cab821d098e28098398d1e7

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

12a4fc1added labels and report_edges
5b15cfbadded weight output option

comment:60 Changed 3 years ago by git

Commit: 5b15cfb6cddaa7c55cab821d098e28098398d1e7f5d43456c5a86c48bea3e85cb9526fd210fe0c51

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

f5d4345added examples in docs abt usage of various parameters

comment:61 Changed 3 years ago by git

Commit: f5d43456c5a86c48bea3e85cb9526fd210fe0c51c176c941c39faaa778304b659260168900657f3a

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

c176c94added tests

comment:62 Changed 3 years ago by Rajat Mittal

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 David Coudert

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 Rajat Mittal

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

Last edited 3 years ago by Rajat Mittal (previous) (diff)

comment:65 Changed 3 years ago by David Coudert

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 git

Commit: c176c941c39faaa778304b659260168900657f3abb6ecb6d852facc1ab208be3e48f2ed483caa619

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

bb6ecb6fixed the bugs discovered

comment:67 Changed 3 years ago by Rajat Mittal

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 git

Commit: bb6ecb6d852facc1ab208be3e48f2ed483caa619b231b5ce0fbdbd150a8f5f4ee210e27b774912ef

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

b231b5cmerging both methods and improvements

comment:69 Changed 3 years ago by Rajat Mittal

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 in reply to:  67 Changed 3 years ago by David Coudert

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 Rajat Mittal

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 David Coudert

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 Rajat Mittal

-- 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:74 Changed 3 years ago by David Coudert

This is good news.

comment:75 Changed 3 years ago by git

Commit: b231b5ce0fbdbd150a8f5f4ee210e27b774912ef6c8b7d02f3e259855d203a1658be4d5ae5eb4c38

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

6c8b7d0moved to path_enumeration.py

comment:76 Changed 3 years ago by Rajat Mittal

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 Changed 3 years ago by David Coudert

The file should be .pyx, as further improvements will come.

You should make a front-end 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 front-end 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 in reply to:  77 Changed 3 years ago by Rajat Mittal

Replying to dcoudert:

You should make a front-end 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.

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 git

Commit: 6c8b7d02f3e259855d203a1658be4d5ae5eb4c38ac823735bb8792d150f9b077c5cb7d42e3009d9f

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

98b04f1improved the comments
1a773d8improved the comments
f307c81minor improvements
ac82373placed all path enumeration into path_enumeration.py

comment:80 Changed 3 years ago by git

Commit: ac823735bb8792d150f9b077c5cb7d42e3009d9f91da250916962ff20ead33c452890c097acb811c

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

91da250transition to path_enumeration.pyx

comment:81 Changed 3 years ago by David Coudert

  • 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 front-end method, like shortest_simple_paths performing some tests and calling the right method. This method can have parameter algorithm to force the selection of the algorithm. Another choice could also be to extend all_simple_paths.
  • Also, could you push the code to a new branch in public/ like public/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 git

Commit: 91da250916962ff20ead33c452890c097acb811cacdc3b97e89de7a6fcedf86f1de1c17e7db58aaa

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

acdc3b9improving the path_enumeration.pyx

comment:83 Changed 3 years ago by git

Commit: acdc3b97e89de7a6fcedf86f1de1c17e7db58aaad9aea14762598997d4d084d62baeb14e9e558b55

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

d9aea14updating the reference

comment:84 Changed 3 years ago by git

Commit: d9aea14762598997d4d084d62baeb14e9e558b556d69868025940e62a3f8f25bc89a8d46b12b4be5

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

6d69868correcting spaces

comment:85 Changed 3 years ago by Rajat Mittal

Branch: u/gh-rajat1433/27859_yen_algorithm_improvedpublic/graphs/27859_enumerate_paths
Commit: 6d69868025940e62a3f8f25bc89a8d46b12b4be5

comment:86 Changed 3 years ago by git

Commit: b5fae2661a81b6588ffa5cb24f5e74f0a9ebd6ff

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

6c8b7d0moved to path_enumeration.py
98b04f1improved the comments
1a773d8improved the comments
f307c81minor improvements
ac82373placed all path enumeration into path_enumeration.py
91da250transition to path_enumeration.pyx
acdc3b9improving the path_enumeration.pyx
d9aea14updating the reference
6d69868correcting spaces
b5fae26made public and rebase on 8.9beta1

comment:87 Changed 3 years ago by Rajat Mittal

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.

Last edited 3 years ago by Rajat Mittal (previous) (diff)

comment:88 Changed 3 years ago by David Coudert

We have 2 options here:

  1. add parameters to methods all_paths and all_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
  2. 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 in reply to:  88 Changed 3 years ago by Rajat Mittal

Replying to dcoudert:

We have 2 options here:

  1. add parameters to methods all_paths and all_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
  2. 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 David Coudert

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 git

Commit: b5fae2661a81b6588ffa5cb24f5e74f0a9ebd6ffb362e51224f72bbeee7b2026a1e7581d05789f72

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

b362e51improved docs and added front_end method shortest_simple_paths

comment:92 Changed 3 years ago by Rajat Mittal

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@rajat-Inspiron-3537:~/new_version/sage-8.7.beta6$ make doc-cleanmake build/make/Makefile --stop
make[1]: Entering directory '/home/rajat/new_version/sage-8.7.beta6'
make[1]: 'build/make/Makefile' is up to date.
make[1]: Leaving directory '/home/rajat/new_version/sage-8.7.beta6'
build/bin/sage-logger \
	"cd build/make && ./install 'doc-clean'" logs/install.log
make[1]: Entering directory '/home/rajat/new_version/sage-8.7.beta6/build/make'
make[1]: Leaving directory '/home/rajat/new_version/sage-8.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/dbus-nBmi6MiTdV
DEFAULTS_PATH=/usr/share/gconf/ubuntu.default.path
DESKTOP_SESSION=ubuntu
DISPLAY=:0
GDM_LANG=en_US
GDMSESSION=ubuntu
GNOME_DESKTOP_SESSION_ID=this-is-deprecated
GNOME_KEYRING_CONTROL=
GNOME_KEYRING_PID=
GPG_AGENT_INFO=/home/rajat/.gnupg/S.gpg-agent:0:1
GTK2_MODULES=overlay-scrollbar
GTK_IM_MODULE=ibus
GTK_MODULES=gail:atk-bridge:unity-gtk-module
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_64-linux-gnu:/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/sage-8.7.beta6/build/bin:/home/rajat/new_version/sage-8.7.beta6/src/bin:/home/rajat/new_version/sage-8.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_64-linux-gnu/pkgconfig:/opt/jderobot/lib/pkgconfig
PWD=/home/rajat/new_version/sage-8.7.beta6/build/make
PYTHONPATH=/home/rajat/new_version/sage-8.7.beta6/local
QT4_IM_MODULE=xim
QT_ACCESSIBILITY=1
QT_IM_MODULE=ibus
QT_LINUX_ACCESSIBILITY_ALWAYS_ON=1
QT_QPA_PLATFORMTHEME=appmenu-qt5
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=--with-gmp=/home/rajat/new_version/sage-8.7.beta6/local
SAGE_CONFIGURE_MPC=--with-mpc=/home/rajat/new_version/sage-8.7.beta6/local
SAGE_CONFIGURE_MPFR=--with-mpfr=/home/rajat/new_version/sage-8.7.beta6/local
SAGE_CONFIGURE_NTL=--with-ntl=/home/rajat/new_version/sage-8.7.beta6/local
SAGE_EXTCODE=/home/rajat/new_version/sage-8.7.beta6/local/share/sage/ext
SAGE_GMP_INCLUDE=/home/rajat/new_version/sage-8.7.beta6/local/include
SAGE_GMP_PREFIX=/home/rajat/new_version/sage-8.7.beta6/local
SAGE_LOCAL=/home/rajat/new_version/sage-8.7.beta6/local
SAGE_LOGS=/home/rajat/new_version/sage-8.7.beta6/logs/pkgs
SAGE_MPC_PREFIX=/home/rajat/new_version/sage-8.7.beta6/local
SAGE_MPFR_PREFIX=/home/rajat/new_version/sage-8.7.beta6/local
SAGE_NTL_PREFIX=/home/rajat/new_version/sage-8.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/sage-8.7.beta6
SAGE_SHARE=/home/rajat/new_version/sage-8.7.beta6/local/share
SAGE_SPKG_INST=/home/rajat/new_version/sage-8.7.beta6/local/var/lib/sage/installed
SAGE_SRC=/home/rajat/new_version/sage-8.7.beta6/src
SAGE_VERSION=8.9.beta1
SESSION_MANAGER=local/rajat-Inspiron-3537:@/tmp/.ICE-unix/1726,unix/rajat-Inspiron-3537:/tmp/.ICE-unix/1726
SESSIONTYPE=gnome-session
SESSION=ubuntu
SHELL=/bin/bash
SHLVL=3
SSH_AUTH_SOCK=/run/user/1000/keyring/ssh
TERM=xterm-256color
UPSTART_SESSION=unix:abstract=/com/ubuntu/upstart-session/1000/1321
USER=rajat
_=/usr/bin/env
VTE_VERSION=4205
WINDOWID=85983242
XAUTHORITY=/home/rajat/.Xauthority
XDG_CONFIG_DIRS=/etc/xdg/xdg-ubuntu:/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/lightdm-data/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/sage-8.7.beta6/build/make'
cd "/home/rajat/new_version/sage-8.7.beta6/src/doc" && make clean
make[2]: Entering directory '/home/rajat/new_version/sage-8.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/sage-8.7.beta6/src/doc'
rm -rf "/home/rajat/new_version/sage-8.7.beta6/local/share/doc/sage"
make[1]: Leaving directory '/home/rajat/new_version/sage-8.7.beta6/build/make'

real	0m0.057s
user	0m0.042s
sys	0m0.009s
Sage build/upgrade complete!
rajat@rajat-Inspiron-3537:~/new_version/sage-8.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/sage-8.7.beta6/build/pkgs                \
&& sage-python23 -u setup.py --no-user-cfg build install
Discovering Python/Cython source code....
Discovered Python/Cython sources, time: 0.02 seconds.
running build
Generating auto-generated 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/sage-8.7.beta6/local/lib/python2.7/site-packages/sage-8.9.beta1-py2.7.egg-info
Writing /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage-8.9.beta1-py2.7.egg-info
Cleaning up stale installed files....
- cleaning /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages
- cleaning build/lib.linux-x86_64-2.7
Finished cleaning, time: 0.15 seconds.
if [ "$UNAME" = "CYGWIN" ]; then                         \
    sage-rebase.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 now-outdated files... none found
[manifolds] /home/rajat/new_version/sage-8.7.beta6/src/doc/en/reference/manifolds/index.rst:4: WARNING: undefined label: tensors-on-free-modules (if the link has no caption the label must precede a section header)
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/chart.py:docstring of sage.manifolds.chart:20: WARNING: citation not found: Lee2011
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/chart.py:docstring of sage.manifolds.chart:21: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/continuous_map.py:docstring of sage.manifolds.continuous_map:12: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/continuous_map.py:docstring of sage.manifolds.continuous_map:13: WARNING: citation not found: Lee2011
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/affine_connection.py:docstring of sage.manifolds.differentiable.affine_connection:13: WARNING: citation not found: Lee1997
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/affine_connection.py:docstring of sage.manifolds.differentiable.affine_connection:14: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/affine_connection.py:docstring of sage.manifolds.differentiable.affine_connection:15: WARNING: citation not found: ONe1983
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/automorphismfield_group.py:docstring of sage.manifolds.differentiable.automorphismfield_group:24: WARNING: citation not found: God1968
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/chart.py:docstring of sage.manifolds.differentiable.chart:19: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/curve.py:docstring of sage.manifolds.differentiable.curve:19: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/curve.py:docstring of sage.manifolds.differentiable.curve:20: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/diff_form.py:docstring of sage.manifolds.differentiable.diff_form:27: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/diff_form.py:docstring of sage.manifolds.differentiable.diff_form:28: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/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/sage-8.7.beta6/local/lib/python2.7/site-packages/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/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/diff_map.py:docstring of sage.manifolds.differentiable.diff_map:16: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/diff_map.py:docstring of sage.manifolds.differentiable.diff_map:17: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/differentiable_submanifold.py:docstring of sage.manifolds.differentiable.differentiable_submanifold:21: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/euclidean.py:docstring of sage.manifolds.differentiable.euclidean:1: WARNING: citation not found: Ber1987
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/euclidean.py:docstring of sage.manifolds.differentiable.euclidean:396: WARNING: citation not found: Ber1987
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/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/sage-8.7.beta6/local/lib/python2.7/site-packages/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/sage-8.7.beta6/local/lib/python2.7/site-packages/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/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:1: WARNING: citation not found: Ser1992
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:1: WARNING: citation not found: Ber2008
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:418: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:419: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:420: WARNING: citation not found: Huy2005
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:421: WARNING: citation not found: Ser1992
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:422: WARNING: citation not found: Ber2008
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold:423: WARNING: citation not found: BG1988
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold.DifferentiableManifold:3: WARNING: citation not found: Ser1992
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/manifold.py:docstring of sage.manifolds.differentiable.manifold.DifferentiableManifold:3: WARNING: citation not found: Ber2008
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/manifold_homset.py:docstring of sage.manifolds.differentiable.manifold_homset:30: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/manifold_homset.py:docstring of sage.manifolds.differentiable.manifold_homset:31: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/metric.py:docstring of sage.manifolds.differentiable.metric:14: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/metric.py:docstring of sage.manifolds.differentiable.metric:15: WARNING: citation not found: Lee1997
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/metric.py:docstring of sage.manifolds.differentiable.metric:16: WARNING: citation not found: ONe1983
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/multivector_module.py:docstring of sage.manifolds.differentiable.multivector_module:20: WARNING: citation not found: BG1980
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/multivector_module.py:docstring of sage.manifolds.differentiable.multivector_module:21: WARNING: citation not found: Mar1997
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield:23: WARNING: citation not found: BG1980
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield:24: WARNING: citation not found: Mar1997
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorField.bracket:47: WARNING: citation not found: Mar1997
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorField.bracket:47: WARNING: citation not found: Kos1985
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorField.bracket:47: WARNING: citation not found: Nij1955
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorField.bracket:47: WARNING: citation not found: Lic1977
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorField.bracket:47: WARNING: citation not found: Vai1994
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorFieldParal.bracket:47: WARNING: citation not found: Mar1997
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorFieldParal.bracket:47: WARNING: citation not found: Kos1985
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorFieldParal.bracket:47: WARNING: citation not found: Nij1955
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorFieldParal.bracket:47: WARNING: citation not found: Lic1977
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/multivectorfield.py:docstring of sage.manifolds.differentiable.multivectorfield.MultivectorFieldParal.bracket:47: WARNING: citation not found: Vai1994
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/pseudo_riemannian.py:docstring of sage.manifolds.differentiable.pseudo_riemannian:254: WARNING: citation not found: ONe1983
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/pseudo_riemannian.py:docstring of sage.manifolds.differentiable.pseudo_riemannian:255: WARNING: citation not found: Lee1997
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/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/sage-8.7.beta6/local/lib/python2.7/site-packages/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/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/real_line.py:docstring of sage.manifolds.differentiable.real_line:12: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/scalarfield.py:docstring of sage.manifolds.differentiable.scalarfield:21: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/scalarfield.py:docstring of sage.manifolds.differentiable.scalarfield:22: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/scalarfield.py:docstring of sage.manifolds.differentiable.scalarfield:23: WARNING: citation not found: ONe1983
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/scalarfield_algebra.py:docstring of sage.manifolds.differentiable.scalarfield_algebra:15: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/scalarfield_algebra.py:docstring of sage.manifolds.differentiable.scalarfield_algebra:16: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/scalarfield_algebra.py:docstring of sage.manifolds.differentiable.scalarfield_algebra:17: WARNING: citation not found: ONe1983
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/tangent_space.py:docstring of sage.manifolds.differentiable.tangent_space:11: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/tangent_vector.py:docstring of sage.manifolds.differentiable.tangent_vector:11: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/tensorfield.py:docstring of sage.manifolds.differentiable.tensorfield:32: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/tensorfield.py:docstring of sage.manifolds.differentiable.tensorfield:33: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/tensorfield.py:docstring of sage.manifolds.differentiable.tensorfield:34: WARNING: citation not found: ONe1983
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/tensorfield_module.py:docstring of sage.manifolds.differentiable.tensorfield_module:20: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/tensorfield_module.py:docstring of sage.manifolds.differentiable.tensorfield_module:21: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/tensorfield_module.py:docstring of sage.manifolds.differentiable.tensorfield_module:22: WARNING: citation not found: ONe1983
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/tensorfield_paral.py:docstring of sage.manifolds.differentiable.tensorfield_paral:32: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/tensorfield_paral.py:docstring of sage.manifolds.differentiable.tensorfield_paral:33: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/tensorfield_paral.py:docstring of sage.manifolds.differentiable.tensorfield_paral:34: WARNING: citation not found: ONe1983
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/vectorfield.py:docstring of sage.manifolds.differentiable.vectorfield:41: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/vectorfield.py:docstring of sage.manifolds.differentiable.vectorfield:42: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/vectorfield.py:docstring of sage.manifolds.differentiable.vectorfield:43: WARNING: citation not found: ONe1983
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/vectorfield.py:docstring of sage.manifolds.differentiable.vectorfield:44: WARNING: citation not found: BG1988
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/vectorfield_module.py:docstring of sage.manifolds.differentiable.vectorfield_module:21: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/vectorfield_module.py:docstring of sage.manifolds.differentiable.vectorfield_module:22: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/vectorfield_module.py:docstring of sage.manifolds.differentiable.vectorfield_module:23: WARNING: citation not found: ONe1983
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/differentiable/vectorframe.py:docstring of sage.manifolds.differentiable.vectorframe:30: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/manifold.py:docstring of sage.manifolds.manifold:307: WARNING: citation not found: Lee2011
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/manifold.py:docstring of sage.manifolds.manifold:308: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/manifold.py:docstring of sage.manifolds.manifold:309: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/manifold.py:docstring of sage.manifolds.manifold:310: WARNING: citation not found: Huy2005
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/manifold_homset.py:docstring of sage.manifolds.manifold_homset:13: WARNING: citation not found: Lee2011
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/manifold_homset.py:docstring of sage.manifolds.manifold_homset:14: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/point.py:docstring of sage.manifolds.point:14: WARNING: citation not found: Lee2011
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/point.py:docstring of sage.manifolds.point:15: WARNING: citation not found: Lee2013
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/scalarfield.py:docstring of sage.manifolds.scalarfield:21: WARNING: citation not found: Lee2011
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/scalarfield.py:docstring of sage.manifolds.scalarfield:22: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/scalarfield_algebra.py:docstring of sage.manifolds.scalarfield_algebra:15: WARNING: citation not found: Lee2011
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/scalarfield_algebra.py:docstring of sage.manifolds.scalarfield_algebra:16: WARNING: citation not found: KN1963
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage/manifolds/subset.py:docstring of sage.manifolds.subset:14: WARNING: citation not found: Lee2011
[manifolds] /home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/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/sage-8.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/sage-8.7.beta6/local/share/doc/sage/html/en/reference/manifolds/_static'
[manifolds] The full traceback has been saved in /tmp/sphinx-err-9g_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/sphinx-doc/sphinx/issues>. Thanks!
Error building the documentation.
Traceback (most recent call last):
  File "/home/rajat/new_version/sage-8.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/sage-8.7.beta6/local/lib/python2.7/runpy.py", line 72, in _run_code
    exec code in run_globals
  File "/home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
    main()
  File "/home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1733, in main
    builder()
  File "/home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 550, in _wrapper
    build_many(build_ref_doc, L)
  File "/home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 288, in _build_many
    ret = x.get(99999)
  File "/home/rajat/new_version/sage-8.7.beta6/local/lib/python2.7/multiprocessing/pool.py", line 572, in get
    raise self._value
OSError: /home/rajat/new_version/sage-8.7.beta6/src/doc/en/reference/manifolds/index.rst:4: WARNING: undefined label: tensors-on-free-modules (if the link has no caption the label must precede a section header)

comment:93 Changed 3 years ago by David Coudert

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 doc-clean && make.

comment:94 Changed 3 years ago by Rajat Mittal

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 doc-clean && make

worked and the documentation is building nicely.

comment:95 Changed 3 years ago by git

Commit: b362e51224f72bbeee7b2026a1e7581d05789f72f74c014f142777ce9d8e596c0e44541f508ee7be

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

f74c014trac #27859 merged with 8.9beta2

comment:96 Changed 3 years ago by git

Commit: f74c014f142777ce9d8e596c0e44541f508ee7be8254b0dfe3888160203f5d0dcd99c533d2009224

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

8254b0dAlgorithm description added for Yen and Feng

comment:97 Changed 3 years ago by git

Commit: 8254b0dfe3888160203f5d0dcd99c533d2009224e84d80279b530c87bd831b3adb4f34e823885a61

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

e84d802algorithm desciption completed

comment:98 Changed 3 years ago by git

Commit: e84d80279b530c87bd831b3adb4f34e823885a616731354ad10cfcdf0c7bd4902dfefacfb65e7fab

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

6731354correct doc method pointer

comment:99 Changed 3 years ago by git

Commit: 6731354ad10cfcdf0c7bd4902dfefacfb65e7fab4eb0c142e5e9a2013683e5d219e696cc4eab9fc7

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

175b38atrac #27859: improve references
31da69atrac #27859: minor edit in c_graph.pyx
4eb0c14trac #27859: review edit in path_enumeration.pyx

comment:100 Changed 3 years ago by David Coudert

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 in reply to:  100 Changed 3 years ago by Rajat Mittal

Replying to dcoudert:

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.

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 David Coudert

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 git

Commit: 4eb0c142e5e9a2013683e5d219e696cc4eab9fc79749101ec8b9443943e3293b43bbeede4980f465

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

9749101fixed a bug

comment:104 Changed 3 years ago by Rajat Mittal

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
Last edited 3 years ago by Rajat Mittal (previous) (diff)

comment:105 Changed 3 years ago by git

Commit: 9749101ec8b9443943e3293b43bbeede4980f4653845829a32fe3b64dc29eb857acfe37eca724c3c

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

3845829added test

comment:106 Changed 3 years ago by Rajat Mittal

I have added this doctest in the shortest_simple_paths.

Last edited 3 years ago by Rajat Mittal (previous) (diff)

comment:107 Changed 3 years ago by David Coudert

Status: needs_reviewneeds_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 git

Commit: 3845829a32fe3b64dc29eb857acfe37eca724c3c0cedd3147b17d93ce57affc2c0c146d137eb6de3

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

db1499dfixed a bud
0cedd31fixed bug and added doctests

comment:109 Changed 3 years ago by git

Commit: 0cedd3147b17d93ce57affc2c0c146d137eb6de3df8fe320c442c22815b21106d180a905174917d7

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

df8fe32improved code

comment:110 Changed 3 years ago by Rajat Mittal

Status: needs_workneeds_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
Last edited 3 years ago by Rajat Mittal (previous) (diff)

comment:111 Changed 3 years ago by David Coudert

-        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 git

Commit: df8fe320c442c22815b21106d180a905174917d7f91e0259adb6ad606a1d3642f2799c30ae2eb024

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

f91e025improved

comment:113 Changed 3 years ago by git

Commit: f91e0259adb6ad606a1d3642f2799c30ae2eb0246eb771d1c81ecba28eeca1ed2d9b3ccf59f2ff43

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

6eb771dmerge conflict solved

comment:114 Changed 3 years ago by git

Commit: 6eb771d1c81ecba28eeca1ed2d9b3ccf59f2ff438a22e2ecfd3be1a739340ba5d2d4d45589243e4a

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

8a22e2eupdated

comment:115 Changed 3 years ago by Rajat Mittal

I have updated the code and merged with sage 8.9 beta 3

comment:116 Changed 3 years ago by David Coudert

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 David Coudert

Status: needs_reviewneeds_work

comment:118 Changed 3 years ago by git

Commit: 8a22e2ecfd3be1a739340ba5d2d4d45589243e4aeab8dba6a8cdda67f1a296b415a6734d89c8a0bd

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

eab8dbaremoved bugs, worked on a copy of original graph, added a doctest

comment:119 Changed 3 years ago by Rajat Mittal

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 Rajat Mittal

Status: needs_workneeds_review

comment:121 Changed 3 years ago by Rajat Mittal

Also ./sage -btp --long src/sage/graphs/ passes all tests now.

comment:122 Changed 3 years ago by David Coudert

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 git

Commit: eab8dba6a8cdda67f1a296b415a6734d89c8a0bd32d1bc8a1923a684513af083652499a864d58d9f

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

32d1bc8added exclude vertices

comment:124 in reply to:  122 Changed 3 years ago by Rajat Mittal

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.

Last edited 3 years ago by Rajat Mittal (previous) (diff)

comment:125 Changed 3 years ago by Rajat Mittal

Status: needs_reviewneeds_work

comment:126 Changed 3 years ago by git

Commit: 32d1bc8a1923a684513af083652499a864d58d9ffbc0faa48aff86dc64b3ad1b682903dd681e8e89

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

fbc0faafix bugs in feng

comment:127 Changed 3 years ago by Rajat Mittal

Status: needs_workneeds_review

comment:128 Changed 3 years ago by David Coudert

Status: needs_reviewneeds_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)
<ipython-input-43-8f520f4e49ee> 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/site-packages/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/site-packages/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/site-packages/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 git

Commit: fbc0faa48aff86dc64b3ad1b682903dd681e8e89ced65d454a7c1c97d0c321bb5ecef9988e5da3de

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

ced65d4fix case of no paths bw vertices in Feng

comment:130 Changed 3 years ago by Rajat Mittal

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')]]

Last edited 3 years ago by Rajat Mittal (previous) (diff)

comment:131 Changed 3 years ago by Rajat Mittal

Status: needs_workneeds_review

comment:132 Changed 3 years ago by git

Commit: ced65d454a7c1c97d0c321bb5ecef9988e5da3dedc98836129bdfcf6fe2268698613aa11050312b9

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

dc98836correct pep8

comment:133 Changed 3 years ago by git

Commit: dc98836129bdfcf6fe2268698613aa11050312b9362ff4beda260691e046505435d56b5ec2c56841

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

362ff4bbased on #28221

comment:134 Changed 3 years ago by Rajat Mittal

Dependencies: #28221

comment:135 Changed 3 years ago by Rajat Mittal

Dependencies: #28221

comment:136 Changed 3 years ago by git

Commit: 362ff4beda260691e046505435d56b5ec2c56841f02d6e584155bde2aa34f4cce714504bdc2ec859

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

f02d6e5trac #27859 merged with 8.9beta4

comment:137 Changed 3 years ago by David Coudert

Status: needs_reviewneeds_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 allowed
    sage: 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 use G.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 git

Commit: f02d6e584155bde2aa34f4cce714504bdc2ec8595839ca6051a1c53fb39840ac728bfa35815013b4

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

5839ca6improvements

comment:139 Changed 3 years ago by Rajat Mittal

Status: needs_workneeds_review

comment:140 Changed 3 years ago by David Coudert

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 git

Commit: 5839ca6051a1c53fb39840ac728bfa35815013b499d8fa7c6c1a6d0c445682e96600fc94c432d5a7

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

99d8fa7corrected

comment:142 Changed 3 years ago by David Coudert

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 David Coudert

Status: needs_reviewneeds_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 David Coudert

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 git

Commit: 99d8fa7c6c1a6d0c445682e96600fc94c432d5a77871701cd23f8a693d36771c2a2e4c422e672782

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

7e7c73cremoved bug in Yen
f503ec8fixed potetial bugs in feng's
7871701adding comments

comment:146 Changed 3 years ago by Rajat Mittal

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")
....:

Last edited 3 years ago by Rajat Mittal (previous) (diff)

comment:147 Changed 3 years ago by Rajat Mittal

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 Rajat Mittal

Status: needs_workneeds_review

comment:149 Changed 3 years ago by git

Commit: 7871701cd23f8a693d36771c2a2e4c422e6727823ae912dd544e9b4aa21dc1a084f6efb2faf19430

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

7c9bc30trac #27859: fix merge conflict with 8.9.beta5
3ae912dtrac #27859: add test on random digraphs

comment:150 Changed 3 years ago by David Coudert

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 David Coudert

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 git

Commit: 3ae912dd544e9b4aa21dc1a084f6efb2faf1943082015e22bcd6a345456b3f1c9644cb4c27547559

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

82015e2made feng faster

comment:153 Changed 3 years ago by Rajat Mittal

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 Rajat Mittal

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 Rajat Mittal

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 git

Commit: 82015e22bcd6a345456b3f1c9644cb4c275475593a2aca351d2952a6fd573ec8b4ddea41f8942c45

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

fabe87btrac #27859: review edit in Yen
3a2aca3trac #27859: review edit in Feng

comment:157 Changed 3 years ago by David Coudert

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 git

Commit: 3a2aca351d2952a6fd573ec8b4ddea41f8942c45034cb7f12ef01704732ae3d044cff43eecd84aaa

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

4bdbe63some improvement
034cb7fMerge branch 'public/graphs/27859_enumerate_paths' of git://trac.sagemath.org/sage into public/graphs/27859_enumerate_paths

comment:159 Changed 3 years ago by Rajat Mittal

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 David Coudert

Status: needs_reviewpositive_review

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

Good to go.

comment:161 Changed 3 years ago by git

Commit: 034cb7f12ef01704732ae3d044cff43eecd84aaafcfa3e661e0840adba52a7e7f4a5b692450a8bad
Status: positive_reviewneeds_review

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

fcfa3e6removing extra newline

comment:162 Changed 3 years ago by Rajat Mittal

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

comment:163 Changed 3 years ago by David Coudert

Status: needs_reviewpositive_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 Volker Braun

Branch: public/graphs/27859_enumerate_pathsfcfa3e661e0840adba52a7e7f4a5b692450a8bad
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.