Home News Feed

search engine by freefind	advanced

code pre 03-02-2014d1659

2014-08-29

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;
}


}


}

About Edit