Solving Maximum Flow Problems in J

Picture of max flow

Journal of J: [pdf]

Source code: [ijs]

Read DIMACS graph format: [ijs]

DIMACS maximum flow instances: [zip]


After a brief introduction to maximum fow problems, a solution is formulated in J. The existing family of push-relabel algorithms is refined in two ways to better suit the high-level nature of J. The focus is on correctness and pedagogy not outright execution efficiency. We conclude by tracing the execution over a specific maximum fow instance. A proficiency in the J programming language is assumed.