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

Subject: Re: [Boost-users] [BGL] edge() function also inside AdjacencyList-concept?
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2010-11-05 09:42:21

On Friday, 5. November 2010 14:22:16 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.
> 

I am not sure but wouldn't it be nice to include this information also into 
the documentation?!
For me personally, this would have saved some (probably redundant) 
programming.

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

Thank you for the clarification. That's about what I assumed also. Before 
finding out that this function also worked for adjacency_list, I had iterated 
over the out_edges (undirected graphs) of one of the vertices and checked for 
existence of an edge between the two vertices.
The overload will probably behave similar and it is a lot shorter and easier 
to use unless you have defined it somewhere on your own and are constantly 
using it.

> Andrew

Best,

Cedric