Re: [Boost-users] BGL vertex(std::size_t i, Graph) is in no concept

Subject: Re: [Boost-users] BGL vertex(std::size_t i, Graph) is in no concept
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-09-04 11:12:30

On Fri, 4 Sep 2009, Andrew Sutton wrote:

>
>             If I am not wrong, then the vertex(std::size_t i, Graph) function is required in no graph concept at all.
>             However, adjacency_list
>             defines it and csr-graphs use it ...
>
>             Did I overlook something or shouldn't the function belong to some graph concept?
> 
> 
> I have now made the CSR graphs not use it for other graphs being copied into CSR format.  There should not be any other
> algorithms that use it; however, it is provided by almost all graphs.  It is the inverse function to the vertex_index
> property map.  Some graphs also have edge_from_index which is the inverse of the edge_index property map.
> 
> 
> I think this function falls into the same category as edge(), which I'm starting to believe is exactly like iterator operations
> distance(), advance(), next() and prev(). Not part of a concept, not a full-fledged algorithm, but nonetheless an operation that
> can be implemented for every graph, with varying degrees of efficiency.

I agree.  Should vertex() by default just be vertex(i, g) = 
{vertex_iterator it = vertices(g).first; advance(it, i); return *it;}?  I 
don't think we can guarantee that matches the vertex_index map, though. 
For edge(), I imagine we should have a trait for whether the out edges of 
a vertex are sorted, and then we can use logarithmic or linear-time 
algorithms.  Particular graphs can specialize it for their own types (such 
as for adjacency_matrix's constant-time version).  The edge_range() 
function should be the same thing, except that it requires that the edges 
are sorted in some way so that parallel edges are together (or we can use 
a filtered_iterator which would be a lot slower).

-- Jeremiah Willcock