#ifndef _SMALLGRAPH_H
#define _SMALLGRAPH_H

#include "misc.h"
#include "sets.h"
#include "combin.h"
#include <stdio.h>

/* Constructs for simple graphs, no self-loops: edge (i,i) never exists.
*/

typedef struct _smallGraph {
    /* vertices numbered 0..n-1 inclusive; n must be <= MAX_SSET (for now)*/
    int n;
    SSET A[MAX_SSET];   /* Adjacency Matrix */
    int degree[MAX_SSET];   /* degree of each v[i] == cardinality of A[i] */
} SMALL_GRAPH;

SMALL_GRAPH *SmallGraphAlloc(unsigned int n);
#define SmallGraphFree free
SMALL_GRAPH *SmallGraphEdgesAllDelete(SMALL_GRAPH *G);
SMALL_GRAPH *SmallGraphConnect(SMALL_GRAPH *G, int i, int j);
SMALL_GRAPH *SmallGraphDisconnect(SMALL_GRAPH *G, int i, int j);
SMALL_GRAPH *SmallGraphComplement(SMALL_GRAPH *Gbar, SMALL_GRAPH *G);
SMALL_GRAPH *SmallGraphUnion(SMALL_GRAPH *destination, SMALL_GRAPH *G1, SMALL_GRAPH *G2);
#define SmallGraphDegree(G,v) ((G)->degree[v])

/* Returns number of nodes in the the distance-d neighborhood, including seed.
 * nodeArray[0] always= seed, distArray[seed] always= 0.
 * distance = 0 implies no BFS, seed as only member of nodeArray, and return value 1.
 * Use distance >= G->n to ensure BFS will go out as far as possible.
 * Both arrays should have at least G->n elements; caller is reponsible for allocating them.
 * For each nodeArray[i], distArray[nodeArray[i]] is the distance from seed.
 * (Note that distArray[j] has an entry for EVERY node in the graph; only those
 * with indices j \in nodeArray have meaning.)
 * Also, worst-case runtime is O(n^2)... very bad, yes.. :-(
 */
int SmallGraphBFS(SMALL_GRAPH *G, int seed, int distance, int *nodeArray, int *distArray);

/*
** SmallGraphInduced_NoVertexDelete doesn't delete any vertices, it only deletes
** edges whose ends don't both appear in V.  SmallGraphInduced builds an entirely
** new graph in which also the vertices not in V are deleted; vertices
** are renumbered but ordering is conserved.
*/
SMALL_GRAPH *SmallGraphInduced_NoVertexDelete(SMALL_GRAPH *Gi, SMALL_GRAPH *G, SSET V);
SMALL_GRAPH *SmallGraphInduced(SMALL_GRAPH *Gi, SMALL_GRAPH *G, SSET V);

void SmallGraphPrintAdjMatrix(FILE *fp, SMALL_GRAPH *G);
SMALL_GRAPH *SmallGraphReadAdjMatrix(FILE *fp);

#define SmallGraphAreConnected(G,i,j) SSetIn((G)->A[i],(j))
#ifndef SmallGraphAreConnected
Boolean SmallGraphAreConnected(SMALL_GRAPH *G, int i, int j);
#endif

/*
** The following subroutines should be used with caution, because they take
** exponential time.  They look for cliques and independent sets of size n,
** respectively.  They return 0 if the requested property doesn't exist, or
** else an SSET containing the subgraph with the property requested.  Calling
** the appropriate SmallGraphNext* function returns the next in the list of
** Kn's or In's. 0 is returned when none are left.
*/
typedef struct _clique {
    SMALL_GRAPH *G;
    SSET sset;
    unsigned cliqueSize, combArray[MAX_SSET], inducedArray[MAX_SSET];
    COMBIN* combin;
} CLIQUE;
CLIQUE *SmallGraphKnFirst(SMALL_GRAPH *G, int n);
Boolean SmallGraphKnContains(SMALL_GRAPH *G, int n);
SSET SmallGraphKnNext(CLIQUE*);
CLIQUE *SmallGraphInFirst(SMALL_GRAPH *G, int n);
Boolean SmallGraphInContains(SMALL_GRAPH *G, int n);
#define SmallGraphInNext SmallGraphKnNext
void SmallGraphCliqueFree(CLIQUE *);

/*
** This is a helper function for Contains Kn, but you can use it.  It
** tells you if adding this edge will cause a triangle; if so, it returns
** the SSET of vertices that are connected to both i and j.
*/
#define SmallGraphConnectingCausesK3(G,i,j) SSetIntersect(G->A[i], G->A[j])

/*
** Isomorphism algorithm for general graphs G1, G2.
** This algorithm uses some simple tests in an attempt to avoid the
** exponential algorithm.  It checks the number of nodes, the number of
** times each degree appears, and then kranks up the exponential time
** algorithm.
*/
Boolean SmallGraphsIsomorphic(SMALL_GRAPH *G1, SMALL_GRAPH *G2);

#endif /* _SMALLGRAPH_H */
