Message Boards Message Boards

Is FindMaximumFlow function broken?

I ran the example on FindMaximumFlow in the documentation and got the following results.

enter image description here

My guess is that the answer is wrong. Instead of pairing with Billy, Mary can easily connect to Dustin and Alecia can then pair with Billy. When I run the results in Table to get maximum flows value I get 3 or 4. Am I wrong or is there something strange with the FindMaximumFlow function?

POSTED BY: Ali Hashmi

Yep, broken, specifically with vertex capacities (not edge capacities). I have a little notebook with some of these bugs. It's been sent to WRI more than once.

enter image description here

Another bug is that when we request the OptimumFlowData, then certain documented properties cannot be retrieved.

SeedRandom[42]
g = RandomGraph[{10, 20}]
fd = FindMaximumFlow[g, 1, 10, "OptimumFlowData"]

Now fd["FlowTable"] and fd["ResidualGraph"] don't work. Retrieving multiple properties also doesn't work, despite being documented: fd[{"CostValue", "EdgeList"}].

Some of these problems actually show in the documentation notebooks. You can also check online, just open Scope, and you'll see the bugs immediately in the Out[] cells. https://reference.wolfram.com/language/ref/OptimumFlowData.html

enter image description here

enter image description here


There was a recent Twitch stream dealing with Graph stuff, and you can see bug counts mentioned in the meeting notebooks. It sounded as if there were a new drive to eliminate some of these bugs.

POSTED BY: Szabolcs Horvát
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract