minimal anisomorphism

SysTom · science forum beginner Joined: 24 Jan 2006 Posts: 3

Hello,

I have two directed acyclic graphs which are known to be very nearly
isomorphic but are different in a relatively small portion of the
graphs. I wish to isolate the anisomorphic bits. Can you suggest any
algorithm(s) to do this?

I was going to do an edge-by-edge, virtex-by-virtex compare - starting
from each point of egress and traversing my way back (in a
depth-first-search) to the first miscompare. Then, likewise, starting
at each point of ingress and working my way forward to the first
miscompare. If each edge and each virtex is 'marked' as it is
traversed then, I would submit, that the remaining 'unmarked' set of
edges and vertices is the anisomorphism.

I believe this will work except for the case when the anisomorphism
creates some kind of 'island' of one or more isormorphic subgraphs -
but in this particular mapping that is unlikely and would not be
critical to my application anyway.

Thanks, Tom

Google