code 03-02-2014d1701
2014-03-03import java.util.ArrayList;
public class GraphGenerator
public static void main(String[] args) {
// TODO Auto-generated method stub
GraphGenerator gg = new GraphGenerator();
System.out.println(gg.generateLatticeGraphInEdgeListFormat(14, 30, 6));
public String generateRandomGraphInEdgeListFormat(int number_of_vertices, int number_of_edges)
String return_string = "";
for(int i=0; i<number_of_edges; i++)
{
int first_value = Double.valueOf(Math.round(Math.random()*(number_of_vertices-1))).intValue();
int second_value = 0;
boolean different_second_value_found = false;
while(!different_second_value_found)
{
second_value = Double.valueOf(Math.round(Math.random()*(number_of_vertices-1))).intValue();
if(first_value!=second_value)
{
different_second_value_found = true;
}
if(i!=number_of_edges-1)
return_string += first_value +"\t"+second_value+"\r\n";
else
return_string += first_value +"\t"+second_value;
}
return return_string;
}
/*
* This generates a ring graph. A ring should have the same number of vertices and edges with the edges connected sequentially.
* With this function a ring is generated first, then the ring is formed again until edges run out
*/
public String generateRingGraphInEdgeListFormat(int number_of_vertices, int number_of_edges)
String return_string ="";
int vertex_count = 1;
for(int edge_count =0; edge_count<number_of_edges; edge_count++)
{
if(edge_count!=number_of_edges-1)
{
return_string+=vertex_count-1+"\t"+vertex_count+"\r\n";
vertex_count++;
if(vertex_count==number_of_vertices)
{
vertex_count=1;
}
else
return_string+=vertex_count-1+"\t"+vertex_count;
}
return return_string;
}
/*
* The lattice has rows and columns. The goal during generation of the lattice is to connect adjacent vertices in rows and columns, but not diagonally.
* To transition from an id to a pair of coordinates of the row and column use the following formula (if there are 4 columns in the lattice)
* row of id n = floor(n/4)
* column of id n = (n-1)%4
*
* id of (row, column) = row*4+column
*
*for a diagram of the testing see
*"C:\Users\kurtw_000\Documents\kurt\storage\DR\2014\03-02-2014d1656\lattice network sketch IMG_20140302_165455.jpg"
*/
public String generateLatticeGraphInEdgeListFormat(int number_of_vertices, int number_of_edges, int number_of_columns_in_lattice)
String return_string ="";
//keep track of the number of connections from each vertex for each vertex and do not allow more than the number of the current round through all of the vertices
ArrayList vertices = new ArrayList();
for(int i=0; i<number_of_vertices; i++)
{
ArrayList vertex_connections = new ArrayList();
for(int j=0; j<number_of_vertices; j++)
{
vertex_connections.add(0);
vertices.add(vertex_connections);
}
int max_number_of_rows = Double.valueOf(Math.floor(number_of_vertices/number_of_columns_in_lattice)+1).intValue();
int vertex_count = 0;
int edge_count=0;
int edges_explored = 0; //this counts the number of 4 edges created for the current vertex
int current_row=0;
int current_column = 0;
int number_of_connections_allowed_from_a_vertex=1;
while(edge_count<number_of_edges)
//connect the current vertex to the 4 adjacent vertices if there are enough edges
if(edges_explored==0)
{
//connect to the left vertex
int row_of_destination_vertex = current_row;
int column_of_destination_vertex = current_column-1;
if(column_of_destination_vertex>-1)
{
int destination_vertex = row_of_destination_vertex*number_of_columns_in_lattice+column_of_destination_vertex;
if(destination_vertex<number_of_vertices)
{
ArrayList connections_for_this_vertex = (ArrayList) vertices.get(vertex_count);
int connections = Integer.valueOf(connections_for_this_vertex.get(destination_vertex).toString()).intValue();
if(connections<number_of_connections_allowed_from_a_vertex)
{
return_string+=vertex_count+"\t"+destination_vertex+"\r\n";
edge_count++;
connections++;
connections_for_this_vertex.set(destination_vertex, connections);
ArrayList connections_for_destination_vertex = (ArrayList) vertices.get(destination_vertex);
int value = Integer.valueOf(connections_for_destination_vertex.get(vertex_count).toString()).intValue();
value++;
connections_for_destination_vertex.set(vertex_count, value);
}
}
edges_explored++;
}
else if(edges_explored==1)
//connect to the right vertex
int row_of_destination_vertex = current_row;
int column_of_destination_vertex = current_column+1;
if(column_of_destination_vertex<number_of_columns_in_lattice)
{
int destination_vertex =row_of_destination_vertex*number_of_columns_in_lattice+column_of_destination_vertex;
if(destination_vertex<number_of_vertices)
{
ArrayList connections_for_this_vertex = (ArrayList) vertices.get(vertex_count);
int connections = Integer.valueOf(connections_for_this_vertex.get(destination_vertex).toString()).intValue();
if(connections<number_of_connections_allowed_from_a_vertex)
{
return_string+=vertex_count+"\t"+destination_vertex+"\r\n";
edge_count++;
connections++;
connections_for_this_vertex.set(destination_vertex, connections);
ArrayList connections_for_destination_vertex = (ArrayList) vertices.get(destination_vertex);
int value = Integer.valueOf(connections_for_destination_vertex.get(vertex_count).toString()).intValue();
value++;
connections_for_destination_vertex.set(vertex_count, value);
}
}
edges_explored++;
}
else if(edges_explored==2)
//connect to the bottom vertex
int row_of_destination_vertex = current_row-1;
int column_of_destination_vertex = current_column;
if(row_of_destination_vertex>-1)
{
int destination_vertex = row_of_destination_vertex*number_of_columns_in_lattice+column_of_destination_vertex;
if(destination_vertex<number_of_vertices)
{
ArrayList connections_for_this_vertex = (ArrayList) vertices.get(vertex_count);
int connections = Integer.valueOf(connections_for_this_vertex.get(destination_vertex).toString()).intValue();
if(connections<number_of_connections_allowed_from_a_vertex)
{
return_string+=vertex_count+"\t"+destination_vertex+"\r\n";
edge_count++;
connections++;
connections_for_this_vertex.set(destination_vertex, connections);
ArrayList connections_for_destination_vertex = (ArrayList) vertices.get(destination_vertex);
int value = Integer.valueOf(connections_for_destination_vertex.get(vertex_count).toString()).intValue();
value++;
connections_for_destination_vertex.set(vertex_count, value);
}
}
edges_explored++;
}
else if(edges_explored==3)
//connect to the top vertex
int row_of_destination_vertex = current_row+1;
int column_of_destination_vertex = current_column;
if(row_of_destination_vertex<max_number_of_rows)
{
int destination_vertex = row_of_destination_vertex*number_of_columns_in_lattice+column_of_destination_vertex;
if(destination_vertex<number_of_vertices)
{
ArrayList connections_for_this_vertex = (ArrayList) vertices.get(vertex_count);
int connections = Integer.valueOf(connections_for_this_vertex.get(destination_vertex).toString()).intValue();
if(connections<number_of_connections_allowed_from_a_vertex)
{
return_string+=vertex_count+"\t"+destination_vertex+"\r\n";
edge_count++;
connections++;
connections_for_this_vertex.set(destination_vertex, connections);
ArrayList connections_for_destination_vertex = (ArrayList) vertices.get(destination_vertex);
int value = Integer.valueOf(connections_for_destination_vertex.get(vertex_count).toString()).intValue();
value++;
connections_for_destination_vertex.set(vertex_count, value);
}
}
edges_explored++;
}
if(edges_explored==4)
edges_explored = 0;
vertex_count++;
if(vertex_count==number_of_vertices)
{
vertex_count=0;
number_of_connections_allowed_from_a_vertex++;
current_row=0;
current_column=0;
else
if((current_column+1)/number_of_columns_in_lattice==1)
{
current_column=0;
current_row++;
else
current_column++;
}
}
}
return return_string;
}
public String generateStarGraphInEdgeListFormat(int number_of_vertices, int number_of_edges)
String return_string ="";
int vertex_count = 1;
for(int edge_count =0; edge_count<number_of_edges; edge_count++)
{
if(edge_count!=number_of_edges-1)
{
return_string+=vertex_count+"\t0\r\n";
vertex_count++;
if(vertex_count==number_of_vertices)
{
vertex_count=1;
}
else
return_string+=vertex_count+"\t0\r\n";
}
return return_string;
}
}