#ifndef _GRAPH_TRANSITIVE_H
#define _GRAPH_TRANSITIVE_H 1

#include "graph.h"

/*
** Same thing except for transitive graphs.  (A transitive graph is one
** in which every node is similar to every other.)
*/
CLIQUE *GraphTransitiveKnFirst(GRAPH *G, int n);
CLIQUE *GraphTransitiveInFirst(GRAPH *G, int n);
Boolean GraphTransitiveKnContains(GRAPH *G, int n);
Boolean GraphTransitiveInContains(GRAPH *G, int n);

#if 0
Boolean GraphTransitivesIsomorphic(GRAPH *G1, GRAPH *G2);
#else
#define GraphTransitivesIsomorphic GraphsIsomorphic
#endif

/*
** Functions to generate all k-circulant graphs on n vertices.
** They are not optimal, in the sense of producing all
** non-isomporphic ones, but (number of graphs produced by these
** functions) / (number of non-isomprphs) should be about O(1+1/k).
** (ie, asymtotically pretty good.)  Pass the same graph pointer
** on and on until GraphNextCirculant returns NULL.
*/

typedef struct _circulant_graph {
    GRAPH *G;
    COMBIN *C;
    long long i;
} GRAPH_CIRCULANTS;

GRAPH_CIRCULANTS *GraphCirculantZeroth(int n, int r);
GRAPH_CIRCULANTS *GraphCirculantIth(int n, int r, unsigned long long I);
GRAPH_CIRCULANTS *GraphCirculantNext(GRAPH_CIRCULANTS *currentCirculant);
void GraphCirculantFree(GRAPH_CIRCULANTS *rrg);

/* Algorithms for generating circulants without isomorphs (from Eppstein) */
GRAPH_CIRCULANTS *GraphCirculantUniqueIth(int n, unsigned long I);
GRAPH_CIRCULANTS *GraphCirculantUniqueZeroth(int n);
GRAPH_CIRCULANTS *GraphCirculantUniqueNext(GRAPH_CIRCULANTS *rrg);
void GraphCirculantUniqueFree(GRAPH_CIRCULANTS *rrg);

#endif /* _GRAPH_TRANSITIVE_H */
