bobluppes / bobluppes/graaf

Add centrality measures (betweenness, closeness)

Aperta
#337 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub
enhancement good first issue help wanted
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

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.