code 03-02-2014d1659

2014-03-03

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\\smaller_airport_network\\airport network clean 500e.txt");
		String 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");
		
		//String small_test_graph = useful_tools.storeTextFiletoString("C:\\Users\\kurtw_000\\Documents\\kurt\\storage\\DR\\2014\\02-26-2014d1654\\graph with three shortest paths from two to three.txt");
		
		
		/*
		UndirectedGraph<String, DefaultEdge> stringGraph = createStringGraph("1\t3\n2\t3");
		*/
		UndirectedGraph<String, DefaultEdge> graph = createStringGraph(network);
        // note undirected edges are printed as: {<v1>,<v2>}
       
		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);
		   
		System.out.println(gm.searchInformationEntropyFromIToB(graph, vertices.get( (Double.valueOf(Math.round(Math.random()*vertices.size())).intValue())).toString().replaceAll(" ", ""), vertices.get(Double.valueOf(Math.round(Math.random()*vertices.size())).intValue()).toString().replaceAll(" ","")));
        
		//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;
    }
    
    public List findShortestPaths(Graph graph, String startVertex, String endVertex)
    {
    	int number_of_paths_to_try = 2;
    	boolean found_all_of_the_shortest_paths = false;
    	List the_return_list = null;
    	while(!found_all_of_the_shortest_paths)
    	{
    		KShortestPaths kshortestpaths = new KShortestPaths(graph,startVertex,number_of_paths_to_try);
        	the_return_list = kshortestpaths.getPaths(endVertex);
        	ArrayList no_of_vertices_in_paths = new ArrayList();
        	if(the_return_list!=null)
        	{
	        	for(int i=0; i<the_return_list.size(); i++)
	        	{
	        		String current_path = the_return_list.get(i).toString();
	        		no_of_vertices_in_paths.add(convertPathToArrayListOfVertices(current_path).size());
	        	}
	        	
	        	if(the_return_list.size()==1)
	    		{
	    			found_all_of_the_shortest_paths = true;
	    		}
	        	else
	        	{
		        	for(int i=1; i<no_of_vertices_in_paths.size();i++)
		        	{
		        		
		        		if(!no_of_vertices_in_paths.get(i).toString().equals(no_of_vertices_in_paths.get(i-1).toString()))
		        		{
		        			found_all_of_the_shortest_paths = true;
		        			kshortestpaths = new KShortestPaths(graph,startVertex,number_of_paths_to_try-1);
		        			the_return_list = kshortestpaths.getPaths(endVertex);
		        		}
		        		
		        	}
		        	if(found_all_of_the_shortest_paths==false)
		        	{
		        		number_of_paths_to_try++;
		        	}
	        	}
        	}
        	else
        	{
        		found_all_of_the_shortest_paths = true;
        	}
        	
    	}
    	
    	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
     */
    //I think there is a slight glitch in this function.  The first and last edges may not list the start vertex first and the end vertex last.  I need to fix this.
    public double probabilityOfFollowingPathInARandomWalk(UndirectedGraph<String, DefaultEdge> graph, ArrayList list_of_vertices_in_path, String start_vertex, String end_vertex)
    {
    	double return_value = 1;
    	int degree = graph.degreeOf(start_vertex);
    	return_value = 1/Integer.valueOf(degree).doubleValue();
    	//remove the start and end vertex from the list of vertices in the path
    	int location_of_start_vertex = list_of_vertices_in_path.indexOf(start_vertex.replaceAll(" ", ""));
    	int location_of_end_vertex = list_of_vertices_in_path.indexOf(end_vertex.replaceAll(" ", ""));
    	list_of_vertices_in_path.remove(location_of_start_vertex);
    	if(location_of_start_vertex<location_of_end_vertex)
    	{
    		list_of_vertices_in_path.remove(location_of_end_vertex-1);
    	}
    	else
    	{
    		list_of_vertices_in_path.remove(location_of_end_vertex);
    	}
    	//now multiply the reciprocal of the degree minus one for each vertex in the path
    	for(int i=0; i<list_of_vertices_in_path.size(); i++)
    	{
    		double current_degree = Double.valueOf(graph.degreeOf(list_of_vertices_in_path.get(i).toString().replaceAll(" ", ""))).doubleValue();
    		
    		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("\\)", "");
    	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)
   {
	   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);
       
	   //now loop through all the paths and get the sum of the probability of following each path in a random walk
	   if(list_of_shortest_paths!=null)
	   {
		   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, start_vertex, end_vertex);
		   }
		   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)
   {
	   
	   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_elements_for_sum++;
		   }
	   }
	   
	   //now get the average entropy
	   return sum/number_of_elements_for_sum;
   }
    
    
}

azim58wiki: