ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 07 Mar 2018 09:34:33 -0600Flow gives error for disconnected verticeshttp://ask.sagemath.org/question/41419/flow-gives-error-for-disconnected-vertices/ When calculating the flow between to vertices which are not connected in a graph, the method returns a ValueError. I would have assumed that it would just return 0. Here's a minimal example:
G=Graph({0:[],1:[]})
G.flow(0,1) # raises the error ValueError: vertex '0' is not in the (di)graph
If on the other hand one tries the shortest_path method it just returns a empty list, since there is not path between 0 and 1.
G.shortest_path(0,1) #returns []Wed, 07 Mar 2018 06:21:06 -0600http://ask.sagemath.org/question/41419/flow-gives-error-for-disconnected-vertices/Answer by tmonteil for <p>When calculating the flow between to vertices which are not connected in a graph, the method returns a ValueError. I would have assumed that it would just return 0. Here's a minimal example:</p>
<pre><code>G=Graph({0:[],1:[]})
G.flow(0,1) # raises the error ValueError: vertex '0' is not in the (di)graph
</code></pre>
<p>If on the other hand one tries the shortest_path method it just returns a empty list, since there is not path between 0 and 1.</p>
<pre><code>G.shortest_path(0,1) #returns []
</code></pre>
http://ask.sagemath.org/question/41419/flow-gives-error-for-disconnected-vertices/?answer=41422#post-id-41422Thanks for reporting, this is now [trac ticket 24925](https://trac.sagemath.org/ticket/24925). As you can see on the explanations on the ticket, the implementation of Ford Fulkerson algorithm does not handle unconnected vertices correctly.
The possible workarounds are:
- use the 'LP' algorithm:
sage: G.flow(0,1, algorithm='LP')
0.0
- install `python_igraph` so that Sage will use it by default:
from a shell:
sage -i python_igraph
then within Sage:
sage: G.flow(0,1)
0.0Wed, 07 Mar 2018 09:34:33 -0600http://ask.sagemath.org/question/41419/flow-gives-error-for-disconnected-vertices/?answer=41422#post-id-41422