Add centrality measures (betweenness, closeness)
- Lingua principale
- C++
- Stelle
- 413
- Fork
- 67
- Merge medio
- 7h 24m
- PR unite (30g)
- 53
Descrizione
## 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.
Guida per i contributori
Apri la guida per i contributori
Direzione di ricerca
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.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Valutazione
- Stack tecnologico
- cpp
- Tipo di issue
- Funzionalità
- Difficoltà
- 4/5
- Tempo stimato
- 3-5 giorni
- Stato di attività
- Attiva
- Chiarezza
- Specificata chiaramente
- Idoneità per principianti
- 45/100