package edu.unl.consystlab.sudokuSolver;
import java.util.LinkedList;
import java.util.List;
import java.util.Hashtable;
import java.util.Set;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Stack;

public class graph {

	private int[][] adjacencyMatrix;
	private List allNodes;
	private List valueNodes;
	private List variableNodes;
	private Hashtable htblValueNodes;
	private Hashtable htblVariableNodes;
	private Hashtable adjacencyValueLookup;
	
	//default constructor not used
//	public graph()
//	{
//	}
	
	public graph(List graphNodes)
	{
		//create and zero out the adjacency matrix.
		adjacencyMatrix = new int[graphNodes.size()][graphNodes.size()];
		for(int i = 0; i < graphNodes.size(); i++)
		{
			for(int j =0; j < graphNodes.size(); j++)
			{
				adjacencyMatrix[i][j] = 0;
			}
		}
		
		allNodes = new LinkedList(graphNodes);
		valueNodes = new LinkedList();
		variableNodes = new LinkedList();
		htblValueNodes = new Hashtable();
		htblVariableNodes = new Hashtable();
		adjacencyValueLookup = new Hashtable();
		
		for(int i =0; i < allNodes.size(); i++)
		{
			if( ((graphNode)allNodes.get(i)).isVariable() )
			{
				variableNodes.add(allNodes.get(i));
				htblVariableNodes.put(((graphNode)allNodes.get(i)).getVariable(),allNodes.get(i));
			}
			else if( ((graphNode)allNodes.get(i)).isValue() )
			{
				valueNodes.add(allNodes.get(i));
				htblValueNodes.put(((graphNode)allNodes.get(i)).getValue(),allNodes.get(i));
			}
			else
			{
				System.out.println("Error in graph object, unknown node type");
			}
			adjacencyValueLookup.put(new Integer(((graphNode)allNodes.get(i)).getAdjacencyValue()), allNodes.get(i));
		}
	}
	
	public int[][] getAdjacencyMatrix()
	{
		return(adjacencyMatrix);
	}
	
	public graph(graph oldGraph)
	{
		allNodes = new LinkedList(oldGraph.getAllNodes());
		
		//copy the adjacency matrix.
		int graphSize = oldGraph.getAllNodes().size();
		int[][]ogAdjacencyMatrix = oldGraph.getAdjacencyMatrix();
		adjacencyMatrix = new int[graphSize][graphSize];
		for(int i = 0; i < graphSize; i++)
		{
			for(int j =0; j < graphSize; j++)
			{
				adjacencyMatrix[i][j] = ogAdjacencyMatrix[i][j];
			}
		}

		valueNodes = new LinkedList();
		variableNodes = new LinkedList();
		htblValueNodes = new Hashtable();
		htblVariableNodes = new Hashtable();
		adjacencyValueLookup = new Hashtable();

		for(int i =0; i < allNodes.size(); i++)
		{
			if( ((graphNode)allNodes.get(i)).isVariable() )
			{
				variableNodes.add(allNodes.get(i));
				htblVariableNodes.put(((graphNode)allNodes.get(i)).getVariable(),allNodes.get(i));
			}
			else if( ((graphNode)allNodes.get(i)).isValue() )
			{
				valueNodes.add(allNodes.get(i));
				htblValueNodes.put(((graphNode)allNodes.get(i)).getValue(),allNodes.get(i));
			}
			else
			{
				System.out.println("Error in graph object, unknown node type");
			}
			adjacencyValueLookup.put(new Integer(((graphNode)allNodes.get(i)).getAdjacencyValue()), allNodes.get(i));
		}
	}
	
	public List getAllFreeNodes()
	{
		List allNodes = this.getAllNodes();
		List freeNodes = new LinkedList();
		
		for(int i = 0; i < allNodes.size(); i++)
		{
			if( this.isFreeNode((graphNode)allNodes.get(i)) )
			{
				freeNodes.add(allNodes.get(i));
			}
		}
		return(freeNodes);
	}
	
	public boolean isFreeNode(graphNode checkNode)
	{
		int nodeAdjValue = checkNode.getAdjacencyValue();
		
		for(int i=0; i<allNodes.size(); i++)
		{
			if(adjacencyMatrix[nodeAdjValue][i]== 1)
			{
				return(false);
			}
		}
		for(int i=0; i<allNodes.size(); i++)
		{
			if(adjacencyMatrix[i][nodeAdjValue]== 1)
			{
				return(false);
			}
		}
		return(true);
	}
	
	public void addVital(graphNode newVital)
	{
		
	}
	
	public graphNode getNode(int adjacencyValue)
	{
		return((graphNode)adjacencyValueLookup.get(new Integer(adjacencyValue)));
	}
	
	public List getAllNodes()
	{
		return(allNodes);
	}
	
	public List getValueNodes()
	{
		return(valueNodes);
	}
	
	public List getVariableNodes()
	{
		return(variableNodes);
	}
	
	public void clear()
	{
		for(int i = 0; i < allNodes.size(); i++)
		{
			for(int j =0; j < allNodes.size(); j++)
			{
				adjacencyMatrix[i][j] = 0;
			}
		}
	}
	
	//if the current graph is not bidirectional it will make it so by
	//adjusting it's adjacency matrix so that every directed edge
	//now goes both ways.
	public void makeBidirectional()
	{
		for(int row=0; row< allNodes.size(); row++)
		{
			for(int col=0; col < allNodes.size(); col++)
			{
				if(adjacencyMatrix[row][col] == 1)
				{
					adjacencyMatrix[col][row] = 1;
				}
			}
		}
	}
	
	public graph getTransverse()
	{
		graph result = new graph(this);
		
		int[][] transverseMatrix = result.getAdjacencyMatrix();
		int[][] originalMatrix = this.getAdjacencyMatrix();
		for(int row=0; row < result.getNodeNumber(); row++)
		{
			for(int col=0; col < result.getNodeNumber(); col++)
			{
				transverseMatrix[row][col] = originalMatrix[col][row];
			}
		}
		
		return (result);
	}
	
	public graphNode getValueNode(String value)
	{
		return((graphNode)htblValueNodes.get(value));
	}
	public graphNode getVariableNode(problemVariable variable)
	{
		return((graphNode)htblVariableNodes.get(variable));
	}
	
	public void addBidirectionalEdge(graphNode firstNode , graphNode secondNode)
	{
		adjacencyMatrix[firstNode.getAdjacencyValue()][secondNode.getAdjacencyValue()] = 1;
		adjacencyMatrix[secondNode.getAdjacencyValue()][firstNode.getAdjacencyValue()] = 1;
	}
	
	public int getNodeNumber()
	{
		return(allNodes.size());
	}
	
	//this is dangerous because it assumes the calling function knows the underlying
	// adjacency matrix structure.  It probably isn't good programing but it is efficient
	// programing.
	public void addEdge(int startPoint, int endPoint)
	{
		adjacencyMatrix[startPoint][endPoint] = 1;
		return;
	}
	
	public void addEdge(graphNode startNode, graphNode endNode)
	{
		int startPoint = startNode.getAdjacencyValue();
		int endPoint = endNode.getAdjacencyValue();
		adjacencyMatrix[startPoint][endPoint] = 1;
		return;
	}
	
	public void removeAllOutEdges(graphNode startNode)
	{
		int startPoint = startNode.getAdjacencyValue();
		for(int i =0; i < getNodeNumber(); i++)
		{
			adjacencyMatrix[startPoint][i] = 0;
		}
	}
	
	//this is dangerous because it assumes the calling function knows the underlying
	// adjacency matrix structure.  It probably isn't good programing but it is efficient
	// programing.
	public void removeEdge(int startPoint, int endPoint)
	{
		adjacencyMatrix[startPoint][endPoint] = 0;
		return;
	}
	
	public void removeEdge(graphNode startNode, graphNode endNode)
	{
		int startPoint = startNode.getAdjacencyValue();
		int endPoint = endNode.getAdjacencyValue();
		adjacencyMatrix[startPoint][endPoint] = 0;
		return;
	}
	
	public boolean existsEdge(int startPoint, int endPoint)
	{
		return(adjacencyMatrix[startPoint][endPoint] == 1);
	}
	
	public List getNodesConnectedTo(graphNode endNode)
	{
		List connectedNodes = new LinkedList();
		
		int endPoint = endNode.getAdjacencyValue();
		
		for(int i = 0; i < getNodeNumber(); i++)
		{
			if(adjacencyMatrix[i][endPoint] == 1)
			{
				connectedNodes.add(getNode(i));
			}
		}
		
		return(connectedNodes);
	}
	
	//this assumes the node structure and adjacencyMatricies of
	// both graphs are the same.
	public void xorWith(graph otherGraph)
	{
		int[][] ogAM = otherGraph.getAdjacencyMatrix();
		for(int row = 0; row < getNodeNumber(); row++)
		{
			for(int col = 0; col < getNodeNumber(); col++)
			{
				adjacencyMatrix[row][col] = adjacencyMatrix[row][col] ^ ogAM[row][col];
			}
		}
	}
	
	public List getNodesPointedTo(graphNode startNode)
	{
		List connectedNodes = new LinkedList();
		
		int startPoint = startNode.getAdjacencyValue();
		
		for(int i = 0; i < getNodeNumber(); i++)
		{
			if(adjacencyMatrix[startPoint][i] == 1)
			{
				connectedNodes.add(getNode(i));
			}
		}
		
		return(connectedNodes);
	}
	
	public graph computeMaximumMatching(graph partialMatching)
	{
		//first step create a graph with the same edges as this graph except that they are directed.
		//if an edges is not in the matching it runs from value to variable, and if it is in the matching
		//it runs from variable to value.
		
		if(partialMatching == null)
		{
			partialMatching = new graph(this.allNodes);
		}
		
		//this may not be necessary, but do it now as a precaution
		partialMatching.makeBidirectional();
		
		//assumes this graph is bidiretional
		graph directedGraph = new graph(this);
		int [][] dgAdjacencyMatrix = directedGraph.getAdjacencyMatrix();

		for(int col = 0; col < directedGraph.getNodeNumber(); col++)
		{
			for(int row = 0; row < directedGraph.getNodeNumber(); row++)
			{
				if(dgAdjacencyMatrix[row][col] == 1)
				{
					//check to see if there is the same edge in the partial matching
					if(partialMatching.existsEdge(row, col))
					{
						//we want it to run from variable to value
						if(directedGraph.getNode(row).isValue())
						{
							directedGraph.removeEdge(row, col);
						}
						else
						{
							directedGraph.removeEdge(col, row);
						}
					}
					else
					{
						//we want it to run from value to variable
						if(directedGraph.getNode(row).isValue())
						{
							directedGraph.removeEdge(col, row);
						}
						else
						{
							directedGraph.removeEdge(row, col);
						}
					}
				}
			}
		}
		
		graph searchGraph = new graph(directedGraph.getAllNodes());
		
		//make L0 which is all of the variables which are free in the matching graph
		//there can be a maximium of the number of nodes in the graph levels ie L[0].. L[this.getNodeNumber]
		Set [] L;
		L = new HashSet[directedGraph.getNodeNumber()];
		L[0] = new HashSet();

		
		//we keep going until we find a free girl/value
		// or we find a Level without any values;
		boolean stopBuilding = false;
		boolean noAugmentPathsExist = false;
		
		noAugmentPathsExist = true;
		List pmVars = partialMatching.getVariableNodes();
		for(int i =0; i < pmVars.size(); i++)
		{
			if( partialMatching.isFreeNode((graphNode)pmVars.get(i)) )
			{
				noAugmentPathsExist = false;
				L[0].add(pmVars.get(i));
			}
		}
		if(noAugmentPathsExist)
		{
			return(partialMatching);
		}
		
		
		//build L1 which is all values that are connected in the directed graph to the variables
		//in L0
		L[1] = new HashSet();
		if(!stopBuilding)
		{
			noAugmentPathsExist = true;
			for(Iterator i = L[0].iterator(); i.hasNext(); )
			{
				graphNode currentNode = (graphNode)i.next();
				List connectedNodes = directedGraph.getNodesConnectedTo(currentNode);
				for(int j =0; j < connectedNodes.size(); j ++)
				{
					noAugmentPathsExist = false;
					L[1].add(connectedNodes.get(j));
					//put in E0 which is the edges from L1 to L0
					searchGraph.addEdge((graphNode)connectedNodes.get(j), currentNode);
				}
			}
			
			if(noAugmentPathsExist)
			{
				return(partialMatching);
			}

			//check to see if we have reached our i* point ie where we found a free
			// girl.  If we have there may be edges we need to remove.
			List freeGirls = (partialMatching.getMatchingFreeValues(L[1]));
			if( freeGirls.size() > 0 )
			{
				stopBuilding = true;
				
				//remove all edges from the search graph that start with a node in L[1]
				// and are not free nodes.
				for(Iterator i = L[1].iterator(); i.hasNext(); )
				{
					graphNode currentNode = (graphNode)i.next();
					if(!freeGirls.contains(currentNode))
					{
						searchGraph.removeAllOutEdges(currentNode);
					}
				}
			}
		}
	
		//now we keep adding levels until a free girl is found.
		// or no new nodes are found.
		int currentLevel = 1;
		while(!stopBuilding)
		{
			//assume we will find no more nodes to add and we will stop
			noAugmentPathsExist = true;
			
			currentLevel++;
			L[currentLevel] = new HashSet();
			for(Iterator i = L[(currentLevel-1)].iterator(); i.hasNext(); )
			{
				
				graphNode currentNode = (graphNode)i.next();
				List connectedNodes = directedGraph.getNodesConnectedTo(currentNode);
				for(int j =0; j < connectedNodes.size(); j ++)
				{
					boolean addNode = true;
					//make sure it is not already in a previous level
					for(int k = currentLevel-2; k>= 0; k-=2)
					{
						if(L[k].contains(connectedNodes.get(j)))
						{
							addNode = false;
						}
					}
					if(addNode ==true)
					{
						noAugmentPathsExist = false;
						L[currentLevel].add(connectedNodes.get(j));						
					}
		
					//put the edge in
					searchGraph.addEdge((graphNode)connectedNodes.get(j), currentNode);
				}
			}
			
			if(noAugmentPathsExist)
			{
				return(partialMatching);
			}
			
			//if this is a girl/value level check to see if we have reached the end.
			if((currentLevel % 2 == 1) && !stopBuilding)
			{
				List freeGirls = (partialMatching.getMatchingFreeValues(L[currentLevel]));
				if( freeGirls.size() > 0 )
				{
					stopBuilding = true;
					
					//remove all edges from the search graph that start with a node in L[1]
					// and are not free nodes.
					for(Iterator i = L[currentLevel].iterator(); i.hasNext(); )
					{
						graphNode currentNode = (graphNode)i.next();
						if(!freeGirls.contains(currentNode))
						{
							searchGraph.removeAllOutEdges(currentNode);
						}
					}
				}
			}
		}
		
		//ok we have now built a graph of currentLevel levels.
		// we need to get the maximal set of augmenting paths.
		//just do a depth first search put the results in directedgraph
		directedGraph.clear();
		Iterator sourceNodes = L[currentLevel].iterator();
		Stack nodeStack = new Stack();
		Set B = new HashSet();
		if(sourceNodes.hasNext())
		{
			nodeStack.push(sourceNodes.next());			
		}

		while(!nodeStack.isEmpty())
		{
			while(!nodeStack.isEmpty() && searchGraph.getNodesPointedTo((graphNode)nodeStack.peek()).size() > 0 )
			{
				graphNode firstNode = ((graphNode)searchGraph.getNodesPointedTo((graphNode)nodeStack.peek()).get(0));
				searchGraph.removeEdge((graphNode)nodeStack.peek(), firstNode);
				if( !B.contains(firstNode) )
				{
					nodeStack.push(firstNode);
					B.add(firstNode);
					if(L[0].contains(nodeStack.peek()))
					{
						//we have found a path.
						//a path assumes there are atleast two nodes in the node stack
						graphNode tempNode = (graphNode)nodeStack.pop();
						while(nodeStack.size() > 0)
						{
							directedGraph.addBidirectionalEdge(tempNode, (graphNode)nodeStack.peek());
							tempNode = (graphNode)nodeStack.pop();
						}
						
						if(sourceNodes.hasNext())
						{
							nodeStack.push(sourceNodes.next());							
						}
					}
				}
			}
			//we may try to pop an empty stack since we do not have a source node
			//instead of poping what we want to do is go to the next source node if there is one.
			if(!nodeStack.isEmpty())
			{
				nodeStack.pop();
				if(nodeStack.isEmpty() && sourceNodes.hasNext())
				{
					nodeStack.push(sourceNodes.next());	
				}
			}
			else
			{
				if(sourceNodes.hasNext())
				{
					nodeStack.push(sourceNodes.next());							
				}
			}
		}
		
		partialMatching.xorWith(directedGraph);
		
		//we are going to call this recursively for now ... could be bad
		this.computeMaximumMatching(partialMatching);
		return(partialMatching);
	}
	

	//returns a list of removed edges.
	public List reduceGraph(graph matching)
	{
		List removedEdges = new LinkedList();
		
		//make sure the matching covers the variables
		//this is actually checked before this is called too.
		if(matching.getAllFreeNodes().size() != 0)
		{
			return null;
		}
		
		
		//make a copy of the graph that will become Gnot aka Go
		graph directedGraph = new graph(this);
		
		int [][] dgAdjacencyMatrix = directedGraph.getAdjacencyMatrix();

		for(int col = 0; col < directedGraph.getNodeNumber(); col++)
		{
			for(int row = 0; row < directedGraph.getNodeNumber(); row++)
			{
				if(dgAdjacencyMatrix[row][col] == 1)
				{
					//check to see if there is the same edge in the matching
					if(matching.existsEdge(row, col))
					{
						//we want it to run from variable to value
						if(directedGraph.getNode(row).isValue())
						{
							directedGraph.removeEdge(row, col);
						}
						else
						{
							directedGraph.removeEdge(col, row);
						}
					}
					else
					{
						//we want it to run from value to variable
						if(directedGraph.getNode(row).isValue())
						{
							directedGraph.removeEdge(col, row);
						}
						else
						{
							directedGraph.removeEdge(row, col);
						}
					}
				}
			}
		}
				
		//step 2 is unnessary because if we have a covering matching for our problem
		//there will be no free vertecies.
		
//		List freeNodes = matching.getAllFreeNodes();
//		//step 2 is to look for all directed edges that belong to a directed
//		//simple path which begins at a free vertex.
//		//do a dfs from the free nodes marking the edges as used and removing them
//		// from the directed graph.
//		Iterator sourceNodes = freeNodes.iterator();
//		Stack nodeStack = new Stack();
//		//B keeps us from doing infinite loops
//		//although since we are removeing edges as we go along this should not be an issue
//		//Set B = new HashSet();
//		
//		if(sourceNodes.hasNext())
//		{
//			nodeStack.push(sourceNodes.next());			
//		}
//
//		while(!nodeStack.isEmpty())
//		{
//			while(!nodeStack.isEmpty() && directedGraph.getNodesPointedTo((graphNode)nodeStack.peek()).size() > 0 )
//			{
//				graphNode firstNode = ((graphNode)directedGraph.getNodesPointedTo((graphNode)nodeStack.peek()).get(0));
//				directedGraph.removeEdge((graphNode)nodeStack.peek(), firstNode);
//				used.addBidirectionalEdge((graphNode)nodeStack.peek(), firstNode);
//				nodeStack.push(firstNode);
//			}
//			//we may try to pop an empty stack since we do not have a source node
//			//instead of poping what we want to do is go to the next source node if there is one.
//			if(!nodeStack.isEmpty())
//			{
//				
//				nodeStack.pop();
//				if(nodeStack.isEmpty() && sourceNodes.hasNext())
//				{
//					nodeStack.push(sourceNodes.next());	
//				}
//			}
//		}
		
		//step three is to compute the strongly connected components of Go
		//we do this with a depth first search of the transverse going in the opposite order
		//that the nodes were left when doing a dfs of the original graph.
		
		//get the transverse before we tear up the directedgraph
		graph transverse = directedGraph.getTransverse();
		
		//we use this to keep track of the order that we leave nodes in.
		LinkedList orderLeft = new LinkedList();
		
		List allNodes = directedGraph.getAllNodes();
		Iterator sourceNodes = allNodes.iterator();
		Stack nodeStack = new Stack();
		Set arrived = new HashSet();
		
		if(sourceNodes.hasNext())
		{
			nodeStack.push(sourceNodes.next());
			arrived.add(nodeStack.peek());
		}

		while(!nodeStack.isEmpty())
		{
			while(!nodeStack.isEmpty() && directedGraph.getNodesPointedTo((graphNode)nodeStack.peek()).size() > 0 )
			{
				graphNode firstNode = ((graphNode)directedGraph.getNodesPointedTo((graphNode)nodeStack.peek()).get(0));
				directedGraph.removeEdge((graphNode)nodeStack.peek(), firstNode);
				if( !arrived.contains(firstNode) )
				{
					nodeStack.push(firstNode);
					arrived.add(firstNode);
				}
			}

			orderLeft.addFirst(nodeStack.pop());
			while(nodeStack.isEmpty() && sourceNodes.hasNext())
			{
				Object next = sourceNodes.next();
				if(!arrived.contains(next))
				{
					nodeStack.push(next);
					arrived.add(nodeStack.peek());
				}
			}
		}
		//we should now have a linked list with the nodes in the inverse order that they were
		// left starting with the last node that was left.
		
		
		nodeStack = new Stack();
		arrived = new HashSet();
		//we have a hashtable where the key is the node and it corresponds to an integer in the
		//hashtable where all nodes with the same integer are in the same SCC
		Hashtable stronglyConnectedComponents = new Hashtable();
		int sccInt = 0;
		Integer sccInteger = Integer.valueOf(sccInt);

		
		if(!orderLeft.isEmpty())
		{
			nodeStack.push(orderLeft.getFirst());
			arrived.add(nodeStack.peek());
			stronglyConnectedComponents.put(nodeStack.peek(), sccInteger);
		}

		while(!nodeStack.isEmpty())
		{
			while(!nodeStack.isEmpty() && transverse.getNodesPointedTo((graphNode)nodeStack.peek()).size() > 0 )
			{
				List nodesPointedTo = transverse.getNodesPointedTo((graphNode)nodeStack.peek());
				Iterator possibleNode = nodesPointedTo.iterator();
				Object nextNode = possibleNode.next();
				while(arrived.contains(nextNode) && possibleNode.hasNext())
				{
					nextNode = possibleNode.next();
				}
				Object firstNode = nextNode;
				
				while(possibleNode.hasNext())
				{
					Object secondNode = possibleNode.next();

					if(!arrived.contains(secondNode) && orderLeft.indexOf(secondNode) < orderLeft.indexOf(firstNode))
					{
						firstNode = secondNode;
					}
				}

				transverse.removeEdge((graphNode)nodeStack.peek(), (graphNode)firstNode);
				//still need the if incase there are no nodes pointed to that are not already arrived at
				if( !arrived.contains(firstNode) )
				{
					nodeStack.push(firstNode);
					arrived.add(firstNode);
					stronglyConnectedComponents.put(nodeStack.peek(), sccInteger);
				}
			}

			nodeStack.pop();

			if(nodeStack.isEmpty())
			{
				//if we make it to here we have explored an entire dfs tree in the dfs forest.
				sccInt++;
				sccInteger = Integer.valueOf(sccInt);
				
				Iterator leftNodes = orderLeft.iterator();
				while(nodeStack.isEmpty() && leftNodes.hasNext())
				{

					Object next = leftNodes.next();
					if(!arrived.contains(next))
					{
						nodeStack.push(next);
						arrived.add(nodeStack.peek());
						stronglyConnectedComponents.put(nodeStack.peek(), sccInteger);
					}
				}
			}
		}
		
		//we should now have a list of sets of nodes which correspond to strongly connected components
		// we now go through every edge and ignore it if it joins two strongly connected components.
		// If it does not a part of a stongly connected component we see if it is vital or if we should
		// add it to removedEdges.
		// also remove values from variables.
		//int [][] adjacencyMatrix = this.getAdjacencyMatrix();
		for(int col = 0; col < this.getNodeNumber(); col++)
		{
			for(int row = 0; row < this.getNodeNumber(); row++)
			{
				if(adjacencyMatrix[row][col] == 1)
				{
					//check to see whether the two are in the same SCC
					if( !((Integer)stronglyConnectedComponents.get(this.getNode(row)))
							.equals(((Integer)stronglyConnectedComponents.get(this.getNode(col)))) )
						{
							//check to see if the edge is in the matching
							if(!matching.existsEdge(row, col))
							{						
								//if they are not then we remove the edge from g
								adjacencyMatrix[row][col] = 0;
								adjacencyMatrix[col][row] = 0;
								List removedEdge = new LinkedList();
								
								if( ((graphNode)this.getNode(row)).isVariable() )
								{
									//remove the value from the variable's domain.
									(((graphNode)this.getNode(row)).getVariable())
										.removeFromCurrentDomain(
												((graphNode)this.getNode(col)).getValue() );
									
									removedEdge.add(this.getNode(row));
									removedEdge.add(this.getNode(col));
								}
								else if ( ((graphNode)this.getNode(col)).isVariable() )
								{
									//remove the value from the variable's domain.
									(((graphNode)this.getNode(col)).getVariable())
										.removeFromCurrentDomain(
												((graphNode)this.getNode(row)).getValue() );
									
									removedEdge.add(this.getNode(row));
									removedEdge.add(this.getNode(col));									
								}

								removedEdges.add(removedEdge);
							}
						}
				}
			}
		}
		
		return (removedEdges);
	}
	
	
	//given a list of girl (or value) nodes it will see if any of them are free 
	// and return a list of those that are if any are.
	private List getMatchingFreeValues(Set currentLevel)
	{
		List freeValues = new LinkedList();
		
		if(currentLevel == null)
		{
			return (freeValues);
		}

		for(Iterator i = currentLevel.iterator(); i.hasNext(); )
		{
			graphNode currentNode = (graphNode)i.next();
			if( this.isFreeNode(currentNode) )
			{
				freeValues.add(currentNode);
			}
		}
		
		return(freeValues);
	}
}