blocks_and_cut_vertices() for disconnected graphs

[jm58660]

This patch adds slow but working code to blocks_and_cut_vertices() handling disconnected graphs. I also change documentation.

Component: graph theory

Author: David Coudert

Branch/Commit: 861ce4c

Reviewer: Jori Mäntysalo

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

[jm58660]

Branch: u/jmantysalo/cut-vertex-disconnected

[jm58660]

New commits:

19d03f6

Blocks of disconnected graph.

[jm58660]

Commit: 19d03f6

[dcoudert]

comment:3

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.

[jm58660]

Changed commit from 19d03f6 to 11700e1

[jm58660]

Changed branch from u/jmantysalo/cut-vertex-disconnected to u/dcoudert/24163

[jm58660]

comment:4

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:

11700e1

trac #24163: handle non connected graphs

[jm58660]

Changed author from Jori Mäntysalo to David Coudert

[jm58660]

comment:6

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.

[sagetrac-git]

Changed commit from 11700e1 to 1d972ee

[sagetrac-git]

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

1d972ee

trac #24163: remove useless tests

[dcoudert]

comment:8

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.

[jm58660]

comment:9

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

[sagetrac-git]

Changed commit from 1d972ee to 96f4d04

[sagetrac-git]

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

41b0a05	trac #24163: update tutte_polynomial.py
96f4d04	trac #24163: update documentation of blocks_and_cuts_tree

[dcoudert]

comment:11

I went through all methods using blocks_and_cut_vertices in graph/ to check that we are not changing behavior.

[jm58660]

Changed branch from u/dcoudert/24163 to u/jmantysalo/24163

[jm58660]

Reviewer: Jori Mäntysalo

[jm58660]

comment:13

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

[jm58660]

Changed commit from 96f4d04 to 861ce4c

[dcoudert]

comment:14

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

[jm58660]

comment:15

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.

[dcoudert]

comment:16

OK. Thanks. This is useful improvement.

[sagetrac-git]

Changed commit from 861ce4c to af2da9e

[sagetrac-git]

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 tests-block.
8de878c	Shortcut for planar graphs.
51fbdba	Another optimization, bug correction etc.
7ed0501	Merge branch 'develop' into crossing_number
af2da9e	Use blocks_and_cut_vertices().

[jm58660]

comment:18

Arghs, wrong ticket number...

---

New commits:

c2773a6	Add crossing number.
669bb34	Reformat tests-block.
8de878c	Shortcut for planar graphs.
51fbdba	Another optimization, bug correction etc.
7ed0501	Merge branch 'develop' into crossing_number
af2da9e	Use blocks_and_cut_vertices().

[sagetrac-git]

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

[sagetrac-git]

Changed commit from af2da9e to 861ce4c

[jm58660]

comment:20

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

[vbraun]

Changed branch from u/jmantysalo/24163 to 861ce4c