- Notifications
You must be signed in to change notification settings - Fork243
Comments
New Algorithm: dynamic approx electrical closeness#1333
New Algorithm: dynamic approx electrical closeness#1333bernlu wants to merge 14 commits intonetworkit:masterfrom
Conversation
…r dynamic algorithm use case
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Pull Request Overview
This PR introduces a dynamic version of the ApproxElectricalCloseness algorithm, refactors the static implementation for reuse, and adds corresponding tests and Python bindings.
- Implemented
DynApproxElectricalClosenessin C++ with update support for edge additions and deletions. - Refactored
ApproxElectricalClosenessinternals (tree structures, memory clearing, parameterized delta). - Added parameterized GTests, Python tests, and Cython bindings for the dynamic algorithm.
Reviewed Changes
Copilot reviewed 10 out of 10 changed files in this pull request and generated 2 comments.
Show a summary per file
| File | Description |
|---|---|
| networkit/test/test_centrality.py | Added Python unit tests forDynApproxElectricalCloseness, including edge addition/deletion |
| networkit/cpp/centrality/test/CentralityGTest.cpp | Removed old static electrical closeness test |
| networkit/cpp/centrality/test/CMakeLists.txt | Registered newApproxElectricalClosenessGTest |
| networkit/cpp/centrality/test/ApproxElectricalClosenessGTest.cpp | Added parameterized GTests for static and dynamic algorithms |
| networkit/cpp/centrality/DynApproxElectricalCloseness.cpp | New implementation of the dynamic approximation algorithm |
| networkit/cpp/centrality/CMakeLists.txt | AddedDynApproxElectricalCloseness.cpp to centrality module |
| networkit/cpp/centrality/ApproxElectricalCloseness.cpp | Refactored static implementation for reuse and added memory cleanup |
| networkit/centrality.pyx | ExposedDynApproxElectricalCloseness Cython bindings and doc updates |
| include/networkit/centrality/DynApproxElectricalCloseness.hpp | Declared the dynamic algorithm interface |
| include/networkit/centrality/ApproxElectricalCloseness.hpp | Extended header for delta parameter and refactored internal data structures |
Comments suppressed due to low confidence (1)
networkit/centrality.pyx:2554
- [nitpick] The class docstring does not describe the
pivotanddeltaparameters in the constructor signature. Add parameter descriptions forpivot(the pivot node for updates) anddelta(approximation probability fallback) to clarify usage.
cdef class DynApproxElectricalCloseness(Centrality, DynAlgorithm):Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
Uh oh!
There was an error while loading.Please reload this page.
| // To debug | ||
| G.forNodes([&](node u) { | ||
| if (childPtr[u] != none) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Not sure whether the conditionals are mitigated by the compiler if the asserts are disabled. How about something like aNDEBUG macro surrounding the if-statements?
| degDist[b] = std::uniform_int_distribution<index>(0, G.degree(b) - 1); | ||
| #pragma omp parallel for | ||
| for (omp_index i = 0; i < ustsCurrentRound; ++i) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
static_cast<omp_index>(ustsCurrentRound)
| return G; | ||
| }; | ||
| GraphEvent add_random_edge(Graph &G) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
What is the reason for using snake_case here? Normally we use camelBack.
| return GraphEvent(GraphEvent::EDGE_ADDITION, a, b); | ||
| }; | ||
| GraphEvent remove_random_edge(Graph &G, const node pivot = none) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Same here.
| const count n_gen = 75; | ||
| const double er_prob = 0.15; | ||
| Graph generate(std::string generator) { |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Better use a more explicit name likegenerateGraph.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Since this is newly added code, better use longer, more explicit names forG.
Alsoauto is used quite a lot in the code. I suggest to use the explicit types if readability (e.g. long names) isn't affected too much. In some cases, it is not clear, what the type exactly might be (given the function name used to initialize the variable).
| auto G = generate(generator); | ||
| ApproxElectricalCloseness apx(G, eps); | ||
| DynApproxElectricalCloseness dapx(G, eps); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
dApx?
Same for other occasions (likeddiag) below.
| auto G = generate(generator); | ||
| // make sure that removing an edge does not disconnect the graph | ||
| auto star_node = G.addNode(); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Why issnake_case used here?
| g.addEdge(n, n+1) | ||
| g.addEdge(n - 1, n) | ||
| dapx = nk.centrality.DynApproxElectricalCloseness(g, eps) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
d_apx?
Same for other occasions.
This PR is an updated version of#1097.
Old description:
This algorithm is based on the ApproxElectricalCloseness algorithm in networkit.
The dynamic algorithm supports:
This implementation currently does not support arbitrary edge deletions: edges on the BFS tree from the pivot element u (which is used to approximate r(u,v) for all v) may not be deleted, because this would require a larger update computation. In principle, this is possible, but for our current use case this is not a problem. The code can easily be extended when the need arises.
Additional changes in this PR: