# Ticket #6632(closed defect: fixed)

Opened 4 years ago

## [with patch, positive review] bug in blocks_and_cut_vertices() of a graph that occurs when vertex 0 is a cut vertex

Reported by: Owned by: hartke rlm minor sage-4.1.1 graph theory rlm Robert Miller Stephen Hartke Sage 4.1.1.rc1

### Description

There is a bug in the blocks_and_cut_vertices() function for graphs such that an incorrect result is returned if the vertex 0 is a cut vertex.

```sage: G=Graph()
sage: print G.blocks_and_cut_vertices()
([[0, 1, 2]], [])
```

The bug arises because the algorithm as presented in the referenced book uses 0 to indicate a vertex not in the graph. However, in Sage, we number the vertices of a graph starting at 0.

A patch will be attached below.

## Change History

### Changed 4 years ago by hartke

Patch to fix bug in blocks_and_cut_vertices() in graph.py

### comment:1 Changed 4 years ago by hartke

• Summary changed from Bug in blocks_and_cut_vertices() of a graph that occurs when vertex 0 is a cut vertex to [with patch] bug in blocks_and_cut_vertices() of a graph that occurs when vertex 0 is a cut vertex

### comment:2 Changed 4 years ago by mvngu

• Summary changed from [with patch] bug in blocks_and_cut_vertices() of a graph that occurs when vertex 0 is a cut vertex to [with patch, needs review] bug in blocks_and_cut_vertices() of a graph that occurs when vertex 0 is a cut vertex

Stephen: If you want people to review your patch, you should mark the subject of the ticket with "needs review". That way, the ticket would be picked up by the relevant trac report and people can easily identify those tickets that need review.

### comment:3 follow-up: ↓ 4 Changed 4 years ago by hartke

• Milestone set to sage-4.1.1

Minh: Thanks for fixing the summary! This was my first submitted patch, so I'm trying to learn the ropes.

### comment:4 in reply to: ↑ 3 Changed 4 years ago by mvngu

Minh: Thanks for fixing the summary! This was my first submitted patch, so I'm trying to learn the ropes.

No worries. We all have to start somewhere :-)

### comment:5 Changed 4 years ago by jason

Thanks for looking at this!

How about we trade reviews? I'd like to get #6659 reviewed and in 4.1.1 :).

Could you also just initialize p to [None]*G.num_verts()? Then the check at the bottom becomes p[v] is None.

I'm a little concerned about you taking out the last B.append(S) statement. Can you comment on it? I don't have Jungnickel handy, so forgive me if the answer is easy.

I noticed a few other things with this function, but I'll open up another ticket to address these. For one, it totally ignores the original vertex labeling in the answer. For example, you can't make sense of the following output.

```sage: g=graphs.CubeGraph(2)
sage: g.blocks_and_cut_vertices()
([[2, 3, 1, 0]], [])
sage: g
2-Cube: Graph on 4 vertices
sage: g.vertices()
['00', '01', '10', '11']
```

Second: there seems to be a serious error (in the old implementation too) in the case of a star graph. Look at the cut vertices returned here.

```sage: g=graphs.StarGraph(8)
sage: g.blocks_and_cut_vertices() # current implementation

([[1, 0], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0], [7, 0], [8, 0], [0]],
[0, 0, 0, 0, 0, 0, 0])
```

Your implementation corrects at least one problem: the last [0] is gone (probably as an effect of you taking out that last append() statement, right?):

```sage: g=graphs.StarGraph(8)

([[1, 0], [2, 0], [3, 0], [4, 0], [5, 0], [6, 0], [7, 0], [8, 0]],
[0, 0, 0, 0, 0, 0, 0])
```

### comment:6 Changed 4 years ago by rlm

• Reviewers set to Robert Miller
• Summary changed from [with patch, needs review] bug in blocks_and_cut_vertices() of a graph that occurs when vertex 0 is a cut vertex to [with patch, positive review] bug in blocks_and_cut_vertices() of a graph that occurs when vertex 0 is a cut vertex
• Authors set to Steven Hartke

Apply both patches.

### comment:7 Changed 4 years ago by mvngu

• Status changed from new to closed
• Resolution set to fixed
• Merged in set to Sage 4.1.1.rc1

### comment:8 Changed 4 years ago by hartke

• Authors changed from Steven Hartke to Stephen Hartke
Note: See TracTickets for help on using tickets.