/* k7test.c */
/************/
/* May 26, 2004								*/
/* This file has a function Prune to be used in conjuction with 	*/
/* Brendan McKay's package nauty 2.2. Copy this file into a directory	*/
/* that includes nauty 2.2, execute make geng and then execute	the 	*/
/* following 2-line command:						*/
/* gcc -o geng -O4 -DMAXN=32 -DPRUNE=Prune geng.c gtools.o nauty1.o \   */
/* 	nautil1.o naugraph1.o k7test.c					*/
/* That will recompile geng with the Prune function included. Now run	*/
/*	geng -d7 9							*/
/*	geng -d7 10							*/
/*	geng -d7 11							*/
/*	geng -d7 12							*/
/*	geng -d7 13							*/
/* The command geng -d7 <n> will generate all graphs on n vertices of 	*/
/* minimum degree at least 7 that:					*/
/* (1) have no K_7\cup K_1 minor and 					*/
/* (2) for every edge ab at least one of a,b has degree exactly 7	*/
/* Please refer to the nauty manual for description of the output	*/
/* format. You can convert the output to a more comprehensible form	*/
/* by running showg on it. A typical usage is				*/
/*	geng -d7 11 | showg						*/

#include <stdio.h>
#include <signal.h>
#include "nauty.h"

#define MAXVERT		15	/* maximum number of vertices in a graph */
#define MAXEDGE		110	/* maximum number of edges in a graph    */
#define t		7	/* testing K_t\cup K_1 minor 		 */
#define MINDEG		7	/* Prune graphs that have an edge with   */
				/* both ends of degree > MINDEG		 */

/* Prune will be called from geng.c */

Prune(graph *g,int n,int maxn)
{static int E1[MAXEDGE+1], E2[MAXEDGE+1];
 int i, j, count;
 set *gi;
 static int deg[MAXVERT+1];

 E1[0] = n;  /* number of vertices */
 E2[0] = 0;  /* number of edges */
 /* E1[i] and E2[i] will be the ends of edge i, i=1,2,...,E1[0] */

 for(i=0; i<n ; i++) {
   gi = GRAPHROW(g, i, 1);
   count=0;
   for(j=0; j<n; j++)
      if( ISELEMENT(gi,j) ) count++;
   deg[i]=count;
   for(j=0; j<i; j++)
      if( ISELEMENT(gi,j) ) {
         if( deg[i]> MINDEG && deg[j]>MINDEG ) return(1); 
            /* graph not edge-minimal */
         ++E2[0];
         E1[ E2[0] ] = i+1;
         E2[ E2[0] ] = j+1;
   } /* j */
 } /* i */
 if( E1[0]==maxn && TestGraph(E1, E2) ) return(2);
 return(0);
} /* Prune */

/* TestGraph will test if the graph with edges given by E1 and E2 as */
/* above has a minor isomorphic to K_t\cup K1                        */
/* It is assumed that E1[0]>t+1 */

int TestGraph(int *E1, int *E2)
{static int V[MAXVERT+1], contr[MAXVERT+1], uncontr[MAXVERT+1];
 int i, k, a, b, answer;

 for(i=1; i<=E1[0]; i++) V[i] = 0;
 /* This will record the forest of contracted edges. In each component     */
 /* V[a]=0 if a is the unique root; otherwise V[a] is the parent of a      */

 /* At the beginning of the loop below edges number contr[1],...,contr[k-1] */
 /* are contracted, and this is noted by the array V                        */
 contr[1] = 0;
 for(k=1; ; ) {
    contr[k]++;
    /* Have contracted k-1 edges, can contract E2[0]-contr[k]+1 more.    */
    /* The condition below says that if upon contracting all those edges */
    /* we end up with > t+1 vertices, then no need to pursue this        */
    if( E2[0]-contr[k]+k+t+1 < E1[0] ) {
       k--; 
       if(k==0) break;
       V[uncontr[k]] = 0;   /* Undo contraction of edge number contr[k] */
       continue;
    }

    /* Check if contraction of edge number contr[k] does not give loop  */
    i = contr[k];
    a = E1[i];
    while( V[a] ) a = V[a]; /* Find root of the component containing E1[i] */
    b = E2[i];
    while( V[b] ) b = V[b]; /* Find root of the component containing E2[i] */
    if( a==b ) continue; /* Contracting i-th edge gives loop */
    V[b] = a;        /* Record the contraction of edge number contr[k]     */
    uncontr[k] = b;  /* Keep record so we can easily undo this contraction */

    /* If there is room for contracting more edges, then do so */
    if( k+t+1 < E1[0] ) {
       contr[k+1]=contr[k];
       k++;
       continue;
    }
    
    /* Now we know that k+t+1 == E1[0]. Time to test K_t\cupK_1 minor */
    if(  TestContraction(E1, E2, V) ) return(1);
    V[uncontr[k]] = 0;   /* Undo contraction of edge number contr[k]  */
 } /* k */
 return(0);
} /* TestGraph */

int FindRoot(int V[], int a)
{
 while( V[a] )  a = V[a];
 return(a);
} /* FindRoot */

int TestContraction(int E1[], int E2[], int V[])
{static int M[MAXVERT+1][MAXVERT+1], compno[MAXVERT+1];
 int i, j, a, b, v, u, counter, comps;

 /* M will be the adjacency matrix of the contracted graph, M[i][j]  */
 /* will be used for i>j only, M[a][0] will be the degree of a       */
 for(i=1; i<=t+1; i++)
 for(j=0; j<i; j++)
    M[i][j]=0;

 /* Find number of components of graph of contracted edges */
 comps = 0;
 for(i=1; i<=E1[0]; i++) 
    if(V[i]==0)
       compno[i] = ++comps;

 /* For each vertex compute what component it belongs to */
 for(i=1; i<=E1[0]; i++)
    if(V[i]!=0)
       compno[i] = compno[FindRoot(V, V[i])];

 /* Find adjacency matrix of the contracted graph */
 for(i=1; i<=E2[0]; i++) {
   a = compno[E1[i]];
   b = compno[E2[i]];
   if( a==b ) continue; /* Gives loop */
   if( M[a][b] ) continue;
   if( a> b ) M[a][b] = 1;
   else M[b][a] = 1;
   M[a][0]++;
   M[b][0]++; 
 }

 /* Check if graph with incidence matrix M has K_t\cup K_1 subgraph */
 counter = 0; /* Will count # of vertices incident with a nonedge   */
 v = 0;	      /* The number of last vertex incident with >1 nonedge */
              /* or 0 if none found  */
 for(u=1; u<=comps; u++) {
    if( M[u][0]<t ) counter++;
    if( M[u][0]<t-1 ) {
       if(v) return(0); /* at least two vertices of antidegree >1 */
       v = u;
    }
 } /* u */

 if( v==0) {
    /* every vertex incident with at most one nonedge, and so graph has */
    /* K_t\cup K_1 minor if and only if complement is an edge           */
    if( counter>=3 ) return(0); /* complement not an edge */
    else return(1);
 }
 /* Now v is the unique vertex incident with >1 nonedges */
 for(i=2; i<=comps; i++)
 for(j=1; j<i; j++)
    if( i!=v && j!=v && M[i][j]==0 ) return(0);
 return(1);
} /* TestContraction */