Ford Fulkerson algorithm does not handle unconnected vertices correctly + unclear error message + lacks tests

[sagetrac-tmonteil]

As reported on 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.

Component: graph theory

Keywords: digraph

Author: David Coudert

Branch/Commit: 0d39e1d

Reviewer: Darij Grinberg

Issue created by migration from https://trac.sagemath.org/ticket/24925

[dcoudert]

Author: David Coudert

[dcoudert]

Commit: 61330f2

[dcoudert]

Branch: u/dcoudert/24925_ford_fulkerson

[dcoudert]

comment:1

The isolated vertices where ignored in the construction of the residual graph. Easy to fix.

---

New commits:

61330f2

trac #24925: add vertices to residual graph

[darijgr]

Changed branch from u/dcoudert/24925_ford_fulkerson to public/ticket/24925

[darijgr]

Changed keywords from none to digraph

[darijgr]

Reviewer: Darij Grinberg

[darijgr]

Changed commit from 61330f2 to 0d39e1d

[darijgr]

comment:2

LGTM, thanks for noticing the bug!

[vbraun]

Changed branch from public/ticket/24925 to 0d39e1d