- All Implemented Interfaces:
- EquivalenceAlgorithm
public class StructurallyEquivalentII
extends StructurallyEquivalent
Checks a graph for sets of structurally equivalent vertices: vertices that
share all the same edges. Specifically, In order for a pair of vertices
i and j to be structurally equivalent, the set of i 's
neighbors must be identical to the set of j 's neighbors, with the
exception of i and j themselves. This algorithm finds all
sets of equivalent vertices in O(V^2) time.
You can extend this class to have a different definition of equivalence (by
overriding "isStructurallyEquivalent"), and may give it hints for
accelerating the process by overriding canpossiblycompare. (For example, in
a bipartitegraph, canPossiblyCompare may return false for vertices in
different partitions. This function should be fast.)
- Author:
- danyelf