COIN-OR::LEMON - Graph Library

Opened 7 weeks ago

Last modified 4 weeks ago

#627 new enhancement

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

Reported by: zhaofeng-shu33 Owned by: Alpar Juttner
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

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

Change History (2)

comment:1 Changed 4 weeks ago by 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

comment:2 Changed 4 weeks ago by zhaofeng-shu33

I think FullDigraph works for my problem.

Note: See TracTickets for help on using tickets.