StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POIs there a way to make PHP's SplHeap recalculate? (aka: add up-heap to SplHeap?)
text
Body
copied!<p>I am using an <a href="http://php.net/SplHeap" rel="noreferrer"><code>SplHeap</code></a> to hold graph nodes of a tree with directed edges that will be traversed from the leaves to the root. For this, I precalculate the "fan-in" of nodes and put them into the heap so that I can always retrieve the node with the smallest fan-in (0) from it.</p> <p>After visiting a node, I reduce the fan-in of its successor by 1. Then obviously, the heap needs to be recalculated because the successor is now in the wrong place there. I have tried <code>recoverFromCorruption()</code>, but it doesn't do anything and keeps the heap in the wrong order (node with larger <code>fanIn</code> stays in front of smaller <code>fanIn</code>).</p> <p>As a workaround, I'm now creating a new heap after each visit, amounting to a full O(N*log(N)) sort each time.</p> <p>It should be possible, however, to make up-heap operations on the changed heap entry until it's in the right position in O(log(N)).</p> <p>The API for <code>SplHeap</code> doesn't mention an up-heap (or deletion of an arbitrary element - it could then be re-added). Can I somehow derive a class from <code>SplHeap</code> to do this or do I have to create a pure PHP heap from scratch?</p> <p><strong>EDIT</strong>: Code example:</p> <pre><code>class VoteGraph { private $nodes = array(); private function calculateFanIn() { /* ... */ } // ... private function calculateWeights() { $this->calculateFanIn(); $fnodes = new GraphNodeHeap(); // heap by fan-in ascending (leaves are first) foreach($this->nodes as $n) { // omitted: filter loops $fnodes->insert($n); } // traversal from leaves to root while($fnodes->valid()) { $node = $fnodes->extract(); // fetch a leaf from the heap $successor = $this->nodes[$node->successor]; // omitted: actual job of traversal $successor->fanIn--; // will need to fix heap (sift up successor) because of this //$fnodes->recoverFromCorruption(); // doesn't work for what I want // workaround: rebuild $fnodes from scratch $fixedHeap = new GraphNodeHeap(); foreach($fnodes as $e) $fixedHeap->insert($e); $fnodes = $fixedHeap; } } } class GraphNodeHeap extends SplHeap { public function compare($a, $b) { if($a->fanIn === $b->fanIn) return 0; else return $a->fanIn < $b->fanIn ? 1 : -1; } } </code></pre> <p>Complete code also available: <a href="https://github.com/md2k7/civicracy/blob/master/civi-php/protected/components/VoteGraph.php#L73" rel="noreferrer">https://github.com/md2k7/civicracy/blob/master/civi-php/protected/components/VoteGraph.php#L73</a></p> <p><strong>EDIT 2</strong>:</p> <pre><code>$this->putNode(new GraphNode(4)); $this->putNode(new GraphNode(1, 2)); $this->putNode(new GraphNode(3, 2)); $this->putNode(new GraphNode(2, 4)); </code></pre> <p>This means <strong>user 1</strong> and <strong>user 3</strong> are voting for <strong>user 2</strong>, and <strong>user 2</strong> is voting for <strong>user 4</strong>, passing on 3 votes (2 received + his/her own). This is called delegative voting: my algorithm is passing on votes "from the bottom" (the leaves) where I already know how much weight (responsibility/representation/as you like it...) each user has.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload