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

Subject: Re: [Boost-users] [BGL] edge() function also inside AdjacencyList-concept?
From: Andrew Sutton (asutton.list_at_[hidden])
Date: 2010-11-05 09:22:16

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

Andrew