onierstrasz / IMAD

experiments using Gt and Mondrian to build executable domain models
MIT License
3 stars 1 forks source link

Need proper implementation of Hypernode equality #30

Closed onierstrasz closed 3 years ago

onierstrasz commented 3 years ago

To be fixed: Hypernode>>#=

The simple solution of testing equality of subnodes and edges is fragile (nodes may not be in same order) and does not terminate for recursive hypernodes. Comparing the storeStrings is also fragile because the order of nodes may change. Full graph isomorphism may be too expensive (though comparing properties may help to reduce costs).

Graph isomorphism has unknown complexity, worse than NP, so we need an easy solution. If we can guarantee a consistent order for reachable nodes, we could traverse them and check if they establish an isomporhism. (Checking an isomorphism is cheaper than finding one!)

But reachableNodes currently creates an identitySet. If we use an OrderedCollection instead, we must take care because reachableNodes uses includes:, which in turn uses =. We must avoid an infinite recursion.

onierstrasz commented 3 years ago

Implemented Hypernode>>#isomorphicTo: which checks if the mapping of nodes from one graph to an other is an isomorphism.