1
$\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
    Commented Jan 29, 2020 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$ Commented Jan 29, 2020 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
    Commented Jan 30, 2020 at 15:32

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .