Graphs wiki - noaelram/Graphs GitHub Wiki

Welcome to the Graphs wiki! As it is describe, in this repository we built a graph structure, which can draw a graph on a window, save them into a file, read them from a file, run some algorithms on them, and see the results. In This Page, I will explain everything there is to know what's in this code and about how the code works.

DGraph class - This class implements the graph interface, and represents a directional weighted graph. It has functions such as: returning the node data by the node ID (the key), return the data of the edge (src,dest) (returns null if none), adding a new node to the graph with the given node data, Connect an edge with weight w (positive weight representing the cost (aka time, price, etc) between src-->dest) between node source to node destination, returning a pointer for the collection representing all the nodes in the graph, returning a pointer for the collection representing all the edges getting out of the given node (all the edges starting (source) at the given node), Deleting the node (with the given ID) from the graph - and removes all edges which starts or ends at this node, Deleting the edge from the graph, returning the number of vertices (nodes) in the graph, returning the number of edges (assuming it's a directional graph), and returning the Mode Count - for testing changes in the graph. How I represented the graph:

  • HashMap of vertices: with a key and a value - node_data,
  • HashMap that saves edges: a key of the source node, and the value, also a HashMap of the destination node and the relevant edges: a key of the destination node and the value: node_data.
  • edgesCounter: counter that counts the edges and updates after adding/deleting an edge.
  • changes: counter that counts changes (the version of the graph), that's up to date after any change in the graph.

Graph_Algo class - This class implements the graph_algorithms interface, that represents the "regular" Graph Theory algorithms. It has functions such as: Initializing this set of algorithms on the parameter "graph", Computing a deep copy of this graph, Initializing a graph from a file, Saving the graph to a file, a function that returns true if and only if there is a valid path from every node to each other node, returning the length of the shortest path between source node to the destination node, returning the shortest path between the source node to the destination node - as an ordered List of nodes: src--> n1-->n2-->...dest, and computing a relatively short path which visit each node in the targets list.

This class keeps graph as a private field.

The saving format : every row represents a source node and the edges that originate from it to other edges. For example, the next line describes the node number 2, which is in location 1,2 and edges number 3 and 4 are originating from this node, at weights 5 and 6 respectively: 2:1-2,3;5,4;6

Here I will describe the algorithms we use:

  1. isConnected - I ran BFS from each node and that is how I could obtained all accessible nodes from the same node. If there is a node whose number of nodes that accessible to it is different from the number of nodes in the graph, return "false", otherwise return "true".
  2. shortestPathDist - I called the function shortestPath and I returned the weight of the last node (the distance from the source node after running the algorithm).
  3. shortestPath - I called the auxiliary function computeShortestPaths to calculate the distances of the nodes from the source node, and then called the auxiliary function shortestPathAux to get the path itself.
  4. shortestPathAux - Assumes a previous run of the auxiliary function computeShortestPaths (so that the information is already at the nodes and only has to calculate). "Going back" from the destination node to the source node. The previous node is known by the tag field stored in the node.
  5. computeShortestPaths - Uses the Dijsktra algorithm to calculate all short paths to all nodes in a graph from a particular source node. Uses the Tag feature of the node to indicate the previous node in the shortest path and the Weight feature to keep the shortest distance from the source node to the particular one.
  6. TSP - Calculates the shortest distances between each of the nodes received as a parameter, for each of the other nodes in the list. Saves everything in HashMaps. Then it passes on all possible permutations of the nodes that received as a parameter, and saves the shortest path that received that passes through all these nodes. Finally, it goes over the HashMaps that were calculated at the beginning of the function, to find the path in the original graph.

Graph_GUI class - In this class, it is possible to load a graph file, as the format specified above, saving a graph into the file, and each of the algorithms in the Graph_Algo class can be run on the loaded graph and the results are being seen in the console. If an algorithm requires an input, then the input must be entered correctly in the inputs.

Sources: