id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
24925 Ford Fulkerson algorithm does not handle unconnected vertices correctly + unclear error message + lacks tests tmonteil "As reported on [https://ask.sagemath.org/question/41419/flow-gives-error-for-disconnected-vertices/ this ask question], the `_ford_fulkerson` method for graphs does not handle unconnected vertices correctly:
{{{
sage: G = Graph({0:[],1:[]})
sage: G.flow(0,1, algorithm='FF')
ValueError: vertex '0' is not in the (di)graph
}}}
To be compared to:
{{{
sage: G.flow(0,1, algorithm='LP')
0.0
sage: G.flow(0,1, algorithm='igraph') # depends on python_igraph
0.0
}}}
Moreover, the error message is misleading since the vertex is here:
{{{
sage: G.vertices()
[0, 1]
}}}
This is because the test is about some `residual` auxiliary graph, not `self`.
Also, this method lacks test, there are much less than the various proposed options.
" defect closed major sage-8.2 graph theory fixed graph, digraph, linear optimization David Coudert Darij Grinberg N/A 0d39e1d89dfb3b9294a4cb91ed88c5d3cdca0bc8 0d39e1d89dfb3b9294a4cb91ed88c5d3cdca0bc8