hlppa

A Java program that implements the highest label preflow-push algorithm for flow networks

This program implements the highest label preflow-push algorithm, a fast solution to the Maximum Flow Problem.
DOWNLOAD

What purpose does this program have? Well, for example you can analyse the Baseball-League, solve scheduling problems or whatever. For further applications see to it that you get your hands on "Network Flows: Theory, Algorithms, and Applications" by Ahuja,Magnati and Orlin


graph file
The actual graph has to be specified as follows:
# comment lines*
n = NumberOfNodes
m = NumberOfEdges
s = NodeIDOfSource
t = NodeIDOfSink
0 : Neighbours of 0
...
n-1 : Neighbours of n-1
With neighbours specified as "TargetNodeIDcCapacityOfEdge"
Compile
compile as follows:
javac Graph.java
Run
java Graph graphFile
With graphFile being the name of the text file you saved your graph in.
Output
The output looks as follows:
flow SOURCE SINK VALUE
0 : used outgoing edges of 0
...
n-1 : used outgoing edges of n-1
with SOURCE the ID of the source node, SINK the ID of the sink node, VALUE the overall value of the flow and outgoing edges specified as "TargetNodeIDfFlowValue"
Example
Example of a small flow network:
# example of a small flow network
n = 4
m = 5
s = 0
t = 3
0 : 1c2 2c2
1 : 2c2 3c2
2 : 3c2
3 :

Which results in...
flow 0 3 4
0 : 1f2 2f2
1 : 3f2
2 : 3f2
3 :
License:
These files belong to the HLPPA-package - a java program that implements
the highest label preflow-push algorithm.
Copyright (C) 2011 Alexander Weinhold

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, version 2 of the License.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.