#ifndef _GRAPH_H
#define _GRAPH_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 _Graph {
    /* vertices numbered 0..n-1 inclusive */
    int n;
    SET **A;   /* Adjacency Matrix, as a dynamically allocated array[G->n] of SETs */
    int *degree;   /* degree of each v[i] == cardinality of A[i] == length of neighbor array */
    int **neighbors; /* adjacency list: UNSORTED list of neighbors */
} GRAPH;

GRAPH *GraphAlloc(unsigned int n);
void GraphFree(GRAPH *G);
GRAPH *GraphEdgesAllDelete(GRAPH *G);
GRAPH *GraphConnect(GRAPH *G, int i, int j);
GRAPH *GraphDisconnect(GRAPH *G, int i, int j);
GRAPH *GraphComplement(GRAPH *Gbar, GRAPH *G);
GRAPH *GraphUnion(GRAPH *destination, GRAPH *G1, GRAPH *G2);
#define GraphDegree(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.)
 */
int GraphBFS(GRAPH *G, int seed, int distance, int *nodeArray, int *distArray);

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

void GraphPrintAdjMatrix(FILE *fp, GRAPH *G);
GRAPH *GraphReadAdjMatrix(FILE *fp);
void GraphPrintAdjList(FILE *fp, GRAPH *G);
GRAPH *GraphReadAdjList(FILE *fp);
void GraphPrintConnections(FILE *fp, GRAPH *G);
GRAPH *GraphReadConnections(FILE *fp);

#define GraphAreConnected(G,i,j) SetIn((G)->A[i],(j))
#ifndef GraphAreConnected
Boolean GraphAreConnected(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 a SET containing the nodes with the property requested.  Calling
** the appropriate GraphNext* function returns the next in the list of
** Kn's or In's. 0 is returned when none are left.
** The underlying graph G should NOT be changed while these routines are
** "in motion".
*/
typedef struct _clique {
    GRAPH *G;
    SET *set;
    unsigned cliqueSize, *combArray, *inducedArray;
    COMBIN* combin;
} CLIQUE;
CLIQUE *GraphKnFirst(GRAPH *G, int n);
Boolean GraphKnContains(GRAPH *G, int n);
SET *GraphKnNext(CLIQUE*);
CLIQUE *GraphInFirst(GRAPH *G, int n);
Boolean GraphInContains(GRAPH *G, int n);
#define GraphInNext GraphKnNext
void GraphCliqueFree(CLIQUE *);

/*
** 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 GraphsIsomorphic(GRAPH *G1, GRAPH *G2);

#endif /* _GRAPH_H */
