/* Store graph into a vector by representing it with lists 
   of vertices connected to others by edges according to their
   labels.  For example, the first element of the vector would 
   represent vertex 0 and would hold a vector whose elements 
   represent all of the other vertices that are connected to it
   by edges.  The second would represent vertex 1, etc.  Then
   generate a layout and calculate its sum.  If the layout
   or sum meets one of the stopping conditions, then return
   the result.  Otherwise continue in the same way with
   a new layout until either a stopping condition is reached
   or every possible permutation of the layout was used.*/
   
   public class MinimumSum {   
	   public vertices = new Vector();
	   public layout = new Vector();
	   /* Initialize a global variable which will hold the smallest sum
	   	  calculated so far */
	   public int min_sum = 0;   
	   
	   /* Initialize a global variable which will hold the layout that
	      gave the smallest sum so far */
	   public Vector min_sum_layout = new Vector();
	   
	   /* Initialize a global boolean variable which will be set to 
	      true if the minimum sum is found */
	   public boolean min_sum_found = false;
	   
	   public static void main(String argv[]) {   
	   // Represent graph numerically with vector's
	   for (i = 0; i < number_of_vertices; i++) {
	   		/* Create a vector to represent the vertex i and add it
	   		   to the vertices vector*/
	   		vertices.addElement( new Vector() );
	   		
	   		for ( j = 0; j < number_of_vertices; j++ ) {   			
	   			/* If vertex i is connected to vertex j, add that vertex 
				   to i's list which represents all vertices connected to 
				   it by and edge. */
	   			if ( vertex_at_j_connected_to_vertex_i ) {
	   				// Add the vertex j that is connected to i.
	   				(vertices.lastElement()).addElement(new Integer(j))
	   			}
	   		}   		   		
	   }
	   
	   /* Go through each permutation of the vertices to find
	      best possible layout.*/
	   while ( (layout = getNextPermutation()) != null 
	   		   && min_sum_found == false) {
	 		/* Set the minimum sum to the sum calculated from the new 
			   layout and save the layout which gave this new 
		       minimum sum */  			  			 
	   		if ( calculate_sum( layout ) < min_sum || min_sum == 0) {   		
	   			min_sum = calculate_sum( layout );  // save minimum sum
	   			min_sum_layout = layout; // save layout
	   		}
	   		
	   		/* As stated in Observation 3, when the sum is the number of 
			   vertices - 1, then the best possible layout is found and 
			   there is no need to keep trying more permutations.  
			   Also if observation 2 is found to be true, the best
	   		   possible layout will have been found and the algorithm 
			   can be terminated. These are the stopping conditions.*/
	   		if ( min_sum = #_of_vertices_in_graph - 1 
				|| check_observation_2(layout) == true) {
	   			 min_sum_found = true;
	   		}
	   }    
	   
	   // Returns the value of the minimum sum found for the graph.
	   return min_sum;
   }
   
   // Pseudo Functions to help calculate the minimum sum
   public Vector getNextPermutation() {
   		/* function will return the next possible permutation in a vector.  
   		   It will return null if all permutations have been exhausted.  
		   The function starts with the permutation 1,2,3...n and works 
		   from there.*/
   }
   
   public int calculate_sum(Vector permutation) {
   		/* function will calculate the sum from the permutation
   		   that is passed to it.*/
   		   
   }
   
   public boolean check_observation_2( Vector layout ) {
   		/* this function will check to see if all the vertices in 
		   the graph meet the following condition as stated in observation 2: 
   		   For a set of vertices nx...ny, if nx and ny are connected by an 
		   edge and every vertex between is connected by an edge of length 
		   one to the vertices adjacent to it, then there is no furthur 
		   optimization possible on this set of vertices. */
   }

• The algorithm starts with the original graph G and creates a vector called "vertices" which is the numerical representation of the graph.
  The vector for this graph looks like this: [[1,3], [0,4], [3], [0,2], [1]].
• Next it calls the function getNextPermutation() to get a layout for the graph. In this case, [0,1,2,3,4] as can be seen in the original graph.
• Now, from the permutation of the graph it calls calculate_sum to get the sum of the current layout. If it is smaller than the current minimum sum, then it will set it to the new calculated sum. Also, the vector layout will save the current permutation layout. In this case the sum is 8 and there was no previous sum, so it sets min_sum to 8. The min_sum doesn't equal n-1, where n is the number of vertices and observation 2 is false, so the min_sum_found flag isn't set true because it didn't meet one of the stopping conditions and there are still other permutations to try.
• The while loop cycles back through and a new layout is generated by the getNextPermutation() function. For this example the new layout is [4,0,1,2,3] as can be seen in step 1.
• Now, from the permutation of the graph it calls calculate_sum to get the sum of the current layout. In this case the sum is 7, which is smaller than the previous sum of 8, so it sets min_sum to 7. The min_sum doesn't equal n-1, where n is the number of vertices and observation 2 is false, so the min_sum_found flag isn't set true because it didn't meet one of the stopping conditions and there are still other permutations to try.
• The while loop cycles back through and a new layout is generated by the getNextPermutation() function. For this example the new layout is [4,1,0,2,3] as can be seen in step 2.
• Now, from the permutation of the graph it calls calculate_sum to get the sum of the current layout. In this case the sum is 5, which is smaller than the previous sum of 7, so it sets min_sum to 5. The min_sum doesn't equal n-1, where n is the number of vertices and observation 2 is false, so the min_sum_found flag isn't set true because it didn't meet one of the stopping conditions and there are still other permutations to try.
• The while loop cycles back through and a new layout is generated by the getNextPermutation() function. For this example the new layout is [4,1,0,3,2] as can be seen in the final step.
• Now, from the permutation of the graph it calls calculate_sum to get the sum of the current layout. In this case the sum is 4, which is smaller than the previous sum of 5, so it sets min_sum to 4. The min_sum equals n-1, where n is the number of vertices, so the min_sum_found flag is set true and the while loop condition fails because we have met one of the stopping conditions.
• Thus, the algorithm returns the result and the minimum sum is 5.

• The algorithm starts with the original graph G and creates a vector called "vertices" which is the numerical representation of the graph.
  The vector for this graph looks like this: [[1,2,3,4], [0,4], [0,3], [0,2], [0,1]].
• Next it calls the function getNextPermutation() to get a layout for the graph. In this case, [0,1,2,3,4] as can be seen in the original graph.
• Now, from the permutation of the graph it calls calculate_sum to get the sum of the current layout. If it is smaller than the current minimum sum, then it will set it to the new calculated sum. Also, the vector layout will save the current permutation layout. In this case the sum is 14 and there was no previous sum, so it sets min_sum to 14. The min_sum doesn't equal n-1, where n is the number of vertices and observation 2 is false, so the min_sum_found flag isn't set true because it didn't meet one of the stopping conditions and there are still other permutations to try.
• The while loop cycles back through and a new layout is generated by the getNextPermutation() function. For this example the new layout is [0,4,1,2,3] as can be seen in step 1.
• Now, from the permutation of the graph it calls calculate_sum to get the sum of the current layout. In this case the sum is 12, which is smaller than the previous sum of 14, so it sets min_sum to 12. The min_sum doesn't equal n-1, where n is the number of vertices and observation 2 is false, so the min_sum_found flag isn't set true because it didn't meet one of the stopping conditions and there are still other permutations to try.
• The while loop cycles back through and a new layout is generated by the getNextPermutation() function. For this example the new layout is [4,1,2,0,3] as can be seen in step 2.
• Now, from the permutation of the graph it calls calculate_sum to get the sum of the current layout. In this case the sum is 10, which is smaller than the previous sum of 12, so it sets min_sum to 10. The min_sum doesn't equal n-1, where n is the number of vertices and observation 2 is false, so the min_sum_found flag isn't set true because it didn't meet one of the stopping conditions and there are still other permutations to try.
• The while loop cycles back through and a new layout is generated by the getNextPermutation() function. For this example the new layout is [4,1,0,3,2] as can be seen in the final step.
• Now, from the permutation of the graph it calls calculate_sum to get the sum of the current layout. In this case the sum is 8, which is smaller than the previous sum of 10, so it sets min_sum to 8. The min_sum does not equal n-1, where n is the number of vertices, but observation 2 is true so the min_sum_found flag is set true and the while loop condition fails because we have met one of the stopping conditions.
• Thus, the algorithm returns the result and the minimum sum is 8.