import java.awt.Point;
import java.util.*;
import edu.uci.ics.jung.graph.UndirectedGraph;
import edu.uci.ics.jung.graph.UndirectedOrderedSparseMultigraph;
/**
* Application to perform GNAVE algorithm
* @author jshou, babsher, cbolson
*
*/
public class RouteCapture {
//public static HashMap<Integer,ArrayList<Node>> network;
public static HashMap<Integer, Node> nodes;
public static UndirectedGraph<Node,Edge> network;
//public static final int SHARED_KEYS = 1;
//public static final int RANGE = 1;
public static void main(String[] args){
nodes = new HashMap<Integer, Node>();
// create a network with a probability of connectedness of .9999
network = createNetwork(.9999, 5, 1, 10, 1);
}
/**
* This function will return the key ring size.
* @param pc - Probability of creating a connected graph
* @param numNodes - number of nodes in graph
* @param pool - size of key pool
* @param n_prime - size of neighborhood
* @return key ring size for each node
*/
public static int calculateKeySizes(double pc, int numNodes, int pool, int n_prime){
// TODO Auto-generated method stub
// Use Corey's matlab stuff
return 1;
}
public static UndirectedGraph<Node,Edge> createNetwork(double Pc, int poolSize, int n_prime, int numNodes, int keyRingSize){
// initalize graph
UndirectedGraph<Node,Edge> graph = new UndirectedOrderedSparseMultigraph<Node, Edge>();
// Create Key Pool
ArrayList<Integer> keyPool = new ArrayList<Integer>();
for(int i = 0; i < poolSize; i++){
keyPool.add(i);
}
HashMap<Integer, Node> nodelist = createNodes(0, 0, keyPool);
// get keys for nodes
ArrayList<Integer> keylist = new ArrayList<Integer>(nodes.keySet());
for(int i = 0; i < keylist.size(); i++){
int key = keylist.get(i);
Node curr = nodelist.get(key);
// find hood
ArrayList<Integer> hood = curr.getNeighborhood(n_prime, numNodes, nodelist);
// for each node in hood of the current node
// create edge if 2 nodes share a key and are near each other
for(int j = 0; j < hood.size(); j++){
int neighborId = hood.get(j);
Node neighbor = nodelist.get(neighborId);
// find the intersection of the two key rings
ArrayList<Integer> sharedKeys = (ArrayList<Integer>) neighbor.getKeys().clone();
sharedKeys.retainAll(curr.getKeys());
// if there is some shared create an edge
if(!sharedKeys.isEmpty()){
Edge edge = new Edge(sharedKeys, curr.getId(), neighbor.getId());
graph.addEdge(edge, curr, neighbor);
}
}
}
return graph;
}
/**
* This class creates the node list for the network.
* @param numNodes - number of nodes to create
* @param keyRingSize - size of key ring for each node
* @param n_prime - size of neighborhood
* @return a hash map of node id to node class
*/
public static HashMap<Integer, Node> createNodes(int numNodes, int keyRingSize, ArrayList<Integer> keyPool){
HashMap<Integer, Node> nodelist = new HashMap<Integer, Node>();
Point gridSize = getGridSize(numNodes);
// iterate over the grid and
// create nodes for each location
for(int x = 0; x < gridSize.x; x++){
for(int y = 0; y < gridSize.y; y++){
int id = Node.computeId(x, y, numNodes);
Point loc = new Point(x,y);
ArrayList<Integer> keyring = getRandomSubset(keyPool, keyRingSize);
nodelist.put(id, new Node(id, loc, keyring));
// make sure we do not over fill
if(nodelist.size() == numNodes){
break;
}
}
if(nodelist.size() == numNodes){
break;
}
}
return nodelist;
}
/**
* Returns a random subset of array of size n.
* @param array
* @param n
* @return
*/
public static ArrayList<Integer> getRandomSubset(ArrayList<Integer> array, int n){
ArrayList<Integer> workinglist = (ArrayList<Integer>) array.clone();
ArrayList<Integer> subset = new ArrayList<Integer>();
for(int i = 0; i < n; i++){
int index = (int) Math.floor(Math.random() * workinglist.size());
subset.add(workinglist.remove(index));
}
return subset;
}
/**
* This method will return the max x and y for the
* physical location of all the nodes.
* @param numNodes - number of nodes dropped in area
* @return - a point representing the max a and y
*/
public static Point getGridSize(int numNodes) {
// TODO Auto-generated method stub
return null;
}
// the following methods are all GNAVE, helper functions or route vulnerability metric
public static ArrayList<Node> gnave(){
ArrayList<Node> C = new ArrayList<Node>();
return C;
}
/**
* Incremental node value of adding node i to C
* @param C - captured nodes
* @return
*/
public static int v(int i, ArrayList<Node> C){
return 0;
}
/**
* Route Vulnerability Metric for independent path routing
* @param C - captured nodes
* @return
*/
public static double VsdIndependent(ArrayList<Node> C){
return 0.0;
}
public static double phi_ij(){
return 0.0;
}
public static double phi_sd(){
return 0.0;
}