June 2013

The latest release is June 2013.

`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.

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 2^{32}). 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 2^{32}. 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