boostorg / boostorg/graph

Supporting undirected CSR graphs

Open
#458 2 comments 2 reactions 1 assignee Claimed by @jeremy-murphy View on GitHub
data structure performance
Dominant language
C++
Stars
392
Forks
239
Avg merge
1d 11m
Merged PRs (30d)
20

Description

## Problem

Currently, the Boost Graph Library's `compressed_sparse_row_graph` only supports directed and bidirectional graphs. There are explicit comments in the codebase and documentation indicating that undirected CSR support is a planned but unimplemented feature:

- [`compressed_sparse_row_graph.hpp`](https://github.com/boostorg/graph/blob/3131c24630e42c79b43c1f32558041c219ab84b8/include/boost/graph/compressed_sparse_row_graph.hpp#L239-L259):
> At this time, the compressed sparse row graph can only be used to create directed and bidirectional graphs. In the future, undirected CSR graphs will also be supported.
- [`doc/compressed_sparse_row.html`](https://github.com/boostorg/graph/blob/3131c24630e42c79b43c1f32558041c219ab84b8/doc/compressed_sparse_row.html#L316-L337):
> At this time, the CSR graph type only supports directed and bidirectional graphs...

This is problematic for several reasons, e.g. for adjusting performance in my Louvain's implementation algorithm: I can't use Louvain on directed graphs, but I can't use undirected CSR. Consequently a gap exists between BGL implementations and GenLouvain (that uses CSR). Having an undirected CSR could bridge that gap:

Image

## Feature Request

Add support for undirected compressed sparse row (CSR) graphs to `compressed_sparse_row_graph`. This would improve memory efficiency and performance for large undirected graphs, matching the benefits provided for directed graphs.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.