Share your knowledge at the LQ Wiki.
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org Graph Orientation:
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

 04-26-2012, 08:14 PM #1 ali2011 Member   Registered: Nov 2011 Location: USA, CA Distribution: Ubuntu+Fedora Posts: 80 Rep: Graph Orientation: Is there any algorithm that can orient undirected graph G(V,E) to achieve maximum flow in the network?
 04-26-2012, 09:05 PM #2 Nominal Animal Senior Member   Registered: Dec 2010 Location: Finland Distribution: Xubuntu, CentOS, LFS Posts: 1,723 Blog Entries: 3 Rep: Ford-Fulkerson or Edmonds-Karp? The latter has example pseudocode in the Wikipedia page.
 04-26-2012, 09:12 PM #3 ali2011 Member   Registered: Nov 2011 Location: USA, CA Distribution: Ubuntu+Fedora Posts: 80 Original Poster Rep: 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.
 04-26-2012, 10:31 PM #4 ta0kira Senior Member   Registered: Sep 2004 Distribution: FreeBSD 9.1, Kubuntu 12.10 Posts: 3,078 Rep: 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 Last edited by ta0kira; 04-26-2012 at 10:42 PM.
 04-26-2012, 10:35 PM #5 Nominal Animal Senior Member   Registered: Dec 2010 Location: Finland Distribution: Xubuntu, CentOS, LFS Posts: 1,723 Blog Entries: 3 Rep: 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. Last edited by Nominal Animal; 04-26-2012 at 10:40 PM.
 04-29-2012, 02:50 PM #6 ejspeiro Member   Registered: Feb 2011 Location: San Diego, California (92115), U.S.A. Distribution: Ubuntu 14.04 LTS (Trusty Tahr) Posts: 201 Rep: 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/