public interface GraphIsomorphismInspector<E>
extends java.util.Iterator<E>
Isomorphism is the problem of testing whether two graphs are topologically the same. Suppose we are given a collection of graphs and must perform some operation on each of them. If we can identify which of the graphs are duplicates, they can be discarded so as to avoid redundant work.
In Formal Math: Input description: Two graphs, G and H. Problem description: Find a (or all) mappings f of the vertices of G to the vertices of H such that G and H are identical; i.e. (x,y) is an edge of G iff (f(x),f(y)) is an edge of H. http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE180.HTM.
Efficiency: The general algorithm is not polynomial, however polynomial algorithms are known for special cases, like acyclic graphs, planar graphs etc. There are several heuristic algorithms which gives quite good results (polynomial) in general graphs, for most but not all cases.
Usage:
Modifier and Type | Method and Description |
---|---|
boolean |
isIsomorphic() |