COIN-OR::LEMON - Graph Library

Opened 9 years ago

Last modified 2 years ago

#329 new enhancement

Sort outgoing arcs in the build() function of StaticDigraph

Reported by: Peter Kovacs Owned by: Alpar Juttner
Priority: major Milestone: LEMON 1.5 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

In the build() function of StaticDigraph which takes another digraph as an argument, the outgoing arcs of each node are sorted with respect to their target nodes.

It clearly makes the build() function (and copying a graph to StaticDigraph) somewhat slower. Preliminary tests showed a difference of about 15 percent. On the other hand, it could make the usage of the constructed graph more efficient due to better caching. However, the trade-off is not clear.

I suggest to make this sorting optional (e.g. by adding a bool parameter to the build() function). However, the default option is of high importance here, since it will be used by DigraphCopy.

This ticket is a follow-up of #68.

Change History (3)

comment:1 Changed 9 years ago by Peter Kovacs

Milestone: LEMON 1.3 release

comment:2 Changed 6 years ago by Alpar Juttner

Milestone: LEMON 1.3 releaseLEMON 1.4 release

comment:3 Changed 2 years ago by Alpar Juttner

Milestone: LEMON 1.4 releaseLEMON 1.5 release
Note: See TracTickets for help on using tickets.