Opened 3 years ago
Closed 3 years ago
#24925 closed defect (fixed)
Ford Fulkerson algorithm does not handle unconnected vertices correctly + unclear error message + lacks tests
Reported by: | tmonteil | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.2 |
Component: | graph theory | Keywords: | graph, digraph, linear optimization |
Cc: | Merged in: | ||
Authors: | David Coudert | Reviewers: | Darij Grinberg |
Report Upstream: | N/A | Work issues: | |
Branch: | 0d39e1d (Commits, GitHub, GitLab) | Commit: | 0d39e1d89dfb3b9294a4cb91ed88c5d3cdca0bc8 |
Dependencies: | Stopgaps: |
Description
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.
Change History (4)
comment:1 Changed 3 years ago by
- Branch set to u/dcoudert/24925_ford_fulkerson
- Commit set to 61330f2295bf134e7fc82b1300dbf06403b47f57
- Status changed from new to needs_review
comment:2 Changed 3 years ago by
- Branch changed from u/dcoudert/24925_ford_fulkerson to public/ticket/24925
- Commit changed from 61330f2295bf134e7fc82b1300dbf06403b47f57 to 0d39e1d89dfb3b9294a4cb91ed88c5d3cdca0bc8
- Keywords graph digraph linear optimization added
- Reviewers set to Darij Grinberg
LGTM, thanks for noticing the bug!
comment:3 Changed 3 years ago by
- Status changed from needs_review to positive_review
comment:4 Changed 3 years ago by
- Branch changed from public/ticket/24925 to 0d39e1d89dfb3b9294a4cb91ed88c5d3cdca0bc8
- Resolution set to fixed
- Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
The isolated vertices where ignored in the construction of the residual graph. Easy to fix.
New commits:
trac #24925: add vertices to residual graph