bobluppes / bobluppes/graaf

Add centrality measures (betweenness, closeness)

Open
#337 0 comments 0 reactions 0 assignees View on GitHub
enhancement good first issue help wanted
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.