code 03-02-2014d1659
2014-03-03code 03-02-2014d1659
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;
}
}