O(1) time to get an arc from node u and node v

[zhaofeng-shu33]

is there any graph structure in lemon library which supports getting an arc from its two nodes in O(1) times? I check ListDigraph?, by iterating all arcs connected with one node, I can achieve this purpose but it could be O(n).

[Peter Kovacs]

As far as I know, LEMON does not provide a graph structure for this purpose. However, it provides utilities for fast arc lookup, namely in O(log d) time (where d is the node degree), which may be appropriate for your use case. They work with any graph structure. Check the classes ArcLookup and DynArcLookup among the basic graph utilities:
http://lemon.cs.elte.hu/pub/doc/1.3.1/a00624.html

If you really need arc lookup in O(1) time (and you don't need parallel arcs), then you may consider using a FullDigraph structure combined with a FilterArcs adaptor, which can hide the unwanted arcs. Using the original graph, you can obtain an arc object in O(1) time for any pair of nodes, and the FilterArcs object can tell you if that arc is actually present in the considered digraph or not, also in O(1) time. See the following pages for the details:
http://lemon.cs.elte.hu/pub/doc/1.3.1/a00176.html
http://lemon.cs.elte.hu/pub/doc/1.3.1/a00169.html

[zhaofeng-shu33]

I think FullDigraph works for my problem.