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)
Change History (12)
comment:1 Changed 6 years ago by
- Status changed from new to needs_review
comment:2 Changed 5 years ago by
- Reviewers set to David Coudert
comment:3 Changed 5 years ago by
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 5 years ago by
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 5 years ago by
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 5 years ago by
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 5 years ago by
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
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
Done. But that's very ugly code.
Nathann
Changed 5 years ago by
comment:10 Changed 5 years ago by
- 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
- Merged in set to sage-5.12.rc0
- Resolution set to fixed
- Status changed from positive_review to closed
Hello,
For me the patch is already good to go, but I have a few remarks
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?David.