From: Jens Theisen (jens-theisen-tmp01_at_[hidden])
Date: 2006-08-09 17:20:04
Hello,
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). 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 are probably other applications where it also matters. In my case,
the quadracticness doesn't really matters much.
Cheers,
Jens