Re: [boost] BGL CSR Format (logarithmic edge search)

Subject: Re: [boost] BGL CSR Format (logarithmic edge search)
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-11-21 11:25:29

On Sun, 20 Nov 2011, Ryan Lichtenwalter wrote:

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

The edges from each vertex used to be sorted, but that was changed when 
linear-time graph construction was introduced.  One problem is that the 
standard sorting routines cannot sort corresponding ranges of elements 
(such as edge targets and properties); also, sorting edges increases the 
time complexity of the graph construction algorithm.  Note that the CSR 
constructors that do sorting, except for the in-place versions, apply 
stable sorts to the edges you input, so you could give it a sorted list of 
edges and then write a logarithmic-time search routine using out_edges().

-- Jeremiah Willcock