Sage: Ticket #26194: Graph.flow() raises a ValueError if the source or sink is isolated
https://trac.sagemath.org/ticket/26194
<p>
When computing the maximal flow of a graph using the Ford-Fulkerson algorithm, Sage throws an exception if the requested source or sink vertices have no edges incident to them with positive capacity:
</p>
<pre class="wiki">G = Graph([range(4), [(1, 2)]], format='vertices_and_edges')
G.flow(0, 1, algorithm='FF') # raises ValueError: vertex '0' is not in the (di)graph
G.flow(1, 3, algorithm='FF') # raises ValueError: vertex '3' is not in the (di)graph
G.flow(0, 1, algorithm='LP') # returns 0 as expected
G.flow(0, 1, algorithm='igraph') # returns 0 as expected
</pre><p>
The expected value of all of these calls should be 0.
</p>
<p>
This occurs running <a class="wiki" href="https://trac.sagemath.org/wiki/SageMath">SageMath</a> version 8.1 on Ubuntu 18.04.1.
</p>
<p>
The cause of this error is the assumption that the residual graph constructed in _ford_fulkerson contains both the source and the sink. Simply checking that this assumption is true (and returning 0 if it is not) should fix the issue.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/26194
Trac 1.1.6pbanksWed, 05 Sep 2018 10:04:56 GMTmilestone changed
https://trac.sagemath.org/ticket/26194#comment:1
https://trac.sagemath.org/ticket/26194#comment:1
<ul>
<li><strong>milestone</strong>
changed from <em>sage-8.4</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
</ul>
<p>
This is a duplicate of <a class="ext-link" href="https://trac.sagemath.org/ticket/24925"><span class="icon"></span>https://trac.sagemath.org/ticket/24925</a>.
</p>
Ticket