Sage: Ticket #7854: speed up edge_connectivity in easy cases
https://trac.sagemath.org/ticket/7854
<p>
This functions uses LP and has a big overhead because of that... Is many cases, though, the graph is not connected, or not 2-connected.
</p>
<p>
To test if a graph is connected, we already have the function is_connected which does the job very efficiently through depth-first-searches.
</p>
<p>
We also have a function is_strongly_connected for <a class="missing wiki">DiGraphs?</a>.
</p>
<p>
To test if a Graph is 2-connected, we can first :
</p>
<ul><li> compute a strongly_connected_orientation with a linear-time function
</li><li> check whether the returned graph is strongly-connected ( linear time too )
</li></ul><p>
Without this, much time is spent over building a useless Linear Program.
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/7854
Trac 1.1.6ncohenSat, 16 Jan 2010 16:59:51 GMTstatus changed
https://trac.sagemath.org/ticket/7854#comment:1
https://trac.sagemath.org/ticket/7854#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
Small modifications, good results :
Before :
</p>
<pre class="wiki">sage: %timeit graphs.WorldMap().edge_connectivity()
10 loops, best of 3: 200 ms per loop
</pre><p>
After :
</p>
<pre class="wiki">sage: %timeit graphs.WorldMap().edge_connectivity()
100 loops, best of 3: 4.75 ms per loop
</pre>
TicketzimmermaThu, 25 Feb 2010 22:23:58 GMTstatus changed
https://trac.sagemath.org/ticket/7854#comment:2
https://trac.sagemath.org/ticket/7854#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
Nathann, I tried before the patch but got:
</p>
<pre class="wiki">sage: %timeit graphs.WorldMap().edge_connectivity()
...
ValueError: There does not seem to be any Linear Program solver installed. Please visit http://www.sagemath.org/packages/optional/ to install CBC or GLPK.
</pre><p>
Which LP package did you use? CBC or GLPK? Did you check you got a speedup with both?
</p>
TicketncohenFri, 26 Feb 2010 06:57:31 GMTstatus changed
https://trac.sagemath.org/ticket/7854#comment:3
https://trac.sagemath.org/ticket/7854#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Hello !!!!
</p>
<p>
Actually, the patch works with any LP solver which is installed.
What you get is is a totally unrelated "bug". After installing the package corresponding to a LP solver, the user has to run "sage -b" but has no way to know about it for the moment. There is an update of GLPK waiting for review (<a class="closed ticket" href="https://trac.sagemath.org/ticket/8298" title="enhancement: GLPK 4.42 + error message (closed: fixed)">#8298</a>) and Cbc will follow (<a class="closed ticket" href="https://trac.sagemath.org/ticket/8171" title="enhancement: New Cbc spkg with Cplex support (closed: fixed)">#8171</a>). Sorry for the trouble !
</p>
<p>
This patch just avoids the use of LP when it is possible -- when the graph isn't connected, or not 2-connected. The functions used are written in Cython, which makes them almost instantaneous to use. Actually, checking the connectivity for low values this way is even faster than just generating the linear program, so it definitely is good to have :-)
</p>
<p>
Nathann
</p>
TicketzimmermaFri, 26 Feb 2010 08:58:51 GMTstatus changed
https://trac.sagemath.org/ticket/7854#comment:4
https://trac.sagemath.org/ticket/7854#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
thanks Nathann for your answer.
I successfully installed the cbc package from <a href="http://www.sagemath.org/packages/optional/">http://www.sagemath.org/packages/optional/</a> in 4.3.3
(btw, there are several compiler warnings during compilation, on a 64-bit Core 2 Duo).
*Before* applying your patch, I get:
</p>
<pre class="wiki">sage: g = 2 * graphs.PetersenGraph()
sage: g.edge_connectivity()
0.0
sage: g = graphs.PathGraph(10)
sage: g.edge_connectivity()
1.0
sage: g = digraphs.ButterflyGraph(3)
sage: g.edge_connectivity()
0.0
sage: g = 2 * graphs.PetersenGraph()
sage: g.vertex_connectivity()
0.0
sage: g = graphs.PathGraph(10)
sage: g.vertex_connectivity()
1.0
sage: g = digraphs.ButterflyGraph(3)
sage: g.vertex_connectivity()
0.0
</pre><p>
thus it seems to me some work is needed, because according to the patch documentation, after
applying the patch I will get integer values instead of floating-point numbers, which may break
some code using those functions.
</p>
<p>
Paul
</p>
TicketncohenFri, 26 Feb 2010 10:27:01 GMTstatus changed
https://trac.sagemath.org/ticket/7854#comment:5
https://trac.sagemath.org/ticket/7854#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Hello !!
</p>
<p>
It was even worse than this... The patch made Sage check manually if the graph was 1- or 2-connected, even if the user requested the weights on the edges to be taken into account, which would clearly have returned wrong results at some point, as the speedup only considered the graph's topology. It now checks this option is set to False. I also set it to False by default, so that the user will be able to enjoy these speed-ups. Anyway, I think it is best not to use the edges' weights by default. I very frequently deal with graph having tuples as labels to remember a lot of informations, and this function wouldn't like it at all :-)
</p>
<p>
(several minutes later)
</p>
<p>
Ahem... And I also noticed a bug that had me worried for a while. When testing docstrings, I found that the <a class="missing wiki">PappusGraph?</a> was only 1-connected instead of 3-connected, and the LP seemed to be in fault. In the end, I just noticed I had called "g" the strongly connected orientation, which was the main graph's name !!!!!
</p>
<p>
Better this way... ;-)
</p>
<p>
Thank you for your help !
</p>
<p>
Nathann
</p>
TicketncohenFri, 26 Feb 2010 10:27:19 GMTattachment set
https://trac.sagemath.org/ticket/7854
https://trac.sagemath.org/ticket/7854
<ul>
<li><strong>attachment</strong>
set to <em>trac_7854.patch</em>
</li>
</ul>
TicketzimmermaSat, 27 Feb 2010 22:23:11 GMTstatus changed; reviewer, author set
https://trac.sagemath.org/ticket/7854#comment:6
https://trac.sagemath.org/ticket/7854#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Paul Zimmermann</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
Now the patch gives floating-point values as before.
However I wonder why those values are floating-point numbers and not integers, since for example
the connectivity is an integer according to the reference wikipedia page.
</p>
<p>
(This might be solved in a further ticket, thus I give a positive review for the present one.)
</p>
TicketncohenSun, 28 Feb 2010 01:06:14 GMT
https://trac.sagemath.org/ticket/7854#comment:7
https://trac.sagemath.org/ticket/7854#comment:7
<p>
The reason is that this function handles weighted edges, and those edges may be weighted with floating-point values :-)
</p>
<p>
I am myself only interested by "topological" connectivity, in which all edges are weighted with 1, but I do not really mind as long as connectivity() == k works...
</p>
<p>
Thank you very much for your help !!!
</p>
<p>
Nathann
</p>
TicketmvnguWed, 03 Mar 2010 14:18:55 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/7854#comment:8
https://trac.sagemath.org/ticket/7854#comment:8
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.3.4.alpha0</em>
</li>
</ul>
Ticket