Opened 6 years ago

Closed 5 years ago

#14856 closed defect (fixed)

Bug in GenericGraph.vertex_connectivity when the digraph is a tournament

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.12
Component: graph theory Keywords:
Cc: Merged in: sage-5.12.rc0
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

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

Attachments (1)

trac_14856.patch (5.7 KB) - added by ncohen 5 years ago.

Download all attachments as: .zip

Change History (12)

comment:1 Changed 6 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 5 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 5 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: Changed 5 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: Changed 5 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: Changed 5 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: Changed 5 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 5 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 5 years ago by ncohen

Done. But that's very ugly code.

Nathann

Changed 5 years ago by ncohen

comment:10 Changed 5 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)
sage: G.add_edge(0,0)
sage: %timeit G.vertex_connectivity()
1000 loops, best of 3: 266 us per loop

Install OK, functionality OK, test OK => the patch is good to go.

comment:11 Changed 5 years ago by jdemeyer

  • Merged in set to sage-5.12.rc0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.