/*-
* $Id: pdmxfl.c,v 1.1.1.1 2002/09/25 18:11:29 ggv Exp $
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Contents: FORTRAN callable functions to test feasibility and detect
* early optimality of minimum cost network problems in PDNET.
*
* Authors: Luis Portugal (Univ. Coimbra - Portugal)
* Mauricio G. C. Resende (AT&T Labs Research - USA)
* Geraldo Veiga (AT&T Labs - USA)
* Joaquim Judice (Univ. Coimbra - Portugal)
* Joao Patricio (EST Tomar - Portugal)
*
* User callable functions:
* >>> pdmxfl <<<
* >>> pdmxfl_ <<<
* >>> pdfeas_ <<<
*
*
* Revision History:
* 2001-12-27 Geraldo Veiga
* Initial release for ACM distribution.
*
*/
/* Include files */
#include "pdnet.h" /* general definitions for PDNET ANSI C */
#include "debug.h" /* PDNET debug macros */
/* Prototypes of local functions */
void pdmxfl (int *actlst, /* List of active edges */
double *cap, /* Edge capacity */
int *endv, /* end vertex array */
int *mflow, /* Maximum flow supplied */
int *mfreq, /* Maximum flow request */
int *mxfe, /* edges in maxflow */
int *mxfv, /* vertices in maxflow */
int *nact, /* Number of active edges */
int *ncap, /* Number of edges at capacity */
int *nedge, /* Number of edges */
int *nvrtx, /* Number of vertices */
int *strv, /* start vertex array */
double *supply, /* Vertex supply */
int *xopt /* Tentative optimal flow */
);
/*-
* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
*
* >>> pdmxfl <<<
*
* Description: Computes a maximum flow across a network comprised
* of the active edges in the optimal solution. This is a FORTRAN
* callable function.
*
* 1. Correct the flow balances in or out of each vertex, as implied
* by edges in upper and lower bound.
*
* 2. Build a list of virtual edges from a source vertex into
* vertices with positive flow balance and from vertices with
* negative flow balance into a sink vertex.
*
* 3. Solve maximum flow problem with Dinic's algorithm.
*
* 4. Build a primal maxflow solution if solution array is currently
* allocated.
*
* Return Value: None.
*
* Side effects: Memory used in maximum flow procedure is allocated
* and deallocated dynamically in this function.
* --------------------------------------------------------------------
*/
void
pdmxfl (int *actlst, /* List of active edges */
double *cap, /* Edge capacity */
int *endv, /* end vertex array */
int *mflow, /* Maximum flow supplied */
int *mfreq, /* Maximum flow request */
int *mxfe, /* edges in maxflow */
int *mxfv, /* vertices in maxflow */
int *nact, /* Number of active edges */
int *ncap, /* Number of edges at capacity */
int *nedge, /* Number of edges */
int *nvrtx, /* Number of vertices */
int *strv, /* start vertex array */
double *supply, /* Vertex supply */
int *xopt /* Tentative optimal flow */
)
{
int *balance = NULL, /* flow balance in maxflo */
*dnlist = NULL, /* dnsub arrays */
*dndist = NULL,
*dnfapt = NULL,
*dnptrf = NULL,
*dnbapt = NULL,
*dnflab = NULL,
*dnptrb = NULL,
*dnfadj = NULL,
*dnfrom = NULL,
*dnmap = NULL,
*dnto = NULL,
*dnbadj = NULL,
*dngcap = NULL, *dncap = NULL, *dnflow = NULL, *dnbtof = NULL;
int edg, /* edge index */
i, /* generic index */
mfedge, /* edges in maxflow */
mfsnk, /* maxflow sink */
mfsrc, /* maxflow source */
mfvrtx, /* vertices in maxflow */
nacut, nncut, numaug, /* number of augmentations */
numstg, /* number of stages */
rc, /* return code for dinic fubctions */
tmp, /* temporary int */
v1, /* vertex index */
v2; /* vertex index */
/* Compute number of vertices */
mfvrtx = *nvrtx + 2;
mfsrc = *nvrtx + 1;
mfsnk = *nvrtx + 2;
/* Allocate memory dependent on number of vertices */
MALLOC (dnlist, int, mfvrtx + 2);
MALLOC (dndist, int, mfvrtx + 2);
MALLOC (dnfapt, int, mfvrtx + 2);
MALLOC (dnptrf, int, mfvrtx + 2);
MALLOC (dnbapt, int, mfvrtx + 2);
MALLOC (dnptrb, int, mfvrtx + 2);
/* Pointers to dnsub sharable arrays */
dnflab = dndist;
/* Overlay temporary array in already allocated area */
balance = dndist;
/* Initialize capacity of virtual edges */
for (i = 0; i < *nvrtx; i++)
balance[i] = (int) -supply[i];
DB_ARRAY (5, balance, "%d ", *nvrtx);
/* Adjust flow balance for edges at capacity */
for (i = *nact; i < *nact + *ncap; i++)
{
edg = actlst[i] - 1;
v1 = strv[edg] - 1;
v2 = endv[edg] - 1;
balance[v1] -= (int) cap[edg];
balance[v2] += (int) cap[edg];
}
/* Compute number of vertices and edges in maxflow */
for (i = 0, mfedge = *nact, *mfreq = 0; i < *nvrtx; i++)
if (balance[i] != 0)
{
mfedge++;
if (balance[i] > 0)
*mfreq += balance[i];
}
DB_ARRAY (5, &actlst[*nact], "%d ", *ncap);
DB_ARRAY (5, strv, "%d ", *nedge);
DB_ARRAY (5, endv, "%d ", *nedge);
DB_ARRAY (5, cap, "%g ", *nedge);
DB_ARRAY (5, supply, "%g ", *nvrtx);
DB_ARRAY (5, balance, "%d ", *nvrtx);
/* Allocate memory dependent on number of edges */
MALLOC (dnmap, int, mfedge + 1);
MALLOC (dnto, int, mfedge + 1);
MALLOC (dnfadj, int, mfedge + 1);
MALLOC (dnbadj, int, mfedge + 1);
MALLOC (dncap, int, mfedge + 1);
MALLOC (dnbtof, int, mfedge + 1);
/* Pointers to dnsub sharable arrays */
dnflow = dnto;
dnfrom = dnbadj;
dngcap = dnbtof;
/* Generate active edges */
for (i = 0; i < *nact; i++)
{
edg = actlst[i] - 1;
tmp = (int) cap[edg];
dnfrom[i] = strv[edg];
dnto[i] = endv[edg];
dngcap[i] = MIN (tmp, *mfreq);
}
/* Generate virtual edges */
for (i = 0, edg = *nact; i < *nvrtx; i++)
if (balance[i] < 0)
{
dnfrom[edg] = i + 1;
dnto[edg] = mfsnk;
dngcap[edg++] = -balance[i];
}
else if (balance[i] > 0)
{
dnfrom[edg] = *nvrtx + 1;
dnto[edg] = i + 1;
dngcap[edg++] = balance[i];
}
/* Discard temporary array */
balance = NULL;
/* Create input data in fwd adjacencies as required by dnsub */
DB_ARRAY (5, dnfrom, "%d ", mfedge);
DB_ARRAY (5, dnto, "%d ", mfedge);
DB_ARRAY (5, dngcap, "%d ", mfedge);
DB_ARRAY (5, dnlist, "%d ", mfvrtx + 2);
DB_ARRAY (5, dnfapt, "%d ", mfvrtx + 2);
DB_ARRAY (5, dnfadj, "%d ", mfedge + 1);
DB_ARRAY (5, dnfrom, "%d ", mfedge);
DB_ARRAY (5, dnto, "%d ", mfedge);
DB_ARRAY (5, dncap, "%d ", mfedge + 1);
DB_ARRAY (5, dngcap, "%d ", mfedge + 1);
DB_ARRAY (5, dnmap, "%d ", mfedge + 1);
dnfwd_ (&mfvrtx, &mfedge, &rc, dnlist, dnfapt, dnfadj, dnfrom, dnto,
dncap, dngcap, dnmap);
*mxfv = mfvrtx;
*mxfe = mfedge;
DB_ARRAY (5, dnlist, "%d ", mfvrtx + 2);
DB_ARRAY (5, dnfapt, "%d ", mfvrtx + 2);
DB_ARRAY (5, dnfadj, "%d ", mfedge + 1);
DB_ARRAY (5, dnfrom, "%d ", mfedge);
DB_ARRAY (5, dnto, "%d ", mfedge);
DB_ARRAY (5, dncap, "%d ", mfedge + 1);
DB_ARRAY (5, dngcap, "%d ", mfedge + 1);
DB_ARRAY (5, dnmap, "%d ", mfedge + 1);
if (rc != 0)
syserr ("Error in dnsub");
/* Solve max flow problem */
dnsub_ (&mfvrtx, &mfedge, &mfsrc, &mfsnk, mflow, &numaug, &numstg,
&nncut, &nacut, &rc, dnlist, dndist, dnfapt,
dnptrf, dnbapt, dnflab, dnptrb, dnfadj, dnfrom, dnto,
dnbadj, dncap, dngcap, dnflow, dnbtof);
DB_ARRAY (5, dnflow, "%d ", mfedge);
if (rc != 0)
syserr ("Error in dnsub");
/* Discard pointers to dnsub sharable arrays */
dnfrom = NULL;
dngcap = NULL;
/* Free memory objects */
FREE (dnfadj);
FREE (dnbtof);
FREE (dncap);
FREE (dnbadj);
FREE (dnptrb);
FREE (dnbapt);
FREE (dnptrf);
FREE (dnfapt);
FREE (dndist);
FREE (dnlist);
/* Build array with optimal flow */
if (xopt != NULL)
{
for (i = 0; i < *nact; i++)
{
edg = actlst[i] - 1;
xopt[edg] = dnflow[dnmap[i] - 1];
}
for (i = *nact; i < *nact + *ncap; i++)
{
edg = actlst[i] - 1;
xopt[edg] = cap[edg];
}
for (i = *nact + *ncap; i < *nedge; i++)
xopt[actlst[i] - 1] = 0;
DB_ARRAY (5, xopt, "%d ", *nedge);
}
/* Free remaining memory */
DB_ARRAY (5, actlst, "%d ", *nedge);
DB_ARRAY (5, dnmap, "%d ", mfedge);
DB_ARRAY (5, dnflow, "%d ", mfedge);
dnflow = NULL;
FREE (dnto);
FREE (dnmap);
}
/*-
* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
*
* >>> pdmxfl_ <<<
*
* Description: Invokes function for computing a maximum flow across
* a network comprised of the active edges. This is a FORTRAN callable
* function used.
*
* Side effects: Invokes function pdmxfl().
* --------------------------------------------------------------------
*/
void
pdmxfl_ (int *actlst, /* List of active edges */
double *cap, /* Edge capacity */
int *endv, /* end vertex array */
int *mflow, /* Maximum flow supplied */
int *mfreq, /* Maximum flow request */
int *mxfe, /* edges in maxflow */
int *mxfv, /* vertices in maxflow */
int *nact, /* Number of active edges */
int *ncap, /* Number of edges at capacity */
int *nedge, /* Number of edges */
int *nvrtx, /* Number of vertices */
int *strv, /* start vertex array */
double *supply, /* Vertex supply */
int *xopt /* Tentative optimal flow */
)
{
(void) pdmxfl (actlst, cap, endv, mflow, mfreq, mxfe, mxfv,
nact, ncap, nedge, nvrtx, strv, supply, xopt);
}
/*-
* ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
*
* >>> pdfeas_ <<<
*
* Description: Invokes function for computing a maximum flow across
* a network comprised of the active edges without computing the max
* flow array. This is a FORTRAN callable function used to test
* feasibility of the active the edge network.
*
* Side effects: Invokes function pdmxfl().
* --------------------------------------------------------------------
*/
void
pdfeas_ (int *nvrtx, /* Number of vertices */
int *nedge, /* Number of edges */
int *strv, /* start vertex array */
int *endv, /* end vertex array */
double *cap, /* Edge capacity */
double *supply, /* Vertex supply */
int *nact, /* Number of active edges */
int *ncap, /* Number of edges at capacity */
int *actlst, /* List of active edges */
int *mfreq, /* Maximum flow request */
int *mflow, /* Maximum flow supplied */
int *mxfv, /* vertices in maxflow */
int *mxfe /* edges in maxflow */
)
{
(void) pdmxfl (actlst, cap, endv, mflow, mfreq, mxfe, mxfv,
nact, ncap, nedge, nvrtx, strv, supply, NULL);
}
syntax highlighted by Code2HTML, v. 0.9.1