The main goal of our project is to build a general graph search tool. To parse datas into graph representation, we implemented fileloader class that reads data from csv or txt file and builds it into an adjacency list. We implemented DFS, IDDFS, BFS, Dijkstra, and Kosaraju algorithms. All our algorithms work on our three selected data sets, GitHub Social Network, California Road Network, and Gnutella peer to peer network. To provide a better user experience, we implemented a mobile robot-like console interacting interface to handle’s requests and parameter inputs. At the same time, we also provide the option for running the program in a single command line without using the user interface.
Next, we will go through each of the algorithms and discuss our results and performance.
DFS
We implemented DFS as a general search algorithm, to detect whether two nodes are connected. It can apply to both directed and undirected graphs. Given a start node and target node as input parameters, DFS expands from the start node to traverse the graph, if the target node is found before all the nodes have been visited, a boolean will be returned to indicate the target is reachable from the start node. The running time would be O(E+V), because the worst case is that we need to traverse all the edges and vertices to detect whether the path exists or not. Therefore, as long as the path between the given vertices exists, DFS can find it. In contrast, if either of the given nodes doesn’t exist or they are in two connected components, no path can be detected. For example, in Gnutella Peer to Peer Network, which is a directed graph, if users give two random vertices, it is more likely that no path is detected. However, in the directed graph such as GitHub Social Network, two randomly selected nodes are more likely to be connected.
IDDFS
We implemented IDDFS to optimize search. Starting with an initial value, IDDFS calls DFS for different depths. DFS is not allowed to go deeper than the given depth in any call. So, in essence, we do DFS in a BFS manner. It's worth noting that we go to top-level nodes several times. The last (or maximum depth) level is visited once, twice for the second last level, and so on. More specifically, a boolean will be returned to indicate whether the target is reachable within the maximum depth. The running time would be O(b^(d)), where b is the branching factor and d is the minimum depth needed for finding the target node. Although the time complexity of IDDFS works out to be the same as BFS when the target can be found in depth d, IDDFS consumes much less memory because its space complexity O(b*d) is smaller than that of BFS (O(b^(d))).
As long as both initial node and target exist and the maximum depth is large enough, the target will be reachable within maximum depth when all three datasets are loaded as an undirected graph. However, there might not be a path if we are trying to find the target within too shallow depth. Also, for Gnutella peer to peer network, which is intended to be used as a directed graph, we might not get a path since these two nodes might not be reachable due to direction when we load it as a directed graph.
Dijkstra
Dijkstra’s algorithm was implemented to find the least weighted path between two given nodes. The weights of the edges were defined as follows: the weight of the edge between node 1 and node 2 equals the number of neighbors of node 2. To find the least weighted path, the min heap priority queue was implemented that chooses which node in the queue has the smallest value of distance and should be processed next and if a shorter path to the node’s neighbor is found then the neighbor node’s distance information is updated accordingly. In the worst case running time the number of edges greatly exceeds the number of vertices and with O((V+E)*logV) running time for our implementation using adjacency list and priority queue this will lead to worst running time of O(E*logV). After the traversal reaches the target node, the least weighted path between starting node and the target node is constructed based on the information of the parent node of each node in the least weighted path. Dijkstra’s algorithms can be used for both undirected and directed graphs. If two given nodes are located in different connected components or are not connected by any path then there will be no path between these two nodes and Dijkstra’s algorithm will lead to no result. As an example of this, we can load GitHub Social Network and California Road Network datasets (intended to be used as undirected graphs) as directed graphs and since there may be no path between the starting node and the target node, Dijkstra’s algorithm will lead to no result.
BFS
We implemented BFS to search the shortest path from two given nodes. Briefly speaking, in this algorithm, we expend neighboring nodes at each step and search for the target node and return the number of expansions. The worst running time requires us to traverse all the vertices in the graph as well as traversing all the edges. Therefore the running time is O(E+V). All three data we have will yield a result when they are loaded as undirected graph. For GitHub Social Network and California Road Network, they were intended to be used as undirected graphs, but we can still load them as directed graphs for testing purposes. In this case, using random nodes for BFS may result in no result because the two nodes may not be reached.
Kosaraju
We did not include Strongly Connected Component algorithm in our original proposal because we want to start off with a plan that fulfills minimum requirements. However, we smoothly finished the fileloader class and graph classes so that we were ahead of our schedule. I was fascinated about finding SCC and would like to utilize this algorithm to search for small communities that reside in the data.
We followed Kosaraju’s algorithm by performing DFS twice, first on a transpose of the graph and then followed by a second DFS on the original graph. Therefore the overall running time is still O(E+V) which is the same as regular DFS. To allow flexibility for generating results, I let users select how many SCCs they would like to see, and the threshold they want to define for being an SCC. To allow displaying top K numbers of SCCs, I used a min-heap to keep track of top K candidates and report the SCCs in ascending order based on SCC size. Worst case I will have V number of SCC. Therefore, the final runtime complexity should be updated to O(E+V+VlogK) which will be O(E+VlogK).
For Gnutella peer to peer network, we only able to detect a single huge SCC with 2068 nodes. For the other two data set, I do not want to include their results in this report because those two data are supposed to be undirected graphs and their SCC results are not meaningful.
Based on the results and test cases, we believe that our algorithms yield expected results.