Given two input directed graphs \$G_1 = (V_1, A_1)\$ and \$G_2 = (V_2, A_2)\$, the problem of isomorphism asks whether the two directed graphs are isomorphic, or in other words, whether the two input graphs have precisely the same structure. Formally, two input graphs \$G_1\$ and \$G_2\$ are isomorphic if and only if there exists a bijection \$f \colon V_1 \to V_2\$ such that \$(f(u), f(v)) \in A_2\$ if and only if \$(u, v) \in A_1\$.
Clearly, if the two input graphs have different amount of nodes or edges, they cannot be isomorphic. Otherwise, if we sort the nodes of both the graphs by their in-/out-degrees and the sequences do not much, the two graphs cannot be isomorphic. If two input graphs will pass the aforementioned tests, a brute force is used in order to find a possible isomorphism. This happens as follows:
- Split the node lists of both the input graphs into groups. A group is a list of nodes with exactly the same in-/out-degrees.
- Permute once the nodes in one single group. If it produces an isomorphism, return it. Otherwise, permute some group one more time.
Now, see what I have:
AbstractGraphNode.java:
package net.coderodde.graph;
import java.util.Objects;
import java.util.Set;
/**
* This class defines the API for a graph node.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Oct 11, 2015)
* @param <N> the actual graph node implementation type.
*/
public abstract class AbstractGraphNode<N extends AbstractGraphNode<N>> {
private final String name;
private Graph<N> ownerGraph;
public AbstractGraphNode(String name) {
Objects.requireNonNull(name, "The name of the node is null.");
this.name = name;
}
public String getName() {
return name;
}
public void setOwnerGraph(Graph<N> ownerGraph) {
if (this.getOwnerGraph() != null) {
clear();
this.getOwnerGraph().removeNode(this);
}
this.ownerGraph = ownerGraph;
}
public Graph<N> getOwnerGraph() {
return ownerGraph;
}
/**
* Makes {@code child} a child node of this node.
*
* @param child the child node.
*/
public abstract void addChild(N child);
/**
* Tests whether {@code node} is a child node of this node.
*
* @param node the node to test.
* @return {@code true} only if {@code node} is the child node of this node.
*/
public abstract boolean hasChild(N node);
/**
* Tests whether {@code node} is a parent node of this node.
*
* @param node the node to test.
* @return {@code true} only if {@code node} is the parent node of this
* node.
*/
public abstract boolean hasParent(N node);
/**
* Removes the child from this node.
*
* @param child the node to remove.
*/
public abstract void removeChild(N child);
/**
* Returns a set of child nodes of this node.
*
* @return a set of nodes.
*/
public abstract Set<N> children();
/**
* Returns a set of parent nodes of this node.
*
* @return a set of nodes.
*/
public abstract Set<N> parents();
/**
* Disconnects this node from all its neighbors.
*/
public abstract void clear();
/**
* {@inheritDoc }
*/
@Override
public int hashCode() {
return name.hashCode();
}
/**
* {@inheritDoc }
*/
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
AbstractGraphNode<N> other = (AbstractGraphNode<N>) obj;
return Objects.equals(name, other.name);
}
protected void checkNodeBelongsToGraph() {
if (this.getOwnerGraph() == null) {
throw new IllegalStateException(
"The node does not belong to any graph.");
}
}
protected void addEdges(int edges) {
ownerGraph.addEdges(edges);
}
}
DirectedGraphNode.java:
package net.coderodde.graph.support;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.Set;
import net.coderodde.graph.AbstractGraphNode;
/**
* This class implements a directed graph node.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Oct 11, 2015)
*/
public class DirectedGraphNode extends AbstractGraphNode<DirectedGraphNode> {
private final Set<DirectedGraphNode> children = new LinkedHashSet<>();
private final Set<DirectedGraphNode> parents = new LinkedHashSet<>();
private final Set<DirectedGraphNode> childrenWrapper =
Collections.<DirectedGraphNode>unmodifiableSet(children);
private final Set<DirectedGraphNode> parentsWrapper =
Collections.<DirectedGraphNode>unmodifiableSet(parents);
/**
* Constructs a new directed graph node with given name.
*
* @param name the name of the node.
*/
public DirectedGraphNode(String name) {
super(name);
}
@Override
public void addChild(DirectedGraphNode child) {
checkNodeBelongsToGraph();
if (child == null) {
return;
}
children.add(child);
child.parents.add(this);
addEdges(1);
}
@Override
public boolean hasChild(DirectedGraphNode node) {
return children.contains(node);
}
@Override
public boolean hasParent(DirectedGraphNode node) {
return parents.contains(node);
}
@Override
public void removeChild(DirectedGraphNode node) {
if (node == null) {
return;
}
if (node.getOwnerGraph() != this.getOwnerGraph()) {
return;
}
if (!children.contains(node)) {
return;
}
children.remove(node);
node.parents.remove(this);
addEdges(-1);
}
@Override
public Set<DirectedGraphNode> children() {
return childrenWrapper;
}
@Override
public Set<DirectedGraphNode> parents() {
return parentsWrapper;
}
@Override
public void clear() {
for (DirectedGraphNode child : children) {
child.parents.remove(this);
}
for (DirectedGraphNode parent : parents) {
parent.children.remove(this);
}
addEdges(-children.size());
addEdges(-parents.size());
children.clear();
parents.clear();
}
@Override
public String toString() {
return "[DirectedGraphNode \"" + getName() + "\"]";
}
}
Graph.java:
package net.coderodde.graph;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Objects;
/**
* This class implements the graph data structure.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Oct 11, 2015)
* @param <N> the actual graph node implementation type.
*/
public class Graph<N extends AbstractGraphNode<N>> implements Iterable<N> {
private final Map<String, N> nameMap = new LinkedHashMap<>();
private int numberOfEdges;
@Override
public Iterator<N> iterator() {
return nameMap.values().iterator();
}
public void addNode(N node) {
Objects.requireNonNull(node, "The input node is null.");
if (!nameMap.containsKey(node.getName())) {
node.setOwnerGraph(this);
nameMap.put(node.getName(), node);
}
}
public void removeNode(AbstractGraphNode<N> node) {
Objects.requireNonNull(node, "The input node is null.");
node.clear();
nameMap.remove(node.getName());
}
public N getNodeByName(String name) {
return nameMap.get(name);
}
public void clear() {
nameMap.clear();
numberOfEdges = 0;
}
public int size() {
return nameMap.size();
}
public int getNumberOfEdges() {
return numberOfEdges;
}
protected void addEdges(int edges) {
numberOfEdges += edges;
}
}
AbstractGraphIsomorphismChecker.java:
package net.coderodde.graph.isomorphism;
import java.util.Map;
import net.coderodde.graph.AbstractGraphNode;
import net.coderodde.graph.Graph;
/**
* This interface defines the API for checking whether two graphs are
* isomorphic, i.e., whether the two graphs have the same structure.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Oct 11, 2015)
* @param <N> the actual graph node implementation type..
*/
public interface AbstractGraphIsomorphismChecker
<N extends AbstractGraphNode<N>> {
/**
* Performs the isomorphism check and returns an isomorphism in case the two
* input graphs are isomorphic. If the input graphs are not isomorphic,
* {@code null} is returned.
*
* @param graph1 the first graph.
* @param graph2 the second graph.
* @return {@code true} only if the two input graphs are isomorphic.
*/
public Map<N, N> getIsomorphism(Graph<N> graph1, Graph<N> graph2);
}
TrivialDirectedGraphIsomorphismChecker.java:
package net.coderodde.graph.isomorphism;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import net.coderodde.graph.Graph;
import net.coderodde.graph.support.DirectedGraphNode;
/**
* This class implements a simple graph isomorphism tester for directed graphs.
*
* @author Rodion "rodde" Efremov
* @version 1.6
*/
public class TrivialDirectedGraphIsomorphismChecker
implements AbstractGraphIsomorphismChecker<DirectedGraphNode>{
private final Comparator<DirectedGraphNode> permutationComparator =
new PermutationComparator();
/**
* {@inheritDoc }
*/
@Override
public Map<DirectedGraphNode, DirectedGraphNode>
getIsomorphism(Graph<DirectedGraphNode> graph1,
Graph<DirectedGraphNode> graph2) {
Objects.requireNonNull(graph1, "The first input graph is null.");
Objects.requireNonNull(graph2, "The second input graph is null.");
if (graph1.size() != graph2.size()) {
return null;
}
if (graph1.getNumberOfEdges() != graph2.getNumberOfEdges()) {
return null;
}
List<DirectedGraphNode> nodeList1 = graphToList(graph1);
List<DirectedGraphNode> nodeList2 = graphToList(graph2);
Comparator<DirectedGraphNode> comparator =
new Comparator<DirectedGraphNode>() {
@Override
public int compare(DirectedGraphNode o1,
DirectedGraphNode o2) {
int outDegree1 = o1.children().size();
int outDegree2 = o2.children().size();
if (outDegree1 != outDegree2) {
return Integer.compare(outDegree1, outDegree2);
}
int inDegree1 = o1.parents().size();
int inDegree2 = o2.parents().size();
return Integer.compare(inDegree1, inDegree2);
}
};
Collections.sort(nodeList1, comparator);
Collections.sort(nodeList2, comparator);
for (int i = 0; i < nodeList1.size(); ++i) {
if (nodeList1.get(i).children().size() !=
nodeList2.get(i).children().size()) {
return null;
}
if (nodeList1.get(i).parents().size() !=
nodeList2.get(i).parents().size()) {
return null;
}
}
return bruteForceIsomorphism(nodeList1, nodeList2);
}
private static List<DirectedGraphNode>
graphToList(Graph<DirectedGraphNode> graph) {
List<DirectedGraphNode> ret = new ArrayList<>(graph.size());
for (DirectedGraphNode node : graph) {
ret.add(node);
}
return ret;
}
private static Map<DirectedGraphNode, DirectedGraphNode>
bruteForceIsomorphism(List<DirectedGraphNode> nodeList1,
List<DirectedGraphNode> nodeList2) {
List<List<DirectedGraphNode>> list1 = new ArrayList<>();
List<List<DirectedGraphNode>> list2 = new ArrayList<>();
list1.add(new ArrayList<DirectedGraphNode>());
list1.get(0).add(nodeList1.get(0));
list2.add(new ArrayList<DirectedGraphNode>());
list2.get(0).add(nodeList2.get(0));
int previousInDegree = nodeList1.get(0).parents().size();
int previousOutDegree = nodeList2.get(0).children().size();
for (int i = 1; i < nodeList1.size(); ++i) {
DirectedGraphNode currentNode = nodeList1.get(i);
int currentInDegree = currentNode.parents().size();
int currentOutDegree = currentNode.children().size();
if (previousInDegree != currentInDegree
|| previousOutDegree != currentOutDegree) {
List<DirectedGraphNode> newSubList1 = new ArrayList<>();
List<DirectedGraphNode> newSubList2 = new ArrayList<>();
newSubList1.add(currentNode);
newSubList2.add(nodeList2.get(i));
list1.add(newSubList1);
list2.add(newSubList2);
previousInDegree = currentInDegree;
previousOutDegree = currentOutDegree;
} else {
list1.get(list1.size() - 1).add(currentNode);
list2.get(list2.size() - 1).add(nodeList2.get(i));
}
}
Map<DirectedGraphNode, DirectedGraphNode> certainMap = new HashMap<>();
for (int i = 0; i < list1.size(); ++i) {
List<DirectedGraphNode> currentSubList = list1.get(i);
if (currentSubList.size() == 1) {
certainMap.put(currentSubList.get(0), list2.get(i).get(0));
}
}
List<List<DirectedGraphNode>> groupList1 = new ArrayList<>();
List<List<DirectedGraphNode>> groupList2 = new ArrayList<>();
for (int i = 0; i < list1.size(); ++i) {
if (list1.get(i).size() > 1) {
groupList1.add(new ArrayList<>(list1.get(i)));
groupList2.add(new ArrayList<>(list2.get(i)));
}
}
if (groupList1.isEmpty()) {
return Utils.isIsomorphism(certainMap) ? certainMap : null;
}
Map<DirectedGraphNode, DirectedGraphNode> isomorphism =
findIsomorphismPermutation(groupList1,
groupList2,
new HashMap<>(certainMap));
return isomorphism;
}
private static Map<DirectedGraphNode, DirectedGraphNode>
findIsomorphismPermutation(List<List<DirectedGraphNode>> groupList1,
List<List<DirectedGraphNode>> groupList2,
Map<DirectedGraphNode,
DirectedGraphNode> certainMap) {
List<PermutationEnumerator> permutationEnumeratorList =
new ArrayList<>(groupList1.size());
for (List<DirectedGraphNode> group : groupList1) {
permutationEnumeratorList
.add(new PermutationEnumerator(group.size()));
}
do {
Map<DirectedGraphNode, DirectedGraphNode> candidate =
generateIsomorphismCandidate(groupList1,
groupList2,
permutationEnumeratorList);
candidate.putAll(certainMap);
if (Utils.isIsomorphism(candidate)) {
return candidate;
}
} while (incrementPermutationEnumeratorList(permutationEnumeratorList));
return null;
}
private static Map<DirectedGraphNode, DirectedGraphNode>
generateIsomorphismCandidate(
List<List<DirectedGraphNode>> groupList1,
List<List<DirectedGraphNode>> groupList2,
List<PermutationEnumerator> permutationEnumeratorList) {
for (int groupIndex = 0; groupIndex < groupList2.size(); ++groupIndex) {
permute(groupList2.get(groupIndex),
permutationEnumeratorList.get(groupIndex));
}
Map<DirectedGraphNode, DirectedGraphNode> isomorphismCandidate =
new HashMap<>();
for (int groupIndex = 0; groupIndex < groupList1.size(); ++groupIndex) {
for (int nodeIndex = 0;
nodeIndex < groupList1.get(groupIndex).size();
nodeIndex++) {
isomorphismCandidate
.put(groupList1.get(groupIndex).get(nodeIndex),
groupList2.get(groupIndex).get(nodeIndex));
}
}
return isomorphismCandidate;
}
private static void
permute(List<DirectedGraphNode> groupList,
PermutationEnumerator permutationEnumeratorList) {
int[] indices = permutationEnumeratorList.indices;
List<DirectedGraphNode> tmp = new ArrayList<>(groupList);
for (int i = 0; i < groupList.size(); ++i) {
groupList.set(indices[i], tmp.get(i));
}
}
private static boolean
incrementPermutationEnumeratorList(List<PermutationEnumerator> list) {
for (int i = 0; i < list.size(); ++i) {
if (list.get(i).next() == null) {
list.get(i).reset();
} else {
return true;
}
}
return false;
}
private static final class PermutationComparator
implements Comparator<DirectedGraphNode> {
;
@Override
public int compare(DirectedGraphNode o1, DirectedGraphNode o2) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
}
}
private static final class PermutationEnumerator {
private final int[] indices;
private boolean initial;
PermutationEnumerator(int length) {
this.indices = new int[length];
reset();
}
void reset() {
initial = true;
for (int i = 0; i < indices.length; ++i) {
indices[i] = i;
}
}
int[] next() {
if (initial) {
initial = false;
return indices;
}
int i = indices.length - 2;
while (i >= 0 && indices[i] > indices[i + 1]) {
--i;
}
if (i == -1) {
return null;
}
int j = i + 1;
int minValue = indices[j];
int minIndex = j;
while (j < indices.length) {
if (indices[i] < indices[j] && indices[j] < minValue) {
minValue = indices[j];
minIndex = j;
}
++j;
}
int tmp = indices[i];
indices[i] = indices[minIndex];
indices[minIndex] = tmp;
++i;
j = indices.length - 1;
while (i < j) {
tmp = indices[i];
indices[i] = indices[j];
indices[j] = tmp;
++i;
--j;
}
return indices;
}
}
}
Utils.java:
package net.coderodde.graph.isomorphism;
import java.util.Map;
import net.coderodde.graph.support.DirectedGraphNode;
/**
* This class provides some utility methods for working with graph isomorphisms.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Oct 11, 2015)
*/
public class Utils {
/**
* This method tests that the input mapping is a graph isomorphism.
*
* @param candidate the candidate isomorphism.
* @return {@code true} only if the input map is a graph isomorphism.
*/
public static boolean
isIsomorphism(Map<DirectedGraphNode, DirectedGraphNode> candidate) {
for (Map.Entry<DirectedGraphNode,
DirectedGraphNode> mapping : candidate.entrySet()) {
if (mapping.getKey().children().size() !=
mapping.getValue().children().size()) {
return false;
}
if (mapping.getKey().parents().size() !=
mapping.getValue().parents().size()) {
return false;
}
for (DirectedGraphNode child : mapping.getKey().children()) {
if (!candidate.get(child)
.hasParent(candidate.get(mapping.getKey()))) {
return false;
}
}
}
return true;
}
}
GraphTest.java:
package net.coderodde.graph;
import java.util.Iterator;
import net.coderodde.graph.support.DirectedGraphNode;
import org.junit.Test;
import static org.junit.Assert.*;
import org.junit.Before;
public class GraphTest {
private final Graph<DirectedGraphNode> graph = new Graph<>();
private final DirectedGraphNode a = new DirectedGraphNode("A");
private final DirectedGraphNode b = new DirectedGraphNode("B");
private final DirectedGraphNode c = new DirectedGraphNode("C");
private final DirectedGraphNode d = new DirectedGraphNode("D");
private final DirectedGraphNode e = new DirectedGraphNode("E");
@Before
public void before() {
graph.clear();
}
@Test
public void test() {
graph.addNode(a);
graph.addNode(e);
graph.addNode(d);
assertEquals(3, graph.size());
Iterator<DirectedGraphNode> iterator = graph.iterator();
assertEquals(a, iterator.next());
assertEquals(e, iterator.next());
assertEquals(d, iterator.next());
assertFalse(iterator.hasNext());
assertTrue(graph.getNodeByName("A").equals(a));
assertTrue(graph.getNodeByName("E").equals(e));
assertTrue(graph.getNodeByName("D").equals(d));
assertTrue(graph.getNodeByName("B") == null);
a.addChild(e);
e.addChild(d);
d.addChild(e);
assertEquals(3, graph.getNumberOfEdges());
Graph<DirectedGraphNode> anotherGraph = new Graph<>();
anotherGraph.addNode(a);
assertEquals(1, anotherGraph.size());
assertEquals(0, anotherGraph.getNumberOfEdges());
assertEquals(anotherGraph, a.getOwnerGraph());
assertEquals(graph, d.getOwnerGraph());
assertEquals(graph, e.getOwnerGraph());
assertEquals(2, graph.size());
assertEquals(2, graph.getNumberOfEdges());
graph.removeNode(e);
d.addChild(d);
assertEquals(1, graph.size());
assertEquals(1, graph.getNumberOfEdges());
assertEquals(d, graph.getNodeByName("D"));
}
}
TrivialDirectedGraphIsomorphismTesterTest.java:
package net.coderodde.graph.isomorphism;
import java.util.Map;
import net.coderodde.graph.Graph;
import net.coderodde.graph.support.DirectedGraphNode;
import org.junit.Test;
import static org.junit.Assert.*;
import org.junit.Before;
public class TrivialDirectedGraphIsomorphismTesterTest {
private final DirectedGraphNode a1 = new DirectedGraphNode("A1");
private final DirectedGraphNode b1 = new DirectedGraphNode("B1");
private final DirectedGraphNode c1 = new DirectedGraphNode("C1");
private final DirectedGraphNode d1 = new DirectedGraphNode("D1");
private final DirectedGraphNode e1 = new DirectedGraphNode("E1");
private final DirectedGraphNode f1 = new DirectedGraphNode("F1");
private final DirectedGraphNode g1 = new DirectedGraphNode("G1");
private final DirectedGraphNode h1 = new DirectedGraphNode("H1");
private final DirectedGraphNode a2 = new DirectedGraphNode("A2");
private final DirectedGraphNode b2 = new DirectedGraphNode("B2");
private final DirectedGraphNode c2 = new DirectedGraphNode("C2");
private final DirectedGraphNode d2 = new DirectedGraphNode("D2");
private final DirectedGraphNode e2 = new DirectedGraphNode("E2");
private final DirectedGraphNode f2 = new DirectedGraphNode("F2");
private final DirectedGraphNode g2 = new DirectedGraphNode("G2");
private final DirectedGraphNode h2 = new DirectedGraphNode("H2");
private final Graph<DirectedGraphNode> graph1 = new Graph<>();
private final Graph<DirectedGraphNode> graph2 = new Graph<>();
private final AbstractGraphIsomorphismChecker<DirectedGraphNode>
checker = new TrivialDirectedGraphIsomorphismChecker();
@Before
public void before() {
graph1.clear();
graph2.clear();
}
@Test
public void testGetIsomorphism1() {
graph1.addNode(a1);
graph1.addNode(b1);
graph1.addNode(c1);
graph2.addNode(a2);
graph2.addNode(b2);
a1.addChild(c1);
a2.addChild(c2);
assertNull(checker.getIsomorphism(graph1, graph2));
}
@Test
public void testGetIsomorphism2() {
graph1.addNode(a1);
graph1.addNode(b1);
graph1.addNode(c1);
graph2.addNode(a2);
graph2.addNode(b2);
graph2.addNode(e2);
a1.addChild(b1);
a2.addChild(e2);
Map<DirectedGraphNode, DirectedGraphNode> isomorphism =
checker.getIsomorphism(graph1, graph2);
assertNotNull(isomorphism);
assertTrue(Utils.isIsomorphism(isomorphism));
}
@Test
public void testGetIsomorphism3() {
graph1.addNode(a1);
graph1.addNode(b1);
graph1.addNode(c1);
graph2.addNode(a2);
graph2.addNode(b2);
graph2.addNode(e2);
a1.addChild(b1);
b1.addChild(c1);
a2.addChild(e2);
assertNull(checker.getIsomorphism(graph1, graph2));
}
@Test
public void testGetIsomorphism4() {
// c - e
// / / \
// a - b | g - h
// \ / /
// d - f
// Directed edges from nodes with smaller lexicographic name to larger.
graph1.addNode(a1);
graph1.addNode(b1);
graph1.addNode(c1);
graph1.addNode(d1);
graph1.addNode(e1);
graph1.addNode(f1);
graph1.addNode(g1);
graph1.addNode(h1);
a1.addChild(b1);
b1.addChild(c1);
b1.addChild(d1);
c1.addChild(e1);
d1.addChild(f1);
d1.addChild(e1);
e1.addChild(g1);
f1.addChild(g1);
g1.addChild(h1);
graph2.addNode(h2);
graph2.addNode(b2);
graph2.addNode(c2);
graph2.addNode(d2);
graph2.addNode(e2);
graph2.addNode(f2);
graph2.addNode(g2);
graph2.addNode(a2);
h2.addChild(b2);
b2.addChild(c2);
b2.addChild(d2);
c2.addChild(e2);
d2.addChild(f2);
d2.addChild(e2);
e2.addChild(g2);
f2.addChild(g2);
g2.addChild(a2);
Map<DirectedGraphNode, DirectedGraphNode> isomorphism =
checker.getIsomorphism(graph1, graph2);
assertNotNull(isomorphism);
assertTrue(Utils.isIsomorphism(isomorphism));
}
}