#7274: graphs: Maximum flow algorithms
----------------------------+-----------------------------------------------
Reporter: tombuc | Owner: rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.3.1
Component: graph theory | Keywords:
Work_issues: | Author: Tomasz Buchert, Michal Bulant
Upstream: N/A | Reviewer: Robert Miller
Merged: |
----------------------------+-----------------------------------------------
Comment(by ncohen):
As #7592 and #7593 just got reviewed, this patch can not be directly added
to sage : there are now functions Graph.flow and Graph.matching available
in Sage ( well, in the next version.. )
The problem with these functions is that they still depend on GLPK or CBC,
two optional packages that can not be made standard are their licenses are
not compatible, so it would be good to have pure Python equivalent.
Several remarks
* In #7600 and in Graph.coloring, the user can chose which algorithm
he would like to use to solve the problem. Maybe the best way is to copy
this behaviour in the case of flows and matching to have the two
algorithms available.
* It could be very useful to know how these algorithms compare in
terms of performances. This will be much easier to test when flow and
matching will be natively in Sage
* #7634 may not be ready, but time could come soon : with this update
the efficiency of the shortest_path method will be improved, and the speed
of this implementation too.
* Somwhere in the code, I saw a call to
{{{
path = R.shortest_path(source, sink,by_weight=False, bidirectional=False)
}}}
I wondered why you chosed not to use the bidirectional version of
the algorithm, as it is expected to be faster.. :-)
Thank you for your work !!!
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7274#comment:5>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
