trickle: linear-time maximum flow in planar graphs with unit capacities (Java)

David Eisenstat

June 2013

Download

The latest release is June 2013.

Introduction

trickle computes single-source single-sink maximum flows in planar embedded graphs with integer capacities. The algorithm, a simplification of joint work with my PhD advisor Philip N. Klein, runs in time O(m + C) where m is the number of edges in the graph and C is their total capacity.

To test trickle, run java -jar trickle-June_2013.jar. If the tests are successful, no output is produced. To extract the source code and other files from the JAR, run jar xvf trickle-June_2013.jar or unzip trickle-June_2013.jar. To build trickle from source, run ant.

trickle is MIT-licensed.

Synopsis

The package com.davideisenstat.trickle provides the following public classes.

Edge

    package com.davideisenstat.trickle;
    public final class Edge implements Serializable {
        public Edge();
        public Edge getSym();
        public Edge getDnext();
        public Edge getOnext();
        public Edge getRprev();
        public Edge getLprev();
        public void swapDnext(Edge that);
        public void swapLprev(Edge that);
        public int getCapacity();
        public void setCapacity(int capacity);
        public int getFlow();
        public void setFlow(int flow);
    }

The class Edge provides a singly linked version of Guibas and Stolfi’s quad-edge data structure for orientable embedded graphs as described in § 4.1 of their paper Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. The constructor replaces MakeEdge, and swapDnext replaces Splice.

The capacity of and flow on both a new edge and its symmetric all are zero. The method setCapacity throws a CapacityIsNotValidException when its argument is negative. The method setFlow sets the flow on the symmetric also to preserve antisymmetry (modulo 232). Neither method enforces the capacity constraints.

Algorithm

    package com.davideisenstat.trickle;
    public final class Algorithm {
        public static int maxFlow(Edge destSource, Edge destSink,
                                  Collection<Edge> cutEdges);
    }

The class Algorithm provides the static method maxFlow. The source is the destination vertex of the edge argument destSource. The sink is the destination vertex of the edge argument destSink. If the source and the sink are distinct yet connected, and the component to which they both belong is planar, then maxFlow succeeds. Otherwise, maxFlow throws an instance of an appropriate subclass of TrickleException.

When successful, maxFlow sets the flow on each edge belonging to the same component as the source and the sink, adds the edges that cross a particular simple minimum cut to cutEdges in cyclic order (unless that collection argument is null), and returns the objective value modulo 232. When maxFlow is unsuccessful, the flow on each edge belonging to the same component as the source or the sink is indeterminate, though cutEdges is unmodified.

TrickleException and subclasses

trickle does not use checked exceptions. The class TrickleException is an abstract subclass of IllegalArgumentException. The four subclasses of TrickleException are CapacityIsNotValidException and EmbeddingIsNotPlanarException and SourceAndSinkAreNotConnectedException and SourceAndSinkAreNotDistinctException.


© 2013 David Eisenstat