Determine if a vertex is a cut vertex

[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.

CC: @sagetrac-lkeough

Component: graph theory

Author: David Coudert

Reviewer: Sebastian Luther

Merged: sage-5.4.rc0

Issue created by migration from https://trac.sagemath.org/ticket/13289

[dcoudert]

comment:1

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.

[sagetrac-lkeough]

comment:3

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?

[dcoudert]

comment:4

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.

[sagetrac-lkeough]

comment:5

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.

[dcoudert]

comment:6

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

[dcoudert]

comment:8

Thanks for the review !

[jdemeyer]

comment:9

Please fill in your real name as Reviewer.

[sagetrac-sluther]

comment:10

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.

[dcoudert]

comment:11

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.

[dcoudert]

comment:12

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

[sagetrac-sluther]

comment:13

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.

[dcoudert]

comment:14

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.

[sagetrac-sluther]

comment:15

Nice work!

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()

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.

[dcoudert]

comment:16

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.

[dcoudert]

comment:17

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.

[sagetrac-sluther]

comment:18

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.

[sagetrac-sluther]

comment:19

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.

[dcoudert]

comment:20

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.

[sagetrac-sluther]

comment:21

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?

[sagetrac-sluther]

Reviewer: Sebastian Luther

[dcoudert]

comment:23

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.

[sagetrac-sluther]

comment:24

Tests pass, documentation looks good. Positiv review!

[dcoudert]

comment:25

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

[jdemeyer]

comment:26

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

[dcoudert]

Attachment: trac_13289_is_cut_vertex.patch.gz

rebased for sage-5.3.beta1

[dcoudert]

comment:27

Hello,

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

Best,

[jdemeyer]

comment:28

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

[dcoudert]

comment:29

I didn't know that.
Thank you.

[jdemeyer]

Merged: sage-5.4.rc0