On Aug 9, 2006, at 5:20 PM, Jens Theisen wrote:
By the way, isn't it rather undesirable that initialisation is done prior to the algorithm, rather than on-demand?
I once had the idea of using boost::graph to implement a diffing algorithm by applying dikstra to the edit graph of two sequences (that's the popular way of doing this I think).
I didn't know that. Very interesting!
But you don't really want to build that graph, or you'll end up with quadratic complexity in any case, whereas you can have something like O(kn) where n is the length of both sequences and k is the number of "edits" in a shortest ed-script (if we take the priority queue lookup as constant).
There is a "no_init" version of Dijkstra's algorithm that skips the initialization entirely. Of course, the user would be responsible for initializing property map values for vertices on demand, e.g., in examine_edge. I've seen the no_init form of Dijkstra's used for other "implicit" graphs, which have similar properties to the one you describe. Doug