DHB Integration #1246
DHB Integration #1246
Conversation
There was a problem hiding this comment.
In order to keep the PR manageable, I suggest to fix all remaining issues concerning the integration in this PR and move optimization and additional thoughts to another PR.
Concerning building / testing: It seems that DHB is not correctly added as a submodule or there is some ill-defined logic in CMakeLists.txt. CI does fetch all submodules, however DHB is not found.
|
@HazelCC Could you clarify and elaborate what exactly you mean with the point: Write tests to check the consistency of unweighted DHBGraph objects.? |
An undirected graph object should store directed edges in both directions. Previously there were issues where logical bugs causing inconsistency for undirected graph, therefore it's good to have more tests addressing this. |
For now, we have referenced you as taking over for this task. Is that fine? |
For sure. I'd happy to do that. |
Including all changes necessary for integrating the DHB graph data structure represented by a single graph class. Does not include tests nor necessary refactorings to reuse Edge type.
This enables us to reuse the Edge type for the DHB Graph class.
…cached boolean value.
3cc5e42 to
b713fd5
Compare
| OpenMP::OpenMP_CXX | ||
| tlx< A92E /span> | ||
| dhb |
There was a problem hiding this comment.
When linking publicly against dhb we may not need to link against dhb again here for the tests.
This PR integrate the data structure Dynamic Hashed Blocks (DHB) into Networkit. This improves NetworKit for dynamic graph operations.
TLTR:
For a detailed description of DHB, refer to the paper: A Fast Data Structure for Dynamic Graphs Based on Hash-Indexed Adjacency Blocks (2022)
Why?
Experiments have shown that DHB outperforms competing dynamic graph structures in edge insertions, updates, deletions, and traversal operations. This integration allows users to leverage DHB to gain performance for dynamic graph operations compared to the (vanilla) Graph class.
How?
This integration extends the functionalities of the default
Graphclass by supporting (almost) all methods implemented inGraph. When NetworKit is build using DHB, the necessary resources will be pulled in as a sub-module, and the associated code branches will be compiled. If the respective NetworKit modules are not compiled using the DHB integration,DHBGraphwill fall back using the implementation of the defaultGraphclass.Measurement:
Experiments run on commodity hardware (MacOS, M1, 8 GB RAM) have been run to get some baseline measurements on the performance of default
Graphclass vs. theDHBGraphclass. For edge insertions, sequential weight update, and sequential edge removal,DHBGraphoutperformsGraphclass in an unweighted graph setting.TODOs:
Review the passing by value semantics for all lambdas passed to a method such asf(L handle). Instead, we might want to pass all lambdas by rvalue-reference as inf(L&& handle).omp parallel forscheduler (guided?) we use.Review possibilities to use a concurrent/parallel version of functions that iterate over edges/vertices. For example, we might makeremoveNodeto use the concurrent version offorNeighbors.edgeIteratorandnodeIterator. (@fabratu)unweightedundirectedDHBGraphobjects. Anunweightedundirected graph should store one edge in both direction. (@HazelCC)