clique.cc

Gambit 是一个游戏库理论软件

      if (!( binspect1 ? connected[p][k] : connected[k][p] )) {
         stk[(*tmplist) + count] = k ;
         count ++ ;
      }
    }  // end loop j, comparing to other side 
    // check if new minimum found, in that case update fixpoint 
    if (count < *minnod) {
      *fixp = p ;
      *posfix = i;
      *minnod = count ;
      // save tmplist by making it the new savelist 
      tmp = *savelist ;
      *savelist = *tmplist;
      *tmplist  = tmp ;
      *bfound = true ;
    }
  }  // end loop  i,  inspecting nodes for fixpoint  
}

// -------------------------------------------------- 
void EnumCliques::genincidence(
			       int e,
			       gArray<edge> &edgelist,
			       int orignode1[MAXM],
			       int orignode2[MAXN],
			       bool connected[MAXM][MAXN],
			       int *m,
			       int *n
			       )
  /* generates the incidence matrix  connected from the edgelist
     starting with edgelist[e]
     pre:  all nodes in edgelist < maxinp1,2
     post: orignode1[0..*m) contains the original node1 numbers
     orignode2[0..*n) contains the original node2 numbers
     connected[][] == true if edge, o/w false
     *m == number of rows 
     *n == number of columns
     */
{
  gArray<int> newnode1(0,maxinp1-1) ;
  gArray<int> newnode2(0,maxinp2-1) ;
  int i,j, newi, newj ;
  
  // init newnode 
  for (i=0; i<maxinp1; i++)  newnode1[i] = -1;
  for (j=0; j<maxinp2; j++)  newnode2[j] = -1;
  
  /* init connected for test ; note different dimension 
     for (i=0; i<MAXM; i++)
     for (j=0; j<MAXN; j++)  connected[i][j] = 2;    
  */
  
  *m = *n = 0;
  
  while (e) { // process the edge list with edge index e 
    i= edgelist[e].node1;
    j= edgelist[e].node2;
    newi = newnode1[i] ;
    newj = newnode2[j] ;
    if (newi == -1) {
      if (*m >= MAXM) { // out of bounds for connected, reject 
	printf("Left bound %d for incidence matrix ", MAXM ) ;
	printf("reached, edge (%d, %d) rejected\n", i, j);
	goto KEEPGOING ;
      }
      else {
	int k;
	newi = (*m) ++ ;
	// init connected on the fly 
	for (k=0; k<MAXN; k++)  connected[newi][k] = false;
	newnode1[i] = newi ;
	orignode1[newi] = i ;
      }
    }
    if (newj == -1) {
      if (*n >= MAXN) { // out of bounds for connected, reject 
	printf("Right bound %d for incidence matrix ", MAXN ) ;
	printf("reached, edge (%d, %d) rejected\n", i, j);
	goto KEEPGOING ;
      }
      else {
	newj = (*n) ++ ;
	newnode2[j] = newj ;
	orignode2[newj] = j ;
      }
    }
    connected[newi][newj] = true ;
    
  KEEPGOING:
    e = edgelist[e].nextedge ;
  }
}

// -------------------------------------------------- 
int EnumCliques::getconnco(gArray<int> &firstedge,
			   gArray<edge> &edgelist
			   )
  
  /* reads edges of bipartite graph from input, puts them in disjoint
     lists of edges representing its connected components 
     pre:  nodes are nonzero integers < maxinp1,2
     other edges are rejected, and so are edges starting
     from the MAXEDGEth edge on and larger, each with a warning msg.
     post: return value == numco  (largest index of a connected component)
     where  numco < MAXCO,  and for   1 <= co <= numco:
     edgelist[co].firstedge == 0    if  co  is not a component
     == edgeindex  e  otherwise where  e > 0  and
     edgelist[e].node1, .node2[e] are endpoints of edge,
     edgelist[e].nextedge == next edgeindex of component,
     zero if  e  is index to the last edge
  */
{
  int numco, newedge ;
  gArray<int> co1(0,maxinp1-1), co2(0,maxinp2-1);   // components of node1,2  
  int i, j;  // indices to left and right nodes 
  
  // initialize  component indices of left and right nodes 
  for (i=0; i<maxinp1; i++)
    co1[i] = 0;
  for (j=0; j<maxinp2; j++)
    co2[j] = 0;
  
  numco = 0;
  for(newedge = 1;newedge<=edgelist.Length();newedge++) {
    i = edgelist[newedge].node1;
    j = edgelist[newedge].node2;
    
    if (i < 0 || i>= maxinp1 || j<0 || j>=maxinp2)
      printf("Edge (%d, %d) not in admitted range (0..%d, 0..%d), rejected\n",
	     i,j, maxinp1-1, maxinp2-1) ;
    else { 
      // add edge (i,j) to current componentlist 
      int  ico, jco ;  // current components of i,j  
      ico = co1[i] ;
      jco = co2[j] ;
      
      if (ico == 0) {
	//  i  has not yet been in a component before  
	if (jco == 0) {
	  //  j  has not yet been in a component before  
	  //  add a new component  
	  numco ++;
	  co1[i] = co2[j] = numco ;
	  firstedge[numco] = newedge ;
	  edgelist[newedge].nextedge  = 0;
	}
	else { /* j  is already in a component: add  i  to j's
		  component, adding list elements in front */
	  co1[i] = jco ;
	  edgelist[newedge].nextedge  = firstedge[jco];
	  firstedge[jco] = newedge;
	}
      }
      else { // i  is already in a component 
	if (jco == 0) {
	  //  j  has not yet been in a component before  
	  //  add  j  to  i's component  
	  co2[j] = ico ;
	  edgelist[newedge].nextedge  = firstedge[ico];
	  firstedge[ico] = newedge;
	}
	else { // i  and  j  are already in components  
	  if (ico == jco) {
	    // i, j  in same component: just add the current edge 
	    edgelist[newedge].nextedge  = firstedge[ico];
	    firstedge[ico] = newedge;
	  }
	  else { /*  i  and  j  in different components:  
		     merge these by traversing the edgelists
		     and updating components of all incident nodes
		     (this is wasteful since only nodes need be
		     updated, not edges)  */
	    int e, newco, oldco ;
	    if (ico < jco) { newco = ico; oldco = jco; }
	    else           { newco = jco; oldco = ico; }
	    // insert the current edge 
	    edgelist[newedge].nextedge= firstedge[oldco] ;
	    e = newedge ; 
	    while (1) {
	      co1[edgelist[e].node1] = co2[edgelist[e].node2] = newco ;
	      if (edgelist[e].nextedge == 0) break;
	      e = edgelist[e].nextedge;
	    }
	    //  e  is now the last edge in the updated list  
	    edgelist[e].nextedge = firstedge[newco] ;
	    firstedge[newco] = newedge ;
	    /* oldco is unused now: reuse it if it was the 
	       last component, otherwise just leave empty */
	    if (oldco == numco) numco-- ;
	    firstedge[oldco] = 0;
	  }
	}
      }
    }
  }  // end scanning input 
  return numco;
}


// -------------------------------------------------- 
void EnumCliques::outCLIQUE(int clique1[], int cliqsize1, 
			    int clique2[], int cliqsize2,
			    int orignode1[MAXM],
			    int orignode2[MAXN]
			    ) 
  // outputs  CLIQUE  using the original node numbers in  orignode
  
{
  if (cliqsize1>0 && cliqsize2>0) {
    int i;
    printf("{") ;
    for (i=0; i<cliqsize1; i++) {
      printf("%d", orignode1[clique1[i]]);
      if (i<cliqsize1-1) printf(", "); 
    }
    printf("}  x  {") ;
    //  the  "x"  in the output symbolizes the product set 
    
    for (i=0; i<cliqsize2; i++) {
      printf("%d", orignode2[clique2[i]]);
      if (i<cliqsize2-1) printf(", "); 
    }
    printf("}\n");
  }
}

// -------------------------------------------------- 
void EnumCliques::workonco(int numco,
			   gArray<int> &firstedge,
			   gArray<edge> &edgelist
			   )
  /* works on the edgelists as generated by  getconnco
     it processes each component by computing its maximal cliques 
     pre : firstedge[1..numco], if nonzero, points to a connected component
     in edgelist
     post: all components are processed
  */
{
  int orignode1[MAXM];
  int orignode2[MAXN];
  bool connected[MAXM][MAXN];
  int m; int n;   // graph dimensions 
  
  int stk[STKSIZE];  // stack 
  int tos;  // top of stack 
  int clique1[MAXM], clique2[MAXN];
  // CLIQUE for first and second node class  
  
  int co;
  int countco = 0;
  
  for (co=1; co <= numco; co++) 
    if (firstedge[co]) {
      // found a nonzero component list 
      countco ++ ;
      printf("\nConnected component %d:\n", countco) ;
      
      genincidence(firstedge[co], edgelist,
		   orignode1, orignode2, connected, &m, &n);
      
      /* compute the cliques of the component via  extend;
	 initialize stack with the full sets of nodes
	 and empty sets CAND and NOT  */
      tos = 0;
      {
	int i ;
	for (i=0; i<m; i++)  stk[tos++] = i;   // CAND1 = NODES1 
	for (i=0; i<n; i++)  stk[tos++] = i;   // CAND2 = NODES2 
      }
      extend(stk, connected, clique1, 0, clique2, 0,
	     0, 0, m, m, m, m+n, tos, orignode1, orignode2);
    }
}


// ----- the following are unused TEST ROUTINES ----- 
// -------------------------------------------------- 
void EnumCliques::getgraph(bool connected[MAXM][MAXN], int *m, int *n)
  /* pre:  graph edges as pairs of nonnegative integers on standard input
     edges with nodes <0 or >=MAXM/2  will be rejected
     with a warning message
     post: connected[i][j] = true for the edges (i,j) of the bipartite
     graph, nodes numbered  0..*m-1  and  0..*n-1
     m <= MAXM,  n <= MAXN
  */
{ 
  int i, j;
  for (i=0; i<MAXM; i++)
    for (j=0; j<MAXN; j++)
      connected[i][j] = false;
  *m = *n = 0;
  while (scanf("%d %d", &i, &j) != EOF) {
    if (i < 0 || i>= MAXM || j<0 || j>=MAXN)
      printf("Edge (%d, %d) not in admitted range (0..%d, 0..%d), rejected\n",
	     i,j, MAXM-1, MAXN-1) ;
    else {
      connected[i][j] = true ;
      *m = MAX(*m, i+1) ;
      *n = MAX(*n, j+1) ;
    }
  }
}
// -------------------------------------------------- 
void EnumCliques::outgraph(
			   int orignode1[MAXM],
			   int orignode2[MAXN],
			   bool connected[MAXM][MAXN],
			   int m,
			   int n
			   )
  /* prints the graph incidence matrix on standard output
     including information about original node numbers */
{
  int i, j;
  printf("\nConnected component: ") ;
  printf("%d columns of right hand side nodes are\n       ", n) ;
  for (j=0; j<n; j++)
    printf("%d ", orignode2[j]);
  printf("\nincidence matrix with %d rows:\n", m) ;
  for (i=0; i<m; i++){
    printf("%5d:", orignode1[i]);
    for (j=0; j<n; j++)
      printf("%2d",  connected[i][j]);
    printf("\n");
  }
}

gOutput& operator << (gOutput& s, const edge& y)
{
  s << "\n( " << y.node1 << " " << y.node2 << " " << y.nextedge << " )";
  return s;
}

#include "base/garray.imp"
template class gArray<edge>;