0
$\begingroup$

I am modeling a traffic network with a simple edge-weighted graph. The edge weights represent the capacity of each road. I would like to measure the maximum flow the network can accept.

In order to implement any kind of max-flow algorithm, I know part of the trick is changing each undirected weighted edge into a pair of directed edges with identical weights.

My problem is I do not have a specified source or sink for my network. The only thing I can think of is to try every possible pairing of distinct vertices as a source/sink pair, but that leaves me $10^{10}$ pairings to check, which is untenable.

Any other ideas on how to approach this?

$\endgroup$
3
  • $\begingroup$ You seem to be asking about maximum flow on a network when source and sink are unspecified. But if the source and sink were allowed to coincide, the flow to and from that node would not be constrained by edge weights (capacity). So some clarification of your problem is needed in order to propose suitable pruning of any search strategy. $\endgroup$ – hardmath Jan 29 '20 at 21:30
  • $\begingroup$ To your first statement, yes that is exactly what I am asking. To your second statement, I do not want the source and sink to coincide for exactly the reason you said. I thought about approaching this as a circulation problem, but because of the way the directed edges are defined, each vertex will have 0 demand (outbound capacity = inbound capacity). $\endgroup$ – Laars Helenius Jan 29 '20 at 21:39
  • $\begingroup$ The final part of your last comment suggests that you do not have either source or sink ("outbound capacity = inbound capacity" applied to each vertex). Perhaps a simple example, a single edge or a few of them in a cycle, would illustrate what you hope to achieve. $\endgroup$ – hardmath Jan 30 '20 at 15:32
0
$\begingroup$

I am not entirely sure, if I got your problem, but that's what I came up with:

I think you should try Minimum-Mean-Cycle-Cancelling Algorithm on a slightly modified graph:

Set costs to all edges in your network to $c(e)=0$. Add two vertices s,t to your Network. Add edges $(s,v)$ and $(v,t)$ $\forall v \in V(G)$ and $(t,s)$ and set the costs to $c((s,v))=c((v,t))=1$ and $c((t,s))=-3$. Capacity of the added edges should be $\infty$.

The mentioned algorithm searches for cycles in $G_f$ with minimum mean weight as long as there are negative weighted cycles in $G_f$ and augments along them. This is a special case of MIN-COST-FLOW-PROBLEM with $b\equiv 0$. Start the algorithm with $f\equiv 0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.