Opened 7 years ago

Closed 7 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 dcoudert)

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)

trac_13665_blocks_and_cuts.patch (6.6 KB) - added by dcoudert 7 years ago.
trac_13665-rev.patch (4.7 KB) - added by ncohen 7 years ago.
trac_13665-rev2.patch (4.5 KB) - added by dcoudert 7 years ago.

Download all attachments as: .zip

Change History (19)

Changed 7 years ago by dcoudert

comment:1 Changed 7 years ago by dcoudert

  • 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

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.

comment:2 Changed 7 years ago by ncohen

Ahahahaah. I am reading the patch, and laughing. Very smart use of iterators :-)

Nathann

comment:3 Changed 7 years ago by dcoudert

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: Changed 7 years ago by ncohen

  • 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 7 years ago by ncohen

comment:5 Changed 7 years ago by ncohen

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 7 years ago by dcoudert

  • 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 7 years ago by ncohen

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 7 years ago by dcoudert

comment:8 Changed 7 years ago by dcoudert

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 7 years ago by ncohen

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 7 years ago by dcoudert

Yes, moving code should be done in specific patchs.

comment:11 Changed 7 years ago by ncohen

  • Status changed from needs_review to positive_review

Well, then... :-)

Nathann

comment:12 Changed 7 years ago by dcoudert

Thanks !

comment:13 Changed 7 years ago by jdemeyer

  • Reviewers set to Nathann Cohen
  • Status changed from positive_review to needs_info

Please clarify which patches should be applied.

comment:14 Changed 7 years ago by dcoudert

  • Description modified (diff)
  • Status changed from needs_info to needs_review

comment:15 Changed 7 years ago by dcoudert

  • Status changed from needs_review to positive_review

comment:16 Changed 7 years ago by jdemeyer

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