#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: | fe55f76ef07c3d38b52f7b361a7a9a6fd512be9f
u/borassi/boost_edge_connectivity | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by ncohen):
Hello Michele,
> * I have tried to clarify a bit more the comment at the beginning of
boost_graph.pyx.
Thanks! That's better.
> * 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!
Oh. Does that mean that there is "no bug" in boost because they never
claimed that it worked? If so, several things need to be done:
1) Close the bug report on boost's trac, as it is invalid
2) Change the milestone of our 'stopgap' ticket #18753 to invalid/wontfix
(and status to positive review)
3) Remove the stopgap warning from this branch's code
4) Remove any claim that boost's algorithm is unreliable for directed
graphs, and claim instead that it is only avilable for undirected graphs
5) Raise an exception when 'boost' is requested to run on a directed
graph.
> * 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.
Good. I missed that `:-/`
> * 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]]`.
OKayyyyyyyyyyy.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/18564#comment:52>
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.
