# SCM Repository

[matrix] View of /pkg/src/Metis/mincover.c
 [matrix] / pkg / src / Metis / mincover.c

# View of /pkg/src/Metis/mincover.c

Mon Mar 22 20:20:05 2004 UTC (15 years, 11 months ago) by bates
File size: 7211 byte(s)
`Initial import`
```/*
* Copyright 1997, Regents of the University of Minnesota
*
* mincover.c
*
* This file implements the minimum cover algorithm
*
* Started 8/1/97
* George
*
* \$Id: mincover.c,v 1.1 2003/12/31 21:32:30 bates Exp \$
*/

#include <metis.h>

/*************************************************************************
* Constants used by mincover algorithm
**************************************************************************/
#define INCOL 10
#define INROW 20
#define VC 1
#define SC 2
#define HC 3
#define VR 4
#define SR 5
#define HR 6

/*************************************************************************
* This function returns the min-cover of a bipartite graph.
* The algorithm used is due to Hopcroft and Karp as modified by Duff etal
*       asize: the number of vertices in the first part of the bipartite graph
* bsize-asize: the number of vertices in the second part
*        0..(asize-1) > A vertices
*        asize..bsize > B vertices
*
* Returns:
*  cover : the actual cover (array)
*  csize : the size of the cover
**************************************************************************/
void MinCover(idxtype *xadj, idxtype *adjncy, int asize, int bsize, idxtype *cover, int *csize)
{
int i, j;
idxtype *mate, *queue, *flag, *level, *lst;
int fptr, rptr, lstptr;
int row, maxlevel, col;

mate = idxsmalloc(bsize, -1, "MinCover: mate");
flag = idxmalloc(bsize, "MinCover: flag");
level = idxmalloc(bsize, "MinCover: level");
queue = idxmalloc(bsize, "MinCover: queue");
lst = idxmalloc(bsize, "MinCover: lst");

/* Get a cheap matching */
for (i=0; i<asize; i++) {
break;
}
}
}

/* Get into the main loop */
while (1) {
/* Initialization */
fptr = rptr = 0;   /* Empty Queue */
lstptr = 0;        /* Empty List */
for (i=0; i<bsize; i++) {
level[i] = -1;
flag[i] = 0;
}
maxlevel = bsize;

/* Insert free nodes into the queue */
for (i=0; i<asize; i++)
if (mate[i] == -1) {
queue[rptr++] = i;
level[i] = 0;
}

/* Perform the BFS */
while (fptr != rptr) {
row = queue[fptr++];
if (level[row] < maxlevel) {
flag[row] = 1;
if (!flag[col]) {  /* If this column has not been accessed yet */
flag[col] = 1;
if (mate[col] == -1) { /* Free column node was found */
maxlevel = level[row];
lst[lstptr++] = col;
}
else { /* This column node is matched */
if (flag[mate[col]])
printf("\nSomething wrong, flag[%d] is 1",mate[col]);
queue[rptr++] = mate[col];
level[mate[col]] = level[row] + 1;
}
}
}
}
}

if (lstptr == 0)
break;   /* No free columns can be reached */

/* Perform restricted DFS from the free column nodes */
for (i=0; i<lstptr; i++)
}

GKfree(&mate, &flag, &level, &queue, &lst, LTERM);

}

/*************************************************************************
* This function perfoms a restricted DFS and augments matchings
**************************************************************************/
int MinCover_Augment(idxtype *xadj, idxtype *adjncy, int col, idxtype *mate, idxtype *flag, idxtype *level, int maxlevel)
{
int i;
int row = -1;
int status;

flag[col] = 2;

if (flag[row] == 1) { /* First time through this row node */
if (level[row] == maxlevel) {  /* (col, row) is an edge of the G^T */
flag[row] = 2;  /* Mark this node as being visited */
if (maxlevel != 0)
else
status = 1;

if (status) {
mate[col] = row;
mate[row] = col;
return 1;
}
}
}
}

return 0;
}

/*************************************************************************
* This function performs a coarse decomposition and determines the
* min-cover.
* REF: Pothen ACMTrans. on Amth Software
**************************************************************************/
void MinCover_Decompose(idxtype *xadj, idxtype *adjncy, int asize, int bsize, idxtype *mate, idxtype *cover, int *csize)
{
int i, k;
idxtype *where;
int card[10];

where = idxmalloc(bsize, "MinCover_Decompose: where");
for (i=0; i<10; i++)
card[i] = 0;

for (i=0; i<asize; i++)
where[i] = SC;
for (; i<bsize; i++)
where[i] = SR;

for (i=0; i<asize; i++)
if (mate[i] == -1)
for (; i<bsize; i++)
if (mate[i] == -1)

for (i=0; i<bsize; i++)
card[where[i]]++;

k = 0;
if (abs(card[VC]+card[SC]-card[HR]) < abs(card[VC]-card[SR]-card[HR])) {  /* S = VC+SC+HR */
/* printf("%d %d ",vc+sc, hr); */
for (i=0; i<bsize; i++)
if (where[i] == VC || where[i] == SC || where[i] == HR)
cover[k++] = i;
}
else {  /* S = VC+SR+HR */
/* printf("%d %d ",vc, hr+sr); */
for (i=0; i<bsize; i++)
if (where[i] == VC || where[i] == SR || where[i] == HR)
cover[k++] = i;
}

*csize = k;
free(where);

}

/*************************************************************************
* This function perfoms a dfs starting from an unmatched col node
* forming alternate paths
**************************************************************************/
void MinCover_ColDFS(idxtype *xadj, idxtype *adjncy, int root, idxtype *mate, idxtype *where, int flag)
{
int i;

if (flag == INCOL) {
if (where[root] == HC)
return;
where[root] = HC;
}
else {
if (where[root] == HR)
return;
where[root] = HR;
if (mate[root] != -1)
}

}

/*************************************************************************
* This function perfoms a dfs starting from an unmatched col node
* forming alternate paths
**************************************************************************/
void MinCover_RowDFS(idxtype *xadj, idxtype *adjncy, int root, idxtype *mate, idxtype *where, int flag)
{
int i;

if (flag == INROW) {
if (where[root] == VR)
return;
where[root] = VR;
}
else {
if (where[root] == VC)
return;
where[root] = VC;
if (mate[root] != -1)