Opened 3 years ago
Closed 7 months ago
#26194 closed defect (duplicate)
Graph.flow() raises a ValueError if the source or sink is isolated
Reported by: | pbanks | 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: |
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 3 years ago by
- Milestone changed from sage-8.4 to sage-duplicate/invalid/wontfix
comment:2 Changed 7 months ago by
- Status changed from new to needs_review
comment:3 Changed 7 months ago by
- Reviewers set to David Coudert
- Status changed from needs_review to positive_review
We can close this ticket.
comment:4 Changed 7 months ago by
- Resolution set to duplicate
- Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
This is a duplicate of https://trac.sagemath.org/ticket/24925.