DHB Integration by HazelCC · Pull Request #1246 · networkit/networkit

HazelCC · 2024-08-20T14:48:44Z

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 Graph class by supporting (almost) all methods implemented in Graph. 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, DHBGraph will fall back using the implementation of the default Graph class.

Measurement:

Experiments run on commodity hardware (MacOS, M1, 8 GB RAM) have been run to get some baseline measurements on the performance of default Graph class vs. the DHBGraph class. For edge insertions, sequential weight update, and sequential edge removal, DHBGraph outperforms Graph class in an unweighted graph setting.

TODOs:

~~Review the passing by value semantics for all lambdas passed to a method such as f(L handle). Instead, we might want to pass all lambdas by rvalue-reference as in f(L&& handle).~~
Review which type of omp parallel for scheduler (guided?) we use.
~~Review possibilities to use a concurrent/parallel version of functions that iterate over edges/vertices. For example, we might make removeNode to use the concurrent version of forNeighbors.~~
Write more tests for edgeIterator and nodeIterator. (@fabratu)
Write tests to check the consistency of ~~unweighted~~ undirected DHBGraph objects. An ~~unweighted~~ undirected graph should store one edge in both direction. (@HazelCC)
Improve documentation. (@fabratu)
Fix GCC build issues. @c-bebop
Build DHB on Clang and fix issues @c-bebop

fabratu

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.

.clang-format

CMakeLists.txt

c-bebop · 2024-10-23T15:24:02Z

@HazelCC Could you clarify and elaborate what exactly you mean with the point: Write tests to check the consistency of unweighted DHBGraph objects.?

HazelCC · 2024-10-29T08:46:04Z

@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.

c-bebop · 2024-10-29T16:37:57Z

@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?

HazelCC · 2024-10-30T09:44:36Z

@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.

…asing coverage.

…parallel way.

CMakeLists.txt

c-bebop

Looks very good, now just some small fixes.

include/networkit/graph/DHBGraph.hpp

networkit/cpp/graph/DHBGraph.cpp

networkit/cpp/graph/test/DHBGraphGTest.cpp

bernlu

We should probably discuss some of these comments, some are quite detailed and maybe out of scope for this PR.

An additional general comment: I think it would be nice to add time complexity to the documentation for (almost) all functions.

bernlu · 2025-04-29T13:26:04Z

include/networkit/graph/Edge.hpp

+/**
+ * A weighted edge used for the graph constructor with
+ * initializer list syntax.
+ */


I am not sure what this comment is supposed to tell me. The 'initializer list' part is obvious from reading the code. A short explanation of this struct would be more useful, or maybe just no comment at all?

bernlu · 2025-04-29T13:34:28Z

include/networkit/graph/Edge.hpp

+struct WeightedEdge : Edge {
+    edgeweight weight;
+
+    // Needed by cython


I guess this function should never be used in c++? Then the comment should clarify this and tell the user to never call this constructor.

bernlu · 2025-06-24T11:18:00Z

include/networkit/graph/DHBGraph.hpp

+// forward declaration to randomization/CurveballImpl.hpp
+namespace CurveballDetails {
+class CurveballMaterialization;
+}


This declaration seems to be unused.

bernlu · 2025-06-24T13:25:52Z

networkit/cpp/graph/DHBGraph.cpp

+    if (!directed) {
+        is_inserted_out = m_dhb_graph.insert(u, v, edge_data, do_update);
+        is_inserted_in = m_dhb_graph.insert(v, u, edge_data, do_update);
+    } else {
+        is_inserted = m_dhb_graph.insert(u, v, edge_data, do_update);
+    }


Reorder for readability

Suggested change

if (!directed) {

is_inserted_out = m_dhb_graph.insert(u, v, edge_data, do_update);

is_inserted_in = m_dhb_graph.insert(v, u, edge_data, do_update);

} else {

is_inserted = m_dhb_graph.insert(u, v, edge_data, do_update);

}

if (directed) {

is_inserted = m_dhb_graph.insert(u, v, edge_data, do_update);

} else {

is_inserted_out = m_dhb_graph.insert(u, v, edge_data, do_update);

is_inserted_in = m_dhb_graph.insert(v, u, edge_data, do_update);

}

bernlu · 2025-06-24T13:27:13Z

networkit/cpp/graph/DHBGraph.cpp

+      edgesIndexed(edgesIndexed), // edges are not indexed by default
+      nodeAttributeMap(this), edgeAttributeMap(this) {
+
+    m_dhb_graph = dhb::Matrix<EdgeData>(n);


move this into initializer list

bernlu · 2025-06-24T16:00:28Z

networkit/cpp/graph/DHBGraph.cpp

+void DHBGraph::removeAllEdges() {
+    m_dhb_graph = dhb::Matrix<EdgeData>(m_dhb_graph.vertices_count());
+    m = 0;
+    storedNumberOfSelfLoops = 0;
+    omega = 0;
+}


this function should invalidate all edgeAttributes as well.

bernlu · 2025-06-24T16:03:53Z

include/networkit/graph/DHBGraph.hpp

+     * BEWARE: Running time is \Theta(1) for DHB implementation but \Theta(deg(u)) for fallback
+     * NetworKit graph DS.


i think this fallback nk graph is outdated information?

bernlu · 2025-06-24T16:07:13Z

include/networkit/graph/DHBGraph.hpp

+     *
+     * @param u Node.
+     * @param i index; should be in [0, degreeOut(u))
+     * @return @a edge weight to the i-th (outgoing) neighbor of @a u, or @c +inf if no such


The function actually returns the default edge weight and not inf when the neighbor does not exist.

bernlu · 2025-06-24T16:08:01Z

include/networkit/graph/DHBGraph.hpp

+     * @param u Node.
+     * @param i index; should be in [0, degreeOut(u))
+     * @return pair: i-th (outgoing) neighbor of @a u and the corresponding
+     * edge weight, or @c defaultEdgeWeight if unweighted.


we should add that none is returned when the neighbor does not exist.

bernlu · 2025-06-24T16:09:39Z

include/networkit/graph/DHBGraph.hpp

+     *
+     * This function is not supported for DHB. Please use getIthNeighborWithWeight(node u, index i).
+     */
+    std::pair<node, edgeweight> getIthNeighborWithWeight(Unsafe, node u, index i) const;


why is this function declared twice, but once we claim that it is not supported while the other one is implemented?

For @c-bebop : Look whether all Unsafe methods are marked as unsupported / unimplemented.

Copilot

Pull Request Overview

This PR integrates the Dynamic Hashed Blocks (DHB) data structure into NetworKit to accelerate dynamic graph operations. Key changes include:

Adding a new DHBGraph implementation and test (DHBGraphGTest).
Updating source files such as EdgeIterators.cpp to add DHB-specific specializations.
Modifying multiple CMakeLists and CI configuration files to incorporate DHB as a submodule and update linking and build settings.

Reviewed Changes

Copilot reviewed 10 out of 13 changed files in this pull request and generated 1 comment.

Show a summary per file

File	Description
networkit/cpp/graph/test/CMakeLists.txt	Added DHBGraphGTest to the test suite.
networkit/cpp/graph/EdgeIterators.cpp	Added DHBGraph-specific template specializations for edge iterators.
networkit/cpp/graph/CMakeLists.txt	Included DHBGraph.cpp in source files for compilation.
include/networkit/graph/Graph.hpp	Removed duplicate edge type definitions (moved to Edge.hpp).
include/networkit/graph/Edge.hpp	Introduced new definitions for Edge and WeightedEdge types.
(Other files)	Updated build scripts, submodules (.gitmodules) and CI configuration accordingly.

Comments suppressed due to low confidence (1)

networkit/cpp/graph/EdgeIterators.cpp:22

The DHBGraph specialization of validEdge omits the Unsafe parameter found in the Graph version's getIthNeighbor call; please confirm that this API difference is intentional and that it correctly reflects the DHBGraph interface design.

Copilot · 2025-06-24T17:33:23Z

CMakeLists.txt

+	target_link_libraries(networkit PRIVATE 
+									dhb 
+									OpenMP::OpenMP_CXX 
+									PUBLIC 
+									tlx)


Review the linking order and the use of PRIVATE vs. PUBLIC for the added 'dhb' dependency to ensure that transitive dependencies are handled correctly.

Suggested change

target_link_libraries(networkit PRIVATE

dhb

OpenMP::OpenMP_CXX

PUBLIC

tlx)

target_link_libraries(networkit PUBLIC

dhb

tlx

PRIVATE

OpenMP::OpenMP_CXX)

Correct @c-bebop

c-bebop · 2025-09-02T14:41:11Z

There are still some review comments but.. are we merging this one?

c-bebop · 2025-12-05T18:15:54Z

I see that there have been some review remarks by @bernlu . We are working on this feature for more than 1 year now. The merge should have happened this spring. I am sure I can address some of the comments. I would like us to focus on a merge ASAP as I need this feature for my work and I would be happy to have this merged into master! 🙏

fabratu · 2025-12-10T13:00:15Z

True, not so easy this one - formost having a final decision. :) If it's possible for you, address the comments you see fit, and I will handle the rest.

fabratu · 2026-01-30T15:55:12Z

include/networkit/graph/DHBGraph.hpp

+ * TODO:
+ * - [ ] Review the passing by value semantics for all lambdas passed
+ *       to a method such as f(L handle). Instead, we might want to pass
+ *       all lambdas by rvalue-reference as in f(L&& handle).


Please mark the DHBGraph class as experimental. It suffices to mark it in the documentation for C++ by adding @note to users.

HazelCC requested review from bernlu, c-bebop and fabratu August 20, 2024 14:48

HazelCC self-assigned this Aug 20, 2024

HazelCC added the performance label Aug 20, 2024

HazelCC marked this pull request as draft August 21, 2024 15:14

fabratu requested changes Aug 22, 2024

View reviewed changes

.clang-format Outdated Show resolved Hide resolved

CMakeLists.txt Outdated Show resolved Hide resolved

CMakeLists.txt Outdated Show resolved Hide resolved

c-bebop self-assigned this Mar 26, 2025

HazelCC and others added 18 commits April 14, 2025 12:48

Integrating DHB represented by a new graph class.

60ca7ab

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.

Move Edge type to its own file.

c8374b5

This enables us to reuse the Edge type for the DHB Graph class.

Test DHB Graph class functionality.

4b14e3c

Use east const!

baf2e5b

set using dhb as false by default

2153a34

No option to pull in DHB anymore: pull in DHB is mandatory.

08ffce7

Add DHB as a submodule

c7e7a7e

Remove compile option for using DHB.

8c6dfac

Remove all code branches where DHB would not be used.

f464147

Use omp parallel for schedule(guided) if possible.

28699ee

Address cmake policy CMP0077 by stating that DHB_WITH_64BIT_IDS is a …

46efc28

…cached boolean value.

Pull in latest changes from DHB repo.

261f4ce

addEdge() looses multi edge parameter (unused, not supported).

23e1cc7

Signed/unsigned compare warning as error fix.

5a97111

Remove unused variables.

ecbe425

TODO: implement getIthNeighborWithWeight()

fe85e3b

Use DHB super_pedantic: latest commit.

8aac99a

Revise doc: swapEdge().

a791d90

fabratu added 17 commits April 24, 2025 12:59

Refactor forInEdgesOf, increasing coverage.

e92e3b9

Refactor parallelSumForEdges, increasing coverage.

9aaf2ae

Fix construction by initializer list + test forced index_edges, incre…

11ec95a

…asing coverage.

Test non-existing neighbor with id.

d084dd8

Test non-existing neighbor with weight.

58b4fc8

Test non-existing neighbor.

8481c16

Enable increaseWeight test.

0890e6b

Add test for negative hasEdge result.

7f1f7bb

Add corner case test for swapEdge.

b7662fc

Test addEdges with update.

024ca32

Add test for weightedInDegree.

be7085e

Remove unneccessary check.

e5cfcf4

Add test for calling edgeId on non-indexed graph.

6635665

Test indexEdges twice for checking early return.

1d1d90c

Fix error in swapEdges, corner case test.

9ddd41e

Restrict addEdges test (weighted, no update) to be executed in a non-…

8a5fd67

…parallel way.

Support updates when calling addEdge (+ adding tests).

3aed00f

c-bebop reviewed Apr 29, 2025

View reviewed changes

CMakeLists.txt Show resolved Hide resolved

c-bebop previously approved these changes Apr 29, 2025

View reviewed changes

Address code related review-comments.

9eff449

fabratu dismissed c-bebop’s stale review via 9eff449 May 2, 2025 10:36

angriman mentioned this pull request Jun 2, 2025

[Do not merge] Proposal for adding node and edgeweight template parameters to Graph #1324

Open

bernlu requested changes Jun 24, 2025

View reviewed changes

bernlu requested a review from Copilot June 24, 2025 17:32

Copilot AI reviewed Jun 24, 2025

View reviewed changes

fabratu added the new feature label Sep 29, 2025

fabratu reviewed Jan 30, 2026

View reviewed changes

		* BEWARE: Running time is \Theta(1) for DHB implementation but \Theta(deg(u)) for fallback
		* NetworKit graph DS.

Conversation

HazelCC commented Aug 20, 2024 • edited by fabratu Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

TLTR:

Uh oh!

fabratu left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

c-bebop commented Oct 23, 2024

Uh oh!

HazelCC commented Oct 29, 2024

Uh oh!

c-bebop commented Oct 29, 2024

Uh oh!

HazelCC commented Oct 30, 2024

Uh oh!

Uh oh!

c-bebop left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

bernlu left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull Request Overview

Reviewed Changes

Uh oh!

Copilot AI Jun 24, 2025

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

c-bebop commented Sep 2, 2025

Uh oh!

c-bebop commented Dec 5, 2025

Uh oh!

fabratu commented Dec 10, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

HazelCC commented Aug 20, 2024 •

edited by fabratu

Loading