This program implements the highest label preflow-push algorithm, a fast solution to the Maximum Flow Problem.
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-1With neighbours specified as "TargetNodeIDcCapacityOfEdge"
compile as follows:
java Graph graphFileWith graphFile being the name of the text file you saved your graph in.
The output looks as follows:
flow SOURCE SINK VALUE 0 : used outgoing edges of 0 ... n-1 : used outgoing edges of n-1with 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 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 :
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/>.