[boost] BGL CSR Format (logarithmic edge search)

Subject: [boost] BGL CSR Format (logarithmic edge search)
From: Ryan Lichtenwalter (rlichten_at_[hidden])
Date: 2011-11-20 14:01:35

Hello,

According to:

http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/compressed_sparse_row.html#edge-access

[Edge search] requires linear time in the number of edges outgoing from u.

The purpose of the CSR format is to support highly efficient computation
with minimal memory requirements at the cost of mutability and additional
time in construction. Is there a reason, then, that the adjacencies are
stored unsorted within their vertex ranges? With minimal additional time
during construction, edge access could be reduced to logarithmic time in
the number of edges outgoing from u without sacrificing any functionality
elsewhere that I can determine.

Can somebody explain this design decision to me? If there is no
explanation, does anybody have plans to adjust the representation? I would
probably be willing to contribute an adjusted representation if nobody else
has plans to do so.

Thanks!

Ryan Lichtenwalter