boostorg / boostorg/graph

Supporting undirected CSR graphs

Abierto
#458 2 comentarios 2 reacciones 1 asignado Reclamado por @jeremy-murphy Ver en GitHub
data structure performance
Lenguaje dominante
C++
Estrellas
392
Forks
239
Merge medio
1 d 11 min
PR fusionados (30 d)
20

Descripción

## 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.

Guía de contribución

Abrir la guía de contribución

Evaluación

Este issue todavía no se ha evaluado.

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.