Algorithm Complexity and Determinism of Graph Module

ownlifeful has asked for the wisdom of the Perl Monks concerning the following question:

Greetings, fellow Perl Monks,

Please accept my sincere gratitude for being a wonderful Perl resource for everyone!

With great humility and respect, I put forth this question before you:

I am developing a new graph algorithm that utilizes the Graph module. The Graph module provides the $g->vertices() method. The results this method returns in a list context, are not deterministic. That is, for the same graph, when you call:

my @vertices = $g->vertices();

the vertices might be in different order. Since I rely on this method, my algorithm is also not deterministic. For a fixed given input, my algorithm produces the correct result, but the number of times it recurses varies wildly.

I could just change it to:

my @vertices = sort $g->vertices();

everywhere, but that would kill the performance of the algorithm. Is there a better way?

Also, I would appreciate any tips on computing the Big-O complexity of an algorithm implemented in Perl. Does one have to mentally unfurl every line of Perl down to C, while computing the complexity?

I await your wise and erudite responses to enlighten me.

Comment on Algorithm Complexity and Determinism of Graph Module Select or Download Code

Replies are listed 'Best First'.
Re: Algorithm Complexity and Determinism of Graph Module by Laurent_R (Canon) on Jun 11, 2017 at 08:51 UTC
Hi, you don't give enough information on what you're doing to elicit a really useful answer. One typical way of dealing with unordered hash entries is to maintain separately another data structure that keeps the right order. For example, you could sort your data only once and store in a separate hash the rank of each value (with the vertex or vertex ref as a key and the rank as value). But we don't have enough information on what you do to know if this would be usable or useful in your case. As for the complexity,, it's even more difficult to say anything without seeing your code. But, no, in general you should not need to mentally unroll Perl code to underlying C to figure out the complexity of your algorithm. But, you need to understand the complexity of the Perl constructs, though. For example, traversing an array with n entries to see if a value is there would have a O(n) complexity. A hash lookup on the same list of entries, on the other hand, would have a complexity of O(1), i.e. the complexity of a hash lookup does not depend on the size of the hash.	[reply]
Re: Algorithm Complexity and Determinism of Graph Module by LanX (Saint) on Jun 11, 2017 at 05:07 UTC
In Graph it's documented for ->vertices that "In list context, return the vertices, in no particular order." `sort` is very efficient and it sounds strange that your algorithm depends on the order of vertices. I'd say this sounds like a XY Problem , and you should elaborate more what you are trying to achieve. Cheers Rolf _{(addicted to the Perl Programming Language and ☆☆☆☆ :) Je suis Charlie!}	[reply]
Re: Algorithm Complexity and Determinism of Graph Module by Anonymous Monk on Jun 11, 2017 at 01:34 UTC
As far as I can tell from the code, `Graph::vertices()` gets its list from `Graph::AdjacencyMap::paths()`, and all three implementations (`::Light`, `::Heavy`, and `::Vertex`) use a hash to store them. Hashes are unordered, so if you need a sorted order, you will have to to sort them yourself. Either that, or modify the internals of the Graph module so vertices aren't stored in a hash but in a sorted data structure.	[reply] [d/l] [select]
Re: Algorithm Complexity and Determinism of Graph Module by ownlifeful (Beadle) on Jun 11, 2017 at 11:03 UTC
Thanks for the thoughtful replies, everyone. Judicious use of `sort` made the algorithm deterministic. The algorithm aims to determine whether a given undirected graph contains any Hamiltonian Cycles. I am still calculating the Big-O complexity, and would appreciate any help. Here is a link to the source code on GitHub. There is also a demo at: `ownlifeful.com`	[reply] [d/l] [select]
Re^2: Algorithm Complexity and Determinism of Graph Module by Discipulus (Canon) on Jun 11, 2017 at 22:29 UTC
sorry if I cant help you ownlifeful but with your project and a poem as first posts you have my warmest welcome to the monastery! L* There are no rules, there are no thumbs.. Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.	[reply] [d/l]
Re^3: Algorithm Complexity and Determinism of Graph Module by ownlifeful (Beadle) on Jun 12, 2017 at 13:21 UTC
Thank you for the warm welcome, Discipulus. I have lurked around the Monastery for years, and have reaped much benefit from the discourse of the Monks. Glad to share the Perl journey with my fellow Monks.	[reply]


laziness, impatience, and hubris
	PerlMonks