/* chromatic.h : 彩色多項式、彩色数関数定義部
graph.h, graphpol.h が必要

K. Shiota
2005.6.12
2005.6.14 version
*/

POL ChromaticPol(Graph g)
{
	Graph h,k;
	int u,v;
	if(EmptyGraphQ(g)) return monomial(g.ord);
	else{
		for(u=0;u<g.ord;u++)
			for(v=u+1;v<g.ord;v++)
				if(g.adj[u][v]>0){
					h=RemoveEdge(g,u,v);
					k=SimplifiedGraph(ContractEdge(g,u,v));
					return polsub(ChromaticPol(h),ChromaticPol(k));
				}
	}
}

int ChromaticNumber(Graph g)
{
	POL f=ChromaticPol(g);
	POL h,q,q0,r;
	int k=-1,e;
	do{
		h=linearfactor(++k);
		e=0;
		q=poldiv(f,h,&r);
		while(polzeroq(r)){
			e++;
			q0=q;
			q=poldiv(q,h,&r);
		}
		f=q0;
	}while(e>0);
	return k;
}

int ChromaticInformation(Graph g, POL *f, POL *ff, int *lf)
{
	POL h,q,q0,r;
	int k=-1,e;

	*f=ChromaticPol(g);
	*ff=*f;
	do{
		h=linearfactor(++k);
		e=0;
		q=poldiv(*ff,h,&r);
		while(polzeroq(r)){
			e++;
			q0=q;
			q=poldiv(q,h,&r);
		}
		*ff=q0;
		lf[k]=e;
	}while(e>0);
	return k;
}