Opened 2 years ago

Closed 2 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) 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 2 years ago by dcoudert

  • Authors set to David Coudert
  • Branch set to u/dcoudert/24925_ford_fulkerson
  • Commit set to 61330f2295bf134e7fc82b1300dbf06403b47f57
  • Status changed from new to needs_review

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

New commits:

​61330f2trac #24925: add vertices to residual graph

comment:2 Changed 2 years ago by darij

  • 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 2 years ago by darij

  • Status changed from needs_review to positive_review

comment:4 Changed 2 years ago by vbraun

  • 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.