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:
> According to:
> [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