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 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 subclassestrickle
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