// generateG0.c
// 	For general version of absorbIntoP.
//	Generate and return a maximal invariant subgraph
//	that deformation retracts on to P.
//	Let S(e) be the minimal invariant subgraph that contains e.
//	Start with G=P, the peripheral subgraph.
//	Go through the edges in turn and add it to G if doing so
//	does not decrease the number of components of G.
//	
//	3/28/96	JR
//	        Compiled. Tested on homeo4.dat.
//	3/29/96 Modified generateG0 to return G0 in components.
//		Changed G0 from a Set to a LinList.

LinList< Set<Name> > Homeo::generateG0() const
{
	Set<Name> G(theNameManager.periphery());
	int nCompsOfG = theGraph.nComponentsOf(G);
	Set<Name> F(theNameManager.edges());
	F-=theNameManager.periphery();	// remove P

	while( !F.isEmpty() )
	{
		Name n=F.removeOne();
		Set<Name> S(theMap.minimalInvariantSetContaining(n));
		S+=G;
		if( nCompsOfG == theGraph.nComponentsOf(S) )
		{
			G.add(n);
		}
		else
		{
		}
	}
	return theGraph.componentsOf(G);
}



LinList< Set<Name> > Graph::componentsOf(Set<Name> S) const
{
	int ncomps=0;
	LinList< Set<Name> > CC;
	Name n;
	while( !S.isEmpty() )
	{
		n=S.removeOne();
		Set<Name> C;
		C.add(n);
		ncomps++;
		
		SetBrowser<Name> i(S);
		for(i.init();i.ok();  )
		{
			if(edgeIncidentOnSet(i.current(),C))
			{
				Name tmp=i.current();
				C.add(tmp);
				S.remove(tmp);
				i.init();
			}
			else
			{
				i.advance();
			}
		}
		CC.append(C);
	}
	return CC;
}

int Graph::nComponentsOf(Set<Name> S) const
{
	int ncomps=0;
	Name n;
	while( !S.isEmpty() )
	{
		n=S.removeOne();
		Set<Name> C;
		C.add(n);
		ncomps++;
		
		SetBrowser<Name> i(S);
		for(i.init();i.ok();  )
		{
			if(edgeIncidentOnSet(i.current(),C))
			{
				Name tmp=i.current();
				C.add(tmp);
				S.remove(tmp);
				i.init();
			}
			else
			{
				i.advance();
			}
		}
	}
	return ncomps;
}

Boolean Graph::edgeIncidentOnSet( Name n, Set<Name> S ) const
{
	// Note: n itself belonging to S does NOT count, unless
	// n is a circle and actually does "touch itself".
	DE e(n,0);

	CircListBrowser<DE> i(originOf(e));
	Set<Name> tmp;
	for(i.init();i.ok();++i) tmp.add(i.ahead().name());

	CircListBrowser<DE> j(originOf(e.bar()));
	for(j.init();j.ok();++j) tmp.add(j.ahead().name());

	// tmp now contains all edges that edge n touches.

	if( tmp.intersects(S) )
	{	
		return 1;
	}
	else
	{
		return 0;	
	}
}



Set<Name> Map::minimalInvariantSetContaining(Name n) const
{
	Set<Name> I,oldNewSet,newSet;
	newSet.add(n);
	I+=newSet;

	while(!newSet.isEmpty())
	{
		oldNewSet=newSet;
		newSet.clear();
		SetBrowser<Name> j(oldNewSet);
		for(j.init();j.ok();j.advance())
		{
			newSet+=namesInImageOf(DE(j.current(),0));
		}
		newSet -= I;
		I += newSet;
	}

	return I;
}