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/>.