Ask Your Question
1

Flow gives error for disconnected vertices

asked 2018-03-07 06:21:06 -0500

Acksl gravatar image

updated 2018-03-07 09:35:47 -0500

tmonteil gravatar image

When calculating the flow between to vertices which are not connected in a graph, the method returns a ValueError. I would have assumed that it would just return 0. Here's a minimal example:

G=Graph({0:[],1:[]})
G.flow(0,1) # raises the error ValueError: vertex '0' is not in the (di)graph

If on the other hand one tries the shortest_path method it just returns a empty list, since there is not path between 0 and 1.

G.shortest_path(0,1) #returns []
edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
2

answered 2018-03-07 09:34:33 -0500

tmonteil gravatar image

updated 2018-03-07 09:35:32 -0500

Thanks for reporting, this is now trac ticket 24925. As you can see on the explanations on the ticket, the implementation of Ford Fulkerson algorithm does not handle unconnected vertices correctly.

The possible workarounds are:

  • use the 'LP' algorithm:

    sage: G.flow(0,1, algorithm='LP')
    0.0
    
  • install python_igraph so that Sage will use it by default:

    from a shell:

    sage -i python_igraph
    

    then within Sage:

    sage: G.flow(0,1)
    0.0
    
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-03-07 06:21:06 -0500

Seen: 46 times

Last updated: Mar 07