COIN-OR::LEMON - Graph Library

Opened 8 years ago

Last modified 17 months ago

#329 new enhancement

Sort outgoing arcs in the build() function of StaticDigraph

Reported by: kpeter Owned by: alpar
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 8 years ago by kpeter

  • Milestone set to LEMON 1.3 release

comment:2 Changed 5 years ago by alpar

  • Milestone changed from LEMON 1.3 release to LEMON 1.4 release

comment:3 Changed 17 months ago by alpar

  • Milestone changed from LEMON 1.4 release to LEMON 1.5 release
Note: See TracTickets for help on using tickets.