net.sf.octet.traversal
Class UllmanIsomorphismTraverser

java.lang.Object
  net.sf.octet.traversal.UllmanIsomorphismTraverser

All Implemented Interfaces:

IsomorphismTraverser

public class UllmanIsomorphismTraverser

extends java.lang.Object

implements IsomorphismTraverser

An implementation of the IsomorphismTraverser interface that uses Ullman's subgraph isomorphism algorithm. The objective of this algorithm is to generate the set of all permutation matricies that map the nodes of an input graph onto a model graph.

The permutation matricies generated by Ullman's algorithm are edge-induced rather than vertex-induced. This distinction has important implications for the type of isomorphism that will be detected. For example, if input is a chain of n vertices and model is a cycle of n vertices, no isomorphism will be detected by Ullman's algorithm because model contains one more edge than input, namely the cycle-closing edge. This behavior contrasts with many forms of substructure comparison in which a chain of n nodes does map to a cycle of n nodes.

UllmanIsomorphismTraverser will traverse as many Atoms and AtomPairs as are present in the input AtomGraph. This implementation was adapted from a discussion of Ullman's algorithm. The structure of the private backtrack method is based on the method of the same name found in the Ullman class contained in the Graph Visualization Framework.

Author:

Richard Apodaca

Nested Class Summary

Nested classes inherited from class net.sf.octet.traversal.IsomorphismTraverser

IsomorphismTraverser.Handler

Constructor Summary

UllmanIsomorphismTraverser()
Constructs a fully functional UllmanIsomorphismTraverser.

Method Summary

void	traverse(AtomGraph input, AtomGraph model, IsomorphismTraverser.Handler handler) Traverses the Atoms and AtomPairs in model that are isomorphic with those contained in input while forwarding traversal events to handler.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

UllmanIsomorphismTraverser

public UllmanIsomorphismTraverser()

Constructs a fully functional UllmanIsomorphismTraverser.

Method Detail

traverse

public void traverse(AtomGraph input,
                     AtomGraph model,
                     IsomorphismTraverser.Handler handler)

Description copied from interface: IsomorphismTraverser

Traverses the Atoms and AtomPairs in model that are isomorphic with those contained in input while forwarding traversal events to handler.

Specified by:

traverse in interface IsomorphismTraverser

Parameters:

input - the AtomGraph whose elements will be compared to model

model - the AtomGraph whose elements that are isomorphic to model will be traversed

handler - receives traversal events