COIN-OR::LEMON - Graph Library

Opened 15 years ago

Last modified 14 years ago

#151 new enhancement

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

Reported by: Peter Kovacs Owned by: Balazs Dezso
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 Peter Kovacs 14 years ago.

Download all attachments as: .zip

Change History (3)

comment:1 Changed 15 years ago by Alpar Juttner

Milestone: LEMON 1.1 release

Changed 14 years ago by Peter Kovacs

Attachment: function-interfaces.diff added

comment:2 Changed 14 years ago by Peter Kovacs

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.