You can find a link to our presentation here.
Our graph is an adjacency list implemented in the parsing folder and constitutes a graph and a node class. A graph can be created by passing the name of a text file to its constructor. Our graph algorithms only required a way to get the entire list of nodes and a way to get adjacent nodes.
Breadth First Search can called directly on a graph object to retrieve a map of nodes to their respective distances from a starting node. Alternatively, depth first search can be called iteratively and recursively on a graph object as well.
Brandes' betweenness centrality algorithm and Tarjan's strongly connected components algorithm are implemented in the algorithm folder.
The primary main file that runs all of our algorithms is also located in the algorithm folder.
The amazon dataset and the subset used for betweenness centrality are located in the data folder. Our results from running all of our algorithms are located in the results folder.
- Clone the repository
cdinto the repository
Run the following commands
$ chmod +x ./bake.sh$ chmod +x ./main.sh$ ./bake.sh
Running the executable
$ ./main.sh
To change the input dataset, navigate to the algorithm/main.cpp and specify the appropriate input and output file paths.
To run the test suite (in the tests folder) for parsing and algorithm, run the following commands in the root of the repository:
$ ./bake.sh$ ./test.sh
We tested our algorithms on several undirected, directed, and disconnected graphs. We also tested our algorithms on edge cases such as empty and very small graphs. For Tarjan's algorithm, we had tests on directed, acyclic graphs and on betweenness centrality, we had tests on graphs with multiple shortest paths.