/* debruijn.c
graph.h, digraph.h を同じディレクトリに download して用いよ

コンパイル命令と実行命令：
gcc debruijn.c -o debruijn
./debruijn

K. Shiota
2005.6.13
*/

#define MAXORDER 256
#include "graph.h"
#include "digraph.h"

void m_adic(int a0, int m, int n)
{
	int x[16],i,a=a0;
	for(i=0;i<n;i++){
		x[i]=a%m;
		a/=m;
	}
	for(i=n-1;i>=0;i--) printf("%d",x[i]);
}

main()
{
	Graph g;
//	int m=5, n=3;	// ５シンボルの３文字単語の場合
	int m=3, n=3;	// m^(n-1) <= MAXORDER の範囲で使用のこと
	int l,ec[1024],i,j,ord,overlap;

	ord=1;
	for(i=0;i<n-1;i++) ord*=m;		// 頂点数は m^(n-1)
	overlap=ord/m;
	
	g.ord=ord;
	for(i=0;i<ord;i++)
		for(j=0;j<ord;j++){
			// m-進数で i の下 n-2 桁 = j の上 n-2 桁のとき弧を書く
			if((i%overlap)==(j/m)) g.adj[i][j]=1;
			else g.adj[i][j]=0;
		}		
	printf("Graph  G :\n");
	WriteGraph(g);
	printf("\n");
	l=EulerianCircuitDirected(g,ec);
	printf("Eulerian Circuit :\n");
	for(i=0;i<=l;i++){
		if(i!=0) printf(" -> ");
		m_adic(ec[i],m,n-1);
	}
	printf("\n\n");
	printf("De Bruijn sequence : \n"); 
	m_adic(ec[0],m,n-1);
	for(i=1;i<=l;i++) printf("%d",ec[i]%m);
	printf("\n");
}