COIN-OR::LEMON - Graph Library

Opened 11 years ago

Closed 6 weeks ago

#32 closed enhancement (done)

Storing Arcs instead of OutArcIts in Dfs stack

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

Description (last modified by Alpar Juttner)

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 Balazs Dezso 10 years ago.

Download all attachments as: .zip

Change History (15)

comment:1 Changed 11 years ago by Alpar Juttner

Description: modified (diff)

comment:2 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.0 releasePost 1.0

comment:3 Changed 11 years ago by Alpar Juttner

Owner: changed from Alpar Juttner to Balazs Dezso

comment:4 Changed 10 years ago by anonymous

Last edited 8 weeks ago by Peter Kovacs (previous) (diff)

comment:5 Changed 10 years ago by Balazs Dezso

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 Changed 10 years ago by Peter Kovacs

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 10 years ago by Balazs Dezso

Attachment: d5bf497757ff.patch added

comment:7 in reply to:  6 Changed 10 years ago by Balazs Dezso

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 10 years ago by Alpar Juttner

Milestone: LEMON 1.1 release

comment:9 Changed 9 years ago by Peter Kovacs

Priority: minormajor

comment:10 Changed 9 years ago by Peter Kovacs

Summary: storing Arcs instead of OutArcIts in Dfs stackStoring Arcs instead of OutArcIts in Dfs stack

comment:11 Changed 9 years ago by Peter Kovacs

Milestone: LEMON 1.3 release

comment:12 Changed 5 years ago by Balazs Dezso

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

comment:13 Changed 5 years ago by Alpar Juttner

Milestone: LEMON 1.3 releaseLEMON 1.4 release

comment:14 Changed 6 weeks ago by Alpar Juttner

Resolution: done
Status: newclosed

[d5bf497757ff] has been rebased as [15282595e6f4] and push to the main branch.

Note: See TracTickets for help on using tickets.