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: sage-8.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:

Status badges

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 Jori Mäntysalo

Branch: u/jmantysalo/cut-vertex-disconnected

comment:2 Changed 5 years ago by Jori Mäntysalo

Commit: 19d03f691662c1d99c7dcd43b56c37dfbfbba27a
Status: newneeds_review

New commits:

19d03f6Blocks of disconnected graph.

comment:3 Changed 5 years ago by David Coudert

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 in reply to:  3 Changed 5 years ago by Jori Mäntysalo

Branch: u/jmantysalo/cut-vertex-disconnectedu/dcoudert/24163
Commit: 19d03f691662c1d99c7dcd43b56c37dfbfbba27a11700e13c5b81d899df0873a7b0efa050321a95e

Replying to dcoudert:

I pushed in u/dcoudert/24163 a much better solution. There is no need to decompose the graph into connected components.

Let's look at it.


New commits:

11700e1trac #24163: handle non connected graphs

comment:5 Changed 5 years ago by Jori Mäntysalo

Authors: Jori MäntysaloDavid Coudert

comment:6 Changed 5 years ago by Jori Mäntysalo

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 git

Commit: 11700e13c5b81d899df0873a7b0efa050321a95e1d972ee64fce5fcb1210d5cabb7527d88d524950

Branch pushed to git repo; I updated commit sha1. New commits:

1d972eetrac #24163: remove useless tests

comment:8 Changed 5 years ago by David Coudert

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 Jori Mäntysalo

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(N-1):
        g.merge_vertices([con[i][-1], con[i+1][0]])
    a,b = g.blocks_and_cut_vertices()
    if len(b) != N-1:
        raise AssertionError("Error 6")
    if len(a) != N:
        raise AssertionError("Error 7")
    
print("Seems to work")

comment:10 Changed 5 years ago by git

Commit: 1d972ee64fce5fcb1210d5cabb7527d88d52495096f4d04cc2389f8451bbcfc15fa531485cb1e93a

Branch pushed to git repo; I updated commit sha1. New commits:

41b0a05trac #24163: update tutte_polynomial.py
96f4d04trac #24163: update documentation of blocks_and_cuts_tree

comment:11 Changed 5 years ago by David Coudert

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 Jori Mäntysalo

Branch: u/dcoudert/24163u/jmantysalo/24163

comment:13 in reply to:  8 Changed 5 years ago by Jori Mäntysalo

Commit: 96f4d04cc2389f8451bbcfc15fa531485cb1e93a861ce4c302ef5a2ae9b9b0bccd935aa7fb3f3451
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:

861ce4cMerge branch 'develop' into t/24163/24163

comment:14 Changed 5 years ago by David Coudert

I assume that the technical merge is a rebase on rc0. Thanks.

comment:15 in reply to:  14 Changed 5 years ago by Jori Mäntysalo

Milestone: sage-8.1sage-8.2
Status: needs_reviewpositive_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:16 Changed 5 years ago by David Coudert

OK. Thanks. This is useful improvement.

comment:17 Changed 5 years ago by git

Commit: 861ce4c302ef5a2ae9b9b0bccd935aa7fb3f3451af2da9ecae0e0bc856ee7e740986d17b7a9a4b52
Status: positive_reviewneeds_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. This was a forced push. New commits:

c2773a6Add crossing number.
669bb34Reformat tests-block.
8de878cShortcut for planar graphs.
51fbdbaAnother optimization, bug correction etc.
7ed0501Merge branch 'develop' into crossing_number
af2da9eUse blocks_and_cut_vertices().

comment:18 Changed 5 years ago by Jori Mäntysalo

Arghs, wrong ticket number...


New commits:

c2773a6Add crossing number.
669bb34Reformat tests-block.
8de878cShortcut for planar graphs.
51fbdbaAnother optimization, bug correction etc.
7ed0501Merge branch 'develop' into crossing_number
af2da9eUse blocks_and_cut_vertices().

comment:19 Changed 5 years ago by git

Commit: af2da9ecae0e0bc856ee7e740986d17b7a9a4b52861ce4c302ef5a2ae9b9b0bccd935aa7fb3f3451

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

11700e1trac #24163: handle non connected graphs
1d972eetrac #24163: remove useless tests
41b0a05trac #24163: update tutte_polynomial.py
96f4d04trac #24163: update documentation of blocks_and_cuts_tree
861ce4cMerge branch 'develop' into t/24163/24163

comment:20 Changed 5 years ago by Jori Mäntysalo

Status: needs_reviewpositive_review

Back to positive, this was automatically put to needs_review after my error.

comment:21 Changed 5 years ago by Volker Braun

Branch: u/jmantysalo/24163861ce4c302ef5a2ae9b9b0bccd935aa7fb3f3451
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.