HLPPA - Highest-Label Preflow Push Algorithm

The Highest-Label Preflow Push Algorithm (HLPPA) computes a maximum flow on a graph in time O(|V|² |E|^1/2). This implementation is written in C. I tried to optimize the program for very high speeds. I programmed this for the lecture 'Fundamental Algorithms' at the university of paderborn.

The program reads a file with the graph information and prints to stdout the information about the flow.

Download

Input Specification

[<COMMENT>]*
n = <NUMBER_OF_NODES>
m = <NUMBER_OF_EDGES>
s = <SOURCE_NODES>
t = <TARGET_NODE>
<NODE> :[ <EDGE_TARGET>c<CAPACITY>]*
...

There can be multiple comment-lines at the beginning of the file. n,m,s and t have to be integers. The node ids have to be from the interval [0, n-1].

Output Specification

flow <SOURCE_NODE> <TARGET_NODE> <FLOW>
<NODE> :[ <EDGE_TARGET>f<FLOW>]*
...

License

//    Highest-Label Preflow-Push Algorithm calculates the maximal flow
//    Copyright (C) 2011 Markus Pargmann <mpargman_AT_mail.upb.de>
//
//    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, either version 3 of the License, or
//    (at your option) any later version.
//
//    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/>.