[Boost-users] [BGL] experience with rooting diff on dijkstra

From: Jens Theisen (jens-theisen-tmp01_at_[hidden])
Date: 2006-08-13 08:59:22

Hello,

after the discussion about on-demand vertex initialisation I implemented 
  a diffing algorithm on top of BGL's dijkstra.

I thought the main problem is that BGL is inherently linear in the 
number of vertices (because it initialises some maps on each vertex 
prior to running the algo), but in practice, for diffing files, that's 
probably not too relevant, as the case of two files being pretty 
different is not a rare one (and two completely different files will 
need to access any node).

The algorithm used by gnu diff is, though also quadratic in the input, 
linear in space usage, which one can't say for the dijsktra approach. (I 
haven't look at the algorithm, but they cite a paper which suggests that.)

And gnu diff is much faster than my program in practice, though my one 
is probably fast enough for what I want to use it for.

Jens