/***************************************************************************
                         GoodPartitionsOfForests.cpp
    List all the good partitions of a set of forests whose mutual subset
                             relations are given
                             -------------------
    begin                : Sun Feb 12 2012
    copyright            : (C) 2012 by Chris Austin
    email                : chris@chrisaustin.info
 ***************************************************************************/

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

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <iostream>
#include <cstdlib>

const int N = 100;

void findnextGSF(bool subsetrels[N][N], bool alrdusdvec[N], int nforest, int& bt, int& tp);

using namespace std;

int main(int argc, char *argv[])
{
  // argc is total number of words in command line
  // argv[] is array of pointers to the command line words

  bool subsetrels[N][N];  // true if forest i is a subset of forest j
  bool alreadyused[N][N], alrdusdvec[N], nomoreforests;
  int i, j, b[N], t[N], nforest, reviseGSF, bt, tp, numgp = 0;
  
  cin >> nforest;
  if ( nforest > N )
  {
    cout << nforest << " > " << N << endl;
    exit (EXIT_FAILURE);
  }
  
  i = 0;
  while ( i < nforest )
  {
    j = 0;
    while ( j < nforest )
    {
      cin >> subsetrels[i][j++];
    }
    i++;
  }
  
  i = 0;
  while ( i < nforest )
  {
    j = 0;
    while ( j < nforest )
    {
      cout << subsetrels[i][j++] << " ";
    }
    cout << endl;
    i++;
  }
  cout << endl;
  
  i = 0;
  while ( i < nforest )
  {
    alreadyused[0][i++] = false;
  }

  reviseGSF = 0;
  t[reviseGSF] = b[reviseGSF] = -1;
  while ( reviseGSF >= 0 )   // we go through this loop once for each good partition found
  {
    i = reviseGSF;
    while ( i <= nforest )
    {
      b[i + 1] = t[i + 1] = -1;
      i++;
    }
    
    nomoreforests = false;
//    bt = tp = -1;
    while ( !nomoreforests  && ( reviseGSF >= 0 ) )
    {
      i = 0;
      while ( i < nforest )
      {
        alrdusdvec[i] = alreadyused[reviseGSF][i];
        i++;
      }
    
      bt = b[reviseGSF];
// cout << "bt = " << bt;
      tp = t[reviseGSF];
// cout << " tp = " << tp << " before call" << endl;
      findnextGSF(subsetrels, alrdusdvec, nforest, bt, tp);
// cout << "bt = " << bt << ", tp = " << tp << ", reviseGSF = " << reviseGSF << endl;
      if ( bt >= 0 )
      {
        b[reviseGSF] = bt;
        t[reviseGSF] = tp;
        reviseGSF++;
// cout << "[";
        i = 0;
        while ( i < nforest )
        {
          alreadyused[reviseGSF][i] = alrdusdvec[i];
// cout << alrdusdvec[i] << ",";
          i++;
        }
// cout << "]" << endl;
        
        i = reviseGSF;
        while ( i <= nforest )
        {
          b[i] = t[i] = -1;
          i++;
        }
        
        // see if there are any more unused forests
        
        nomoreforests = true;
        i = 0;
        while ( i < nforest )
        {
          if ( alreadyused[reviseGSF][i] == false ) nomoreforests = false;
          i++;
        }
      }
      else
      {
        reviseGSF--;
        if ( reviseGSF < 0 ) cout << "No more good partitions" << endl;
      }
    }
    
    if ( reviseGSF >= 0 )
    {
      i = 0;
      cout << "{";
      while ( ( i < nforest ) && ( b[i] >= 0 ) )
      {
        if ( i >= 1 ) cout << ", ";
        cout << "(" << b[i] << "," << t[i] << ")";
        i++;
      }
      cout << "}" << endl;
      numgp++;
      reviseGSF--;
    }
    
  }
  cout << numgp << " good partitions of the " << nforest << " forests found" << endl;
  
  return 0;
}

// find the next good set of forests.  bt is -1 if tp not used before, else prev bt

void findnextGSF(bool subsetrels[N][N], bool alrdusdvec[N], int nforest, int& bt, int& tp)
{
  int i, j;
  bool iscand, notfound;
  
  if ( tp < 0 )
  {
    // find the topforest, it will be the first maximal forest of the unused forests
    
    i = 0;
    notfound = true;
    while ( ( i < nforest ) && notfound )
    {
      j = 0;
      iscand = true;
      if ( alrdusdvec[i] ) iscand = false;
      while ( j < nforest )
      {
        if ( ( j != i )  && !alrdusdvec[j] && subsetrels[i][j] ) iscand = false;
        j++;
      }
      if ( iscand ) notfound = false;
      else i++;
    }
    if ( !notfound ) tp = i;
  }
  
  if ( tp >= 0 )
  {
    // find first subforest of max forest we have not tried already
  
    i = bt + 1;
    notfound = true;
    while ( ( i < nforest ) && notfound )
    {
      if ( !alrdusdvec[i] && subsetrels[i][ tp ] ) notfound = false;
      else i++;
    }
    if ( !notfound )
    {
      bt = i;
      
      // Strike out all members of the GSF just found
      i = 0;
      while ( i < nforest )
      {
        if ( ( subsetrels[bt][i] ) && ( subsetrels[i][tp] ) ) alrdusdvec[i] = true;
        i++;
      }
    }
    else bt = -1;     // this indicates that no further GSF with that topforest was found
  }
}