Opened 4 years ago

Closed 2 years ago

#26194 closed defect (duplicate)

Graph.flow() raises a ValueError if the source or sink is isolated

Reported by: Peter Banks Owned by:
Priority: minor Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords: graph, network, flow
Cc: Merged in:
Authors: Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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:

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

The expected value of all of these calls should be 0.

This occurs running SageMath version 8.1 on Ubuntu 18.04.1.

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.

Change History (4)

comment:1 Changed 4 years ago by Peter Banks

Milestone: sage-8.4sage-duplicate/invalid/wontfix

comment:2 Changed 2 years ago by David Coudert

Status: newneeds_review

comment:3 Changed 2 years ago by David Coudert

Reviewers: David Coudert
Status: needs_reviewpositive_review

We can close this ticket.

comment:4 Changed 2 years ago by Frédéric Chapoton

Resolution: duplicate
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.