#include "graph.h"
#include "graph-transitive.h"

/*
** Not a public function, but defined in graph.c
*/
extern SET *Graph_IsCombClique(CLIQUE *c);


/**************************************************************************
**
** Clique and Indep sets on Transitives.
**
**************************************************************************/

/*
** Finding k-Cliques on K-transitive graphs: every vertex is similar to
** every other, and has degree K.  So rather than searching all
** Choose(n,k), we can fix one vertex and only look at the induced
** subgraph on it's neighbors.  If there is a clique at all, then
** every vertex is a member of a similar clique.  Thus when looking for
** k-cliques in a K-transitive graph, it suffices to look for
** (k-1)-cliques among the K neighbors of vertex 0.
*/
CLIQUE *GraphTransitiveKnFirst(GRAPH *G, int k)
{
    unsigned K;
    CLIQUE *c;

    assert(k <= G->n);
    if(k == 0)
	return NULL;

    c = (CLIQUE*)Calloc(1,sizeof(CLIQUE));
    c->G = GraphCopy(NULL, G->n);
    c->cliqueSize = k-1;
    c->inducedArray = Calloc(G->n, sizeof(c->inducedArray[0]));
    K = SetToArray(c->inducedArray, G->A[0]);
    c->combArray = Calloc(k-1, sizeof(c->combArray[0]));
    c->combin = CombinZeroth(K, k - 1, c->combArray);
    c->set = SetAlloc(G->n);
    if(Graph_IsCombClique(c) || GraphKnNext(c))
	return c;
    /* else */
    GraphCliqueFree(c);
    return NULL;
}

CLIQUE *GraphTransitiveInFirst(GRAPH *G, int k)
{
    static GRAPH Gbar;  /* non re-entrant! */
    GraphComplement(&Gbar, G);
    return GraphTransitiveKnFirst(&Gbar, k);
}


Boolean GraphTransitiveKnContains(GRAPH *g, int k)
{
    CLIQUE *c = GraphTransitiveKnFirst(g, k);
    if(c)
	GraphCliqueFree(c);
    return c != NULL;
}

Boolean GraphTransitiveInContains(GRAPH *g, int k)
{
    CLIQUE *c = GraphTransitiveInFirst(g, k);
    if(c)
	GraphCliqueFree(c);
    return c != NULL;
}


/* Algorithms for 2-Layered Circulants */

#if 0
Boolean GraphTransitive2KnContains(GRAPH *g, int k)
{
    static GRAPH Gswap; /* NOT RE-ENTRANT! */
    int i, j, n = g->n/2; /* n = number of vertices PER LAYER */
    assert(2*n == g->n);

    /* First check neigbors of node 0, then neighbors of node n
     * Note that we can "cheat" the GraphTransitiveKnContains code
     * because it doesn't check if the graph is actually a circulant,
     * and that the code to check if node 0 is in a Clique of size k
     * works just fine even if node 0 is in a layered circulant.
     * However, we still (below) need to check node n as well.
     */
#error need to convert from here down, from SMALL_GRAPH to GRAPH datatypes!
    if(SmallGraphTransitiveKnContains(g, k))
	return true;

    /* Now check the neighbors of node n.  We swap the layers and
     * use the same trick as above. */
    Gswap.n = g->n;
    SmallGraphEdgesAllDelete(&Gswap);
    for(i=0; i<n; i++) for(j=0; j<n; j++)
    {
	/* Connect the layers to each other */
	if(SmallGraphAreConnected(g, i, n+j))
	{
	    assert(SmallGraphAreConnected(g, n+i, j)); /* verify g is a layered circulant */
	    SmallGraphConnect(&Gswap, i, n+j);
	    SmallGraphConnect(&Gswap, n+i, j);
	}

	/* Now swap the layers themselves */
	if(SmallGraphAreConnected(g, i, j))
	    SmallGraphConnect(&Gswap, n+i, n+j);
	if(SmallGraphAreConnected(g, n+i, n+j))
	    SmallGraphConnect(&Gswap, i, j);
    }
    return SmallGraphTransitiveKnContains(&Gswap, k);
}

Boolean SmallGraphTransitive2InContains(SMALL_GRAPH *g, int k)
{
    static SMALL_GRAPH Gbar;  /* non re-entrant! */
    SmallGraphComplement(&Gbar, g);
    return SmallGraphTransitive2KnContains(&Gbar, k);
}
#endif

#if 0 /* DOESN'T WORK!!! */

/************************************************************************
**                                                                     **
**                  Graph Isomorphism on Transitives                   **
**                                                                     **
**  If G1 and G2 are transitive, then G1 is isomorphic to G2 iff       **
** the neighborhood of v1 \in G1 is isomorphic to the neighborhood of  **
** v2 \in G2                                                           **
**                                                                     **
************************************************************************/

Boolean SmallGraphTransitivesIsomorphic(SMALL_GRAPH *G1, SMALL_GRAPH *G2)
{
    SMALL_GRAPH neighV1, neighV2;

    SmallGraphInduced(&neighV1, G1, G1->A[0]);
    SmallGraphInduced(&neighV2, G2, G2->A[0]);

    return SmallGraphsIsomorphic(&neighV1, &neighV2);
}

#endif


/************************************************************************
**
**                         GENERATING CIRCULANTS
**
** The algorithm: Each vertex is treated identically.  For each of the n
** vertices, we want to go through the Choose (floor(n/2), k) possible
** other vertices we can connect it to.
**
************************************************************************/

GRAPH_CIRCULANTS *SmallGraphCirculantZeroth(int n, int r)
{
    return SmallGraphCirculantIth(n, r, 0);
}

/***********************************************************************
Observation:
If n is odd // n-1 is even
    r must be even, because no node has another "directly across" from it.
else // n is even
    r is odd iff 0 is connected to n/2.

THUS:
if n is odd
    assert r is even.
    there are Choose((n-1)/2, r/2) connections to try on the right side
	of the graph, and we connect the left side in a mirror image.
else // n is even
    if r is odd // 0 must be connected to n/2, leaving
	Choose((n-2)/2, (r-1)/2) possibilies to try on the right side...
    else // r is even, 0 must NOT be connected to n/2
	Choose(n/2-1, r/2) possibilies...
***********************************************************************/

static GRAPH_CIRCULANTS *SmallGraphCirculantConnect(GRAPH_CIRCULANTS *rrg)
{   
    int n = rrg->G->n, r = rrg->G->degree[0], i, last;
    SSET s = SSetFromArray(rrg->C->m, rrg->C->array);

    /* COMBIN numbers things from 0.  Also, the "matrix" numbers bits
    ** from left to right, but machine bits are numbered right to left.
    ** Conceptually the row of the matrix is being rotated to the right.
    */
    s = RotLeft(SSET, s,n,1);
    assert((s & 1) == 0);   /* ensure no self-connection */

    if(r&1) /* if r is odd, then n must be even and 0 is connected to n/2 */
    {
	assert((n&1) == 0);
	SSetAdd(s, n/2);
    }

    /* s now contains the connections of 0 to the right hand side of the
    ** graph.  Now add the symmetrical connections.
    */
    last = (n & 1) ? n/2 : n/2 - 1; /* one before the 6 o'clock vertex */
    for(i=1; i <= last; i++)
	if(SSetIn(s, i))
	    SSetAdd(s, n-i);

    /* Each node is identical: so we just rotate the bit vector
    ** representing the adjacency list by 1 for each new row.
    */
    for(i=0; i<n; i++)
    {   
	rrg->G->A[i] = s;
	s = RotLeft(SSET, s,n,1);
    }

    /* The above method only connects in one direction; we need to ensure
    ** (i,j) \in E <=> (j,i) \in E.
    */
    for(i=0; i<n; i++)
    {   
	int j;
	for(j=i+1; j<n; j++)
	    assert(!SmallGraphAreConnected(rrg->G, i, j) ==
		    !SmallGraphAreConnected(rrg->G, j, i));
    }
    for(i=0; i<n; i++)
    {   
	int card = SSetCardinality(rrg->G->A[i]);
	assert(r == rrg->G->degree[i]);
	assert(card == r);
    }
    return rrg;
}


GRAPH_CIRCULANTS *SmallGraphCirculantIth(int n, int r, unsigned long long I)
{
    GRAPH_CIRCULANTS *rrg = (GRAPH_CIRCULANTS*)Calloc(1,sizeof(GRAPH_CIRCULANTS));
    int i;
    unsigned *array = (unsigned*)Calloc(sizeof(unsigned), r/2);
    /*
    ** if n is even, r may be even or odd; else n is odd => r must be even.
    ** In other words, (n odd => r even) <==> (n even || r even)
    */
    assert((n & 1) == 0 || (r & 1) == 0);

    rrg->G = SmallGraphAlloc(n);
    /* r/2 really means floor(r/2), which is what we want */
    rrg->C = CombinIth(((n & 1) ? (n-1)/2 : n/2-1), r/2, array, I);
    for(i=0; i<n; i++)
	rrg->G->degree[i] = r;
    return SmallGraphCirculantConnect(rrg);
}


GRAPH_CIRCULANTS *SmallGraphCirculantNext(GRAPH_CIRCULANTS *rrg)
{
    if(CombinNext(rrg->C))
	return SmallGraphCirculantConnect(rrg);
    return NULL;
}

void SmallGraphCirculantFree(GRAPH_CIRCULANTS *rrg)
{
    SmallGraphFree(rrg->G);
    Free(rrg->C->array);
    CombinFree(rrg->C);
    Free(rrg);
}


/* From Nema Press's 2006 course project */

static Boolean coprime(int a,int b){
    if(gcd(a,b) == 1)
	return true;
    else return false;
}

static Boolean smallsym(int multiplier, int pattern[], int length, int n)
{
    //Test whether multiplying by m makes pattern smaller.
    
    Boolean smallable=false;
    int i;
    for(i=0; i<length; i++)
    {
	
	int j = ((i+1)*multiplier)%n - 1;
	
	if(j >= length)
	    j = n - j - 2;
	assert(i >= 0 && i < length);
	assert(j >= 0 && j < length);
	if ((pattern[j] > pattern[i]) || (pattern[j] == -1))
	{
		return false;
	}
	else if( pattern[j] < pattern[i])
	    return true;
    }
    return smallable;  //returns false, if you never find a multiplier that increases the lexicographical value
}

static Boolean smallerable(int pattern[], int length, int n)
{
    //Test whether some symmetry makes the current pattern smaller.
    int multiplier;
    for(multiplier=2; multiplier <(n+1)/2; multiplier++ )
    {
	if (coprime(multiplier,n)){
#if 0
	    if(multiplier==13)
		    printf("The multiplier is 13");
#endif
	    if (smallsym(multiplier, pattern, length, n))
		return true;  //there exists a multiplier for which the pattern could be lexicographically smaller
	}
    }
    return false;
}
/*
 circulants(): Works only for the n= prime case and for the n= prime square-free 
	case.  This function takes in a number of nodes n and computes either the 
	number of connection set classes using symmetries made by multipliers prime to n, 
	or may also store representative connection sets from each connection set class
	as they are computed in a two dimensional array.
 Parameters: int n- the number of nodes in the circulant
			 int ncs-the number of connection set classes, this parameter is attained
					 from previously running the function, and will only
					 useful when the function is used to list and store the 
					 connection sets. 
			 boolean simply_count-when set to true, this flag designates that
				the function will count the connection set representatives, when set
				to false, the function will also be stored.
			char cs[][]- a 2-d array used to store the representatives of each 
				connection set class.
 Returns: The number of connection set classes that pertain to n, which is synonymous
	with the number of rows in the 2 dimensional array used to store the representatives.
*/
static int circulants(int n, int ncs, Boolean simply_count, char cs[ncs][(n/2)])
{
    /*
    Code written in Python originally by Dr Eppstein, translated to C
    ************************************************
    Generate sequence of connection patterns for n-circulants.
    The general idea is a backtracking search that fills in one
    bit of the connection pattern at a time. We represent the pattern
    internally as an array of values in {-1,0,1}; -1 means not set yet,
    0 means disconnected, 1 means connected.  After each step of
    the search, we test whether some possible symmetry would lead
    to a lexicographically earlier pattern; if so, we backtrack.

    We only consider symmetries formed by multiplication by m, with
    gcd(m,n) = 1; if other symmetries exist, we may report some circulants
    more than once.  This appears to happen first for n = 16; we
    report 88 circulants while the number is listed as 84 in
http://www.research.att.com/projects/OEIS?Anum=A049287

This is an unoptimized proof of concept; significant speedups are
likely by (1) precomputing a table of the symmetries, (2) using
data structures to keep track of how far each symmetry has already
been tested, and (3) translating to a faster language than Python.
     */

    int length=n/2;
    int pattern[length];
    int pos = 0;
    int row=-1;

    //initialize the connection set pattern
    int i;
    for(i=0; i<n/2; i++)
	pattern[i]=-1;
    //initialize the storing array, but only if we are enumerating the connection sets

    if(!simply_count)
    {
	if(cs ==NULL)//error handling
	{	
	    fprintf(stderr, "Fill is set, but the array is null");
	    return -2;
	}
	else
	{
	    int j;
	    for(i=0; i<ncs; i++)
		for(j=0; j<n/2; j++)
		    cs[i][j]=-1; 
	}
    }
   

    while(pos >= 0)
    {
	if(pos == length)
	{
	    //we have found a new representative for a connection set class.  Count this
	    //class and store the representative, if simply_count==false
	    row++;
	    if(!simply_count)
	    {//fill the array with the row specified right now
		int col=0;
		for(i=0; i<length; i++)
		{
		    //wherever there is a 1 in the pattern, contribute that index i to this row's array
		    if (pattern[i] == 1)
		    {
			cs[row][col]=i;
			col=col+1;    
		    }
		}
	    }
	    pos -= 1;
	}
	else
	{
	    pattern[pos] += 1;
	    if (pattern[pos] > 1)
	    {  
		pattern[pos] = -1;  //backtracking, reset last changed index
		pos -= 1;           //go back to the parent of this node
	    }
	    else if (!smallerable(pattern, length, n))
	    {
		pos += 1; //continue building the connection set, if can't get lexicographically smaller
	    }
	}
    }
    return (row+1);//returns the number of connection sets in the array
}

static char *ary[MAX_SSET+1];	/* maximum graph size */
static long num_ary[MAX_SSET+1];

static void init_ary(int n)
{
    int nd;

    assert(n >= 0 && n <= MAX_SSET);

    if(ary[n])
	return;
    
    num_ary[n] = circulants(n, 1, true, NULL);  // number of connection sets, or rows for the array
    ary[n] = Malloc(num_ary[n]*(n/2));
    nd = circulants(n, num_ary[n], false, ary[n]);
    assert(nd == num_ary[n]);
}


GRAPH_CIRCULANTS *SmallGraphCirculantUniqueIth(int n, unsigned long I)
{
    int j, a_n;
    unsigned *array = (unsigned*)Calloc(sizeof(unsigned), n/2);
    GRAPH_CIRCULANTS *rrg = (GRAPH_CIRCULANTS*)Calloc(1,sizeof(GRAPH_CIRCULANTS));

    init_ary(n);
    assert(I < num_ary[n]);
    rrg->i = I;
    rrg->G = SmallGraphAlloc(n);
    rrg->C = CombinZeroth(n, n/2, array);	/* Just to allocate it */

    a_n = 0;
    for(j=0; j<n/2; j++)
	if(ary[n][I*(n/2)+j]!=-1)
	    array[a_n++] = ary[n][I*(n/2)+j];
    rrg->C->m = a_n;

    // Just to compute degree[0]
    for(j=0; j<a_n; j++)
    {
	SmallGraphConnect(rrg->G, 0, array[j]);
	SmallGraphConnect(rrg->G, 0, n-array[j]);
    }
    return SmallGraphCirculantConnect(rrg);
}

GRAPH_CIRCULANTS *SmallGraphCirculantUniqueZeroth(int n)
{
    init_ary(n);
    return SmallGraphCirculantUniqueIth(n, 0L);
}

GRAPH_CIRCULANTS *SmallGraphCirculantUniqueNext(GRAPH_CIRCULANTS *rrg)
{
    int I, j, a_n, n = rrg->G->n;
    assert(ary[n]);
    I = ++(rrg->i);
    if(I >= num_ary[n])
	return NULL;

    a_n = 0;
    for(j=0; j<n/2; j++)
	if(ary[n][I*(n/2)+j]!=-1)
	    rrg->C->array[a_n++] = ary[n][I*(n/2)+j];
    rrg->C->m = a_n;

    // Just to compute degree[0]
    for(j=0; j<a_n; j++)
    {
	SmallGraphConnect(rrg->G, 0, rrg->C->array[j]);
	SmallGraphConnect(rrg->G, 0, n-rrg->C->array[j]);
    }
    return SmallGraphCirculantConnect(rrg);
}

void SmallGraphCirculantUniqueFree(GRAPH_CIRCULANTS *rrg)
{
    SmallGraphFree(rrg->G);
    Free(rrg->C->array);
    CombinFree(rrg->C);
    Free(rrg);
}
