Opened 5 years ago
Closed 5 years ago
#24163 closed enhancement (fixed)
blocks_and_cut_vertices() for disconnected graphs
Reported by:  Jori Mäntysalo  Owned by:  

Priority:  minor  Milestone:  sage8.2 
Component:  graph theory  Keywords:  
Cc:  Merged in:  
Authors:  David Coudert  Reviewers:  Jori Mäntysalo 
Report Upstream:  N/A  Work issues:  
Branch:  861ce4c (Commits, GitHub, GitLab)  Commit:  861ce4c302ef5a2ae9b9b0bccd935aa7fb3f3451 
Dependencies:  Stopgaps: 
Description
This patch adds slow but working code to blocks_and_cut_vertices()
handling disconnected graphs. I also change documentation.
Change History (21)
comment:1 Changed 5 years ago by
Branch:  → u/jmantysalo/cutvertexdisconnected 

comment:2 Changed 5 years ago by
Commit:  → 19d03f691662c1d99c7dcd43b56c37dfbfbba27a 

Status:  new → needs_review 
comment:3 followup: 4 Changed 5 years ago by
I pushed in u/dcoudert/24163
a much better solution. There is no need to decompose the graph into connected components.
This said, I run tests on src/sage/graphs/
without error, but we have to check that we are not introducing inconsistency. So we have to check in each method using blocks_and_cut_vertices
that what we do is not changing the behavior. For instance, the blocks_and_cuts_tree
method now returns a forest... We should certainly document that.
comment:4 Changed 5 years ago by
Branch:  u/jmantysalo/cutvertexdisconnected → u/dcoudert/24163 

Commit:  19d03f691662c1d99c7dcd43b56c37dfbfbba27a → 11700e13c5b81d899df0873a7b0efa050321a95e 
comment:5 Changed 5 years ago by
Authors:  Jori Mäntysalo → David Coudert 

comment:6 Changed 5 years ago by
As the main code now handles special cases too, you can remove
if not self: # empty graph return [],[] if len(self) == 1: # only one vertex return [self.vertices()],[]
It seems strange to say
try: # We consider the next of its neighbors w = next(neighbors[v]) . . . # We went through all of v's neighbors except StopIteration: . . .
as you could just use
for w in neighbors[v]: . . . . . .
Otherwise I did not yet read the code.
comment:7 Changed 5 years ago by
Commit:  11700e13c5b81d899df0873a7b0efa050321a95e → 1d972ee64fce5fcb1210d5cabb7527d88d524950 

Branch pushed to git repo; I updated commit sha1. New commits:
1d972ee  trac #24163: remove useless tests

comment:8 followup: 13 Changed 5 years ago by
I have removed the special cases.
The try/except is needed here. The original algorithm do recursive calls. To avoid that, we use stack, plus we use an array (dictionary) of iterators over the neighbors to do the for loop.
comment:9 Changed 5 years ago by
Seems to work, here is my test code:
set_random_seed(0) N = 4 for _ in range(100): gg = [] while len(gg) < N: g = graphs.RandomGNP(randint(2, 20), 0.3) if g.is_biconnected(): gg.append(g) g = Graph() for g_ in gg: g = g+g_ a,b = g.blocks_and_cut_vertices() if sorted(x.order() for x in gg) != sorted(len(x) for x in a): raise AssertionError("Error 1") if b: raise AssertionError("Error 2") g.merge_vertices([x[0] for x in g.connected_components()]) a,b = g.blocks_and_cut_vertices() if len(b) != 1: raise AssertionError("Error 3") if len(a) != N: raise AssertionError("Error 4") if not all(b[0] in x for x in a): raise AssertionError("Error 5") g = Graph() for g_ in gg: g = g+g_ con = g.connected_components() for i in range(N1): g.merge_vertices([con[i][1], con[i+1][0]]) a,b = g.blocks_and_cut_vertices() if len(b) != N1: raise AssertionError("Error 6") if len(a) != N: raise AssertionError("Error 7") print("Seems to work")
comment:10 Changed 5 years ago by
Commit:  1d972ee64fce5fcb1210d5cabb7527d88d524950 → 96f4d04cc2389f8451bbcfc15fa531485cb1e93a 

comment:11 Changed 5 years ago by
I went through all methods using blocks_and_cut_vertices
in graph/
to check that we are not changing behavior.
comment:12 Changed 5 years ago by
Branch:  u/dcoudert/24163 → u/jmantysalo/24163 

comment:13 Changed 5 years ago by
Commit:  96f4d04cc2389f8451bbcfc15fa531485cb1e93a → 861ce4c302ef5a2ae9b9b0bccd935aa7fb3f3451 

Reviewers:  → Jori Mäntysalo 
Replying to dcoudert:
I have removed the special cases.
Good. This addition actually made parts of Sage simpler.
The try/except is needed here. The original algorithm do recursive calls. To avoid that, we use stack, plus we use an array (dictionary) of iterators over the neighbors to do the for loop.
Yeah, that was my bad.
I did a technical merge and will check this one.
New commits:
861ce4c  Merge branch 'develop' into t/24163/24163

comment:14 followup: 15 Changed 5 years ago by
I assume that the technical merge is a rebase on rc0. Thanks.
comment:15 Changed 5 years ago by
Milestone:  sage8.1 → sage8.2 

Status:  needs_review → positive_review 
Replying to dcoudert:
I assume that the technical merge is a rebase on rc0. Thanks.
Just that.
This is good to go, but rc0 is out so I changed the milestone.
comment:17 Changed 5 years ago by
Commit:  861ce4c302ef5a2ae9b9b0bccd935aa7fb3f3451 → af2da9ecae0e0bc856ee7e740986d17b7a9a4b52 

Status:  positive_review → needs_review 
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. This was a forced push. New commits:
c2773a6  Add crossing number.

669bb34  Reformat testsblock.

8de878c  Shortcut for planar graphs.

51fbdba  Another optimization, bug correction etc.

7ed0501  Merge branch 'develop' into crossing_number

af2da9e  Use blocks_and_cut_vertices().

comment:18 Changed 5 years ago by
comment:19 Changed 5 years ago by
Commit:  af2da9ecae0e0bc856ee7e740986d17b7a9a4b52 → 861ce4c302ef5a2ae9b9b0bccd935aa7fb3f3451 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
11700e1  trac #24163: handle non connected graphs

1d972ee  trac #24163: remove useless tests

41b0a05  trac #24163: update tutte_polynomial.py

96f4d04  trac #24163: update documentation of blocks_and_cuts_tree

861ce4c  Merge branch 'develop' into t/24163/24163

comment:20 Changed 5 years ago by
Status:  needs_review → positive_review 

Back to positive, this was automatically put to needs_review after my error.
comment:21 Changed 5 years ago by
Branch:  u/jmantysalo/24163 → 861ce4c302ef5a2ae9b9b0bccd935aa7fb3f3451 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
Blocks of disconnected graph.