Is it possible to calculate the maximum flow in undirected graphs?

Hello,

I have constructed an undirected graph G and I want to calculate the maximum flow of it. I tried this:

G = graph(true(5000), 'omitselfloops'); 
p = randperm(numedges(G), 10000);
G = graph(G.Edges(p, :));
G.Edges.Weights = randi([1,200], 10000,1);
mf = maxflow(G,4000,666);

If I choose any (4000, t) node pair, i.e. (1<t<5000), will get the same value, which is "3". I don't know why!

How can I also determine the source and sink nodes in undirected graphs?

Answer 1

[Divyam]

Hi @Rayan Glus,

The graph edges have not been correctly assigned the weights and are hence giving out the same output for maximum flow for every pair of nodes. Here is the correct implementation for calculating the maximum flow for an undirected graph.

% Create a random undirected graph with 5000 nodes and 10000 edges

G = graph(true(5000), 'omitselfloops'); 

% Assign random weights to the edges
G.Edges.Weight = randi([1, 200], numedges(G), 1);

% Choose different source and sink nodes for testing
source = 4000;
sink = randi([1, 4999]);

% Calculate the maximum flow
mf = maxflow(G, source, sink);

% Display the result
fprintf('Maximum flow from node %d to node %d is %d\n', source, sink, mf);

Maximum flow from node 4000 to node 4982 is 502718

To determine the sources and sinks in an undirected graph, the standard definition of sources and sinks which revolve around in-degrees and out-degrees is unusable. You can instead select a threshold percentile for the degrees of the node and declare all nodes above the threshold as sources and sinks. To find the degrees of each node, you can utilize the "degree" function.

For more information regarding the "degree" function, refer to this documentation link: https://www.mathworks.com/help/matlab/ref/graph.degree.html