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