#18564: Boost Edge Connectivity
-------------------------------------+-------------------------------------
Reporter: borassi | Owner: borassi
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.8
Component: graph theory | Resolution:
Keywords: Boost, | Merged in:
connectivity | Reviewers:
Authors: Michele Borassi | Work issues:
Report Upstream: N/A | Commit:
Branch: | 75cdbb6786b2cdce82715a56bcbb6924de317cf4
u/borassi/boost_edge_connectivity | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by borassi):
* status: new => needs_review
Comment:
This code should be a first draft of the final code. I have cleaned the
Boost part and I have inserted the Boost edge connectivity. I have also
cleaned the old edge connectivity, in order to integrate the new part. The
following tests show that the cleaning did not affect speed, and that the
new algorithm is much faster. Still, we might improve two points:
* implement weighted graphs;
* there is a (small) bottleneck when `vertices = True` and Boost is used.
TESTS:
{{{
sage: G = graphs.CompleteGraph(40)
sage: %timeit G.edge_connectivity(boost = False)
1 loops, best of 3: 8.84 s per loop
(OLD: 1 loops, best of 3: 8.78 s per loop)
sage: %timeit G.edge_connectivity(boost = False, vertices = True)
1 loops, best of 3: 8.82 s per loop
(OLD: 1 loops, best of 3: 8.8 s per loop)
sage: %timeit G.edge_connectivity()
1000 loops, best of 3: 445 µs per loop
sage: %timeit G.edge_connectivity(vertices = True)
100 loops, best of 3: 1.57 ms per loop
sage: G = graphs.PathGraph(100)
sage: %timeit G.edge_connectivity(boost = False)
100 loops, best of 3: 2.2 ms per loop
(OLD: 100 loops, best of 3: 2.26 ms per loop)
sage: %timeit G.edge_connectivity(boost = False, value_only = False)
10 loops, best of 3: 59.2 ms per loop
(OLD: 10 loops, best of 3: 58.9 ms per loop)
sage: %timeit G.edge_connectivity(boost = False, vertices = True)
10 loops, best of 3: 59.8 ms per loop
(OLD: 10 loops, best of 3: 58.2 ms per loop)
sage: %timeit G.edge_connectivity()
1000 loops, best of 3: 226 µs per loop
sage: %timeit G.edge_connectivity(vertices = True)
1000 loops, best of 3: 524 µs per loop
}}}
PROBLEMS
Unfortunately, the Boost edge connectivity has a bug when dealing with
directed graphs, evidenced by the following C++ code. What can we do?
Should we open a ticket in Boost graph library?
{{{
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/edge_connectivity.hpp>
using namespace boost;
typedef adjacency_list<vecS,vecS,bidirectionalS> MyGraph;
int main()
{
typedef graph_traits < MyGraph >::vertex_descriptor vertex_descriptor;
typedef graph_traits < MyGraph >::edge_descriptor edge_descriptor;
MyGraph g;
vertex_descriptor v1 = add_vertex(g);
vertex_descriptor v2 = add_vertex(g);
vertex_descriptor v3 = add_vertex(g);
add_edge(v1, v2, g);
add_edge(v2, v3, g);
std::cout << "Number of vertices: " << num_vertices(g) << ".\nNumber
of edges: " << num_edges(g) << ".\n";
std::vector < edge_descriptor > disconnecting_set;
std::cout << "The edge connectivity is "
<< edge_connectivity(g,
std::back_inserter(disconnecting_set))
<< "." << std::endl;
add_edge(v2, v1, g);
std::cout << "Number of vertices: " << num_vertices(g) << ".\nNumber
of edges: " << num_edges(g) << ".\n";
std::cout << "Now, the edge connectivity is "
<< edge_connectivity(g,
std::back_inserter(disconnecting_set))
<< "." << std::endl;
return EXIT_SUCCESS;
}
}}}
Output:
{{{
Number of vertices: 3.
Number of edges: 2.
The edge connectivity is 1.
Number of vertices: 3.
Number of edges: 3.
Now, the edge connectivity is 0.
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/18564#comment:24>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
