Visit Jeremy's Blog.
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org Graph Orientation:
 User Name Remember Me? Password
 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 Distribution: Ubuntu 14.04 LTS (Trusty Tahr) Posts: 203 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/

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post varun Red Hat 4 12-23-2010 12:17 PM vharishankar LQ Suggestions & Feedback 0 01-09-2007 07:53 AM blotch Linux - Software 4 10-13-2005 02:47 AM chidman Linux - Newbie 8 09-11-2004 11:57 AM themole101687 Linux - Newbie 3 01-17-2004 09:33 PM

LinuxQuestions.org

All times are GMT -5. The time now is 10:49 PM.

 Contact Us - Advertising Info - Rules - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -