Storing Arcs instead of OutArcIts in Dfs stack

[Balazs Dezso]

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.

[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?

[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?

[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

[Balazs Dezso]

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

[Alpar Juttner]

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