Algorithm features:
- Redirect edges based on degree order to reduce the computation complexity
- Use CSR(Compressed Sparse Row) format to reduce the memory usage on GPU
- Use SIMT to parallel the sorted lists intersections on GPU
The problem is from the competition 2018 CCF BDCI in China, and we are very lucky to win the first prize.
Dataset | Vertices | Edges | Triangles |
---|---|---|---|
twitter_rv.bin | 61578415 | 1468365182 | 34824916864 |
s26.kron.edgelist | 67108861 | 1073741824 | 49167172995 |
s27.kron.edgelist | 134217725 | 2147483648 | 106869298996 |
Google Drive: 【BDCI 2018】欧拉的核弹PPT
Baidu Netdisk: 【BDCI 2018】欧拉的核弹PPT
Build the project with:
cd src
make all
If you wanna use gpu version, run
./tricount -f {{your dataset path}}
or if you wanna try the old cpu version
./tricount_cpu -f {{your dataset path}}
Apache License 2.0