Opened 8 years ago
Closed 8 years ago
#13665 closed enhancement (fixed)
New implementation of the blocks_and_cut_vertices method
Reported by: | dcoudert | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-5.5 |
Component: | graph theory | Keywords: | |
Cc: | ncohen | Merged in: | sage-5.5.beta2 |
Authors: | David Coudert | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This patch implements the blocks_and_cut_vertices
method as proposed by Tarjan in 1972. The time complexity is now in O(|V|+|E|). The running time improvement is significant compared to previous implementation, in particular on large-scale graphs with many blocks.
Before:
sage: GP = graphs.PathGraph(6) sage: %timeit B,C = GP.blocks_and_cut_vertices() 625 loops, best of 3: 167 µs per loop sage: import networkx sage: Gbig = Graph(networkx.read_edgelist('/PATHTOFILE/as-rel.20120601.edgelist')) sage: Gbig.num_verts(),G.num_edges() (41203, 121309) sage: %timeit B,C = G.blocks_and_cut_vertices() 5 loops, best of 3: 44.1 s per loop
After:
sage: %timeit B,C = GP.blocks_and_cut_vertices() 625 loops, best of 3: 152 µs per loop sage: %timeit B,C = Gbig.blocks_and_cut_vertices() 5 loops, best of 3: 1.61 s per loop
Apply:
Attachments (3)
Change History (19)
Changed 8 years ago by
comment:1 Changed 8 years ago by
- Cc ncohen added
- Description modified (diff)
- Status changed from new to needs_review
- Summary changed from New implementation of the blocks_and_cut_vertices methods to New implementation of the blocks_and_cut_vertices method
comment:2 Changed 8 years ago by
Ahahahaah. I am reading the patch, and laughing. Very smart use of iterators :-)
Nathann
comment:3 Changed 8 years ago by
When you are to implement Tarjan's algorithms, you have to be smart ;-)
This algorithm has been published 40 years ago. We have to show some respect to the Master!
comment:4 follow-up: ↓ 6 Changed 8 years ago by
- Status changed from needs_review to needs_work
HelloooooooooooooooooooOO again !
Here is a patch that contains documentation only (if you like it), and three comments :
- What about replacing top by -1 everywhere ? This is Python code, not C arrays ! :-P
- Instead of
if stack
and indenting maaaaaaaaany lines in the code, what about writing instead
if not stack: return whatever
(and remove the terminal 'return' line) or
if not stack: break
and leave the code at its natural level ?
w = stack.pop()
at this line w is equal to v, isn't it ?
O_o
as it appears often afterwards I would sleep easier (unless I make a mistake) if it were replaced by
w = v
to make it explicit. With a
stack.pop()
just near, or course.
Thaaaaaaaanks for that patch ! I'll go enjoy some sun while it stays :-)
Nathann
Changed 8 years ago by
comment:5 Changed 8 years ago by
Oh by the way : what about adding, when everything here will be settled, another patch files that just moves the code we settle on to the file graph.py ? This has nothing to do in generic_graph.py !!!
Nathann
comment:6 in reply to: ↑ 4 Changed 8 years ago by
- Status changed from needs_work to needs_review
Here is a patch that contains documentation only (if you like it), and three comments :
I like the doc
- What about replacing top by -1 everywhere ? This is Python code, not C arrays ! :-P
done
- Instead of
if stack
and indenting maaaaaaaaany lines in the code, what about writing instead
if not stack: return whatever
(and remove the terminal 'return' line) or
if not stack: break
and leave the code at its natural level ?
done
w = stack.pop()
at this line w is equal to v, isn't it ?
O_o
as it appears often afterwards I would sleep easier (unless I make a mistake) if it were replaced by
w = v
to make it explicit. With a
stack.pop()
just near, or course.
I disagree. If we put w = v
, then we still have to pop the top of the stack. It is more compact to write w = stack.pop()
. Furthermore I don't think it could be faster to have 2 operations instead of 1.
Thaaaaaaaanks for that patch ! I'll go enjoy some sun while it stays
:-)
Lucky you are. Here it's cold, raining, no light... welcome to the french riviera ;-)
comment:7 Changed 8 years ago by
Oh. It was only to make it easier to read. Just adding a comment above like "at this point w=v, as v is the value of stack[-1]" is more or less the same.
By the way, do we move the code to graph.py ?
Nathann
Changed 8 years ago by
comment:8 Changed 8 years ago by
I have added a comment before w = stack.pop()
I have nothing against moving the code, but are you sure no one is using this method on directed graphs?
Also, this method is used in generic_graph.py
by several methods: genus, vertex_connectivity, is_gallai_graph
, and in isgci.py
. Would that be a problem?
comment:9 Changed 8 years ago by
Well.. I have no idea what this algorithm returns when using on a DiGraph?. All I can tell is that it returns the blocks and cut vertices of the underlying graph, but what does it mean in a DiGraph? ?
Genus and is_gallai_graph should be moved to graph.py too, by the way. Nothing to do in generic_graph either. This being said, vertex_connectivity should definitely stay there, but there is no problem with it as it only calls blocks_and_cut_vertices after checking that the graph is NOT directed :-)
Well. If we are to do all this, let's do it in another patch, don't you think ?
Nathann
comment:10 Changed 8 years ago by
Yes, moving code should be done in specific patchs.
comment:11 Changed 8 years ago by
- Status changed from needs_review to positive_review
Well, then... :-)
Nathann
comment:12 Changed 8 years ago by
Thanks !
comment:13 Changed 8 years ago by
- Reviewers set to Nathann Cohen
- Status changed from positive_review to needs_info
Please clarify which patches should be applied.
comment:14 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_info to needs_review
comment:15 Changed 8 years ago by
- Status changed from needs_review to positive_review
comment:16 Changed 8 years ago by
- Merged in set to sage-5.5.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
In fact the time complexity is more than O(|V|+|E|) since I'm sorting the lists, but the extra computation time is negligible. This can be removed.
I'm using a try...except to test the end of iterations. This could be replaced with a more appropriate test, if any.