COIN-OR::LEMON - Graph Library

Opened 9 years ago

Last modified 8 years ago

#151 new enhancement

Possible improvement in the function-type implementation of BFS/DFS/Dijkstra

Reported by: kpeter Owned by: deba
Priority: minor Milestone:
Component: core Version: hg main
Keywords: Cc:
Revision id:


This ticket is a follow-up of #96.

Maybe it would be better if we could avoid using NodeMaps (instead of NullMaps) as PredMap and DistMap structures in the cases when they are not necessary. So the default type of these maps would be a NullMap in Bfs/Dfs/DijkstraWizardDefaultTraits classes, and it would be changed only if it is really needed (i.e. path() and/or dist() named parameter is used).

Balazs suggested a solution for this, saying: "iff at least one s-t path search is queried, real pred map should be defined, and iff at least one length of an s-t path queried, real dist map should be used. It could be done with the ForkMaps".

It is a benchmark question however, that this implementation would be more efficient or not in practice.

Attachments (1)

function-interfaces.diff (3.9 KB) - added by kpeter 8 years ago.

Download all attachments as: .zip

Change History (3)

comment:1 Changed 9 years ago by alpar

  • Milestone LEMON 1.1 release deleted

Changed 8 years ago by kpeter

comment:2 Changed 8 years ago by kpeter

The attached patch file shows a possible solution for this task (using run time check inside the run() functions). Note that it modifies only one function, the others could be implemented similarly. It would cause a lot of code repeating.

Note: See TracTickets for help on using tickets.