Opened 9 years ago

Closed 9 years ago

#7724 closed enhancement (fixed)

breadth/depth first search and basic connectivity for c_graphs

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.3.1
Component: graph theory Keywords:
Cc: rlm Merged in: sage-4.3.1.alpha0
Authors: Nathann Cohen, Yann Laigle-Chapuy Reviewers: Robert Miller
Report Upstream: N/A Work issues: needs rebase
Branch: Commit:
Dependencies: Stopgaps:

Description

Some improvement on this side, and so for ther functions like connected components, strongly connected components, etc...

sage: g= graphs.RandomGNP(1000,.01)
sage: h=g.copy(implementation="c_graph")
sage: timeit("list(g.depth_first_search(0))")
25 loops, best of 3: 10.9 ms per loop
sage: timeit("list(h.depth_first_search(0))")
125 loops, best of 3: 2.03 ms per loop

Nathann

Attachments (2)

trac_7724_iterator-rebased.patch (12.5 KB) - added by rlm 9 years ago.
trac_7724-ref.patch (1.7 KB) - added by rlm 9 years ago.

Download all attachments as: .zip

Change History (17)

comment:1 Changed 9 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by ncohen

( small bug fixed : I had forgotten bitset_set_first_n which was quite problematic in a few cases :-) )

comment:3 Changed 9 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to needs_work
  • Work issues set to needs rebase

There's a merging conflict:

-        ALGORITHM: 8.3.8 in [1]. Notice that the termination condition on 
-        line (23) of the algorithm uses "p[v] == 0" which in the book 
-        means that the parent is undefined; in this case, v must be the 
+        ALGORITHM: 8.3.8 in [Jungnickel2005]_. Notice that the termination 
+        condition on line (23) of the algorithm uses "p[v] == 0" which in
+        the book means that the parent is undefined; in this case, v must be the 
         root s.  Since our vertex names start with 0, we substitute instead
         the condition "v == s".  This is the terminating condition used 
         in the general Depth First Search tree in Algorithm 8.2.1.
         
         REFERENCE:
 
-        - [1] D. Jungnickel, Graphs, Networks and Algorithms,
+        .. [Jungnickel2005] D. Jungnickel, Graphs, Networks and Algorithms,

This change already made it into 4.3.rc1, I believe, in #7314. Can you rebase on top of that patch?

comment:4 Changed 9 years ago by ncohen

I'm not at home and won't be able to do it today... I should be able to produce it tomorrow morning though :-)

comment:5 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review
  • Summary changed from breadth/depth first search for c_graphs to breadth/depth first search and basic connectivity for c_graphs

Hello !!

I could not reproduce your merging conflict, though as I had applied the patch I use the occasion to add a few other things... You will find in this new version of the patch

  • A function beadth_dirst_search ( with optional arguments reverse and ignore_direction
  • A function depth_first_search with the same paremeters
  • A function is_connected
  • A function is_strongly_connected
  • I needed to know inside the graph backend whether the graph was directed or not : I thought for some time about it, and ended up adding to the constructors of Graph and DiGraph? a line self._backend.directed = True/False? according to the situation.
  • I also modified graph.py so that it would use the functions defined in c_graph whenever possible, and NetworkX otherwise

And with this, we should be another step closer.. :-)

Nathann

comment:6 Changed 9 years ago by ylchapuy

The actual breadth/depth_first_search are generator objects but your new ones are plain lists. Is it a design choice?

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

There is no "yield" command available at the moment in Cython... :-)

comment:8 Changed 9 years ago by ncohen

Now using bitset_first to find a vertex in the graph :-)

Nathann

comment:9 in reply to: ↑ 7 Changed 9 years ago by ylchapuy

Replying to ncohen:

There is no "yield" command available at the moment in Cython... :-)

But you can still define a iterator class.

The following patch is based on your work, and defines an iterator. You can choose which one you prefer.

comment:10 Changed 9 years ago by ncohen

Well, actually until now Robert Miller just typed : return iter(value)) which was good too... If you prefer to return an iterator instead of alist, perhaps this would be better :-)

comment:11 Changed 9 years ago by ylchapuy

The way I did it, I don't copy the data, the big list doesn't exist, this can be an advantage. But I let you do the choice, I won't use big graphs anyway.

comment:12 Changed 9 years ago by ncohen

Well, my view was that if just waiting can prevent us from writing lines of codes that could be replaced by a "yield" once it will be available, why not ? :-)

Let's see what Robert thinks about it if he is finally reviewing this ticket .. And thank you again for your help ! :-)

Nathann

comment:13 Changed 9 years ago by ylchapuy

slight update: use extend instead of append improves performance

Changed 9 years ago by rlm

comment:14 Changed 9 years ago by rlm

  • Authors changed from Nathann Cohen to Nathann Cohen, Yann Laigle-Chapuy
  • Status changed from needs_review to positive_review
  1. The iterator patch is preferable, since there are actual speed gains when a loop is terminated early. I've rebased the patch against sage-4.3.
  1. There is some confusion as to the function get_vertex. This should go from Python objects to ints, and in several places it is used the other way around. The function vertex_label will go from int to Python object, and I've switched these in the appropriate places (see trac_7724-ref.patch). I've also added an example where the vertex labels aren't integers.
  1. I've tested this with #7634 applied, and everything looks good with the fixes mentioned above.

Changed 9 years ago by rlm

comment:15 Changed 9 years ago by mhansen

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