Symbolic maxflow algorithm. More...

#include "ntr.h"

Include dependency graph for ntrMflow.c:

Data Structures
struct	flowStatsStruct
	Structure to hold statistics. More...

Macros
#define	MAXPHASE 1000

#define	MAXLAYER 1000

#define	MAXFPIT 100000

#define	MANY_TIMES 3.0

#define	PRUNE /* If defined, enables pruning of E */

Typedefs
typedef struct flowStatsStruct	flowStats
	Structure to hold statistics.

Functions
double	Ntr_maximum01Flow (DdManager bdd, DdNode sx, DdNode ty, DdNode E, DdNode F, DdNode cut, DdNode x, DdNode y, DdNode **z, int n, int pr)
	Symbolic Dinit's algorithm. More...

static void	maximal_pull (DdManager bdd, int l, DdNode ty, DdNode neW, DdNode U, DdNode E, DdNode F, DdNode x, DdNode y, DdNode z, int n, DdNode pryz, DdNode prxz, flowStats stats)
	Selects set of edge-disjoint paths from layered network. More...

static void	propagate_maximal_flow (DdManager bdd, int m, DdNode neW, DdNode U, DdNode x, DdNode y, DdNode z, int n, DdNode pryz, DdNode prxz, flowStats stats)
	Pulls flow though a layer. More...

static void	trellis (DdManager bdd, int m, DdNode neW, DdNode U, DdNode x, DdNode y, DdNode z, int n, DdNode pryz, DdNode prxz, flowStats stats)
	Selects edges from a trellis-type bilayer. More...

static void	rhombus (DdManager bdd, int m, DdNode neW, DdNode U, DdNode x, DdNode y, DdNode z, int n, DdNode pryz, DdNode prxz, flowStats stats)
	Selects edges from a rhombus-type bilayer. More...

static void	hourglass (DdManager bdd, int m, DdNode neW, DdNode U, DdNode x, DdNode y, DdNode z, int n, DdNode pryz, DdNode prxz, flowStats stats)
	Selects edges from a hourglass-type bilayer. More...

static void	maximal_push (DdManager bdd, int l, DdNode U, DdNode F, DdNode x, DdNode y, DdNode z, int n, DdNode pryz, DdNode prxz, flowStats stats)
	Pushes flow through useful edges. More...

static void	trellisPush (DdManager bdd, int m, DdNode U, DdNode x, DdNode y, DdNode z, int n, DdNode pryz, DdNode prxz, flowStats stats)
	Pushes flow through a trellis. More...

static void	rhombusPush (DdManager bdd, int m, DdNode U, DdNode x, DdNode y, DdNode z, int n, DdNode pryz, DdNode prxz, flowStats stats)
	Pushes flow through a rhombus. More...

static void	hourglassPush (DdManager bdd, int m, DdNode U, DdNode x, DdNode y, DdNode z, int n, DdNode pryz, DdNode prxz, flowStats stats)
	Pushes flow through an hourglass. More...

Variables
static DdNode *	xcube

static DdNode *	ycube

static DdNode *	zcube

Detailed Description

Symbolic maxflow algorithm.

This file contains the functions that implement the symbolic version of Dinits's maxflow algorithm described in the ICCAD93 paper. The present implementation differs from the algorithm described in the paper in that more than one matching techniques is used. The technique of the paper is the one applied to hourglass-type bilayers here.

Author: Fabio Somenzi, Gary Hachtel

Copyright

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

Neither the name of the University of Colorado nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Function Documentation

◆ hourglass()

static void hourglass	(	DdManager *	bdd,
		int	m,
		DdNode **	neW,
		DdNode **	U,
		DdNode **	x,
		DdNode **	y,
		DdNode **	z,
		int	n,
		DdNode *	pryz,
		DdNode *	prxz,
		flowStats *	stats
	)

static

Selects edges from a hourglass-type bilayer.

Used to pull flow. Method described in paper. More general, but more expensive than the others.

Side effects None

See also: trellis rhombus hourglassPush

Parameters

bdd	DD manager
m	center level of current bilayer
neW	array for flow propagation
U	array for flow propagation
x	array of variables for rows and columns
y	array of variables for rows and columns
z	array of variables for rows and columns
n	number of x variables
pryz	priority function
prxz	priority function
stats	statistics

◆ hourglassPush()

static void hourglassPush	(	DdManager *	bdd,
		int	m,
		DdNode **	U,
		DdNode **	x,
		DdNode **	y,
		DdNode **	z,
		int	n,
		DdNode *	pryz,
		DdNode *	prxz,
		flowStats *	stats
	)

static

Pushes flow through an hourglass.

Side effects None

Parameters

bdd	DD manager
m	Current layer
U	Array of edge sets for flow propagation
x	Array of variables for rows and columns
y	Array of variables for rows and columns
z	Array of variables for rows and columns
n	Number of x variables
pryz	Priority function
prxz	Priority function
stats	statistics

◆ maximal_pull()

static void maximal_pull	(	DdManager *	bdd,
		int	l,
		DdNode *	ty,
		DdNode **	neW,
		DdNode **	U,
		DdNode *	E,
		DdNode **	F,
		DdNode **	x,
		DdNode **	y,
		DdNode **	z,
		int	n,
		DdNode *	pryz,
		DdNode *	prxz,
		flowStats *	stats
	)

static

Selects set of edge-disjoint paths from layered network.

maximal_pull is called when the BFS constructing the layered graph reaches a sink. At this point the new sets of the BFS have been formed, and we know every vertex in these sets is reachable from the source vertex (or vertices) s. The new sets are used to compute the set of useful edges exiting each layer to the right. In each layer, propagate_maximal_flow is called to select a maximal subset of these useful edges. This subset is then used to prune new and U.

Side effects None

See also: maximal_push

Parameters

bdd	manager
l	depth of layered network for current phase
ty	sink node
neW	array of BFS layers
U	array of useful edges
E	edge relation
F	flow relation
x	array of variables for rows and columns
y	array of variables for rows and columns
z	array of variables for rows and columns
n	number of x variables
pryz	priority function
prxz	priority function
stats	statistics

◆ maximal_push()

static void maximal_push	(	DdManager *	bdd,
		int	l,
		DdNode **	U,
		DdNode **	F,
		DdNode **	x,
		DdNode **	y,
		DdNode **	z,
		int	n,
		DdNode *	pryz,
		DdNode *	prxz,
		flowStats *	stats
	)

static

Pushes flow through useful edges.

Pushes flow from the source(s) to the sink(s) through useful edges.

Side effects None

Parameters

bdd	DD manager
l	Depth of layered network for current phase
U	array of edge sets for flow propagation
F	edge and flow relations
x	array of variables for rows and columns
y	array of variables for rows and columns
z	array of variables for rows and columns
n	number of x variables
pryz	priority function
prxz	priority function
stats	statistics

◆ Ntr_maximum01Flow()

double Ntr_maximum01Flow	(	DdManager *	bdd,
		DdNode *	sx,
		DdNode *	ty,
		DdNode *	E,
		DdNode **	F,
		DdNode **	cut,
		DdNode **	x,
		DdNode **	y,
		DdNode **	z,
		int	n,
		int	pr
	)

Symbolic Dinit's algorithm.

This function implements Dinits's algorithm for (0-1) max flow, using BDDs and a symbolic technique to trace multiple edge-disjoint augmenting paths to complete a phase. The outer forever loop is over phases, and the inner forever loop is to propagate a (not yet) maximal flow of edge-disjoint augmenting paths from one layer to the previous. The subprocedure call implements a least fixed point iteration to compute a (not yet) maximal flow update between layers. At the end of each phase (except the last one) the flow is actually pushed from the source to the sink.

Data items:

sx(ty) BDD representations of s(t).
x(y) The variables encoding the from(to)-node u(v) of an edge (u,v) in the given digraph.
z Another set of variables.
E(x,y) The edge relation.
F(x,y) BDD representation of the current flow, initialized to 0 for each arc, and updated by +1, -1, or 0 at the end of each phase.
Ms Mt The maximum flow, that is, the cardinality of a minimum cut, measured at the source and at the sink, respectively. The two values should be identical.
reached The set of nodes already visited in the BFS of the digraph.
fos fanout of the source node s.
fit fanin of the sink node t.

Side effects The flow realtion F and the cutset relation cut are returned: as side effects.

Parameters

bdd	manager
sx	source node
ty	sink node
E	edge relation
F	flow relation
cut	cutset relation
x	array of row variables
y	array of column variables
z	arrays of auxiliary variables
n	number of variables in each array
pr	verbosity level

◆ propagate_maximal_flow()

static void propagate_maximal_flow	(	DdManager *	bdd,
		int	m,
		DdNode **	neW,
		DdNode **	U,
		DdNode **	x,
		DdNode **	y,
		DdNode **	z,
		int	n,
		DdNode *	pryz,
		DdNode *	prxz,
		flowStats *	stats
	)

static

Pulls flow though a layer.

propagate_maximal_flow only affects U[m-1 and new[m-1]. At the end of this function, the edges in U[m] are guaranteed to drain all the flow supplied by the edges in U[m-1]. This effect is obtained by pruning U[m-1]. After the pruned U[m-1] is computed, new[m-1] is updated to keep track of what nodes are still useful.

The pruning is performed without actually measuring the in-potential and the out-potential of each node. Instead, pairs of nodes from U[m-1] and U[m] are matched. To avoid counting, the procedure computes sets of paths that connect layer m-1 to layer m+1 and are edge-disjoint.

Two paths from layer m-1 to layer m+1 are disjoint if they have distinct end-point or if they have distinct middle points. What condition to enforce depends on the "shape" of the layers.]

Side effects Changes U[m-1 and new[m-1]]

See also: trellis rhombus hourglass

Parameters

bdd	DD manager
m	center of current bilayer
neW	array of reachable or useful nodes
U	array of usable or useful edges
x	array of variables for rows and columns
y	array of variables for rows and columns
z	array of variables for rows and columns
n	number of x variables
pryz	priority function
prxz	priority function
stats	statistics

◆ rhombus()

static void rhombus	(	DdManager *	bdd,
		int	m,
		DdNode **	neW,
		DdNode **	U,
		DdNode **	x,
		DdNode **	y,
		DdNode **	z,
		int	n,
		DdNode *	pryz,
		DdNode *	prxz,
		flowStats *	stats
	)

static

Selects edges from a rhombus-type bilayer.

Used to pull flow. Makes the left layer left-unique and the right layer right-unique. Prunes and repeats until convergence to a maximal flow. It makes sure that all intermediate points of the two-arc paths are disjoint at each iteration.

Side effects None

See also: trellis hourglass rhombusPush

Parameters

bdd	DD manager
m	center of current bilayer
neW	array for flow propagation
U	array for flow propagation
x	array of variables for rows and columns
y	array of variables for rows and columns
z	array of variables for rows and columns
n	number of x variables
pryz	priority function
prxz	priority function
stats	statistics

◆ rhombusPush()

static void rhombusPush	(	DdManager *	bdd,
		int	m,
		DdNode **	U,
		DdNode **	x,
		DdNode **	y,
		DdNode **	z,
		int	n,
		DdNode *	pryz,
		DdNode *	prxz,
		flowStats *	stats
	)

static

Pushes flow through a rhombus.

Side effects None

Parameters

bdd	DD manager
m	Current layer
U	Array of edge sets for flow propagation
x	Array of variables for rows and columns
y	Array of variables for rows and columns
z	Array of variables for rows and columns
n	Number of x variables
pryz	Priority function
prxz	Priority function
stats	statistics

◆ trellis()

static void trellis	(	DdManager *	bdd,
		int	m,
		DdNode **	neW,
		DdNode **	U,
		DdNode **	x,
		DdNode **	y,
		DdNode **	z,
		int	n,
		DdNode *	pryz,
		DdNode *	prxz,
		flowStats *	stats
	)

static

Selects edges from a trellis-type bilayer.

Used to pull flow. First a matching is found in the left layer. Then the paths are extended (if possible) through the right layer. This process is repeated until a maximal flow is found.

Side effects None

See also: rhombus hourglass trellisPush

Parameters

bdd	DD manager
m	center level of current bilayer
neW	array of node levels
U	array of edge layers
x	array of variables for rows and columns
y	array of variables for rows and columns
z	array of variables for rows and columns
n	number of x variables
pryz	priority function
prxz	priority function
stats	statistics

◆ trellisPush()

static void trellisPush	(	DdManager *	bdd,
		int	m,
		DdNode **	U,
		DdNode **	x,
		DdNode **	y,
		DdNode **	z,
		int	n,
		DdNode *	pryz,
		DdNode *	prxz,
		flowStats *	stats
	)

static

Pushes flow through a trellis.

Side effects None

Parameters

bdd	DD manager
m	Current layer
U	Array of edge sets for flow propagation
x	Array of variables for rows and columns
y	Array of variables for rows and columns
z	Array of variables for rows and columns
n	Number of x variables
pryz	Priority function
prxz	Priority function
stats	statistics

Data Structures

Macros

Typedefs

Functions

Variables

Detailed Description

Function Documentation

◆ hourglass()

◆ hourglassPush()

◆ maximal_pull()

◆ maximal_push()

◆ Ntr_maximum01Flow()

◆ propagate_maximal_flow()

◆ rhombus()

◆ rhombusPush()

◆ trellis()

◆ trellisPush()