Opened 10 years ago

Closed 10 years ago

#13289 closed enhancement (fixed)

Determine if a vertex is a cut vertex

Reported by: dcoudert Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.4
Component: graph theory Keywords:
Cc: lkeough Merged in: sage-5.4.rc0
Authors: David Coudert Reviewers: Sebastian Luther
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by dcoudert)

This patch test if a given vertex is a cut vertex, that is if its removal from the (di)graph increases the number of (weakly) connected components.

Attachments (1)

trac_13289_is_cut_vertex.patch (5.0 KB) - added by dcoudert 10 years ago.
rebased for sage-5.3.beta1

Download all attachments as: .zip

Change History (31)

comment:1 Changed 10 years ago by dcoudert

  • Cc lkeough added
  • Description modified (diff)
  • Status changed from new to needs_review

I'm not fully satisfied of this patch, but I have no better implementation in mind.

For digraphs, this patch considers weakly connected components, but it could also considers strongly connected components. I'm not sure of the most relevant definition.

Last edited 10 years ago by dcoudert (previous) (diff)

comment:2 Changed 10 years ago by dcoudert

  • Description modified (diff)

comment:3 Changed 10 years ago by lkeough

I'm not sure of the most relevant definition either, but blocks_and_cut_vertices also uses the underlying graph for directed graphs.

I tried using blocks and cut vertices to write is_cut_vertex, but it appears to be much slower (as expected). I'm not sure of a better way to implement this.

The tests all ran fine, maybe it's a good idea to add a digraphs test/example?

comment:4 Changed 10 years ago by dcoudert

I added a test on a digraph.

I don't know how to make this patch faster. So unless someone has a better proposition now, you can validate this patch, and future improvements will go to a new patch.

Thanks.

comment:5 Changed 10 years ago by lkeough

Good, all the tests ran fine. When I built the documentation I noticed a colon is missing in line 4026 so the example with giving a vertex not in the graph isn't showing up properly. Once that is fixed I'll give a positive review.

comment:6 Changed 10 years ago by dcoudert

Oups. That's the default of working remotely. I don't always notice such mistakes. It should now be OK.

comment:7 Changed 10 years ago by lkeough

  • Status changed from needs_review to positive_review

comment:8 Changed 10 years ago by dcoudert

Thanks for the review !

comment:9 Changed 10 years ago by jdemeyer

Please fill in your real name as Reviewer.

comment:10 Changed 10 years ago by sluther

  • Status changed from positive_review to needs_work

There is major problem with this patch. It modifies the given graph.

While it tries to revert the effect, this is still a bad idea. If an exception occurs between the removal of the vertex and the addition of the edges then the graph will end up modified (just think of CTRL+C or out of memory).

Also the reversal doesn't work for directed graphs currently. Just check the number of edges of D in your test case.

I'd argue that you shouldn't try to fix the reversal, but get rid of it. I don't now much about the problem, so can't suggest a better algorithm that what a quick google search would reveal. If you can't find a better algorithm, make a copy of the graph and modify this copy.

comment:11 Changed 10 years ago by dcoudert

That's right, the patch should not modify the graph. Unfortunately I have no got implementation to propose. In particular, it is impossible to use the blocks and cuts procedure since it is way to slow (should be cythonized some day).

I have changed the patch. I'm not happy with this implementation but it's working. One may later propose a faster implementation.

comment:12 Changed 10 years ago by dcoudert

If fact the running time of the function is largely dominated by the copy of the graph. This is boring.

comment:13 Changed 10 years ago by sluther

At least for the undirected case you could perform two DFSs and count the visited vertices. The first search would start at v and run on the orginal graph. The second one would ignore all edges incident to v and start at any neighbor of v. If v is not a cut vertex, the number of visited vertices should decrese only by 1.

For the first search you could call connected_component_containing_vertex. For the second run you need to inline the code and add the ability to ignore edges.

comment:14 Changed 10 years ago by dcoudert

  • Status changed from needs_work to needs_review

I fact, only one DFS is required for undirected graphs (or weak connectivity), and two for the strong connectivity of directed graphs. I don't need to copy the graph anymore and the running time of the resulting algorithm is acceptable.

sage: G = digraphs.RandomDirectedGNP(1000,.3)
sage: H = digraphs.RandomDirectedGNP(1000,.3)
sage: K = G+H
sage: K.add_edge(0,1000)
sage: K.add_edge(1200,300)
sage: %time K.is_strongly_connected()
CPU times: user 0.09 s, sys: 0.00 s, total: 0.09 s
Wall time: 0.09 s
True
sage: %time K.is_cut_vertex(0)
CPU times: user 0.23 s, sys: 0.00 s, total: 0.23 s
Wall time: 0.23 s
True
sage: %time K.is_cut_vertex(0, weak=True)
CPU times: user 1.01 s, sys: 0.00 s, total: 1.01 s
Wall time: 1.01 s
False

The only way to be faster is to use cython, as for the is_strongly_connected function. But I'm not sure it is worth the effort.

comment:15 Changed 10 years ago by sluther

Nice work!

1)

4034	        if not u in self.vertices(): 

should be:

4034	        if u not in self:

2) Any reason you're using self._directed instead of self.is_directed()
3)

while len(queue) > 0: 

should be:

while queue:

4) There is a potential performance optimization. Currently you first perform the full dfs and then check if all neighbors of v have been seen. You could instead mark the neighbors as seen once you saw them and abort the dfs once you saw all of them.
i.e. store them in a set and call discard on the set whenever you add a vertex to 'seen'. Then abort the dfs when the set is empty.

comment:16 Changed 10 years ago by dcoudert

You are right for 1 and 3. It's not obvious for me to write such stuff.

2: it's just that both are working. I changed to is_directed() which is cleaner.

4: I did it. So far I have not seen any difference but it could be interesting for some graphs, and it is strongly dependent on the dfs ordering.

I have also changed seen from set to dict. It could be faster to access a cell of a dictionary than to test is a elt is in a set. Furthermore, I avoid testing w!=u by initializing seen[u] to True, so it will never be considered.

Thanks for the comments.

comment:17 Changed 10 years ago by dcoudert

I changed the position of the targets.discard(w) to discard when it enters the queue and not when it is removed. That's better.

comment:18 Changed 10 years ago by sluther

Replying to dcoudert:

I have also changed seen from set to dict. It could be faster to access a cell of a >dictionary than to test is a elt is in a set.

IIRC they are both implemented as hash maps, which should make the set faster. I think it has something to do with the fact that the "v in s" has to catch the KeyError? and return False instead of just raising the exception. That's exactly what happens with your dict here. It doesn't catch KeyError?, but that's fine because it never occurs. Making it faster.

In contrast, if you let it catch the exception aka "seen.get(w, False)", the dict is a lot slower.

Furthermore, I avoid testing w!=u by initializing seen[u] to True, so it will never be considered.

Good idea.

Once I checked the manual and ptestlong, I'll give it a positive review.

comment:19 Changed 10 years ago by sluther

I found a bug in the directed case.

sage: D = DiGraph()
sage: D.add_edges(((1,2),(2,1),(2,5),(3,4),(4,3),(4,5),(5,6),(6,5),(5,7),(7,5),(6,7),(7,6)))
sage: D.is_cut_vertex(5) # Should be False
True
sage: D.strongly_connected_components()
[[1, 2], [3, 4], [5, 6, 7]]
sage: D.delete_vertex(5)
sage: D.strongly_connected_components()  # The number of components did not increase.
[[1, 2], [3, 4], [6, 7]]

Edit: Possible solution: Check only those neighbors which are in the same strong component as v.

Last edited 10 years ago by sluther (previous) (diff)

comment:20 follow-up: Changed 10 years ago by dcoudert

Ouppss. This is solved in this new version. I'm using a set of vertices to restrict the DFS to the vertices in the connected or strongly connected component containing u.

I have also restored the seen = set([start, u]) instead of a dict since only a subset of the vertices are now considered. In fact I don't know if it has a real impact on the performances, but it reduces initialization cost per loop.

I hope everything is in order now ;-)

Don't forget to put your name as reviewer.

comment:21 in reply to: ↑ 20 Changed 10 years ago by sluther

Replying to dcoudert:

Ouppss. This is solved in this new version. I'm using a set of vertices to restrict the DFS to the vertices in the connected or strongly connected component containing u.

Is this really necessary for the undirected case? Aren't all neighbors of v in the same connected component as v?

comment:22 Changed 10 years ago by sluther

  • Reviewers set to Sebastian Luther

comment:23 Changed 10 years ago by dcoudert

Yes, all neighbors of v are in the same connected component. I have replaced the code with CC = [self.vertex_iterator()].

I did several tests to see if it would be faster to duplicate the code to avoid the test w in CC but then we need to add the test w != u which takes some time as well (although very little) and overall the difference is very small. So I have finally decided not to duplicate the code.

comment:24 Changed 10 years ago by sluther

  • Status changed from needs_review to positive_review

Tests pass, documentation looks good. Positiv review!

comment:25 Changed 10 years ago by dcoudert

Thanks for the review and all the comments. The patch is much better now.

comment:26 Changed 10 years ago by jdemeyer

  • Status changed from positive_review to needs_work

This needs to be rebased to sage-5.3.beta1.

Changed 10 years ago by dcoudert

rebased for sage-5.3.beta1

comment:27 Changed 10 years ago by dcoudert

  • Status changed from needs_work to needs_review

Hello,

I have rebased the patch to sage-5.3.beta1, so it should be easily reviewed.

Best,

comment:28 Changed 10 years ago by jdemeyer

  • Status changed from needs_review to positive_review

For a trivial rebase, you can change the status yourself to positive_review.

comment:29 Changed 10 years ago by dcoudert

I didn't know that. Thank you.

comment:30 Changed 10 years ago by jdemeyer

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