nanotrav/ntrMflow.c File Reference

Symbolic maxflow algorithm. More...

#include "ntr.h"
Include dependency graph for ntrMflow.c:

Data Structures

struct  flowStatsStruct
 Structure to hold statistics. More...

Defines

#define MAXPHASE   1000
#define MAXLAYER   1000
#define MAXFPIT   100000
#define MANY_TIMES   3.0
#define PRUNE

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

Variables

static DdNodexcube
static DdNodeycube
static DdNodezcube

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 (c) 1995-2015, Regents of the University of Colorado

All rights reserved.

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

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
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
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
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
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
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
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
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
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
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
 All Data Structures Files Functions Variables Typedefs Enumerations Defines

Generated on 31 Dec 2015 for cudd by  doxygen 1.6.1