0

Hello All,

I am trying to solve maximum flow, and I am experiencing some problems formatting the output.

Here is some pseudocode I am trying to implement.

c [u, v] is capacity from u to v, f [u, v] is the flow, cf [u, v] is the residual capacity.
for each edge (u, v) in the graph do:

f [u, v]: = 0; f [v, u]: = 0
cf [u, v]: = c [u, v], cf [v, u]: = c [v, u]
While there is a path p from s to t in residual flow graph do
r: = min (cf [u, v]: (u, v) is included in p)
for each edge (u, v) in p do
f [u, v]: = f [u, v] + r, f [v, u]: = - f [u, v]
cf [u, v]: = c [u, v] - f [u, v], cf [v, u]: = c [v, u] - f [v, u]

Input

The first row contains an integer that specifies the number of vertices in V.
The second line consists of two integers s and t that defines the corners of source and outlet.
The third line consists of a number indicating | E |, ie the number of edges in the graph.
The following | E | rows consisting each of three integers corresponding to an edge.
The corners are numbered from 1 upwards. If you entered a corner of V we let V = {1, 2 ,..., a}. An edge is indicated by the endpoints (only from the corner and then to-corner) followed by its capacity.

For example, a graph, for example, is coded as follows.

4
1:04 a.m.
5
1 2 1
1 2 3
2 4 2
3 2 2
3 4 1

Output

The first row contains an integer that specifies the number of vertices in V.
The second line consists of three integers s, t, and the flow from s to t.
The third row contains an integer that specifies the number of edges with positive flow.
Then assigned a number for each such edge. The edge is described by three numbers in a similar way as the input, but instead of capacity, we now have flow.

Example: If we have the graph above as input, so output can look like this.

4
1 4 3
5
1 2 1
1 2 3
2 4 2
3 2 1
3 4 1

I am having problems formatting input. Can someone help?

2
Contributors
1
Reply
3
Views
6 Years
Discussion Span
Last Post by daviddoria
1

MylesDBaker,

Is this for a course (where they have made you write your own graph class, etc)? Or because you actually need to use a maxflow algorithm? If it is the later, I would like to suggest that you use an existing graph library (I use vtkGraph from VTK (vtk.org) ). Unfortunately it does not have a maxflow function already, but I've been meaning to write one for a long time, so I'd like to recruit your help!

I have started the infrastructure here:
https://github.com/daviddoria/vtkGraphCut

(which algorithm do you plan to implement?)

If you are interested, please let me know and I'll get you some instructions to compile VTK etc and show you the basics (most of which can be found here: http://www.vtk.org/Wiki/VTK/Examples/Cxx#Graphs )

Thanks,

David

Votes + Comments
Awesome!
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.