This program implements Scalable Triangle Counting algorithm introduced by S.Acerm, A.Yasar, S.Rajamanickam, M.Wolf and U.Catalyurek [1].
Graph is read from an input file created by RandomGraph generator by S.Pettie and V.Ramachandran [2].
Two implementations are included, one executing the algorithm in serial, and one using the MPI Standard.
MPI implementation requires openmpi package to be installed.
Graph Matrix is conformally partioned to blocks, based on MPI processes.
Each process is assigned with a block and calculate a local triangles count.
In order to calculate the local triangles count, required blocks are retrieved from other processes, based on the algorithm.
Both version can be invocted via the Makefile, or by directly compiling and executing.
% make
To include a different input file:
% make FILE={file_path}
% make mpi
To configure different how many processes to use:
% make mpi PROCESSES={processes}
To include a different input file:
% make mpi FILE={file_path}
Compilation:
% gcc -o triangles_counting triangles_counting.c
Execution:
% ./triangles_counting {input_file}
Compilation:
% mpicc -lm -o mpi_triangles_counting mpi_triangles_counting.c
Execution:
% mpiexec -np {processes} ./mpi_triangles_counting {input_file}
❯ make
Executing normal code...
gcc -o triangles_counting triangles_counting.c
./triangles_counting grph_triangles
Counting Triangles of Graph retrieved from input file: grph_triangles
Nodes count: 1000
Algorithm started, please wait...
Graph contains: 14 triangles
Algorithm finished!
Time spend: 1.403673 secs
Program terminates.
❯ make mpi
Executing MPI code...
mpicc -lm -o mpi_triangles_counting mpi_triangles_counting.c
mpiexec -np 4 ./mpi_triangles_counting grph_triangles
Counting Triangles of Graph retrieved from input file: grph_triangles
Nodes count: 1000
Algorithm started, please wait...
Graph contains: 14 triangles
Algorithm finished!
Time spend: 1.029489 secs
[1] S. Acer, A. Yaşar, S. Rajamanickam, M. Wolf and Ü. V. Catalyürek, "Scalable Triangle Counting on Distributed-Memory Systems," 2019 IEEE High Performance Extreme Computing Conference (HPEC), 2019, pp. 1-5, doi: 10.1109/HPEC.2019.8916302.
[2] http://www.dis.uniroma1.it/challenge9/code/Randgraph.tar.gz