LinuxQuestions.org
Did you know LQ has a Linux Hardware Compatibility List?
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
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

Reply
 
Search this Thread
Old 04-26-2012, 08:14 PM   #1
ali2011
Member
 
Registered: Nov 2011
Location: USA, CA
Distribution: Ubuntu+Fedora
Posts: 80

Rep: Reputation: Disabled
Graph Orientation:


Is there any algorithm that can orient undirected graph G(V,E) to achieve maximum flow in the network?
 
Old 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: Reputation: 942Reputation: 942Reputation: 942Reputation: 942Reputation: 942Reputation: 942Reputation: 942Reputation: 942
Ford-Fulkerson or Edmonds-Karp? The latter has example pseudocode in the Wikipedia page.
 
Old 04-26-2012, 09:12 PM   #3
ali2011
Member
 
Registered: Nov 2011
Location: USA, CA
Distribution: Ubuntu+Fedora
Posts: 80

Original Poster
Rep: Reputation: Disabled
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.
 
Old 04-26-2012, 10:31 PM   #4
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Rep: Reputation: Disabled
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.
 
Old 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: Reputation: 942Reputation: 942Reputation: 942Reputation: 942Reputation: 942Reputation: 942Reputation: 942Reputation: 942
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.
 
Old 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: Reputation: 26
Wink

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/
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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


Similar Threads
Thread Thread Starter Forum Replies Last Post
carrier orientation varun Red Hat 4 12-23-2010 12:17 PM
New orientation and thoughts for 2007 vharishankar LQ Suggestions & Feedback 0 01-09-2007 07:53 AM
Scribus and page orientation blotch Linux - Software 4 10-13-2005 02:47 AM
Looking for Orientation Online chidman Linux - Newbie 8 09-11-2004 11:57 AM
n00b orientation please!! themole101687 Linux - Newbie 3 01-17-2004 09:33 PM


All times are GMT -5. The time now is 01:22 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration