This project represents an un-directional weighted graph and the uses of searching algorithms on it. The src folder contains three interfaces and two classes which implements the interfaces. The test's folder contains two junit test classes which tests the implemented classes.
NodeInfo is the inner class that implements the node_data interface which represents a single node in the graph.
with each node having a unique key, info and a tag .
The tag and info contains data which is used by the algorithm class.
WGraph_DS is the class that implements the weighted_graph interface which represents a weighted graph.
every edge in the graph has a weight that represents the distance from another node therefor it can only be bigger or equal to 0.
The class contains the methods:
getNode(int key); return the node associated with the key, if no node return null.
hasEdge(int node1, int node2); return true if there's an edge between nodes else false.
getEdge(int node1, int node2); return the weight of the edge of the two nodes, if no edge return -1.
addNode(int key); adds new node with the associated key to the graph. if the key is already there, do nothing.
connect(int node1, int node2, double w); connect two nodes with an edge with the given weight.
getV(); return a collection of all the nodes in the graph.
getV(int node_id); return a collection of all the "neighbours" of the node_id node.
removeNode(int key); removes the node with the associated key from the graph and deletes all the edges connected to it.
removeEdge(int node1, int node2); removes the edge connected with node1 and node2.
nodeSize(); return node size in the graph.
edgeSize(); return edge size in the graph.
getMC(); return the number of changes made in the graph.
WGraph_Algo is a class that implements the graph_algorithms interface which contains algorithms that can be used on a weighted graph.
The class consists the methods:
init(weighted_graph g); Initiate the weighted graph with the WGraph_Algo object.
getGraph(); Returns the graph associated with the WGraph_Algo object.
copy(); Returns a deep copie of a given graph.
isConnected(); Return true if all the nodes in the graph are connected, else returns false.
shortestPathDist(int src, int dest); Returns the sum of the weights in the shortest path.
shortestPath(int src, int dest); Returns a list of the shortest path.
save(String file); Saves the graph associated with the WGraph_Algo object as a stream of byts.
load(String file); Loads an object which is a stream of byts and casts it as a graph.
each graph has the following HashMaps:
private HashMap<Integer, node_info> nodeMap;
private HashMap<Integer, HashMap<Integer, node_info>> neighbourMap;
private HashMap<Integer, HashMap<Integer, Double>> edgesWeightMap;
and with more detail:
nodeMap for <node index,node> pairing to keep track of the nodes in the graph.
neighbourMap for <node index,<neighbour index,neighbour node>> in order to keep track of the neighbours.
edgesWeightMap for <node index,<neighbour index,connection Weight>> in order to keep track of the edges weight.