// valence2.C
// JR
//	10/26/95  Started.
//	12/7/95   Resuming work on this: finished writing the part
//		  for when the map is a permutation. Compiled.
//		  Started testing.
// 		  Should we collapseEdgesWithEmptyImage() after
//		  vertex removal? Yes.
//	3/14/96	  Had forgotten to deal with the image of the
//		  collapsed edge. Fixed.



#define TOL 0.00001
#define NITMAX 200

#include "Homeo.H"
#include "IncidenceMatrix.H"
#include "Set.H"
//#include "Boolean.H"
//#include "Vertex.H"
//#include "NameManager.H"


Boolean Homeo::removeAValenceTwoVertex()
{
	theFingers.markInvalid();	// Finger update not yet coded.

//cout << "Entered removeValenceTwoVertices()" << endl;
//cout << theGraph << endl;
	Boolean removedSomething=0;
	SetIterator<Vertex> iv(theGraph);
	for(iv.init();iv.ok();)
	{
		if(iv.current().length()==2)
		{				// Found valence-2 vertex.

cout << "  Removing valence-2 vertex " << iv.current() << endl;

			DE e1=iv.current().ahead();
			DE e2=iv.current().behind();

			assert(!peripheral(e1)); // precluded by Lemma 4.2.1(3)
			assert(!peripheral(e2)); // precluded by Lemma 4.2.1(3)

			Set<Name> prePee(preP());
					// B&H p126
					// "If at least one of the edges
					// adjacent to v lies in pre-P ..."
//cout << (*this) << endl;
			if( prePee.has( e1.name() ) )
			{	
cout << "    across edge " << e1 << 
	" which belongs to pre-P=" << preP() << "." << endl;
				theMap.prependToImageOf(e2,theMap.copyOfImageOf(e1.bar()));
				collapseEdge( e1 );
			}
			else if( prePee.has( e2.name() ) )
			{	
cout << "    across edge " << e2 << 
	" which belongs to pre-P=" << preP() << "." << endl;
				theMap.prependToImageOf(e1,theMap.copyOfImageOf(e2.bar()));
				collapseEdge( e2 );
			}
			else 
			{				
				Set<Name> H(theNameManager.edges());
				H -= theNameManager.periphery();
				H -= preP();
				if(!theMap.isPermutation())
				{
					// "if lambda>1 follow recipe in 3.2(5)."
					IncidenceMatrix MH(H,theMap);
					if(MH.growthRate(TOL,NITMAX)>1)
					{
//cout << "Eigenvector components:" << endl;
//cout << "  for " << e1 << ", " << MH.eigenvectorComponent(e1.name(),TOL,NITMAX) << endl;
//cout << "  for " << e2 << ", " << MH.eigenvectorComponent(e2.name(),TOL,NITMAX) << endl;

						if(MH.eigenvectorComponent(e1.name(),TOL,NITMAX)
					  	>MH.eigenvectorComponent(e2.name(),TOL,NITMAX)
					  	)
						{
//cout << "  About to collapse edge " << e1 << endl;
cout << "    by collapsing edge " << e1 << 
	" which has the larger eigenvector component" << endl << "    (" <<
	MH.eigenvectorComponent(e1.name(),TOL,NITMAX) << " vs. " << 
	MH.eigenvectorComponent(e2.name(),TOL,NITMAX) << ")." << endl;

							theMap.prependToImageOf(e2,theMap.copyOfImageOf(e1.bar()));
							collapseEdge(e1);
						}
						else
						{
//cout << "  About to collapse edge " << e2 << endl;
cout << "    by collapsing edge " << e2 << 
	" which has the larger eigenvector component" << endl << "    (" <<
	MH.eigenvectorComponent(e2.name(),TOL,NITMAX) << " vs. " << 
	MH.eigenvectorComponent(e1.name(),TOL,NITMAX) << ")." << endl;

							theMap.prependToImageOf(e1,theMap.copyOfImageOf(e2.bar()));
							collapseEdge(e2);
						}
					}		
				}
				else
				{
						// lambda=1
						// "Simply erase all the valence-2
						// vertices with both incident edges
						// in H."
cout << "  About to 'simply erase all ...' " << endl;
cout << "NOT CODED YET." << endl;
assert(0);  // Images to be discarded?	
					// Make a set of all the edgepairs in H
					// incident on a valence-2 vertex.
	
					LinList<DE> togo;
					togo.append(iv.current().ahead());
				
					for(iv.advance();iv.ok();iv.advance())
					{
						if(iv.current().length()==2)
						{	// Found another valence-2 vertex.
							if( H.has(iv.current().behind().name())
							  &&H.has(iv.current().ahead().name()) )
	 						{
								togo.append(iv.current().ahead());
							}
						}
					}
		
					// Now togo contains all the edges to be deleted.
					LinListBrowser<DE> ip(togo);
					for(ip.init();ip.ok();++ip)
					{
						collapseEdge(ip.ahead());
					}
				}
			}
//cout << (*this) << endl;

// ONLY difference from removeValenceTwoVertices():
//			removedSomething=1;
			collapseEdgesWithEmptyImage();
			return 1;
//			iv.init();
		}
		else	
		{
			iv.advance();
		}
	}
cout << "  There is no valence-2 vertex to remove." << endl;
	return removedSomething;
}

Boolean Homeo::removeValenceTwoVertices()
{
cout << "Entered removeValenceTwoVertices()" << endl;
cout << theGraph << endl;
	Boolean removedSomething=0;
	SetIterator<Vertex> iv(theGraph);
	for(iv.init();iv.ok();)
	{
		if(iv.current().length()==2)
		{				// Found valence-2 vertex.

cout << "Will remove valence-2 vertex " << iv.current() << endl;

			DE e1=iv.current().ahead();
			DE e2=iv.current().behind();

			assert(!peripheral(e1)); // precluded by Lemma 4.2.1(3)
			assert(!peripheral(e2)); // precluded by Lemma 4.2.1(3)

			Set<Name> prePee(preP());
					// B&H p126
					// "If at least one of the edges
					// adjacent to v lies in pre-P ..."
cout << (*this) << endl;
			if( prePee.has( e1.name() ) )
			{	
cout << "  About to collapse edge " << e1 << endl;
				theMap.prependToImageOf(e2,theMap.copyOfImageOf(e1.bar()));
				collapseEdge( e1 );
			}
			else if( prePee.has( e2.name() ) )
			{	
cout << "  About to collapse edge " << e2 << endl;
				theMap.prependToImageOf(e1,theMap.copyOfImageOf(e2.bar()));
				collapseEdge( e2 );
			}
			else 
			{				
				Set<Name> H(theNameManager.edges());
				H -= theNameManager.periphery();
				H -= preP();
				if(!theMap.isPermutation())
				{
					// "if lambda>1 follow recipe in 3.2(5)."
					IncidenceMatrix MH(H,theMap);
					if(MH.growthRate(TOL,NITMAX)>1)
					{
cout << "Eigenvector components:" << endl;
cout << "  for " << e1 << ", " << MH.eigenvectorComponent(e1.name(),TOL,NITMAX) << endl;
cout << "  for " << e2 << ", " << MH.eigenvectorComponent(e2.name(),TOL,NITMAX) << endl;
						if(MH.eigenvectorComponent(e1.name(),TOL,NITMAX)
					  	>MH.eigenvectorComponent(e2.name(),TOL,NITMAX)
					  	)
						{
cout << "  About to collapse edge " << e1 << endl;
							theMap.prependToImageOf(e2,theMap.copyOfImageOf(e1.bar()));
							collapseEdge(e1);
						}
						else
						{
cout << "  About to collapse edge " << e2 << endl;
							theMap.prependToImageOf(e1,theMap.copyOfImageOf(e2.bar()));
							collapseEdge(e2);
						}
					}		
				}
				else
				{
						// lambda=1
						// "Simply erase all the valence-2
						// vertices with both incident edges
						// in H."
cout << "  About to 'simply erase all ...' " << endl;
assert(0);  // Images to be discarded?	
					// Make a set of all the edgepairs in H
					// incident on a valence-2 vertex.
	
					LinList<DE> togo;
					togo.append(iv.current().ahead());
				
					for(iv.advance();iv.ok();iv.advance())
					{
						if(iv.current().length()==2)
						{	// Found another valence-2 vertex.
							if( H.has(iv.current().behind().name())
							  &&H.has(iv.current().ahead().name()) )
	 						{
								togo.append(iv.current().ahead());
							}
						}
					}
		
					// Now togo contains all the edges to be deleted.
					LinListBrowser<DE> ip(togo);
					for(ip.init();ip.ok();++ip)
					{
						collapseEdge(ip.ahead());
					}
				}
			}
cout << (*this) << endl;

			removedSomething=1;
			iv.init();
		}
		else	
		{
			iv.advance();
		}
	}
cout << "Leaving removeValenceTwoVertices() : " << removedSomething << endl;
	return removedSomething;
}


Set<Name> Homeo::preP() const
{
		// Return the set of names of edges whose iterated image
		// is eventually contained in the peripheral set.

		// The set Q will become the complement of P union preP.

	Set<Name> Q(theNameManager.edges());	// Start with everything.
	Q -= theNameManager.periphery();	// Remove P.

		// Now iteratively remove any edge in Q that gets mapped
		// entirely out of Q.

	SetIterator<Name> iq(Q);
	for(iq.init();iq.ok();)
	{
		Set<Name> image(theMap.namesInImageOf(DE(iq.current(),0)));
		if( !image.intersects(Q) )
		{ 	Q.remove(iq.current());
			iq.init();
		}
		else iq.advance();
	}
	
	Set<Name> tmp(theNameManager.edges());	// Start with everything. 
	tmp -= theNameManager.periphery();	// Remove P.
	tmp -= Q;				// Remove Q.
						// preP remains.
	return tmp;
}