// invariantForest.C

// Find the maximal invariantForest not incident on P
// and collapse it.

// John Ringland 8/22/95
//	10/26/95  Updated and compiled.
//	3/19/96   Noticed note in notes of  12/19/95 to 
//	          check if the case of multi-component circles
//		  is properly dealt with here.


Boolean Homeo::collapseInvariantForest()
{
//cout << "Entered collapseInvariantForest()" << endl;

					// First, find the maximal
					// invariant forest, f, not "incident" on P.
					// An edge is incident on P if it and an edge in P
					// "belong" to the same vertex.

	Set<Name> f(theNameManager.edges());		// Start with all the names.
//cout << "f initialized " << f << endl;

					// Create and remove from f
					// the peripheral edges 
					// and the edges incident on the 
					// peripheral set.

	f -= theGraph.touching(theNameManager.periphery());	
//cout << "stuff touching P removed " << f ;

					// Now iterate and remove any
					// edges that map out of f.
	Boolean mightBeMore=1;
	while( mightBeMore )
	{	
		mightBeMore=0;
		Set<Name> mapOut;
		SetIterator<Name> fi(f);
		for( fi.init(); fi.ok(); fi.advance() )	// For each edge in f
		{
						// prepare to examine its image
			DELListBrowser j(theMap.imageOf(DE(fi.current(),0)));
						// see if any edges in the image are not in f
			for( j.init(); j.ok(); ++j )
			{
				if( ! f.has(j.ahead().name()) )
				{	
					mapOut.add(fi.current());  // mark fi for removal
					mightBeMore=1;
					break;		 // and move on to next
							 // edge in f
				}
			}
		}

				// Remove from f the edges that map out of f

		if( mightBeMore ) f -= mapOut;
	}

	// f is now the maximal invariant forest

	if( f.isEmpty() ) 
	{
cout << "  There is no invariant forest to collapse." << endl;
		return 0;
	}
	else
	{
cout << "  Collapsing maximal invariant forest " << f;
		SetIterator<Name> fi(f);
		for( fi.init(); fi.ok(); fi.advance() ) 
			collapseEdge(DE(fi.current(),0));
	}
//cout << "InvariantForest collapsed." << endl;
}

Set<Name> Homeo::invariantForestNotIntersectingPInAnEdge() const
{
// Differs from collapseInvariantForest in that it 
// allows edges that intersect P only in vertices,
// and that it does no collapsing: just returns the forest.

//cout << "Entered collapseInvariantForest()" << endl;

					// First, find the maximal
					// invariant forest, f, not "incident" on P.
					// An edge is incident on P if it and an edge in P
					// "belong" to the same vertex.

	Set<Name> f(theNameManager.edges());		// Start with all the names.
//cout << "f initialized " << f << endl;

					// Create and remove from f
					// the peripheral edges. 

	f -= theNameManager.periphery();	
//cout << "stuff touching P removed " << f ;

					// Now iterate and remove any
					// edges that map out of f.
	Boolean mightBeMore=1;
	while( mightBeMore )
	{	
		mightBeMore=0;
		Set<Name> mapOut;
		SetIterator<Name> fi(f);
		for( fi.init(); fi.ok(); fi.advance() )	// For each edge in f
		{
						// prepare to examine its image
			DELListBrowser j(theMap.imageOf(DE(fi.current(),0)));
						// see if any edges in the image are not in f
			for( j.init(); j.ok(); ++j )
			{
				if( ! f.has(j.ahead().name()) )
				{	
					mapOut.add(fi.current());  // mark fi for removal
					mightBeMore=1;
					break;		 // and move on to next
							 // edge in f
				}
			}
		}

				// Remove from f the edges that map out of f

		if( mightBeMore ) f -= mapOut;
	}

	// f is now the maximal invariant forest that does
	// not intersect P in an edge.

	return f;
}









