Re: [Boost-users] [BGL] edge() function also inside AdjacencyList-concept?

Subject: Re: [Boost-users] [BGL] edge() function also inside AdjacencyList-concept?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-11-05 09:41:48

On Fri, 5 Nov 2010, Andrew Sutton wrote:

>
>       I was wondering that the edge()-function (to see if there is an edge between
>       two vertices and if so also return it) also exists for the AdjacenyList-
>       concept?! As in the documentation, I find it only under "AdjacencyMatrix refines
>       Graph" but nowhere else.
>       Where is it defined and what is it's time complexity (just to make sure that my
>       assumptions on the complexity are correct) please?
> 
> 
> The edge function isn't formally part of the AdjacencyList specification, but all adjacency lists provide an
> overload (curiously). The signature of the function is the same as the AdjacencyMatrix documentation.
> 
> It's probably better to think of edge() as an algorithm rather than an accessor function. Using edge() with an
> AdjacencyMatrix has O(1) performance. It's slower for a graph modeling any other concept.

There is also a lookup_edge() function (in <boost/graph/lookup_edge.hpp>) 
that acts like edge() but automatically falls back to searching in a 
vertex's out edge list when the graph doesn't have an edge() function.

-- Jeremiah Willcock