clique.cc

Gambit 是一个游戏库理论软件

//
// $Source: /home/gambit/CVS/gambit/sources/nash/clique.cc,v $
// $Date: 2002/08/27 18:29:37 $
// $Revision: 1.2 $
//
// DESCRIPTION:
// Maximal cliques and solution components via von Stengel's algorithm
//
// This file is part of Gambit
// Copyright (c) 2002, The Gambit Project
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
//

#include "clique.h"
#include "base/base.h"

// to compile as standalone,compile with -DSTANDALONE

#ifdef STANDALONE
// =============== main =============== 

int main()
{
  gArray<edge> edgelist1(MAXEDGES);
  
  int i,j, count = 0;
  while (scanf("%d %d", &i, &j) != EOF) {
    count ++;
    edgelist1[count].node1=i;
    edgelist1[count].node2=j;
  }
  gArray<edge> edgelist(count);
  for(int i=1;i<=count;i++) {
    edgelist[i].node1 = edgelist1[i].node1;
    edgelist[i].node2 = edgelist1[i].node2;
  }
  EnumCliques clique(edgelist,MAXINP1,MAXINP2);
  return 1 ;
}

// =============== end main =============== 
#endif

// -------------------------------------------------- 

EnumCliques::EnumCliques(gArray<edge> &edgelist,int maxinp1,int maxinp2 ) 
  : firstedge(MIN(maxinp1,maxinp2)+1), maxinp1(maxinp1), maxinp2(maxinp2)
{
  int numco = getconnco(firstedge, edgelist);
  workonco(numco, firstedge, edgelist) ;
  
};

EnumCliques::~EnumCliques()
{
};

void EnumCliques::
candtry1 (int stk[], // stack 
	  bool connected[MAXM][MAXN],
	  int cand,  // the candidate from NODES1  to be added to CLIQUE 
	  int clique1[], int cliqsize1,  // CLIQUE so far in NODES1 
	  int clique2[], int cliqsize2,  // CLIQUE so far in NODES2 
	  int sn1, int *sc1, int ec1,   // start NOT1, start CAND1, end CAND1 
	  int sn2, int sc2, int ec2,   // start NOT2, start CAND2, end CAND2 
	  int tos,  // top of stack 
	  int orignode1[MAXM],
	  int orignode2[MAXN]
	  )
  /* recurses down by moving  cand  from  CAND1  to  clique1  and
     then to NOT1  after extension.
     clique1  is extended by  cand  where all points in  NOT2 and CAND2 
     relate to  cand.
     pre:  cand  is in CAND1
     post: cand  is moved from  CAND1  to  NOT1
     CAND1 may be shuffled,  o/w stack unchanged 
  */
{
  int i, j, snnew, scnew, ecnew;
  
  clique1[cliqsize1++] = cand ;
  // remove  cand  from CAND1 by replacing it with the last element of CAND1 
  for (i=*sc1; i<ec1; i++)
      if (cand == stk[i]) {
         stk[i] = stk[--ec1] ;
         break ;
         }
  // stk[ec1] is free now but will after extension be needed again 
  // fill new sets NOT2, CAND2 
  snnew = tos ;
  for (j=sn2; j<sc2; j++) 
    if (connected[cand][stk[j]])
      stk[tos++] = stk[j] ;
  scnew = tos ;
  for (j=sc2; j<ec2; j++) 
    if (connected[cand][stk[j]])
      stk[tos++] = stk[j] ;
  ecnew = tos ;
  
  extend(stk, connected, clique1, cliqsize1, clique2, cliqsize2,
	 sn1, *sc1, ec1, snnew, scnew, ecnew, tos, orignode1, orignode2);
  
  /* remove  cand  from  clique1,
     put  cand  into  NOT1  by increasing  *sc1  and moving
     the node at position  *sc1  to the end of CAND1 */
  // The following lines modified since ec1 and cliqsize1 are
  // never used after the increments
  //cliqsize1-- ;
  //stk[ec1++] = stk[*sc1] ;
  stk[ec1] = stk[*sc1];
  stk[*sc1] = cand ;
  (*sc1)++ ;
}

// -------------------------------------------------- 
void EnumCliques::
candtry2 (int stk[], // stack 
	  bool connected[MAXM][MAXN],
	  int cand,  // the candidate from NODES2  to be added to CLIQUE 
	  int clique1[], int cliqsize1,  // CLIQUE so far in NODES1 
	  int clique2[], int cliqsize2,  // CLIQUE so far in NODES2 
	  int sn1, int sc1, int ec1,   // start NOT1, start CAND1, end CAND1 
	  int sn2, int *sc2, int ec2,   // start NOT2, start CAND2, end CAND2 
	  int tos,  // top of stack 
	  int orignode1[MAXM],
	  int orignode2[MAXN]
	  )
  // recurses down by moving  cand  from  CAND2  to  clique2  and
  // then to NOT2  after extension;
  // clique2  is extended by  cand  where all points in  NOT1 and CAND1 
  // relate to  cand.
  // pre:  cand  is in CAND2
  // post: cand  is moved from  CAND2  to  NOT2
  // CAND2 may be shuffled,  o/w stack unchanged
  
{
  int i, j,  snnew, scnew, ecnew;
  
  clique2[cliqsize2++] = cand ;
  // remove  cand  from CAND2 by replacing it with the last element of CAND2 
  for (j=*sc2; j<ec2; j++)
      if (cand == stk[j]) {
	 stk[j] = stk[--ec2] ;
	 break ;
	 }
  // stk[ec2] is free now but will after extension be needed again 
  // fill new sets NOT1, CAND1 
  snnew = tos ;
  for (i=sn1; i<sc1; i++) 
    if (connected[stk[i]][cand])
      stk[tos++] = stk[i] ;
  scnew = tos ;
  for (i=sc1; i<ec1; i++) 
    if (connected[stk[i]][cand])
      stk[tos++] = stk[i] ;
  ecnew = tos ;
  
  extend(stk, connected, clique1, cliqsize1, clique2, cliqsize2,
	 snnew, scnew, ecnew, sn2, *sc2, ec2, tos, orignode1, orignode2);
  
  // remove  cand  from  clique2,
  // put  cand  into  NOT2  by increasing  *sc2  and moving
  // the node at position  sc2  to the end of CAND1 

  // The following lines modified since ec2 and cliqsize2 are not used
  // after the increments
  // cliqsize2-- ;
  // stk[ec2++] = stk[*sc2] ;
  stk[ec2] = stk[*sc2];
  stk[*sc2] = cand ;
  (*sc2)++ ;
}

// -------------------------------------------------- 
void EnumCliques::
extend (int stk[], // stack 
	bool connected[MAXM][MAXN],
	int clique1[], int cliqsize1,  // CLIQUE so far in NODES1 
	int clique2[], int cliqsize2,  // CLIQUE so far in NODES2 
	int sn1, int sc1, int ec1,   // start NOT1, start CAND1, end CAND1 
	int sn2, int sc2, int ec2,   // start NOT2, start CAND2, end CAND2 
	int tos,   // top of stack,   tos >= ec1, ec2  
	int orignode1[MAXM],   // original node numbers as input 
	int orignode2[MAXN]
	)
  /* extends the current set CLIQUE or outputs it if
     NOT and CAND are empty.
     
     pre:  CLIQUE = clique1[0, cliqsize1], clique2[0, cliqsize2]
     NOT1 = stk[sn1, sc1],  CAND1= stk[sc1, ec1]   
     NOT2 = stk[sn2, sc2],  CAND2= stk[sc2, ec2]   
     sn1 <= sc1 <= ec1, sn2 <= sc2 <= ec2 
     all cliques extending  CLIQUE
     containing a node in  NOT1  or  NOT2  have already been generated
     post: output of all maximal cliques extending  CLIQUE  with
     candidates from  CAND1  or  CAND2  but not from NOT1, NOT2.
  */
{
  /* if no further extension is possible then  
     output the current CLIQUE if applicable, and return */
  
  if (sc1 == ec1 && sc2 == ec2) {
    //  CAND is empty  
    if (sn1 == sc1 && sn2 == sc2)
      //  NOT is empty, otherwise do nothing  
      outCLIQUE(clique1, cliqsize1, clique2, cliqsize2,
                orignode1, orignode2) ;
  }
  
  else {  //  CAND not empty 
    int cmax;  // maximal number of candidates on either side  
    int firstlist, savelist, tmplist, posfix ; // stack positions 
    int fixp;  // the fixpoint 
    int minnod ;
    bool bfound, bfixin1, bcandfix;
    
    cmax = MAX(ec1-sc1, ec2-sc2);  // the larger of |CAND1|, |CAND2|  
    
    // reserve two arrays of size cmax on the stack 
    firstlist = tmplist = tos;  tos += cmax;
    savelist = tos;  

    // tos is not used again.. 
    // tos += cmax;
    
    /* find fixpoint  fixp (a node of the graph) in  NOT  or  CAND
       which has the smallest possible number of disconnections  minnod 
       to CAND  */
    minnod = cmax + 1 ;
    
    // look for  fixp  in NODES1  
    findfixpoint(stk, connected, &savelist, &tmplist, &minnod,
		 sn1, ec1, sc2, ec2, 1, &bfixin1, &fixp, &posfix) ;
    bcandfix = (posfix >= sc1);
    
    // look for  fixp  in nodes2  
    findfixpoint(stk, connected, &savelist, &tmplist, &minnod,
		 sn2, ec2, sc1, ec1, 0, &bfound, &fixp, &posfix) ;
    
    if (bfound) {
      bfixin1 = false ;
      bcandfix = (posfix >= sc2);
    }
    
    /* now:  fixp     = the node that is the fixpoint,
       posfix   = its position on the stack,
       bfixin1  = fixp  is in NODES1
       bcandfix = fixp  is a candidate
       stk[savelist, +minnod] = nodes disconnected to fixp
       which are all either in CAND1 or in CAND2;
    */
    /*    top of stack can be reset to  savelist+minnod  where
	  if savelist  is the second of the two lists, recopy it
	  to avoid that stk[firstlist, +cmax] is wasted
    */
    if (savelist != firstlist) {int i;
    for (i=0; i < minnod; i++) 
      stk[firstlist + i] = stk[savelist + i];
    savelist = firstlist ;
    }
    tos = savelist + minnod;
    
    if (bfixin1) {int j;  // fixpoint in NODES1  
    if (bcandfix)      // fixpoint is a candidate 
      candtry1(stk, connected, fixp, 
	       clique1, cliqsize1, clique2, cliqsize2,
	       sn1, &sc1, ec1, sn2, sc2, ec2, tos, orignode1, orignode2);
    // fixpoint is now in NOT1, try all the nodes disconnected to it 
    for (j=0; j<minnod;  j++) 
      candtry2(stk, connected, stk[savelist+j],
	       clique1, cliqsize1, clique2, cliqsize2,
	       sn1, sc1, ec1, sn2, &sc2, ec2, tos, orignode1, orignode2);
    }
    else {int j;          // fixpoint in NODES2  
    if (bcandfix)      // fixpoint is a candidate 
      candtry2(stk, connected, fixp,
	       clique1, cliqsize1, clique2, cliqsize2,
	       sn1, sc1, ec1, sn2, &sc2, ec2, tos, orignode1, orignode2);
    // fixpoint is now in NOT2, try all the nodes disconnected to it 
    for (j=0; j<minnod;  j++) 
      candtry1(stk, connected, stk[savelist+j],
	       clique1, cliqsize1, clique2, cliqsize2,
	       sn1, &sc1, ec1, sn2, sc2, ec2, tos, orignode1, orignode2);
    }
  }  // end candidates not empty 
} 

// -------------------------------------------------- 
void EnumCliques::
findfixpoint(int stk[], // stack 
	     bool connected[MAXM][MAXN],
	     int *savelist,      // position of savelist on the stack 
	     int *tmplist,       // position of tmplist on the stack 
	     // might be swapped afterwards 
	     int *minnod,        // currently lowest no. of disconnections 
	     int sninspect, int ecinspect, /* range of stack positions
					      containing the nodes inspected 
					      as possible fixpoints */
	     int scother, int ecother,
	     // range of corresponding candidates on the other side  
	     bool binspect1,  // inspected nodes are in class1, o/w class2 
	     bool *bfound,  // a new lower no. of disconnections was found 
	     int *fixp,     // the new fixpoint, if *bfound = true  
	     int *posfix    // position of fixpoint on the stack, if *bfound 
	     )
  /* pre:  enough space on stack for the two lists  savelist,  tmplist
     post: *minnod contains the new minimum no. of disconnections
     stk[*savelist, +*minnod] contains the candidates disconnected to
     the fixpoint
  */
{
  int i,j, p ;
  int count ;
  int tmp ;
  *bfound = false ;
  
  for (i=sninspect; i<ecinspect; i++) {
    p = stk[i] ;
    count = 0;
    /* count number of disconnections to  p,  
       building up stk[tmplist+count] containing the
       disconnected points */
    for (j=scother; (j<ecother) && (count < *minnod); j++) {
      int k = stk[j] ;