Graph Orientation:

ali2011 · 04-26-2012, 08:14 PM

Is there any algorithm that can orient undirected graph G(V,E) to achieve maximum flow in the network?

Nominal Animal · 04-26-2012, 09:05 PM

Ford-Fulkerson or Edmonds-Karp? The latter has example pseudocode in the Wikipedia page.

ali2011 · 04-26-2012, 09:12 PM

The two algorithms you mentioned are working ONLY when you have a ready directed network (i.e., all edges have given directions). In here the only given is the capacity of each edge, but no direction. So, I asked if there is an algorithm that can assign directions that give max-flow to undirected network.

ta0kira · 04-26-2012, 10:31 PM

I don't think the solution will be unique in most useful instances, otherwise I would suggest using a branch-and-bound algorithm. You might just solve the max flow problem with edges in both directions except where that doesn't make sense (e.g. at the source and the sink) with a constraint that one of the edges in each pair must have 0 flow. (edit: Unless your problem includes assigning the source and sink.)
Kevin Barry

Nominal Animal · 04-26-2012, 10:35 PM

And exactly what stops you from defining each undirected edge twice, once in each direction, with the same maximum flow?

Oops, ta0kira posted before I wrote my reply. My thoughts exactly. You probably have to apply the constraint by canceling opposing flows on the same edge, but I cannot see any reason why it should not work reliably.

ejspeiro · 04-29-2012, 02:50 PM

Hello ali2011:

First of all, I would like to ask you about your question. Orientation is a property of the graph which arises from the system which is intended to be modeled. That is why I am asking... are you sure that the problem you are modeling is not already giving you a direction?

Both of the preceding replies are quite valid BUT again ali2011, isn't a directionality pattern being already provided from your problem?

\m/