code
{
import java.util.List;
import java.net.*;
import java.util.ArrayList;
import java.util.HashSet;

import org.jgrapht.*;
import org.jgrapht.alg.KShortestPaths;
import org.jgrapht.graph.*;


public class GraphManager<V> {

	UsefulTools useful_tools = new UsefulTools();
	
	public static void main(String[] args) {
		
		GraphManager gm = new GraphManager();
		UsefulTools useful_tools = new UsefulTools();
		System.out.println(useful_tools.getTime());
		String airport_network = useful_tools.storeTextFiletoString("C:\\Users\\kurtw_000\\Documents\\kurt\\storage\\CIM Research Folder\\DR\\2013\\11-11-13\\analysis of a variety of networks\\airports\\airport network clean.txt");
		/*
		UndirectedGraph<String, DefaultEdge> stringGraph = createStringGraph("1\t3\n2\t3");
		*/
		UndirectedGraph<String, DefaultEdge> stringGraph = createStringGraph(airport_network);
        // note undirected edges are printed as: {<v1>,<v2>}
       
		
		
        System.out.println(gm.averageSearchInformationEntropyOfWholeGraph(stringGraph, 50));
        System.out.println(useful_tools.getTime());
	}

	
	 /***
     ** Take a string of an edge list format graph, and then build the corresponding JGraphT undirected graph.
     */
    private static UndirectedGraph<String, DefaultEdge> createStringGraph(String graph_in_edge_list_format)
    {
        UndirectedGraph<String, DefaultEdge> g =
            new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

        String[] rows = graph_in_edge_list_format.split("\r");
        ArrayList vertices = new ArrayList();
        for(int i=0; i<rows.length; i++)
        {
        	String[] v = rows[i].split("\\s");
        	vertices.add(v[0]);
        	vertices.add(v[1]);
        }
     // add elements to al, including duplicates
        HashSet hs = new HashSet();
        hs.addAll(vertices);
        vertices.clear();
        vertices.addAll(hs);
        
        
        // add the vertices
        for(int i=0; i<vertices.size(); i++)
        {
        	
        	g.addVertex(vertices.get(i).toString());
        }
        

        // add edges to create a circuit
        for(int i=0; i<rows.length; i++)
        {
        	String[] v = rows[i].split("\\s");
        	g.addEdge(v[0], v[1]);
        }

        return g;
    }
    
    public List findShortestPaths(Graph graph, String startVertex, String endVertex, int number_of_paths_to_be_computed)
    {
    	KShortestPaths kshortestpaths = new KShortestPaths(graph,startVertex,number_of_paths_to_be_computed);
    	List the_return_list = kshortestpaths.getPaths(endVertex);
    	return the_return_list;
    }
    
    /*
     * probability Of Following Path In A RandomWalk
     * from the paper titled "Characterization of complex networks: A survey of measurements" when they are defining search information entropy
     */
    
    public double probabilityOfFollowingPathInARandomWalk(UndirectedGraph<String, DefaultEdge> graph, ArrayList list_of_vertices_in_path)
    {
    	double return_value = 0;
    	return_value = 1/graph.degreeOf(list_of_vertices_in_path.get(0).toString().replaceAll(" ", ""));
    	//now multiply the reciprocal of the degree minus one for each vertex in the path
    	for(int i=1; i<list_of_vertices_in_path.size()-1; i++)
    	{
    		int current_degree = graph.degreeOf(list_of_vertices_in_path.get(i).toString().replaceAll(" ", ""));
    		return_value=return_value*(1/(current_degree-1));
    	}
    	
    	return return_value;
    }
    
   public ArrayList convertPathToArrayListOfVertices(String the_path_from_jgrapht)
    {
    	the_path_from_jgrapht =  the_path_from_jgrapht.replaceAll(":", ",");
    	the_path_from_jgrapht = the_path_from_jgrapht.replaceAll("\\[", "");
    	the_path_from_jgrapht = the_path_from_jgrapht.replaceAll("]", "");
    	the_path_from_jgrapht = the_path_from_jgrapht.replaceAll("\\(", "");
    	the_path_from_jgrapht = the_path_from_jgrapht.replaceAll("\\)", "");
    	ArrayList list = useful_tools.stringWithCommasToArrayList(the_path_from_jgrapht);
    	list = useful_tools.removeDuplicates(list);
    	/*
    	the_path_from_jgrapht = list.toString();
    	the_path_from_jgrapht = the_path_from_jgrapht.replaceAll("\\[", "");
    	the_path_from_jgrapht = the_path_from_jgrapht.replaceAll("]", "");
    	*/
    	return list;
    }
   
   /*
    * The search information entropy from vertex I to vertex B.
    */
   
   public double searchInformationEntropyFromIToB(UndirectedGraph<String, DefaultEdge> graph, String start_vertex, String end_vertex, int number_of_paths_to_compute_in_shortest_path_calculation)
   {
	   double return_value = 0;
	   //first get all of the shortest paths from i to b
	   List list_of_shortest_paths = findShortestPaths(graph, start_vertex,end_vertex, number_of_paths_to_compute_in_shortest_path_calculation);
       
	   //now loop through all the paths and get the sum of the probability of following each path in a random walk
	   
	   for(int path_count=0; path_count<list_of_shortest_paths.size(); path_count++)
	   {
		   ArrayList path = convertPathToArrayListOfVertices(list_of_shortest_paths.get(0).toString());
	       return_value+= probabilityOfFollowingPathInARandomWalk(graph, path);
	   }
       
	   return_value = 0-(Math.log(return_value)/Math.log(2));
	   
	   return return_value;
   }
   
   /*
    * This method calculates the average search information entropy of the whole graph
    */
   public double averageSearchInformationEntropyOfWholeGraph(UndirectedGraph<String, DefaultEdge> graph, int number_of_paths_to_compute_in_shortest_path_calculation)
   {
	   
	   double sum =0;
	   double number_of_elements_for_sum = 0;
	   ArrayList entropies = new ArrayList();
	   //get a list of the vertices
	   String s_vertices = graph.vertexSet().toString();
	   s_vertices = s_vertices.replaceAll("\\[", "");
	   s_vertices = s_vertices.replaceAll("\\]", "");
	   s_vertices = s_vertices.replaceAll(" ", "");
	   ArrayList vertices = useful_tools.stringWithCommasToArrayList(s_vertices);
	   for(int start_vertex_count=0; start_vertex_count<vertices.size();start_vertex_count++)
	   {
		   for(int end_vertex_count=start_vertex_count+1; end_vertex_count<vertices.size();end_vertex_count++)
		   {
			   sum+=searchInformationEntropyFromIToB(graph, vertices.get(start_vertex_count).toString().replaceAll(" ", ""), vertices.get(end_vertex_count).toString().replaceAll(" ",""), number_of_paths_to_compute_in_shortest_path_calculation);
			   number_of_elements_for_sum++;
		   }
	   }
	   
	   //now get the average entropy
	   return sum/number_of_elements_for_sum;
   }
    
    
}


}