/**This is a class that represents a graph,
***Written by Chris Hanusa on January 26, 2006.
**/

class Graph
{
    /***********Private data in a "Graph"***********/

    private Node NodeSet[];     //List of vertices   
    private Edge EdgeSet[];     //List of edges.
    private int sign;           //Sign of the the graph (its contribution)
    private int PrevGraph;      //The graph in the list of graphs that spawned this graph.

    /************Instantiators*************/

    Graph()
    {
	this.NodeSet=null;      
	this.EdgeSet=null;    
        this.sign=1;
    }
    Graph(Node[] a, Edge[] b)
    {
	this.NodeSet=a;
        this.EdgeSet=b;
        this.sign=1;
    }
    Graph(Node[] a, Edge[] b, int c)
    {
	this.NodeSet=a;
        this.EdgeSet=b;
        this.sign=c;
    }

    /***********Simple Commands************/

    public void negate()    //In case you need to change the sign of this graph.
    {
	this.sign = this.sign*(-1);
    }

    public void set_PrevGraph(int a)  //In order to set the number of the graph that spawned this graph.
    {
	this.PrevGraph = a;
    }

    public void add_node(Node a)   //In order to add a node to the graph.
    {
    	boolean contains = false;    //First, check to see if the list of Nodes already 
        int ii = 0;	             //contains the node to be added.                   
	for(ii=0;ii<NodeSet.length;ii++)
	{   if(!contains) contains = NodeSet[ii].name()==a.name();
	}
	if(!contains)            // If not, then create a new list of Nodes and put
	{                    // the new node at the end.
	    Node[] new_NodeSet = new Node[this.NodeSet.length+1];
	    int j;
	    for(j=0;j<this.NodeSet.length;j++)
		new_NodeSet[j]=this.NodeSet[j];
	    new_NodeSet[this.NodeSet.length] = a;
	    this.NodeSet = new_NodeSet;
	    //	    System.out.println("Node added.");
	}
	//        else
	    //	    System.out.println("This node already exists in the graph.");
    }
    
    public void add_edge(Edge b)   //A method to add an edge to the graph, incorporating multiple edges
    {                              //in previous Edge structures.
    	boolean exists = false;            //First, check to see if it exists already in the list of Edges 
    	boolean reverse_exists = false;    //or the reverse. 
        int i = 0;            //Represents a counter
	int edgeNumber = -1;  //Represents the edge that exists.
	for(i=0;i<EdgeSet.length;i++)
	{   
	    if(!exists && !reverse_exists) 
		{
		    int initi = EdgeSet[i].initial_name();
		    int termi = EdgeSet[i].terminal_name();
		    exists = (initi==b.initial_name() && termi==b.terminal_name());   //Check if init and term are same
		    reverse_exists = (termi==b.initial_name() && initi==b.terminal_name());  //Check if reversed.
		    edgeNumber = i;   //Keep track of which edge the new edge duplicated.
		}
	}
	
	if(!exists && !reverse_exists)  // If not, then create a new list of Edges and put
	{                               // the new Edge at the end.
	    Edge[] new_EdgeSet = new Edge[this.EdgeSet.length+1];
	    int j;
	    for(j=0;j<this.EdgeSet.length;j++)
		new_EdgeSet[j]=this.EdgeSet[j];
	    new_EdgeSet[this.EdgeSet.length] = b;
	    this.EdgeSet = new_EdgeSet;
//System.out.println("Edge added.");
	}
        else if(exists)  //If it does exist already, then make sure the list of gains contains the gains
	{                //from the new edge.
//System.out.println("This edge already exists in the graph; gains added to old edge.");
	    int ii=0;
	    for(ii=0;ii<b.gain().length;ii++)
		EdgeSet[edgeNumber].add_gain(b.gain()[ii]);
	}
	else  //If the reverse of the edge already exists, then make sure the list of gains contains
	{     //the NEGATIVES of the gains of the new edge.
//System.out.println("The reverse of this edge already exists in the graph; negative gains added to old edge.");
	    int ii=0;
	    for(ii=0;ii<b.gain().length;ii++)
		EdgeSet[edgeNumber].add_gain((-1)*b.gain()[ii]);
	}
    }

    /***************Complex Commands***********/

    /*********************************Deletion*********************************/
    public void delete(Edge b)   // A method to remove an edge.  Since multiple edges are represented in the same 
	                         // edge with multiple gains, we remove the edge if there is only one gain; 
	                         // otherwise we remove the FIRST gain.
    {
	if(b.isloop())           // In this program, we do not bother to remove loops.
	{
//System.out.println("This is a loop.  No need to delete this edge.");  
	    return;
	}

    	boolean exists = false;            //First, check to see if the list of Edges contains the edge 
    	boolean reverse_exists = false;    //or its reverse. 
        int i = 0;	                   //A loop counter.
	int edgeNumber = -1;               //Keeps track of which edge is to be removed.
	int orientedGain = -999;           //Keeps track of the gain to remove from the edge.
	boolean onlyOneGain = false;       //Determines if the edge we'll remove from is a multiple edge.

	for(i=0;i<this.EdgeSet.length;i++)  //pre-processing.
	{   
	    if(!exists && !reverse_exists) 
	    {
		int initi = this.EdgeSet[i].initial_name();    //Check edge number i to see if it is the same as b.
		int termi = this.EdgeSet[i].terminal_name();

		exists = (initi==b.initial_name() && termi==b.terminal_name());   //If correct orientation,
		if(exists)
		{   
		    orientedGain = b.gain()[0];                         //The gain to be removed is b[0].
		    onlyOneGain = (this.EdgeSet[i].gain().length==1);   //Check if this is the only gain in edge i
		}

       		reverse_exists = (termi==b.initial_name() && initi==b.terminal_name());  //Check if reversed.
		if(reverse_exists)
     	        {
		    orientedGain = -1*b.gain()[0];                      //The gain to be removed is (-1)*b[0]
		    onlyOneGain = (this.EdgeSet[i].gain().length==1);   //Check if this is the only gain in edge i
		}
		edgeNumber = i;   //Keep track of which edge in EdgeSet to remove.
	    }
	}

	if(!exists && !reverse_exists)  //error report
	{
	    //	    System.out.println("There is a problem.  You tried to delete an edge that does not exist.");
	}
	else         //You do this if the edge exists somewhere.
	{
	    if(onlyOneGain)   //If there is only one gain, remove the edge.
	    {
		if(b.gain()[0]==this.EdgeSet[edgeNumber].gain()[0])   //Of course, check if the gain to be removed
		{                                                     // Is the one in the list!
		    Edge[] new_EdgeSet = new Edge[this.EdgeSet.length-1];
		    for(i=0;i<edgeNumber;i++)
			new_EdgeSet[i] = this.EdgeSet[i];
		    for(i=edgeNumber;i<this.EdgeSet.length-1;i++)
			new_EdgeSet[i] = this.EdgeSet[i+1];
		    this.EdgeSet = new_EdgeSet;
//System.out.println("Edge deleted.");		
		}
//else
//   System.out.println("The gain to be deleted was not found in the list. Gains unchanged");
	    }
	    else             //If there is more than one gain, remove the gain.
	    {
		this.EdgeSet[edgeNumber].remove_gain(b.gain()[0]);
	    }
	}
//System.out.println("***Edge " + b + " deleted.");
    }


    /*********************************Contraction******************************/
    public void contract(Edge b)
    {
	if(b.isloop())
	{    
//System.out.println("This is a loop.  No need to contract this edge.");  
	    return;
	}

	//Check that the edge is an edge of the graph.
    	boolean exists = false;            //First, check to see if the list of Edges contains the edge 
    	boolean reverse_exists = false;    //or its reverse. 
        int i,j;               //Represent counters.
	int edgeNumber = -1;   //Represents the edge that `b' may duplicate.
	for(i=0;i<this.EdgeSet.length;i++)
	{   
	    if(!exists && !reverse_exists) 
	    {
		int initi = this.EdgeSet[i].initial_name();
		int termi = this.EdgeSet[i].terminal_name();
		exists = (initi==b.initial_name() && termi==b.terminal_name());   //Check if init and term are same
		reverse_exists = (termi==b.initial_name() && initi==b.terminal_name());  //Check if reversed.
		edgeNumber = i;   //Keep track of which edge the new edge duplicated.
	    }
	}
	if(!exists && !reverse_exists)  //error report
	{
//System.out.println("There is a problem.  You tried to contract an edge that does not exist.  Command ignored.");
	    return;
	}
	else   //Check that one of the gains is indeed zero, and keep track of which gain it is.
	{      //In order to contract an edge, one of its gains must be zero.  If not, you should have switched before.
	    boolean NoZeroGain=true;
	    int ZeroGain = -1;
	    for(i=0;i<this.EdgeSet[edgeNumber].gain().length;i++)
	    {
		if(NoZeroGain) 
		{ 
		    NoZeroGain = (this.EdgeSet[edgeNumber].gain()[i]!=0);
		    ZeroGain= i;
		}
	    }

	    if(NoZeroGain)
	    {
//System.out.println("Warning, you tried to contract an edge with no zero gain.  Command ignored");  
		return;
	    }
	    
    //If we've passed all the above conditions, we can proceed since the edge is not a loop and has a zero gain.
    //We'll make sure the lower numbered vertex is the initial vertex.
	    if(b.terminal_name()<b.initial_name())
		b.orient();

    //Determine the nodes we are going to join, and give the new node the max weight of the other two.
	    int initNode = b.initial_name();
	    int termNode = b.terminal_name();
	    int maxWeight;

	    if(b.initial_weight()>b.terminal_weight()) 
		maxWeight=b.initial_weight(); 
	    else maxWeight=b.terminal_weight();

	    Node Joined = new Node(b.initial_name(),maxWeight);  //This is the new node.
	    
    //For every edge that was incident to either of the joining nodes, modify that edge accordingly
    //by changing the edge to be incident to the new joined node.
	    
    //First, we'll remove the zero gain edge, either by deletion of the edge or removing the gain.
	    int[] Gain0 = {0};
	    Edge RemoveMe = new Edge(b.initial(),b.terminal(),Gain0);
	    this.delete(RemoveMe);

    //Next, we'll copy the list of edges.
	    Edge[] new_EdgeSet = new Edge[this.EdgeSet.length];
	    for(i=0;i<this.EdgeSet.length;i++)
		new_EdgeSet[i] = EdgeSet[i];
	    for(i=0;i<this.EdgeSet.length;i++)		
	    {
    //For each edge in the list that must be changed, either the initial node is transformed to Joined,
		if(this.EdgeSet[i].initial_name()==initNode || this.EdgeSet[i].initial_name()==termNode)
		{
		    Edge newEdge = new Edge(Joined,this.EdgeSet[i].terminal(),this.EdgeSet[i].gain());
		    new_EdgeSet[i] = newEdge;
		}
    //or the terminal node is transformed to Joined,
		if(this.EdgeSet[i].terminal_name()==initNode || this.EdgeSet[i].terminal_name()==termNode)
		{
		    Edge newEdge = new Edge(this.EdgeSet[i].initial(),Joined,this.EdgeSet[i].gain());
		    new_EdgeSet[i] = newEdge;
		}
    //or both.
		if((this.EdgeSet[i].initial_name()==initNode || this.EdgeSet[i].initial_name()==termNode)&& (this.EdgeSet[i].terminal_name()==initNode || this.EdgeSet[i].terminal_name()==termNode))
		{
		    Edge newEdge = new Edge(Joined,Joined,this.EdgeSet[i].gain());
		    new_EdgeSet[i] = newEdge;
		}
	    }

    //Find the two vertices initial and terminal, and remove the node of smaller number.
    //(We are making the assumption that there is at most one node of each number.)


	    boolean found_init = false; 
	    boolean found_term = false;            
	    int nodeNumber_init = -1;
	    int nodeNumber_term = -1;
	    for(i=0;i<this.NodeSet.length;i++)
	    {   
		if(!found_init)
	        {
		    found_init = found_init ||(b.initial_name()==this.NodeSet[i].name());  
		    nodeNumber_init = i;
		}
		if(!found_term) 
	        {
		    found_term = found_term ||(b.terminal_name()==this.NodeSet[i].name());  
		    nodeNumber_term = i;   
		}
	    }

	    Node[] new_NodeSet = new Node[this.NodeSet.length-1];
	    if(b.initial_name()<b.terminal_name())
	    {
		for(i=0;i<nodeNumber_term;i++)		
		    new_NodeSet[i] = this.NodeSet[i];
		for(i=nodeNumber_term;i<this.NodeSet.length-1;i++)		
		    new_NodeSet[i] = this.NodeSet[i+1];
		new_NodeSet[nodeNumber_init] = Joined;
	    }
	    else
	    {
		for(i=0;i<nodeNumber_init;i++)		
		    new_NodeSet[i] = this.NodeSet[i];
		for(i=nodeNumber_init;i<this.NodeSet.length-1;i++)		
		    new_NodeSet[i] = this.NodeSet[i+1];
		new_NodeSet[nodeNumber_term] = Joined;
	    }

	    this.NodeSet = new_NodeSet;
	    this.EdgeSet = new_EdgeSet;

    // We're going to need to consolidate edges that are the same!
    // That is, multiple edges connecting the same nodes need to be put into the same Edge structure.
	    this.ConsolidateEdges();

//System.out.println("****Edge " + b + " contracted.");
	}
    }

    /********************Consolidating edges with the same nodes***************/
    public void ConsolidateEdges()
    { 
	if(this.EdgeSet.length==0)
	{
	    //	    System.out.println("The graph has no edges; nothing to consolidate.");
	    return;
	}
	if(this.EdgeSet.length==1)
	{
	    //	    System.out.println("The graph has one edge; nothing to consolidate.");
	    return;
	}

	/**We create an array (EdgeList) to keep track of the incidences and go through the list of edges, 
	   keeping a list (DeleteMe) of those that repeat previous edges.  
	 **/
	int Vert1 = this.EdgeSet[0].initial_name();
	int Vert2 = this.EdgeSet[0].terminal_name();
	int[][] EdgeList = {{0,Vert1,Vert2}};   //A double array that keeps track of incidences, starting with 0th edge
	int[] DeleteMe = {};                    //A list of edges to be deleted.
	int i,j,k,l;             //These are counters.
	boolean forward,backward;//Used along the way to keep track if current edge is seen forward or backward before.
	int whichEdge;           //and where it occured previously.
	
	for(i=1;i<this.EdgeSet.length;i++)  //Starting with Edge 1 (2nd edge), check to see if it's in EdgeList.
	{
	    forward = false;
	    backward = false;
	    whichEdge = -1;
	    for(j=0;j<EdgeList.length;j++)  
	    {
		if(this.EdgeSet[i].initial_name()==EdgeList[j][1] && this.EdgeSet[i].terminal_name()==EdgeList[j][2])
		{   forward=true; whichEdge=j;}
	     else if(this.EdgeSet[i].terminal_name()==EdgeList[j][1] && this.EdgeSet[i].initial_name()==EdgeList[j][2])
		{   backward=true; whichEdge=j;}
	    }
	    
	    if(forward)
//This is the same edge, so consolidate gains and make a note to remove the edge later.
	    {
//System.out.println("I see the same edge");
		this.EdgeSet[EdgeList[whichEdge][0]].add_gain(this.EdgeSet[i].gain());
		int[] newDeleteMe = new int[DeleteMe.length+1];
		for(k=0;k<DeleteMe.length;k++)
		    newDeleteMe[k] = DeleteMe[k];
		newDeleteMe[DeleteMe.length] = i;
	    }
	    else 
	    {
		if(backward)
//This is the reverse of the same edge, so turn around, consolidate gains, and make a note to remove the edge later.
		{
//System.out.println("I see the reverse of the same edge");
		    this.EdgeSet[i].orient();
		    this.EdgeSet[EdgeList[whichEdge][0]].add_gain(this.EdgeSet[i].gain());
		    int[] newDeleteMe = new int[DeleteMe.length+1];
		    for(k=0;k<DeleteMe.length;k++)
			newDeleteMe[k] = DeleteMe[k];
		    newDeleteMe[DeleteMe.length] = i;
		}
		else 
//This is a new edge, so put it in EdgeList.
		{
//System.out.println("I see a new edge");
		    int ListLength = EdgeList.length;
		    int[][] newEdgeList = new int[ListLength+1][3];
		    for(k=0;k<ListLength;k++)
		    {for(l=0;l<3;l++)
		     {
			 newEdgeList[k][l] = EdgeList[k][l];
		     }
		    }
		    newEdgeList[ListLength][0] = i;
		    newEdgeList[ListLength][1] = this.EdgeSet[i].initial_name();
		    newEdgeList[ListLength][2] = this.EdgeSet[i].terminal_name();
		    EdgeList=newEdgeList;
		}
	    }
	}
    
	//Now delete the edges that were in the list of edges to be deleted.
	i=0;  //Represents the edge in the EdgeSet 
	j=0;  //Represents the edge in the EdgeList
	k=0;  //Represents the edge in the newEdgeSet.
	Edge[] newEdgeSet = new Edge[EdgeList.length];
	while(i<this.EdgeSet.length && j!=EdgeList.length)
	{	    
	    if(i==EdgeList[j][0])
	    {
 		newEdgeSet[k] = this.EdgeSet[i];
		i++; j++; k++;
	    }
	    else i++;
	}
	this.EdgeSet=newEdgeSet;
    }

    /*************************Switching**********************/

    public void switching(Node a, int b)
    {
	int i,j;
	boolean exists=false;
	int WhichNode=-1;
	//Make sure that the Node exists.  When you find it, add b to the weight.
	for(i=0;i<this.NodeSet.length;i++)
	{   
	    if(this.NodeSet[i].name()==a.name())
		{exists=true; this.NodeSet[i].new_weight(this.NodeSet[i].weight()+b); WhichNode=i;}
	}
	if(!exists)  //If you don't find it, scream!
	{
//System.out.println("You tried to do a top-vertex switching on a vertex that does not exist.  Command ignored.");
	    return;
	}	

	// Now we have to switch every edge that is adjacent to a.

	int[] ToBeSw;  // list of gains to be modified.
	for(i=0;i<this.EdgeSet.length;i++)
	{
	    if(!this.EdgeSet[i].isloop())   //If it's a loop, you don't have to do any switching.
	    {
		if(this.EdgeSet[i].initial_name()==a.name()) //If the node is the initial vertex,
		{
		    ToBeSw = this.EdgeSet[i].gain();
		    for(j=0;j<ToBeSw.length;j++)
		    {
			ToBeSw[j] = ToBeSw[j]-b;  //subtract b from each gain.
		    }
		    this.EdgeSet[i].new_gain(ToBeSw);  //replace the gains, and then modify the weight of the node
		    this.EdgeSet[i].initial().new_weight(this.NodeSet[WhichNode].weight());  //in the edge set.
		}	   
		if(this.EdgeSet[i].terminal_name()==a.name()) //If the node is the terminal vertex,
		{
		    ToBeSw = this.EdgeSet[i].gain();
		    for(j=0;j<ToBeSw.length;j++)
		    {
			ToBeSw[j] = ToBeSw[j]+b; //add b to each gain.
		    }
		    this.EdgeSet[i].new_gain(ToBeSw); 
		    this.EdgeSet[i].terminal().new_weight(this.NodeSet[WhichNode].weight());
		}
	    }	   
	}
//System.out.println("Switched Graph:\n" + this);
    }

    /**********************Output the array of vertex weights.*****************/
    public int[] Vertex_Weights()
    {
	//There should be an error to make sure that there are no more edges.
        int i;         // A generic counter.
        int[] weights = new int[this.NodeSet.length];     // An array of the weights.
        for(i=0;i<this.NodeSet.length;i++)        // Go through the list of nodes.
	{
	    weights[i]=this.NodeSet[i].weight();    // Record a list of all the weights of the nodes.
        }
        return(weights);   // Output the list of weights.
    }
    

    /**************************Outputting Commands**********************/
    public int PrevGraph()
    {
	return this.PrevGraph;
    }
    public Node[] NodeSet()
    {
	return this.NodeSet;
    }
    public Edge[] EdgeSet()
    {
	return this.EdgeSet;
    }
    public int sign()
    {
	return this.sign;
    }
    public boolean NoArcs()
    {
	boolean NoArcExists=true;
	for(int i=0;i<this.EdgeSet.length;i++)
	    NoArcExists= NoArcExists && this.EdgeSet[i].isloop();
      	return(NoArcExists);
    }

    /***************Method to output the graph in a pretty format************/

   public String toString()
   {
      String output= new String();  //makes the output string and then
      output = "#This graph contains " + this.NodeSet.length + " vertices and " + this.EdgeSet.length + " (multi)edge(s). It contributes a sign of " + this.sign + ".\n";

      int i;
      if(NodeSet.length>2)
      {
	  output = output + "#The vertices (and weights) are:  ";
	  for(i=0;i<NodeSet.length-1;i++)
	  {
	      output = output + this.NodeSet[i].name() + " (" + this.NodeSet[i].weight() + "), ";
	  }
      output = output + "and " + this.NodeSet[this.NodeSet.length-1].name() + " (" + this.NodeSet[i].weight() + ").\n#The edges are:";
      }
      if(NodeSet.length==2)
      output = output + "#The vertices (and weights) are: " + this.NodeSet[0].name() + " (" + this.NodeSet[0].weight() + ") and " + this.NodeSet[1].name() + " (" + this.NodeSet[1].weight() + ").\n#The edges are:";
      if(NodeSet.length==1)
      output = output + "#The vertex (with its weight) is: " + this.NodeSet[0].name() + " (" + this.NodeSet[0].weight() + ").\n#The edges are:";

      for(i=0;i<EdgeSet.length;i++)
      {
	  output = output + "\n#  " + this.EdgeSet[i];
      }
      return output;
   }


}