#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 borassi):
> > * 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.
Well, not so fast! Martin told me that the edge connectivity is a work in
progress, and that they might make it work on directed graph soon.
Furthermore, I still think that the Boost code *has* a bug: the comment I
mentioned is a line comment in the middle of the code, and a user does not
necessarily read the whole code before using it! Furthermore, the comment
does not say explicitly that they do not claim it works. For this reason,
I have added a comment saying this in the Boost ticket, but I think we
should leave the patch as it is, waiting for the final Boost edge
connectivity!
What do you think?
Thank you very much,
Michele
--
Ticket URL: <http://trac.sagemath.org/ticket/18564#comment:53>
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.
