Opened 10 years ago
Closed 10 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)
Change History (17)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
comment:3 Changed 10 years ago by
- 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 10 years ago by
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 10 years ago by
- 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 10 years ago by
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: ↓ 9 Changed 10 years ago by
There is no "yield" command available at the moment in Cython... :-)
comment:8 Changed 10 years ago by
Now using bitset_first to find a vertex in the graph :-)
Nathann
comment:9 in reply to: ↑ 7 Changed 10 years ago by
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 10 years ago by
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 10 years ago by
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 10 years ago by
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 10 years ago by
slight update: use extend instead of append improves performance
Changed 10 years ago by
comment:14 Changed 10 years ago by
- Status changed from needs_review to positive_review
- 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.
- 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 functionvertex_label
will go from int to Python object, and I've switched these in the appropriate places (seetrac_7724-ref.patch
). I've also added an example where the vertex labels aren't integers.
- I've tested this with #7634 applied, and everything looks good with the fixes mentioned above.
Changed 10 years ago by
comment:15 Changed 10 years ago by
- Merged in set to sage-4.3.1.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
( small bug fixed : I had forgotten bitset_set_first_n which was quite problematic in a few cases :-) )