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

[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