#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: Nathann Cohen
Authors: Michele Borassi | Work issues:
Report Upstream: N/A | Commit:
Branch: | f0709aa5df62b6c266524099b9b6071b7c860bd0
u/borassi/boost_edge_connectivity | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by borassi):
Hello!
I have checked your code and included it into the current version. I have
made a few modifications:
* I have tried to clarify a bit more the comment at the beginning of
boost_graph.pyx.
* Martin showed me that the Boost edge connectivity code actually tells
that the input graph must be undirected (`Create a network flow graph out
of the undirected graph FlowGraph flow_g(num_vertices(g))`). Hence, I
changed the stopgap sentence to "`The edge connectivity of directed graphs
is not implemented in Boost. The result may be mathematically
unreliable.`" Thank you, Martin!
* I have added some spaces at the bottom of boost_graph.pxd, so that
different graph implementations are aligned.
* Currently, our Boost code does not support edge labels. With the
previous code, if we have used
`"implementation='boost',use_edge_labels=True"` the edge labels would
simply have been ignored without a warning. Now, the algorithm raises an
error.
* If `num_edges()==0` and `vertices=True`, I have modified the output to
return `[0,[],[[],[]]]`, that is `[edge_connectivity, edges, [first set of
vertices, second set of vertices]]`.
Also for me, now the patch is good to go!
--
Ticket URL: <http://trac.sagemath.org/ticket/18564#comment:50>
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.
