• Geo- implements Geolocation
• Vertex- implements NodeData
• Edge- implements EdgeData
• Graph- implements DirectedwheightedGrah
• Algo- implements DirectedwheightedGrah
• FrameGUI
• Panel_GUI
• Ex2
• main
Geo
In this class there are three variables x, y, z.
these variables are doubles and are used to represent a 3D location,
in this project we are using 2D points so the z variable wont be used much.
this class has getters for x, y, z and a function to find the distance between 2 points.
Vertex
In this class we have 6 variables: ID, pos, tag, weight, info, and nodes.
ID in an int, pos is a Geo, tag is int, weight is a double, info is a string, and nodes is a HashMap.
We have 3 constructers, 1 that gets everything, 1 that gets ID and pos, and a copy constructor.
In this project we didn’t use the info and weights of the vertex
we have getters and setters for almost everything.
Edge
In this class we have 5 variables: src, dest, tag, weight, info.
src and dest are Vertexes tag is int, weight is a double, and info is a string.
We have 2 constructers, 1 that gets everything, and a copy constructor.
In this project we didn’t use the info of the edge.
we have getters and setters for almost everything.
Graph
In this class we have 4 variables: mc, Nodes, Edge, edg.
mc is a int, Nodes is a HashMap, Edge is a HashMap>, and edg is a HashMap.
We have 3 constructers, 1 that gets a graph from a json file, 1 that gets everything, and a copy constructor.
in this class we have the following functions:
getNode: returns the vertex of the key given.
getEdge: returns the edge that has the src and dest given.
addNode: adds the NodeData that we were given to the graph (Vertex).
connect: creates a new edge with the data given.
nodeIter, edgeIter, edgeIter (node_id) :creating an iterator that will give a run time exception if we changed the graph while the iterator was running.
there is an iterator to go through the Vertexes in the graph, the edges in the graph, and to go through the edges that are coming from a certain vertex.
removeNode: removes the vertex from the graph and all edges that start or end at this vertex.
removeEdge: removes the edge from the graph.
nodeSize: return the amount of vertexes in this graph.
edgeSize: return the amount of edges in this graph.
getMC: return the mc;
Algo
this class has1 variables myGraph which is a Graph
We have 3 constructers 1 that gets a graph from a json file, 1 that just creates the class with out a graph, and a copy constructer.
in this class we have the following functions:
init: makes a copy of the given graph – myGraph.
getGraph: return the graph
copy: creates a deep copy of the graph
isConnected: checks if you can get from every vertex to every other vertex
tagchild: marks that we have seen this vertex
flipGraph: edges of the graph
shortestPathDist: return the shortest weight of the shortest distance between the vertexes.
shortestPath: return a list of Vertexes that is the path of the shortest distance between the vertexes.
center: returns the center of the graph if there is 1. This is the vertex that distance of the farthest vertex from is the least out of all the vertexes in the graph.
tsp: this function returns a path that has all the vertexes in a list, the path should be as minimal as possible. In this function you can use nodes that aren’t in the list and can repeat nodes.
save: saves the graph to a json file
load: loads a json file of a graph
Floyd_Warshall: makes a HashMap of the shortest distance between all pairs of Vertexes.
Floyd_Warshall_list: makes a HashMap of lists of vertexes that are the shortest path between each pair of Vertexes. we will elaborate more about most of these function later
FrameGUI
this class make the frame of the gui.
creates the menu bar, and the action listener.
when you open the menu bar and press on the function you want to run, the action bar will ask for input if needed till it gets correct input, and than runs the function and a window will pop up with answer.
Panel_GUI
this class makes the panel of the gui.
in the panel we will be showing the graph.
the panel has the functions to take the x,y coordinates from the vertexes and the edges and change them so that they fit nicely in the panel.
we also have a function to make arrows as edges.
we found this function on stack over flow: https://stackoverflow.com/questions/2027613/how-to-draw-a-directed-arrow-line-in-java
Ex2
this class has 3 functions:
getGraph: creates a new object algo, load a json file to it, return the graph from algo
getGraphAlgo: creates the object algo with a graph we get from a json file, return algo.
runGUI: create an object of frameGUI that shows the GUI.
main
this class gets a String for the json file and runs the function in Ex2 that creates the GUI.
__________________________________________________________________________________________
init:
makes a copy of the given graph into are graph-myGraph
run time O(|v|+|e|) v=vertexes, e=edges .
getGraph:
returns the graph
the run time is O(1)
copy:
this creates a deep copy of the graph
run time O(|v|+|e|) v=vertexes, e=edges .
isConnected:
we will check if you can get from every Vertex to Every Vertex.
if the graph has no nodes by default it is connected.
if the graph has fewer edges than vertexes it can not be connected.
if neither of the if give us an answer.
we will start by marking each vertex as not seen.
taking the first Vertex in the Hashmap of Vertexes.
and running the function tagchild.
after we will iterate through the Vertexes and make sure that all the Vertexes have been seen.
if we find a vertex that hasn't been seen the graph isn't connected.
if all the vertexes have been seen we will flip the graph.
and repeat on the flipped graph.
the running time is O(|v|^2) v=vertex.
because tagchild running time is O(|v|^2)
the max run time for flip graph is also O(|v|^2) =O (|v|+|e|)
when every Vertex has edges to every vertex v*(v-1)+v=v^2
tagchild:
we will check if the vertx has been seen.
if it hasn't been seen we will mark that it has been seen.
we will iterate through the Vertexes in the graph.
if the vertex we get to while iterating hasn't been seen and isn't vertex v.
we will see if there is an edge between v and this vertex.
if there is we will run the function again with the new vertex.
the run time of this function is O(|v|^2) v=vertex.
flipGraph:
we will start by creating a new graph.
we will copy the vertexes from the given graph to our new graph.
we will copy the edges from the given graph to our new graph.
BUT we will switch the src and dest.
run time O(|v|+|e|) v=vertexes, e=edges .
shortestPathDist:
create a hashmap from the Floyd_Warshall function
create a list l1 with the src and dest keys
create the list l2 by getting the value of l1 from the hashmap
return l2
the run time of the function is O(|v|^3) because of the Floyd_Warshall function
shortestPath:
create a hashmap from the Floyd_Warshall_list function
create a list l1 with the src and dest keys
create a new list l2 from access the hashmap with the l1 and get its value
create a new list l3 of Vertexes from the l2 we got from the hashmap
return l3
the run time of the function is O(|v|^3) because of the Floyd_Warshall_list function
center:
if the graph isn't connected the graph doesn't have a center.
create a hashmap from the Floyd_Warshall function.
create a new hashmap that contains the farthest vertex from each vertex when looking at the shortest path between vertexes.
we will create a loop in a loop to find the farthest vertex from each vertex
and add it to the hashmap.
we will loop through the hashmap to find the vertex with the smallest value
and return that vertex.
the run time of the function is O(|v|^3) because of the Floyd_Warshall function.
tsp:
if cities is empty return null.
if cities has 1 city return cities.
hashmap1= Floyd_Warshall.
hashmap2= Floyd_Warshall_list.
create 2 arraylists of the cities city1,city2.
create a loop on a loop to find the shortest path in the cities list.
create list ans and add the Vertexes in that path to it.
go through ans and remove from city 2 the vertexes in ans.
while city2 >0
go through city2 and find the smallest path that we can add on to the left or right.
add the Vertexes in that path to ans.
go through ans and remove from city 2 the vertexes in ans.
we have added all the vertexes from cities to the ans.
now we need to connect the last Vertex to the first vertex.
return ans.
the run time of the function is O(|v|^3) v=vertex or O(|c|!) c=vertexes in cities which ever is bigger.
save:
we created a map
than a jsonObject and jsonArray
we will iterate through the edges and create a linkedList in every iterartion.
we will add the edges parts to the linkedList and dd the linked list to the json array
when we finish iterating through the edges we will add the jsonArray to the Json object.
and do the same thing for the Vertexes.than we will open a file writer and write the json object into a file
we will flush and clos the file
if we didnt have ant errors we will return true else we will false
the run time is O(|v|+|e|) v=vertex e=edge.
load:
this function loads a graph from a json file
run time O(|v|+|e|) v=vertexes, e=edges .
Floyd_Warshall:
this function finds the shortest path between all 2 vertexes
here is a explanation to how the code works
https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
the run time of the function is O(|v|^3) v=vertex
Floyd_Warshall_list:
this function finds the shortest path between all 2 vertexes with a list of vertexes keys in the path
here is a explanation to how the Floyd_Warshall works
https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
in this function as we updated the main hashmap we update the other hashmap with the path.
the run time of the function is O(|v|^3).
| isConnected | shortestPathDist | shortestpath | center | tsp (group of 5) | tsp (group of 20) | load | save | |
|---|---|---|---|---|---|---|---|---|
| 10 Nodes | 35 ms | 37 ms | 35 ms | 34 ms | 40 ms | --- | 53 ms | 63 ms |
| 100 Nodes | 47 ms | 47 ms | 53 ms | 56 ms | 61 ms | 199 ms | 53 ms | 63 ms |
| 1000 Nodes | 235 ms | 299 ms | 245 ms | 6 sec 542 ms | 554 ms | 756 ms | 345 ms | 342 ms |
| 10000 Nodes | 1 sec 942 ms | 1 sec 299 ms | 1sec 52 ms | 49 min 29 sec | 3 sec 619 ms | 8 sec 215 ms | 1 sec 567 ms | 1 sec 804 ms |
| 100000 Nodes | 4 min 40 sec | 55 sec 589 ms | 55 sec 589 ms | ---- | 4 min 27 sec | ----- | 21 sec 434 ms | 23 sec 907 ms |