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: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-09-04 11:45:29

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

Does that mean that mean that we minimally require VertexListGraph<G> (in
what I will not refer to as C?? syntax).

I know of only one adaptor that doesn't model VertexListGraph (edge_list),
but that's just a weird data structure anyway. Actually Michael Lopez
(SoC09, function graphs) has cases where a function does not model this
concept, but that's a weird data structure too.

Maybe vertex is more like swap(), where we have a general algorithm with
lots of specializations?

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

Logically that sounds about right. The following is purely hypothetical.

template <EdgeListGraph G>
pair<Edge, bool>edge(Vertex u, Vertex v, G const& g)
{ for(...) { if source(e, g) == u && target(e, g) == v) return {e, true}; }
}

template <AdajcencyMatrix G>
pair<Edge, bool> edge(Vertex u, Vertex v, G const& g)
{ return g(u, v); }

template <IncidenceGraph G>
  requires Range<G::out_edge_range>
pair<Edge,  bool> edge(Vertex u, Vertex v, G const& g)
{ /* linear search in out_edges */ }

template <IncidenceGraph G>
  requires SortedRange<G::out_edge_range>
pair<Edge, bool> edge(Vertex u, Vertex v, G const& g)
{ /* binary search in out_edges */ }

template <IncidenceGraph G>
  requires AssociativeContainer<G::out_edge_range>
pair<Edge, bool> edge(Vertex u, Vertex v, G const& g)
{ /* use x.find() */ }

We can map these back to tag dispatch with a little bit of work.

The biggest problem I see here is that the BGL doesn't let us easily reason
about the internal properties of out edge lists for adjacency list-like data
structures or adaptors. It would be one thing to return the a legitimate
range or reference to a container, but that's not where we are right now.

One might require member functions for efficient edge queries like my
theoretical adjacency_matrix () overload. That would certainly reduce the
requirements on overloads, but leaves us more or less where we are now
(maybe?)

I wonder if this also admits the existence of an AdjacencyList concept.

Andrew Sutton
andrew.n.sutton_at_[hidden]