First time here? Check out the FAQ!

Ask Your Question
1

Flow gives error for disconnected vertices

asked 6 years ago

Acksl gravatar image

updated 2 years ago

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 []
Preview: (hide)

1 Answer

Sort by » oldest newest most voted
2

answered 6 years ago

tmonteil gravatar image

updated 6 years ago

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
Preview: (hide)
link

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: 6 years ago

Seen: 348 times

Last updated: Mar 07 '18