Graph_Algo - NoaAizer/Graphs GitHub Wiki

We implemented graph_algorithms interface in Graph_Algo.

graph - holds the graph.

Graph_Algo function:

• Constructors- creates an empty graph (default constructor) and builds a new graph from a given graph.
• init - Init this set of algorithms on the parameter - graph.
• init(String file_name) - Init a graph from file.
• save(String file_name) - Saves the graph to a file.
• isConnected() - Returns true if and only if (iff) there is a valid path from EVREY node to each other node. NOTE: assume directional graph - a valid path (a-->b) does NOT imply a valid path (b-->a). return TRUE- if there a valid path from Every node to each, otherwise return FALSE.
• shortestPathDist - returns the length of the shortest path between src to dest (src - start node, dest - end (target) node).
• shortestPath - returns the the shortest path between src to dest - as an ordered List of nodes: src--> n1-->n2-->...dest (src - start node, dest - end (target) node).
• TSP - computes a relatively short path which visit each node in the targets List. Note: this is NOT the classical traveling salesman problem, as you can visit a node more than once, and there is no need to return to source node - just a simple path going over all nodes in the list (targets represents a list of the requested nodes). return the shortest path between those nodes.

NOTE: There is another way (was left as a remark) which give the shortest path between the nodes -Take each one of the nodes to be a source node, and pick the node with the shortest path. This way take a lot of time so we decided to pick the source node randomly.

• copy() - Compute a deep copy of this graph.
• getG() - Graph getter, return the graph in this class.

Private Methods

• Runs DFS algorithm on the given graph (gr represents the graph to be traveled). return true- if all nodes are connected , otherwise false.
• DFSUtil - Runs DFS starting from the first node (key represents the first node).
• getTranspose - Transposes the original graph, return transpose of this graph .
• findMinNode - Finds the node with the minimum weight and removes it from the queue (q represents the queue with the unvisited nodes). return the node with the minimum weight
• shortestPathDistToAll - Calculates the shortest path from one of the nodes in the target list to the rest. // NOTE: Related to the remark in TSP method.
• haveAPath - Checks if there a path between some of the nodes in the graph (targets represents a list of the requested nodes in the graph) return true- if there a path, otherwise return false.
• isConnect - Checks if the graph is connected (except a path to the source node). return the graph after visiting the nodes.
• isSrcConnect - Checks if there a path to the source node from the other nodes. return the graph after visiting the nodes.