Add centrality measures (betweenness, closeness)
- Dominant language
- C++
- Stars
- 413
- Forks
- 67
- Avg merge
- 7h 24m
- Merged PRs (30d)
- 53
Description
## Summary
Graaf's vertex-properties module exposes only raw degree counts. None of the standard centrality measures (betweenness, closeness, eigenvector) are implemented.
## Current state
[include/graaflib/properties/vertex_properties.h](../blob/main/include/graaflib/properties/vertex_properties.h) currently exposes exactly three functions: `vertex_degree`, `vertex_outdegree`, `vertex_indegree`. A search across `include/graaflib/` for "centrality" (betweenness/closeness/eigenvector) returns no results.
## Why this matters
Degree is the simplest possible notion of "importance" in a graph, but it's rarely sufficient on its own — betweenness centrality (how often a vertex lies on shortest paths between other vertices) and closeness centrality (how close a vertex is to all others) are the standard next tier of analysis for questions like "which node is a bottleneck" or "which node can reach the rest of the network fastest," and they come up constantly in social-network analysis, infrastructure/routing analysis, and organizational-graph analysis. Their absence means the library currently only answers "how many neighbors does this vertex have," not "how structurally important is this vertex" — a meaningful gap for anyone using Graaf for network analysis rather than pure pathfinding.
## Suggested resolution
- Implement betweenness centrality (e.g. via Brandes' algorithm, which computes it for all vertices in `O(V*E)` for unweighted graphs and is the standard approach) and closeness centrality, most naturally alongside or reusing the existing shortest-path algorithms.
- Place these under `include/graaflib/properties/` (extending the existing `vertex_properties` module) or a new `algorithm/centrality/` category, whichever fits the existing degree functions' precedent better.
- Add corresponding documentation, including complexity.
## Acceptance criteria
- [ ] Betweenness centrality is implemented for at least one graph type (directed and/or undirected, weighted and/or unweighted — scope to be decided).
- [ ] Closeness centrality is implemented.
- [ ] Documentation added, including complexity.
- [ ] Unit tests cover a known small graph with hand-verifiable expected centrality values.
Contributor guide
Research direction
The issue points to the vertex_properties.h header in include/graaflib/properties/. Start by examining the existing degree functions and the library's graph types and shortest-path algorithms to understand the data structures. Implement Brandes' algorithm for betweenness centrality and compute closeness centrality, likely reusing shortest-path logic. Write unit tests for a small graph with known centrality values to verify correctness.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 45/100