Workshop In Algorithms And Data Structures
2009-2010, Semester A

Maximum Flow Algorithms

Course	0368-3500-01 Workshop In Computer Science
Meeting Time And Place (first few classes only!)	Sunday, 11:00-13:00. Kaplun Building, Room 324.
Lecturer	Professor Haim Kaplan
Lecturer Email	haimk@cs.tau.ac.il
Teaching Assistant	Sagi Hed
Teaching Assistant Email	sagihed@post.tau.ac.il

Announcements

24/12/09 22:30 Postponed the specification document deadline.
16/10/09 11:00 Workshop web page is up.

Overview

For many years there has been much research on different algorithms for the maximum flow problem and their performance in practice. While some algorithmic combinations show better theoretical upper bounds, others prove to be much better in practice.

Each group will select a maximum flow algorithm/s such as dinic, push-relabel or boykov-kolmogorov, and implement the algorithm you have chosen from scratch, as efficiently as you can (you are not allowed to use existing code found on the web or elsewhere). You may implement any known version of your chosen algorithm and/or come up with implementation ideas of your own. You are provided with various inputs from various applications (see below), and you have to measure the performance of your implementation on these inputs. You are also provided with public implementations of the algorithms, and you must compare your run the same measurements on the public code and compare the results.

Part of the goal is to make your implementation as fast as you can (within the bounderies of the chosen programming language and the chosen algorithm). Your running times will be compared with runing times of other implementations of your algorithm, including the public versions of your algorithm and versions from other groups, and this will have some weight on the final grade.

Specification Document

By a chosen deadline (see below), each group will submit a specification document explaining its choices and future plan for the workshop (see below for details).
There will be a meeting held with each group to review the document and the plan, and to make sure everything is on track.

Technical Information

Submission is in pairs.
Only the first few classes will be held, giving background and technical information concerning the workshop.
After that, work is independent. You are welcome to contact the teaching assistant (sagihed@post.tau.ac.il) if you have questions or run into difficulties.

References

Dinic

Push-Relabel

Boykov-Kolmogorov

http://www.csd.uwo.ca/faculty/yuri/Papers/pami04.pdf

Goldberg-Rao (flow scaling)

http://portal.acm.org/citation.cfm?doid=290179.290181

Network Simplex

Input and Output Formats

The input and output formats are the DIMACS standard format for the maximum flow problem. You can find an accurate specification at http://www.avglab.com/andrew/CATS/maxflow_formats.htm.

Immediately after you generate the initial residual graph, you must randomly permute the order of arcs (and anti-arcs) for every node!

Trace Formats

When your program recieves a "-trace" command line argument, it must output a trace text, according to the specifications below. This trace will help you and us follow your algorithm implementation.

Dinic

Whenever performing a new dinic phase, print -
phase <shortest_path_length>
for example,
phase 5

Whenever performing an augmentation, print -
augmentation <bottleneck_flow_amount> <node0_id> <node1_id> <node2_id> ...
where the node id's indicate the nodes along the augmentation in order from source to sink.
for example,
augmentation 22 34 55 99

Push-Relabel

After assigning the initial labels and excesses to all nodes, print a line for every node -
node <node_id> <node_label> <node_excess> <s/t>
where s or t appear if the node represents the source or the sink.
for example,
node 1 999 0 s
node 2 0 0 t
node 3 1 20

Whenever performing a push, print -
push <from_node_id> <from_node_label> <from_node_excess_before_push> <to_node_id> <to_node_label> <to_node_excess_before_push> <push_amount>
for example,
push 98 9 1010 99 8 1000 10

Whenever performing a relabel, print -
relabel <node_id> <node_label_before_relabel> <node_label_after_relabel>
for example,
relabel 98 9 11

Whenever performing a global relabeling (bfs), print -
bfs
followed by node lines as above, stating the labels and excessed of all nodes after the bfs.
for example,
bfs
node 1 999 0 s
node 2 0 0 t
node 3 1 20

Boykov-Kolmogorov

When a new node is discovered in a growth step, print -
growth <S/T> <scanned_node_id> <found_node_id>
where S or T indicates whether the growth step is performed on the source tree or sink tree.
for example,
growth S 22 33

Whenever performing an augmentation, print -
augmentation <S/T> <bottleneck_flow_amount> <node0_id> <node1_id> <node2_id> ...
where S or T indicates whether the augmentation was found during a growth step in S or in T, and the node id's indicate the nodes along the augmentation in order from source to sink.
for example,
augmentation S 22 34 55 99

Whenever performing an orphan step and reattaching the node to its former tree, print -
orphan reattach <S/T> <node_id> <new_parent_node_id>
where S or T indicates whether the orphan step was in S or in T.
for example,
orphan reattach S 22 34

Whenever performing an orphan step and not reattaching the node to its former tree, print -
orphan dettach <S/T> <node_id> <child0_node_id> <child1_node_id> <child2_node_id> ...
where S or T indicates whether the orphan step was in S or in T, and child id's indicate the children of the node that are inserted into the orphan list.
for example,
orphan dettach S 22 34 99 98

Network Simplex

After building the initial basis, print for every edge in the basis tree/s
basis <node_id_0> <node_id_1>
where the two nodes are the nodes of the edge that is in the basis tree/s.
for example,
basis 88 99

After building the initial labels, print for every node
node <node_id> <node_label>
for example,
node 99 3

Whenever performing an augmentation, print -
augment <pivot_node_id_0> <pivot_node_label_0> <pivot_node_id_1> <pivot_node_label_1> <bottleneck_arc_node_id_0> <bottleneck_arc_node_label_0> <bottleneck_arc_node_id_1> <bottleneck_arc_node_label_1> <bottleneck_amount>
where bottleneck arc is the outgoing arc of the pivot step (the arc that is saturated). If several exist, choose one arbitrarily.
for example,
augment 77 9 66 10 99 7 98 8 1000

Whenever changing a node's label, print -
label <node_id> <previous_node_label> <new_node_label>
for example,
label 77 9 11

Inputs

graph family instances (http://www.avglab.com/andrew/CATS/maxflow_synthetic.htm)
Use the graph generators linked above to generate several graph families. All the details you need to generate theg raph familes is specfied inside. Measure your performance on the WASHINGTON-RLG-LONG, WASHINGTON-RLG-WIDE, WASHINGTON-LINE-MODERATE, GENRMF-LONG, GENRMF-WIDE and AC graph gamilies. Do not run on the AK family.
vision instances (http://vision.csd.uwo.ca/maxflow-data)
These graphs are taken from vision applications. Run on as many of them as you can, as long your implementation still fits into memory (RAM).
At the very least you must compare results on the BVZ-* graphs, the KVZ-* graphs, the BL06-camel-sml graph and the BL06-gargoyle-sml graph.

Public Code

Dinic

http://www.avglab.com/andrew/soft/prf.tar (df.c)

A version of the above code with operation counts
The operation counts are printed in the main method.

Push-Relabel

http://www.igsystems.com/hipr/

Boykov-Kolmogorov

http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/software/maxflow-v3.0.src.tar.gz

A version of the above code with operation counts
The operation counts are held in the following class members:
double growth - the number of growth steps
double orphans - the number of orphan steps
double orphansBackTraversal - the number of nodes traversed during the traversal back to the root in an orphan step
double augs - the number of augmentations
double sumAugLens - the sum of the augmentation lengths

Goldberg-Rao (flow scaling)

Network Simplex

Deadlines

The specification document should be submitted by - 17 / 1 / 2010 (note the deadline has been postponed a little, in response to student requests).
The final workshop project should be submitted by - 23 / 5 / 2010.
Note: the final project deadline is the final deadline for all submitted works from this semester. This deadline is dictated by the university and therefore we have no control over it!! Therefore note that no extensions to this date will be possible.

What to submit?

The specification document should be in html, word, pdf or rtf:

your names, IDs and emails.
describe the algorithm you have selected and how you intend to implement it
specify the program language and IDE (eclipse, visual studio, notepad etc.)
explain how you will test correctness
describe what you intend to compare

The final project submission:

All source code and related libraries / files zipped into 1 compressed file.

do not submit executables

the program must accept input and write output as specified above. All input and output lines are space separated between data elements and “\n” or “\r\n” separated between lines.

A documentation in html, word, pdf or rtf:

your names, IDs and emails.
short reminder of the project you selected
description of any difference between the original work plan submitted and final work performed on the project.

very general classes and/or main methods overview
explanation of how to compile and run the programs
explanation of how correctness was checked
a precise description of the experiments performed, the inputs used and all exact parameters.
a description on the experiments’ results, including all relevant measurment graphs.

How to submit?

All submissions are via email to the teaching assistant (sagihed@post.tau.ac.il).

Good Luck!

Workshop In Algorithms And Data Structures 2009-2010, Semester A

Maximum Flow Algorithms

Workshop In Algorithms And Data Structures
2009-2010, Semester A