Opened 8 years ago

Closed 7 years ago

# Bug in GenericGraph.vertex_connectivity when the digraph is a tournament

Reported by: Owned by: ncohen jason, ncohen, rlm major sage-5.12 graph theory sage-5.12.rc0 Nathann Cohen David Coudert N/A

### Description

The vertex-connectivity of a complete graph on k elements is defined to be equal to k-1. Unfortunately, this special case is also triggered when the input graph is directed, and that is a problem.

Nathann

### comment:1 Changed 8 years ago by ncohen

• Status changed from new to needs_review

### comment:2 Changed 7 years ago by dcoudert

• Reviewers set to David Coudert

Hello,

For me the patch is already good to go, but I have a few remarks

• For directed graphs: can't we say that when `D.allows_loops()==False and D.allows_multiple_edges()==False and D.size()==D.order()*(D.order()-1)` then we can safely return N-1?
• Could you also get rid of the 0.0 and 1.0?

David.

### comment:3 Changed 7 years ago by ncohen

What about this one ? The LP is actually infeasible when the input graph is complete, so it isn't only about optimization after all.

Nathann

### comment:4 follow-up: ↓ 5 Changed 7 years ago by dcoudert

In the test `(g.is_directed() and g.size() >= (g.order()-1*g.order()) and all(g.has_edge(u,v) for u in g for v in g if v != u)))` you should add () around g.order()-1.

Furthermore, you should add the simple test I have proposed because it is way faster for digraphs without loops or multiple edges.

So the test could be:

```( g.is_directed() and g.size()>=(g.order()-1)*g.order() and
( (not g.allows_loops() and not g.allows_multiple_edges())
or all(g.has_edge(u,v) for u in g for v in g if v != u) ) )
```

### comment:5 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 7 years ago by ncohen

Yoooooooooo !!

In the test `(g.is_directed() and g.size() >= (g.order()-1*g.order()) and all(g.has_edge(u,v) for u in g for v in g if v != u)))` you should add () around g.order()-1.

Oops.

Furthermore, you should add the simple test I have proposed because it is way faster for digraphs without loops or multiple edges.

Create a complete digraph, add a loop and compute the vertex connectivity --> an exception is raised by the LP solver. That's why I wrote this version instead.

Nathann

### comment:6 in reply to: ↑ 5 ; follow-up: ↓ 7 Changed 7 years ago by dcoudert

Furthermore, you should add the simple test I have proposed because it is way faster for digraphs without loops or multiple edges.

Create a complete digraph, add a loop and compute the vertex connectivity --> an exception is raised by the LP solver. That's why I wrote this version instead.

Hmmmm.... I think you went too quickly on what I wrote: If you know that the digraph has N*(N-1) arcs and that loops and multiple arcs are forbidden, then you know that the digraph is a clique, isn't it? If loops or multiple edges are allowed, clearly you have to go through all edges.

Adding this simple test could save a lot of time.

### comment:7 in reply to: ↑ 6 ; follow-up: ↓ 8 Changed 7 years ago by ncohen

Hmmmm.... I think you went too quickly on what I wrote:

If the graph is a clique plus a loop, it does not satisfy your condition and gets solved by the LP. Which then raises an exception.

Do you mean that you want me to add both sets of constraints to the list ?

Nathann

### comment:8 in reply to: ↑ 7 Changed 7 years ago by dcoudert

Do you mean that you want me to add both sets of constraints to the list ?

Yes! Testing these two booleans could avoid testing all edges, so it is interesting.

### comment:9 Changed 7 years ago by ncohen

Done. But that's very ugly code.

Nathann

### comment:10 Changed 7 years ago by dcoudert

• Status changed from needs_review to positive_review

I agree this is an ugly test, but it is efficient ;-)

```sage: G = DiGraph(graphs.CompleteGraph(10))
sage: %timeit G.vertex_connectivity()
100000 loops, best of 3: 4.98 us per loop
sage: G.allow_loops(True)