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,,