Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net