#include <stream.h>
#include "mathlink.h"
/* #include "/home/staff1/elena/mathematica/Source/Includes/mathlink.h" */
/* #include "/home/lie/mathematica/Source/Includes/mathlink.h" */
/* #include "/disks/3/usrlocal/Mathematica/Source/Includes/mathlink.h"*/
extern "C" {
#include "nauty/nauty.h"
}
#define MAXCi 32

	/* Data types: */

enum VertexType {Ci,UV,Blue,Green,Red,X,Y,Z,Arrow,Dashed,OV,UOV,Marker};

struct nautycoloring	/* A structure to contain vertex coloring in the */
{			/* nauty format */
  int n;		/* Number of vertices */
  nvector lab[MAXN];	/* Same as nauty's lab */
  nvector ptn[MAXN];	/* Same as nauty's ptn */
};

class Graph
{
private:
  int N;		/* Number of vertices (including markers) */
  int n;		/* Number of vertices (not including markers) */
  int *vd;		/* Vertex degrees */
  VertexType *vt;	/* Vertex types */
  int *vp;		/* Vertex parity */
  int *vai;		/* Vertex auxiliary integer */
  int **v;		/* Vertices */
  int coeff;		/* The coefficient of the graph, usually 0, 1, or -1 */

public:
  Graph() {N=0;}
  ~Graph();
  int PermuteSign(permutation *perm);
  inline int VertexPriority(int i) const {
    return (
      2*MAXCi*(Marker+1) - 
      (2*MAXCi*vt[i]+MAXCi*vp[i]+(vt[i]==Ci ? vai[i] : 0))
    );
  }
  inline void SetCoefficient(int c) {coeff=c;}
  inline int Order() const {return n;}
  inline int VertexDegree(int i) const {return vd[i];};
  inline int VertexParity(int i) const {return vp[i];};
  inline int Neighbor(int i, int j) const {return v[i][j];}

  friend MLINK operator>>(MLINK link, Graph &G);
  friend MLINK operator<<(MLINK link, Graph &G);
  friend ostream& operator<<(ostream& s, Graph &G);
  friend Graph &Permute(Graph &G, permutation *perm);
  friend Graph Permute(permutation *perm, Graph G);
  friend int SplitGraph(Graph &G, Graph *&glist);
};

struct DigestedGraph	/* A structure to contain graphs prepared for Phi */
{
  int e;		/* Number of internal edges */
  int k;		/* Number of colored ends (ce's) */
  int links[MAXN];	/* The links of the trivially thickened graph */
			/* in the format: */
			/* edge[0,0],edge[0,1],edge[0,2],edge[0,3],... */
			/* edge[e-1,0],...,edge[e-1,3],... */
			/* ce[0,0],ce[0,1],color[0],color[0],... */
			/* ce[c-1,0],ce[c-1,1],color[c-1],color[c-1]. */
  /* ??? */
};

class SumOfSurfaces	/* A linear combination of marked surfaces */
{
};

	/* Functions: */

void MLCanonicalForm(MLINK link);
Graph &CanonicalForm(Graph &G);
void MLPhi(MLINK link);
void MLSplitGraph(MLINK link);
Graph *OnAutomorphismGraph;	/* The Graph OnAutomorphism is looking at */
extern "C" void OnAutomorphism(
  int count,
  permutation *perm, 
  nvector *orbits,
  int numorbits,
  int stabvertex,
  int n
);
void tonauty(const Graph& G, graph *g);
			/* From class Graph to the nauty graph format */
void nautycolors(const Graph& G, nautycoloring& c);
			/* The nauty initial labelling of a Graph */
int Signature(int l, int *list, permutation *perm);
			/* The signature of the action of perm */
			/* on list; l is the length of list */
int SignedSort(int l, int *list);
			/* Sorts the list list (whose length is l) in */
			/* place and returns the signature */
DigestedGraph Digest(Graph& G);
			/* Prepares a Graph for efficient processing */
			/* by Phi. */
SumOfSurfaces Phi(DigestedGraph& DG);
			/* Computes Phi of a digested graph DG */
char *VertexName(char *vname, int vp, VertexType vt, int vai);
			/* The ASCII name of a vertex */

	/* Operators */

MLINK operator<<(MLINK link, SumOfSurfaces &sum);