Styjun

1, 2, 4, 8, 16, ... 33?

What are these pixel-level discolored specks? How can I fix it?

Can the U.S. president make military decisions without consulting anyone?

Is it a good idea to leave minor world details to the reader's imagination?

Going to France with limited French for a day

Is It Possible to Have Different Sea Levels, Eventually Causing New Landforms to Appear?

How to conditionally load a package only if shell-escape (write18) is passed

Which museums have artworks of all four Ninja Turtles' namesakes?

Plugging in laptop to charger increases ping and reduces download speeds

How do I deal with too many NPCs in my campaign?

Sparse columns, cpu time & filtered indexes

Hilbert's hotel, why can't I repeat it infinitely many times?

Do the villains know Batman has no superpowers?

How use custom order in folder on Windows 7 and 10

What can a pilot do if an air traffic controller is incapacitated?

Guitar tuning (EADGBE), "perfect" fourths?

How to make interviewee comfortable interviewing in lounge chairs

Can this word order be rearranged?

Why does NASA publish all the results/data it gets?

Worms crawling under skin

Are there non JavaScript ways to hide HTML source code?

Why is there not an optimal solution for a MIP?

How much damage can be done just by heating matter?

Subtle meanings of the noun 'stole', or am I reading too much in to it?

Finding any feasible flow in graph as fast as possible

Python progression path - From apprentice to guruCan Goldberg algorithm in ocamlgraph be used to find Minimum Cost Flow graph?Peak detection in a 2D arrayFast max-flow min-cut library for PythonMaximum Flow in Dynamic graphsAll pair Maximum FlowFinding edge connectivity of a network by using Maximum Flow algorithmWhat algorithm should I use to find the minimum flow on a digraph where there are lower bounds but not upper bounds on flow?Fast Maximum Matching Algorithm for Bipartite GraphsFind a path from Source to Target in residual graph of a Network flow graph in O(E) time

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

1

2

I have a flow graph with lower and upper bounds and my task is to find any feasible solution as fast as possible. I found many algorithms and approaches to maximum/minimum flow and so on (also many times uses feasible solution as start point) but nothing specific for any feasible solution. Is there any algorithm/approach that is specific for it and fast?

python graph network-flow

share|improve this question

asked Mar 28 at 15:05

eXPRESSeXPRESS

1021111 bronze badges

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Why is this tagged Python?
  
  – Davis Herring
  Mar 28 at 19:05
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  The task is in python so I thought that if anybody would want to illustrate some pseudo solution in code and was choosing between languages... Should I remove it?
  
  – eXPRESS
  Mar 29 at 11:27
  

  
  
  
  

add a comment
 | 

1

2

I have a flow graph with lower and upper bounds and my task is to find any feasible solution as fast as possible. I found many algorithms and approaches to maximum/minimum flow and so on (also many times uses feasible solution as start point) but nothing specific for any feasible solution. Is there any algorithm/approach that is specific for it and fast?

python graph network-flow

share|improve this question

asked Mar 28 at 15:05

eXPRESSeXPRESS

1021111 bronze badges

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Why is this tagged Python?
  
  – Davis Herring
  Mar 28 at 19:05
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  The task is in python so I thought that if anybody would want to illustrate some pseudo solution in code and was choosing between languages... Should I remove it?
  
  – eXPRESS
  Mar 29 at 11:27
  

  
  
  
  

add a comment
 | 

I have a flow graph with lower and upper bounds and my task is to find any feasible solution as fast as possible. I found many algorithms and approaches to maximum/minimum flow and so on (also many times uses feasible solution as start point) but nothing specific for any feasible solution. Is there any algorithm/approach that is specific for it and fast?

python graph network-flow

share|improve this question

asked Mar 28 at 15:05

eXPRESSeXPRESS

1021111 bronze badges

share|improve this question

asked Mar 28 at 15:05

eXPRESSeXPRESS

1021111 bronze badges

share|improve this question

asked Mar 28 at 15:05

eXPRESSeXPRESS

1021111 bronze badges

asked Mar 28 at 15:05

eXPRESSeXPRESS

1021111 bronze badges

asked Mar 28 at 15:05

eXPRESSeXPRESS

1021111 bronze badges

1 Answer
1

active

oldest

votes

0

So I finally got time to sum this up. The solution I used is to take the initial graph and transform it in these steps.

(Weights are in this order: lower bound, current flow, upper bound.)

1. Connect t to s by edge of (0, 0, infinity).

2. To each node of the
initial graph add balance value equal to: (sum of lower bound of
incoming edges - sum of lower bound of outgoing edges).

3. Set upper
bound of every edge to (upper bound - lower bound). Set lower bound
and current flow of each edge to 0.

4. Now make new s (s') and new t (t') which will be our new start and end (DO NOT DELETE s and t already in the graph, they just became
normal nodes).

5. Create edge from s' to every vertex with positive balance with (0,
0, vertex.balance) bounds.

6. Create edge from every vertex with negative balance to t' with (0,
0, abs(vertex.balance)).

7. Run Ford-Fulkerson (or other maximum flow algorithm of your choice)
on the new graph.

8. For every edge of initial graph sum value of the
edge with the initial old lower bound before transformation and you have your
initial flows for every edge of the initial graph.

This problem is actually a bit harder than to maximize flow when feasible flow is provided.

share|improve this answer

edited Apr 7 at 11:03

answered Apr 7 at 8:30

eXPRESSeXPRESS

1021111 bronze badges

add a comment
 | 

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55400911%2ffinding-any-feasible-flow-in-graph-as-fast-as-possible%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

So I finally got time to sum this up. The solution I used is to take the initial graph and transform it in these steps.

(Weights are in this order: lower bound, current flow, upper bound.)

1. Connect t to s by edge of (0, 0, infinity).

2. To each node of the
initial graph add balance value equal to: (sum of lower bound of
incoming edges - sum of lower bound of outgoing edges).

3. Set upper
bound of every edge to (upper bound - lower bound). Set lower bound
and current flow of each edge to 0.

4. Now make new s (s') and new t (t') which will be our new start and end (DO NOT DELETE s and t already in the graph, they just became
normal nodes).

5. Create edge from s' to every vertex with positive balance with (0,
0, vertex.balance) bounds.

6. Create edge from every vertex with negative balance to t' with (0,
0, abs(vertex.balance)).

7. Run Ford-Fulkerson (or other maximum flow algorithm of your choice)
on the new graph.

8. For every edge of initial graph sum value of the
edge with the initial old lower bound before transformation and you have your
initial flows for every edge of the initial graph.

This problem is actually a bit harder than to maximize flow when feasible flow is provided.

share|improve this answer

edited Apr 7 at 11:03

answered Apr 7 at 8:30

eXPRESSeXPRESS

1021111 bronze badges

add a comment
 | 

0

So I finally got time to sum this up. The solution I used is to take the initial graph and transform it in these steps.

(Weights are in this order: lower bound, current flow, upper bound.)

1. Connect t to s by edge of (0, 0, infinity).

2. To each node of the
initial graph add balance value equal to: (sum of lower bound of
incoming edges - sum of lower bound of outgoing edges).

3. Set upper
bound of every edge to (upper bound - lower bound). Set lower bound
and current flow of each edge to 0.

4. Now make new s (s') and new t (t') which will be our new start and end (DO NOT DELETE s and t already in the graph, they just became
normal nodes).

5. Create edge from s' to every vertex with positive balance with (0,
0, vertex.balance) bounds.

6. Create edge from every vertex with negative balance to t' with (0,
0, abs(vertex.balance)).

7. Run Ford-Fulkerson (or other maximum flow algorithm of your choice)
on the new graph.

8. For every edge of initial graph sum value of the
edge with the initial old lower bound before transformation and you have your
initial flows for every edge of the initial graph.

This problem is actually a bit harder than to maximize flow when feasible flow is provided.

share|improve this answer

edited Apr 7 at 11:03

answered Apr 7 at 8:30

eXPRESSeXPRESS

1021111 bronze badges

add a comment
 | 

So I finally got time to sum this up. The solution I used is to take the initial graph and transform it in these steps.

(Weights are in this order: lower bound, current flow, upper bound.)

1. Connect t to s by edge of (0, 0, infinity).

2. To each node of the
initial graph add balance value equal to: (sum of lower bound of
incoming edges - sum of lower bound of outgoing edges).

3. Set upper
bound of every edge to (upper bound - lower bound). Set lower bound
and current flow of each edge to 0.

4. Now make new s (s') and new t (t') which will be our new start and end (DO NOT DELETE s and t already in the graph, they just became
normal nodes).

5. Create edge from s' to every vertex with positive balance with (0,
0, vertex.balance) bounds.

6. Create edge from every vertex with negative balance to t' with (0,
0, abs(vertex.balance)).

7. Run Ford-Fulkerson (or other maximum flow algorithm of your choice)
on the new graph.

8. For every edge of initial graph sum value of the
edge with the initial old lower bound before transformation and you have your
initial flows for every edge of the initial graph.

This problem is actually a bit harder than to maximize flow when feasible flow is provided.

share|improve this answer

edited Apr 7 at 11:03

answered Apr 7 at 8:30

eXPRESSeXPRESS

1021111 bronze badges

share|improve this answer

edited Apr 7 at 11:03

answered Apr 7 at 8:30

eXPRESSeXPRESS

1021111 bronze badges

answered Apr 7 at 8:30

eXPRESSeXPRESS

1021111 bronze badges

answered Apr 7 at 8:30

eXPRESSeXPRESS

1021111 bronze badges