On Jul 19, 2004, at 10:33 AM, Chris Muller wrote:

> It's been a long time since I messed with it, and my goal was only a 
> reasonable
> determination of whether two object-graphs were equivalent (so I could 
> use it
> for Magma's test cases).  It was too hard to get it to work with 
> complex
> graphs.

Comparing two graphs for equality (isomorphism) is a fairly well known 
problem, although certainly a hard one in terms of being 
computationally intensive.  The basic idea is to use backtracking: walk 
through the graphs in tandem, making guesses as to how the nodes match 
up, and if you hit an inconsistency, go back and revise one of your 
previous guesses and try again.  There are some good links here:

http://www.cs.sunysb.edu/~algorith/files/graph-isomorphism.shtml

However, what Göran's looking for is much more than simply testing for 
equality: he wants to be able to get a description of the (minimal, 
presumably) operations that transform one graph into another, which can 
then be used to merge two concurrent changes to the same graph.  This 
is also a hard problem in the general case - even just for trees, it's 
NP-complete, and the algorithms are quite involved.  I don't know of 
any work anyone's done on this for arbitrary graphs.

A recent thought I had is this: if your data can be normalized into 
what relational database people call 1NF, or "first normal form" ("each 
column must contain a single value and each row must contain the same 
columns"), then the problem becomes quite easy - it's having 
collections (ie, multiple edges of the same type from a single node in 
the graph) that make the problem hard, and 1NF doesn't (explicitly) 
have any collections.  Luckily, Smalltalkers have struggled for years 
with the problem of mapping object models to 1NF - that's what 
object/relational mapping frameworks like GLORP do.  So it may be 
possible to rip the metamodel and transformation code from something 
like GLORP and apply it instead to the diff/merge problem.  Like GLORP 
itself, this wouldn't work for every object model out there (for 
example, you need some way to derive a unique and immutable primary key 
for each object), but it would do just fine for the likes of SqueakMap.

Cheers,
Avi