I made this blog less eye hurty. The existing css frightened me so I deleted most of it and rewrote some.
Thus some things may not work! Especially on *your* browser.
Re the algorithm in last post.
That the graph contains an 'implies not' relationship is a pre-condition of using the algorithm. For my application, this is also fairly easy to do.
There has to be some sort of check to ensure that you're not getting stuck in an infinite loop - this is done by checking you're not redundantly updating the implication_set.
There will be a finite, and for todays hardware, small number of atoms. This means the implication_set could be represented as a 1 dimensional array. Therefore set insertion and lookup can be done in constant time O(1).
I wrongly stated that the working from one graph can be insert into another. It CANNOT be.
The stack need not grow - we could have a data structure to which work could be pooled, and then executed after the stack has shrank again.
The setInterval function may be useful for implementing the algorithm in javascript - that way we can run a long computation without freezing the browser.
Optimized algorithm later :)
20 August 2010
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment