Opened 10 years ago

Closed 10 years ago

#7640 closed defect (fixed)

shortest_path should not use NetworkX if the underlying graph is a c_graph

Reported by: rlm Owned by: rlm
Priority: major Milestone: sage-4.3
Component: graph theory Keywords:
Cc: ncohen, rlm, jason, mvngu Merged in: sage-4.3.rc1
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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

Attachments (1)

trac_7640.patch (5.7 KB) - added by ncohen 10 years ago.

Download all attachments as: .zip

Change History (21)

comment:1 Changed 10 years ago by rlm

This is one of those functions that should probably be written in Cython, on as low a level as possible...

comment:2 Changed 10 years ago by ncohen

To be honest, I intended to write it as soon as your partch to make them the default format is merged :-)

comment:3 Changed 10 years ago by rlm

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

comment:4 follow-up: Changed 10 years ago by ylchapuy

One problem IMHO with c_graph is that as is (correct me if I'm wrong) we won't be able to have a fast in_neighbors.

At least the current implementation is to test all vertices in the graph.

comment:5 in reply to: ↑ 4 Changed 10 years ago by rlm

Replying to ylchapuy:

One problem IMHO with c_graph is that as is (correct me if I'm wrong) we won't be able to have a fast in_neighbors.

At least the current implementation is to test all vertices in the graph.

This belongs here: http://groups.google.com/group/sage-devel/browse_thread/thread/8edd29e9bddc67e5

See my comments there.

comment:6 Changed 10 years ago by jason

  • Cc jason added

comment:7 Changed 10 years ago by ncohen

  • Status changed from new to needs_review

One less between Sage and c_graphs :-)

Here is the result of the test given in the description of this ticket :

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

Nathann

comment:8 Changed 10 years ago by rlm

  • Status changed from needs_review to needs_work

Great work!

A few comments:

  1. You can use if self._backend.hasattr('_cg') to test whether self is a c_graph or a networkx graph. This seems cleaner than a try-except block.
  1. It should be easy to implement something in the case bidirectional=False, and we should do this since the point is to replace NetworkX with our own functionality.
  1. We also need to handle the case by_weight=True: this is only relevant for SparseGraphs, since DenseGraphs don't support edge labeling.

comment:9 follow-up: Changed 10 years ago by ncohen

  • Cc mvngu added

Several answers, then :-)

  1. That's why I wanted to use at first but Martin Albrecht told me in #7637 that this version should be more efficient
  1. The version bidirectional = False is indeed very easy to write ( one only needs to remove variables ), but I wondered if this was useful... bidirectional=True is the default option, used in all the others call to it, and this second version is meant to be faster... :-)
  1. 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 ! :-)

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

Nathann

comment:10 Changed 10 years ago by rlm

I applied the patch here, together with the patch at #7634, (to 4.3.rc0) in order to fully test the new functionality, and here are the results of -t -long sage/graphs (files not listed passed):

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.
**********************************************************************
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
**********************************************************************

comment:11 in reply to: ↑ 9 Changed 10 years ago by rlm

Replying to ncohen:

Several answers, then :-)

  1. That's why I wanted to use at first but Martin Albrecht told me in #7637 that this version should be more efficient

Great!

  1. The version bidirectional = False is indeed very easy to write ( one only needs to remove variables ), but I wondered if this was useful... bidirectional=True is the default option, used in all the others call to it, and this second version is meant to be faster... :-)

This is indeed a good point. I wonder if anyone ever in the history of Sage has used bidirectional=False.

  1. 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 ! :-)

I'm not sure...

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

I don't think bidirectional=False is a showstopper at all (in fact we should ping sage-devel about removing this option, since it seems silly). However, by_weights=True is going to be necessary to make the switch. I also just noticed that the function shortest_paths needs to be implemented for c_graphs too.

comment:12 follow-ups: Changed 10 years ago by ncohen

I'll take a look at those errors immediately.

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 ?

Nathann

comment:13 in reply to: ↑ 12 Changed 10 years ago by rlm

Replying to ncohen:

I'll take a look at those errors immediately.

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 ?

Nathann

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 inline in situations like these!)

comment:14 in reply to: ↑ 12 ; follow-up: Changed 10 years ago by rlm

Replying to ncohen:

I'll take a look at those errors immediately.

Not remembering whether I tested #7634 with -long by itself, I'm checking to see how #7634 does on its own (on top of alpha0 of course, since rc0 has distance_graphs, which time out...)

comment:15 in reply to: ↑ 14 Changed 10 years ago by rlm

Replying to rlm:

Replying to ncohen:

I'll take a look at those errors immediately.

Not remembering whether I tested #7634 with -long by itself, I'm checking to see how #7634 does on its own (on top of alpha0 of course, since rc0 has distance_graphs, which time out...)

All tests pass here, so it looks like all the issues above are relevant.

comment:16 Changed 10 years ago by ncohen

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 RuntimeErrors? that follow... I will update this patch as soon as possible :-)

comment:17 follow-up: Changed 10 years ago by ncohen

  • Status changed from needs_work to needs_review

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

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

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 ) ?

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

We're almost there !!!!!!!!!! :-)

Nathann

Changed 10 years ago by ncohen

comment:18 in reply to: ↑ 17 Changed 10 years ago by rlm

Replying to ncohen:

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

Absolutely not! There is *much* work that needs to be done before #7634 gets merged (this is just one piece). Once this patch is finalized, we can say #7634 depends on this, and then the testing issue will be moot.

Review of the current patch coming shortly...

comment:19 Changed 10 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to positive_review

I've created #7673 to deal with the by_weight=True case. I like this patch as it is, since it makes it possible to test #7634. Also, by itself it passes long tests in sage/graphs. Nice work!

comment:20 Changed 10 years ago by mhansen

  • Merged in set to sage-4.3.rc1
  • Milestone changed from sage-4.3.1 to sage-4.3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.