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 |
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
Are you new to LinuxQuestions.org? Visit the following links:
Site Howto |
Site FAQ |
Sitemap |
Register Now
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQ-related cookies.
 |
GNU/Linux Basic Guide
This 255-page guide will provide you with the keys to understand the philosophy of free software, teach you how to use and handle it, and give you the tools required to move easily in the world of GNU/Linux. Many users and administrators will be taking their first steps with this GNU/Linux Basic guide and it will show you how to approach and solve the problems you encounter.
Click Here to receive this Complete Guide absolutely free. |
|
 |
04-26-2012, 08:14 PM
|
#1
|
|
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
|
|
Senior Member
Registered: Dec 2010
Location: Finland
Distribution: Xubuntu, CentOS, LFS
Posts: 1,723
|
Ford-Fulkerson or Edmonds-Karp? The latter has example pseudocode in the Wikipedia page.
|
|
|
|
04-26-2012, 09:12 PM
|
#3
|
|
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
|
|
Senior Member
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,009
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
|
|
Senior Member
Registered: Dec 2010
Location: Finland
Distribution: Xubuntu, CentOS, LFS
Posts: 1,723
|
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
|
|
Member
Registered: Feb 2011
Location: San Diego, California (92115), U.S.A.
Distribution: Kubuntu 12.04 - The Precise Pangolin.
Posts: 140
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/
|
|
|
|
| Thread Tools |
Search this Thread |
|
|
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
All times are GMT -5. The time now is 12:53 AM.
|
|
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.
|
Latest Threads
LQ News
|
|