advance_algorithms_project

Strongly connected component algorithms implementations using BGL (boost graph library)

Files:

Presentation:

• Project slides presented on July, the 25th

Algorithms :

• my_tarjan.cpp : Tarjan's algorithm implementation with timer
• my_nuutila.cpp : Nuutila's algorithm implementation with timer
• my_pearce.cpp : Pearce's algorithm recursive implementation with timer
• my_pearce_not_recursive.cpp : Pearce's algorithm non recursive implementation with timer
• my_transitive_closure.cpp : Pearce's paper application example with graph transitive closure computation

Mains :

• main.cpp : simple test running the three versions against the bgl implementation on a randomly generated graph, build with g++ -O2 -lboost_graph -lboost_timer main.cpp -o main, run with ./main
• main_*.cpp : examples of application and timing with graphs passed from stdin in graphml format build with g++ -O2 -lboost_graph -lboost_timer main_*.cpp -o main_*, run with ./main_* < graphml_file
• test_from_stdin.cpp : runs the four versions of the algorithm against the bgl implementation timing them and checking for correctness, reads graph from stdin in graphml format, used to measure timing samples, build with g++ -O2 -lboost_graph -lboost_timer test_from_stdin.cpp -o test_from_stdin, run with ./test_from_stdin < graphml_file

Scripts :

• time_test.sh : runs test_from_stdin for each of the graphs in the specified directory and prints to stdout the results (time and correctness), run with ./time_test.sh dir_with_graphs
• generate_graph.cpp : outputs to stdout a graph in graphml format with a specified number of vertices and probability of having an edge between two vertices, build with g++ -O2 -lboost_graph -lboost_timer generate_graph.cpp -o generate_graph, run with ./generate_graph number_of_vertices edge_probability
• generate_graph.sh : script generates in a specified direcotory graphs to be used for timing measures, run with ./generate_graph.sh root_dir min_nodes step max_nodes step_edges max_edges
• test_tc.sh : tests transitive closure over all the graphs in a directory and store to file results
• read_peaks.sh : reads memory peaks from a specified directory of files outputted from massif and produces a csv with the measurements, run with ./read_peaks.sh massif_files_directory (better cd mem_test/massif_files_directory && ../read_peaks.sh .)
• read_peaks.py : script used by read_peaks.sh, reads res.txt and produces res.csv

Notebooks :

• time_analysis.ipynb : notebook taking the output from time_test.sh, generating a csv and plotting the measurements
• memory.ipynb : notebook taking the output from read_peaks.sh and plotting the measurements

Data :

• g0_1000/* : randomly generated graphs with 0 to 1000 vertices (V) with step 10 and 0 to 1000 edges, increasing probability s.t. number of edges is between 0 and V*(V-1) with step 10
• mem_test// : graphs generated to be used for memory profiling
• res.txt, res.csv : memory usage peaks generated by read_peaks.sh and used for plotting in memory.ipynb
• time_optimized_0_1000.csv : timeings of the 4 algorithms (tarjan, nuutila, pearce, non recursive pearce) generated by time_test.sh and used for plotting in time_analysis.ipynb
• tarjan.html,nuutila.html, pearce.html, pearceNR.html : the 3d plots of the timing results for tarjan, nuutila, pearce and pearce not recursive in (V, E, t) space