[BGL] edge() function also inside AdjacencyList-concept?
Hi, 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? Best regards, Cedric
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
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
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
participants (3)
-
Andrew Sutton -
Cedric Laczny -
Jeremiah Willcock