search

fslaborg / Graphoscope

A pragmatic approach to network science.
http://fslab.org/Graphoscope/
MIT License
14 stars 6 forks source link

Benchmark conversion to Adjacency Matrix #15

Closed HarryMcCarney closed 1 year ago

HarryMcCarney commented 1 year ago

Do this for both for DiGraph and FGraph.

This is a preliminary step for the Floyd-Warshall algorithm.

HarryMcCarney commented 1 year ago
Method NumberNodes NumberEdges Mean Error StdDev Gen0 Gen1 Gen2 Allocated
AdjMat_FGraph 100 500 173.561 us 3.1940 us 3.4176 us 13.1836 2.4414 - 81.69 KB
AdjMat_DiGraph 100 500 7.883 us 0.0580 us 0.0514 us 13.7787 2.9449 - 84.42 KB
AdjMat_FGraph 100 5000 257.543 us 4.9729 us 5.7268 us 13.1836 2.4414 - 81.69 KB
AdjMat_DiGraph 100 5000 15.737 us 0.3080 us 0.2881 us 13.7634 2.5940 - 84.42 KB
AdjMat_FGraph 1000 500 12,772.888 us 207.7044 us 194.2868 us 1312.5000 656.2500 203.1250 7847.91 KB
AdjMat_DiGraph 1000 500 1,766.697 us 32.7418 us 75.2296 us 1343.7500 671.8750 140.6250 7875.32 KB
AdjMat_FGraph 1000 5000 14,287.332 us 201.4449 us 239.8058 us 1343.7500 671.8750 234.3750 7848.1 KB
AdjMat_DiGraph 1000 5000 2,192.189 us 42.5847 us 107.6171 us 1378.9063 691.4063 152.3438 7875.46 KB
HarryMcCarney commented 1 year ago

DiGraph perform about 10 times faster on this. Conversion to Adjacency Matrix is going to be a common operation prior to running algorithms such as Floyd-Warshall. So for v0.1 we will go with DiGraph and do further benchmarking of FGraph and others in future sprints.