Algorithm underlying the max flow min cost method

[Lygeri Sakellaridi]

Hello!

I have a network in mind I'd like to apply the max flow min cost method on. I haven't constructed the network yet but I estimate it will have about 12000 vertices and 300000 edges. 

I'd like to know what the algorithm is behind the implementation of the max_flow_min_cost method (eg is it some version of push-relabel, or something else?) and what the complexity is in terms of number of edges and vertices. That way I know if it will be feasible for my network.

[Dan Schult]

The Complexity of the algorithm doesn’t tell you anything about how long your example is — it just tells you how the complexity changes as you increase the size of your problem.  Much better just to try an example close to your example and see how long it takes.

n=12000

p=300000/(n*n)

G=nx.binomial_graph(n,p,seed=9)

G.add_edges_from([(u,v,{"capacity":0.9, "weight": 4}) for u,v in G.edges])

nx.max_flow_min_cost(G,0,1)

Took about 3 seconds for me.  

The function takes an input parameter function that determines what algorithm is used. Hope this helps even though it doesn’t answer your exact question.

[lygeri.sakellaridi]

Hi Dan, thanks for the answer. When I look at the documetation of max cost min flow, I don't see the parameter you mentioned that determines the algorithm. Could you point me to it?

I am looking at this: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.flow.max_flow_min_cost.html#networkx.algorithms.flow.max_flow_min_cost According to this, the parameters that can be set are G, s, t, capacity and weight.

--
You received this message because you are subscribed to a topic in the Google Groups "networkx-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/networkx-discuss/HMjsLgi0zJ0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to networkx-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CA%2BXMcTOSbvM4oNpcxOm5T0ddx0reo6m8McBcSfR7Xfdzqjz0iQ%40mail.gmail.com.

[Dan Schult]

Oop... sorry about that.  The "source" option at the signature line of the docs you point to shows that `max_flow_min_cost` basically wraps a call to `max_flow_value` followed by a call to `min_cost`.  The max_flow_value function takes a parameter `flow_func` which is the heart of the algorithm based on my limited understanding.

Some choices are:

default_flow_func = preflow_push
# Functions that don't support cutoff for minimum cut computations.
flow_funcs = [
    boykov_kolmogorov,
    dinitz,
    edmonds_karp,
    preflow_push,
    shortest_augmenting_path]

You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CAJEuJ8qCKJPkGLg_-07%2BoFp1HEK5BpB_v8j5iNNBBPv6RQBF1Q%40mail.gmail.com.