COIN-OR::LEMON - Graph Library

Opened 10 years ago

Last modified 4 years ago

#32 new enhancement

Storing Arcs instead of OutArcIts in Dfs stack

Reported by: deba Owned by: deba
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description (last modified by alpar)

The OutArcIt contains an int data field and a pointer to the graph, while the Arc just stores the int member. If we used Arcs in the Dfs stack, that could decrease the memory request of Dfs and it may provide better runtime performance.

Attachments (1)

d5bf497757ff.patch (1.6 KB) - added by deba 9 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 10 years ago by alpar

  • Description modified (diff)

comment:2 Changed 10 years ago by alpar

  • Milestone changed from LEMON 1.0 release to Post 1.0

comment:3 Changed 10 years ago by alpar

  • Owner changed from alpar to deba

comment:4 Changed 9 years ago by anonymous

Iron decorates your home. They have a wide variety of design, assuring that you will find a special one for display at home. The metal stai http://www.hebei-railings.cn/

comment:5 Changed 9 years ago by deba

Hi I have tested this change, but obviously this is not a real performance enhancement. At most 2.5% speedup can be achieved with this change. What is your opinion, can we close the ticket or should we put the changeset in the repo?

comment:6 follow-up: Changed 9 years ago by kpeter

The memory request of this implementation is about half of the current one, and it is not slower, or sometimes slightly faster. Am I right? So if it does not have any disadvantage compared to the current one, then it should be put in the repo, I think.

Did you tested the change on huge graphs (containing millions of nodes and arcs), in which the DFS tree contains very long paths, too?

Changed 9 years ago by deba

comment:7 in reply to: ↑ 6 Changed 9 years ago by deba

Replying to kpeter:

The memory request of this implementation is about half of the current one, and it is not slower, or sometimes slightly faster. Am I right? So if it does not have any disadvantage compared to the current one, then it should be put in the repo, I think.

Did you tested the change on huge graphs (containing millions of nodes and arcs), in which the DFS tree contains very long paths, too?

Thanks for the suggestion, I tested with large cycle graph, and in this case I have measured 10% of improvement in the running time. I have uploaded the patch [d5bf497757ff]. The tester code can be found on the following place,
http://lime.cs.elte.hu/~deba/hgwebdir.cgi/deba_lemon_loc/file/badee141a2d0/dfs_test.cc

comment:8 Changed 9 years ago by alpar

  • Milestone LEMON 1.1 release deleted

comment:9 Changed 8 years ago by kpeter

  • Priority changed from minor to major

comment:10 Changed 8 years ago by kpeter

  • Summary changed from storing Arcs instead of OutArcIts in Dfs stack to Storing Arcs instead of OutArcIts in Dfs stack

comment:11 Changed 8 years ago by kpeter

  • Milestone set to LEMON 1.3 release

comment:12 Changed 4 years ago by deba

This change looks small, so I think we can try use it.

comment:13 Changed 4 years ago by alpar

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