Sage: Ticket #7640: shortest_path should not use NetworkX if the underlying graph is a c_graph
https://trac.sagemath.org/ticket/7640
<pre class="wiki">sage: G = graphs.CubeGraph(5)
sage: C = G.copy(implementation='c_graph')
sage: timeit("G.shortest_path('01001', '10100')")
625 loops, best of 3: 49.3 µs per loop
sage: timeit("C.shortest_path('01001', '10100')")
625 loops, best of 3: 992 µs per loop
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/7640
Trac 1.1.6rlmWed, 09 Dec 2009 17:03:16 GMT
https://trac.sagemath.org/ticket/7640#comment:1
https://trac.sagemath.org/ticket/7640#comment:1
<p>
This is one of those functions that should probably be written in Cython, on as low a level as possible...
</p>
TicketncohenWed, 09 Dec 2009 17:36:38 GMT
https://trac.sagemath.org/ticket/7640#comment:2
https://trac.sagemath.org/ticket/7640#comment:2
<p>
To be honest, I intended to write it as soon as your partch to make them the default format is merged :-)
</p>
TicketrlmWed, 09 Dec 2009 17:37:59 GMT
https://trac.sagemath.org/ticket/7640#comment:3
https://trac.sagemath.org/ticket/7640#comment:3
<p>
It should be the other order: this ticket needs to be dealt with before we switch over. There are probably other issues like this one lurking...
</p>
TicketylchapuyWed, 09 Dec 2009 19:31:25 GMT
https://trac.sagemath.org/ticket/7640#comment:4
https://trac.sagemath.org/ticket/7640#comment:4
<p>
One problem IMHO with <code>c_graph</code> is that as is (correct me if I'm wrong)
we won't be able to have a fast <code>in_neighbors</code>.
</p>
<p>
At least the current implementation is to test all vertices in the graph.
</p>
TicketrlmWed, 09 Dec 2009 19:44:12 GMT
https://trac.sagemath.org/ticket/7640#comment:5
https://trac.sagemath.org/ticket/7640#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7640#comment:4" title="Comment 4">ylchapuy</a>:
</p>
<blockquote class="citation">
<p>
One problem IMHO with <code>c_graph</code> is that as is (correct me if I'm wrong)
we won't be able to have a fast <code>in_neighbors</code>.
</p>
<p>
At least the current implementation is to test all vertices in the graph.
</p>
</blockquote>
<p>
This belongs here: <a class="ext-link" href="http://groups.google.com/group/sage-devel/browse_thread/thread/8edd29e9bddc67e5"><span class="icon"></span>http://groups.google.com/group/sage-devel/browse_thread/thread/8edd29e9bddc67e5</a>
</p>
<p>
See my comments there.
</p>
TicketjasonThu, 10 Dec 2009 10:30:26 GMTcc changed
https://trac.sagemath.org/ticket/7640#comment:6
https://trac.sagemath.org/ticket/7640#comment:6
<ul>
<li><strong>cc</strong>
<em>jason</em> added
</li>
</ul>
TicketncohenSat, 12 Dec 2009 17:46:11 GMTstatus changed
https://trac.sagemath.org/ticket/7640#comment:7
https://trac.sagemath.org/ticket/7640#comment:7
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
One less between Sage and c_graphs :-)
</p>
<p>
Here is the result of the test given in the description of this ticket :
</p>
<pre class="wiki">sage: sage: G = graphs.CubeGraph(5)
sage: sage: C = G.copy(implementation='c_graph')
sage: sage: timeit("G.shortest_path('01001', '10100')")
625 loops, best of 3: 51.6 µs per loop
sage: sage: timeit("C.shortest_path('01001', '10100')")
625 loops, best of 3: 30.4 µs per loop
</pre><p>
Nathann
</p>
TicketrlmSat, 12 Dec 2009 18:20:36 GMTstatus changed
https://trac.sagemath.org/ticket/7640#comment:8
https://trac.sagemath.org/ticket/7640#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Great work!
</p>
<p>
A few comments:
</p>
<ol><li>You can use <code>if self._backend.hasattr('_cg')</code> to test whether self is a <code>c_graph</code> or a <code>networkx</code> graph. This seems cleaner than a try-except block.
</li></ol><ol start="2"><li>It should be easy to implement something in the case <code>bidirectional=False</code>, and we should do this since the point is to replace NetworkX with our own functionality.
</li></ol><ol start="3"><li>We also need to handle the case <code>by_weight=True</code>: this is only relevant for <code>SparseGraph</code>s, since <code>DenseGraph</code>s don't support edge labeling.
</li></ol>
TicketncohenSat, 12 Dec 2009 18:28:32 GMTcc changed
https://trac.sagemath.org/ticket/7640#comment:9
https://trac.sagemath.org/ticket/7640#comment:9
<ul>
<li><strong>cc</strong>
<em>mvngu</em> added
</li>
</ul>
<p>
Several answers, then :-)
</p>
<ol><li>That's why I wanted to use at first but Martin Albrecht told me in <a class="closed ticket" href="https://trac.sagemath.org/ticket/7637" title="enhancement: Default dictionary in MixedIntegerLinearProgram (closed: fixed)">#7637</a> that this version should be more efficient
</li></ol><ol start="2"><li>The version <code></code>bidirectional = False<code></code> is indeed very easy to write ( one only needs to remove variables ), but I wondered if this was useful... <code></code>bidirectional=True<code></code> is the default option, used in all the others call to it, and this second version is meant to be faster... :-)
</li></ol><ol start="3"><li>I started by trying to write the Dijkstra algorithm, and ended up wondering whether there was a Heap structure already written in Cython. I needed to maintain a sorted list, and found no reference about it ... If you know how to do it, I'll begin immediately ! :-)
</li></ol><p>
This version of shortest_path seems to be the most used ( bidirectional=True, weights=False ), so I thought the most urgent was to make your c_graphs the default ones.. I just created two tickets in the graph section about functions that should be moved from networkx to c_graphs, we could just add these two ! Anyway I intend to take care of them :-)
</p>
<p>
Nathann
</p>
TicketrlmSat, 12 Dec 2009 18:31:05 GMT
https://trac.sagemath.org/ticket/7640#comment:10
https://trac.sagemath.org/ticket/7640#comment:10
<p>
I applied the patch here, together with the patch at <a class="closed ticket" href="https://trac.sagemath.org/ticket/7634" title="enhancement: switch default Sage graphs over to c_graph, and split up graph.py and ... (closed: fixed)">#7634</a>, (to <code>4.3.rc0</code>) in order to fully test the new functionality, and here are the results of <code>-t -long sage/graphs</code> (files not listed passed):
</p>
<pre class="wiki">sage -t -long "devel/sage-main/sage/graphs/graph.py"
**********************************************************************
File "/Users/rlmill/sage-4.3.rc0/devel/sage-main/sage/graphs/graph.py", line 5838:
sage: H.is_isomorphic(graphs.CompleteGraph(n))
Expected:
True
Got:
False
**********************************************************************
File "/Users/rlmill/sage-4.3.rc0/devel/sage-main/sage/graphs/graph.py", line 7329:
sage: g.transitive_reduction().size()
Expected:
5
Got:
6
**********************************************************************
File "/Users/rlmill/sage-4.3.rc0/devel/sage-main/sage/graphs/graph.py", line 2206:
sage: o.in_degree()
Expected:
[2, 2, 2, 2, 1, 2, 1, 1, 1, 1]
Got:
[2, 2, 2, 2, 2, 1, 1, 1, 1, 1]
**********************************************************************
File "/Users/rlmill/sage-4.3.rc0/devel/sage-main/sage/graphs/graph.py", line 2208:
sage: o.out_degree()
Expected:
[1, 1, 1, 1, 2, 1, 2, 2, 2, 2]
Got:
[1, 1, 1, 1, 1, 2, 2, 2, 2, 2]
**********************************************************************
File "/Users/rlmill/sage-4.3.rc0/devel/sage-main/sage/graphs/graph.py", line 4736:
sage: g.degree_sequence()
Exception raised:
Traceback (most recent call last):
File "/Users/rlmill/sage-4.3.rc0/local/bin/ncadoctest.py", line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Users/rlmill/sage-4.3.rc0/local/bin/sagedoctest.py", line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
File "/Users/rlmill/sage-4.3.rc0/local/bin/ncadoctest.py", line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_96[3]>", line 1, in <module>
g.degree_sequence()###line 4736:
sage: g.degree_sequence()
File "/Users/rlmill/sage-4.3.rc0/local/lib/python/site-packages/sage/graphs/graph.py", line 4754, in degree_sequence
return sorted(self.degree_iterator(), reverse=True)
File "/Users/rlmill/sage-4.3.rc0/local/lib/python/site-packages/sage/graphs/graph.py", line 4725, in degree_iterator
yield filter(v, self)
File "/Users/rlmill/sage-4.3.rc0/local/lib/python/site-packages/sage/graphs/graph.py", line 4723, in <lambda>
filter = lambda v, self: self._backend.degree(v, self._directed)
File "c_graph.pyx", line 751, in sage.graphs.base.c_graph.CGraphBackend.degree (sage/graphs/base/c_graph.c:7480)
File "c_graph.pyx", line 594, in sage.graphs.base.c_graph.CGraph._out_degree (sage/graphs/base/c_graph.c:6472)
RuntimeError: Vertex (5) is not a vertex of the graph.
**********************************************************************
File "/Users/rlmill/sage-4.3.rc0/devel/sage-main/sage/graphs/graph.py", line 4742:
sage: g.degree_sequence()
Exception raised:
Traceback (most recent call last):
File "/Users/rlmill/sage-4.3.rc0/local/bin/ncadoctest.py", line 1231, in run_one_test
self.run_one_example(test, example, filename, compileflags)
File "/Users/rlmill/sage-4.3.rc0/local/bin/sagedoctest.py", line 38, in run_one_example
OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
File "/Users/rlmill/sage-4.3.rc0/local/bin/ncadoctest.py", line 1172, in run_one_example
compileflags, 1) in test.globs
File "<doctest __main__.example_96[5]>", line 1, in <module>
g.degree_sequence()###line 4742:
sage: g.degree_sequence()
File "/Users/rlmill/sage-4.3.rc0/local/lib/python/site-packages/sage/graphs/graph.py", line 4754, in degree_sequence
return sorted(self.degree_iterator(), reverse=True)
File "/Users/rlmill/sage-4.3.rc0/local/lib/python/site-packages/sage/graphs/graph.py", line 4725, in degree_iterator
yield filter(v, self)
File "/Users/rlmill/sage-4.3.rc0/local/lib/python/site-packages/sage/graphs/graph.py", line 4723, in <lambda>
filter = lambda v, self: self._backend.degree(v, self._directed)
File "c_graph.pyx", line 749, in sage.graphs.base.c_graph.CGraphBackend.degree (sage/graphs/base/c_graph.c:7433)
File "c_graph.pyx", line 580, in sage.graphs.base.c_graph.CGraph._in_degree (sage/graphs/base/c_graph.c:6372)
RuntimeError: Vertex (6) is not a vertex of the graph.
**********************************************************************
</pre><pre class="wiki">sage -t -long "devel/sage-main/sage/graphs/linearextensions.py"
**********************************************************************
File "/Users/rlmill/sage-4.3.rc0/devel/sage-main/sage/graphs/linearextensions.py", line 360:
sage: l.incomparable(1,2)
Expected:
True
Got:
False
**********************************************************************
</pre>
TicketrlmSat, 12 Dec 2009 18:35:32 GMT
https://trac.sagemath.org/ticket/7640#comment:11
https://trac.sagemath.org/ticket/7640#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7640#comment:9" title="Comment 9">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Several answers, then :-)
</p>
<ol><li>That's why I wanted to use at first but Martin Albrecht told me in <a class="closed ticket" href="https://trac.sagemath.org/ticket/7637" title="enhancement: Default dictionary in MixedIntegerLinearProgram (closed: fixed)">#7637</a> that this version should be more efficient
</li></ol></blockquote>
<p>
Great!
</p>
<blockquote class="citation">
<ol start="2"><li>The version <code></code>bidirectional = False<code></code> is indeed very easy to write ( one only needs to remove variables ), but I wondered if this was useful... <code></code>bidirectional=True<code></code> is the default option, used in all the others call to it, and this second version is meant to be faster... :-)
</li></ol></blockquote>
<p>
This is indeed a good point. I wonder if anyone ever in the history of Sage has used bidirectional=False.
</p>
<blockquote class="citation">
<ol start="3"><li>I started by trying to write the Dijkstra algorithm, and ended up wondering whether there was a Heap structure already written in Cython. I needed to maintain a sorted list, and found no reference about it ... If you know how to do it, I'll begin immediately ! :-)
</li></ol></blockquote>
<p>
I'm not sure...
</p>
<blockquote class="citation">
<p>
This version of shortest_path seems to be the most used ( bidirectional=True, weights=False ), so I thought the most urgent was to make your c_graphs the default ones.. I just created two tickets in the graph section about functions that should be moved from networkx to c_graphs, we could just add these two ! Anyway I intend to take care of them :-)
</p>
</blockquote>
<p>
I don't think <code>bidirectional=False</code> is a showstopper at all (in fact we should ping sage-devel about removing this option, since it seems silly). However, <code>by_weights=True</code> is going to be necessary to make the switch. I also just noticed that the function <code>shortest_paths</code> needs to be implemented for <code>c_graph</code>s too.
</p>
TicketncohenSat, 12 Dec 2009 18:37:31 GMT
https://trac.sagemath.org/ticket/7640#comment:12
https://trac.sagemath.org/ticket/7640#comment:12
<p>
I'll take a look at those errors immediately.
</p>
<p>
shortest_paths is but a slight modification of this function, but as it needs to be very fast I wondered about copying most of the code and adding the necessary details.. What's you advice ?
</p>
<p>
Nathann
</p>
TicketrlmSat, 12 Dec 2009 18:39:41 GMT
https://trac.sagemath.org/ticket/7640#comment:13
https://trac.sagemath.org/ticket/7640#comment:13
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7640#comment:12" title="Comment 12">ncohen</a>:
</p>
<blockquote class="citation">
<p>
I'll take a look at those errors immediately.
</p>
<p>
shortest_paths is but a slight modification of this function, but as it needs to be very fast I wondered about copying most of the code and adding the necessary details.. What's you advice ?
</p>
<p>
Nathann
</p>
</blockquote>
<p>
I would think about using the same code. Or factoring it out so that the redundant parts get written only once. (I don't know how familiar you are with Cython, but you can use <code>inline</code> in situations like these!)
</p>
TicketrlmSat, 12 Dec 2009 18:42:22 GMT
https://trac.sagemath.org/ticket/7640#comment:14
https://trac.sagemath.org/ticket/7640#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7640#comment:12" title="Comment 12">ncohen</a>:
</p>
<blockquote class="citation">
<p>
I'll take a look at those errors immediately.
</p>
</blockquote>
<p>
Not remembering whether I tested <a class="closed ticket" href="https://trac.sagemath.org/ticket/7634" title="enhancement: switch default Sage graphs over to c_graph, and split up graph.py and ... (closed: fixed)">#7634</a> with <code>-long</code> by itself, I'm checking to see how <a class="closed ticket" href="https://trac.sagemath.org/ticket/7634" title="enhancement: switch default Sage graphs over to c_graph, and split up graph.py and ... (closed: fixed)">#7634</a> does on its own (on top of alpha0 of course, since rc0 has distance_graphs, which time out...)
</p>
TicketrlmSat, 12 Dec 2009 19:01:10 GMT
https://trac.sagemath.org/ticket/7640#comment:15
https://trac.sagemath.org/ticket/7640#comment:15
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7640#comment:14" title="Comment 14">rlm</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7640#comment:12" title="Comment 12">ncohen</a>:
</p>
<blockquote class="citation">
<p>
I'll take a look at those errors immediately.
</p>
</blockquote>
<p>
Not remembering whether I tested <a class="closed ticket" href="https://trac.sagemath.org/ticket/7634" title="enhancement: switch default Sage graphs over to c_graph, and split up graph.py and ... (closed: fixed)">#7634</a> with <code>-long</code> by itself, I'm checking to see how <a class="closed ticket" href="https://trac.sagemath.org/ticket/7634" title="enhancement: switch default Sage graphs over to c_graph, and split up graph.py and ... (closed: fixed)">#7634</a> does on its own (on top of alpha0 of course, since rc0 has distance_graphs, which time out...)
</p>
</blockquote>
<p>
All tests pass here, so it looks like all the issues above are relevant.
</p>
TicketncohenSat, 12 Dec 2009 19:03:19 GMT
https://trac.sagemath.org/ticket/7640#comment:16
https://trac.sagemath.org/ticket/7640#comment:16
<p>
The first (test of isomorphism) error was a mistake in the algorithm and is fixed already. I am dealing with the second one (transitive_reduction) which is related to the fact that we are dealing with a digraph... I am not worried by the <a class="missing wiki">RuntimeErrors?</a> that follow... I will update this patch as soon as possible :-)
</p>
TicketncohenSat, 12 Dec 2009 19:33:26 GMTstatus changed
https://trac.sagemath.org/ticket/7640#comment:17
https://trac.sagemath.org/ticket/7640#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Well, in the end I corrected the first two errors, which were directly errors in the algorithm ( I ignored the direction of arcs, which is now fixed ).
</p>
<p>
The following ones are created by the enumeration of degree ( for example the error in eulerian_orientation is not really one. The result given is correct, but there is one inversion due to the fact that the order in the listing of neighbors is not the same when you patch is applied :-)
</p>
<p>
This reminded me that your patch for c_graphs had not actually been tested against the new Sage because of the slowness in the distance function.. As eulerian_orientation does not care about distances ( I wrote this one :-) ), I do not think shortest_path is responsible for this one... Could you take a look at the last bugs to see if it could come from the switching process ( it it for sure in the case of eulerian_orientation ) ?
</p>
<p>
Actually, as it is not possible to test your switching patch without the shortest)path functiom, perhaps we should merge the two in just one patch....
</p>
<p>
We're almost there !!!!!!!!!! :-)
</p>
<p>
Nathann
</p>
TicketncohenSat, 12 Dec 2009 19:33:46 GMTattachment set
https://trac.sagemath.org/ticket/7640
https://trac.sagemath.org/ticket/7640
<ul>
<li><strong>attachment</strong>
set to <em>trac_7640.patch</em>
</li>
</ul>
TicketrlmSat, 12 Dec 2009 19:39:51 GMT
https://trac.sagemath.org/ticket/7640#comment:18
https://trac.sagemath.org/ticket/7640#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7640#comment:17" title="Comment 17">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Actually, as it is not possible to test your switching patch without the shortest)path functiom, perhaps we should merge the two in just one patch....
</p>
</blockquote>
<p>
Absolutely not! There is *much* work that needs to be done before <a class="closed ticket" href="https://trac.sagemath.org/ticket/7634" title="enhancement: switch default Sage graphs over to c_graph, and split up graph.py and ... (closed: fixed)">#7634</a> gets merged (this is just one piece). Once this patch is finalized, we can say <a class="closed ticket" href="https://trac.sagemath.org/ticket/7634" title="enhancement: switch default Sage graphs over to c_graph, and split up graph.py and ... (closed: fixed)">#7634</a> depends on this, and then the testing issue will be moot.
</p>
<p>
Review of the current patch coming shortly...
</p>
TicketrlmSat, 12 Dec 2009 20:02:19 GMTstatus changed; reviewer, author set
https://trac.sagemath.org/ticket/7640#comment:19
https://trac.sagemath.org/ticket/7640#comment:19
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Robert Miller</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
I've created <a class="closed ticket" href="https://trac.sagemath.org/ticket/7673" title="defect: implement Dijkstra's algorithm for C graphs (closed: fixed)">#7673</a> to deal with the <code>by_weight=True</code> case. I like this patch as it is, since it makes it possible to test <a class="closed ticket" href="https://trac.sagemath.org/ticket/7634" title="enhancement: switch default Sage graphs over to c_graph, and split up graph.py and ... (closed: fixed)">#7634</a>. Also, by itself it passes long tests in sage/graphs. Nice work!
</p>
TicketmhansenMon, 14 Dec 2009 16:41:40 GMTstatus, milestone changed; resolution, merged set
https://trac.sagemath.org/ticket/7640#comment:20
https://trac.sagemath.org/ticket/7640#comment:20
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.3.rc1</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-4.3.1</em> to <em>sage-4.3</em>
</li>
</ul>
Ticket