Stack Overflow
Stack Overflow

Questions tagged [push-relabel]

10 questions
3
votes
1 answer

Boost max flow algorithms do not compile. error: forming reference to void

Boost provides three different algorithms for finding max flow in directed graphs: boykov_kolmogorov, edmonds_karp and push_relabel. All of them have named and non-named parameter versions. Parameter sets they use are also very similar. Despite…
Nikita Rudenko
  • 55
  • 1
  • 5
2
votes
0 answers

CUDA implemented PUSH RELABEL solves general graph?

I've been trying to find some opensource code, that does Goldberg's push and relabel, or preflow-push , preflow-relabel to solve graph cuts for a GENERAL graph. I know CUDA has the npp GrabCut 2D sample code, and I also know that nppiGraphCut()…
vpakwong
  • 105
  • 5
1
vote
1 answer

In Push Relabel algorithms for max flow why is there not path from source s to sink t?

I have difficulty understanding the following lemma from CLRS: Let G be a flow network, s and t be source and sink nodes, f be a preflow from s to t, and h be a height function on G. Then there is no augmenting path from s to t in the residual…
user494461
1
vote
1 answer

how can I read data from file in boost library

I am using boost library to find maximum flow (push relabel) , and there is a file read_dimacs.hpp read the data but stdin. the problem is my data file is too big and i want to read data file in direct way from file . Can any one help me.the code is…
Haeder ALjoburey
  • 11
  • 4
1
vote
1 answer

How To Convert A Pre-Flow Push Network With Excess Flow To A Flow Network

I implemented first phase of the highest label push relabel algorithm for maximum flow but I could not find any resources about how to implement the second phase, i.e. to convert the preflow push network to a valid flow network.
Corei13
  • 401
  • 2
  • 9
1
vote
1 answer

implementation of push-relabel algorithm

I was learning the push-relabel algorithm from the topcoder site: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxflowPushRelabel I think there is something wrong with the implementation. How can a node push back the excess flow…
sudeepdino008
  • 3,194
  • 5
  • 39
  • 73
1
vote
0 answers

What are restrictions of the MPM algorithm and Push-relabel algorithm for max flow?

I am coding this and need to be aware of the restrictions for these two different algorithms: 1) Capacities have to be integer or not? 2) Graph has to be acyclic or not? Can anyone give some hint? Thanks
Simo
  • 2,292
  • 5
  • 30
  • 45
1
vote
1 answer

Push-relabel gap heuristics

I don't understand how to implement gap heuristics with push relabel. Wiki described it like this: "In gap relabeling heuristic we maintain an array A of size n, holding in A[i] the number of nodes for each label (up to n). If a label d is found,…
vpakwong
  • 105
  • 5
1
vote
0 answers

push relabel algorithm

I have done a MATLAB version of the push-relabel FIFO code (exactly like the one on wikipedia and tried it. The discharge function is exactly like wikipedia. It works perfectly for small graphs (e.g. number of Nodes = 7). However, when I increase my…
vpakwong
  • 105
  • 5
0
votes
1 answer

How to create a graph and call the algorithm with this code

I've been trying to understand this code; it's an implementation of the push-relabel algorithm in C++: // Adjacency list implementation of FIFO push relabel maximum flow // with the gap relabeling heuristic. This implementation is // significantly…
Chiffa
  • 1,486
  • 2
  • 19
  • 38