Directed graph isomorphism in Java

Question

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:

1. 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.
2. 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));
    }
}

Answer 1

Java based suggestions

• in getIsomorphism, the comparator you define can be a static final field. It can additionally be simplified to just:

  Comparator<DirectedGraphNode> comparator = Comparator.comparing(n -> n.children().size())
        .thenComparing(n -> n.parents().size());
  

  If you were exposing inDegree and outDegree you could put DirectedGraphNode::inDegree and DirectedGraphNode::outDegree as the key-extractor functions instead.

• Just below that you're iterating over an ordered collection of nodes, again comparing their inDegree and outDegree. If java were a more functional language, this could be better expressed like the following:

  all (== 0) $ map comparator::compare $ zip nodeList1 nodeList2
  

  What happens here is essentially that the ordered items are associated together into a tuple, the comparator compares them and the == 0 checks that all elements are equal according to the comparator.
  I'm not quite sure why you're not reusing the comparator here. That would simplify the code to:

  for (int i = 0; i < nodeList1.size(); ++i) {
      if (0 != comparator.compare(nodeList1.get(i), nodeList2.get(i))) {
          return null;
      }
  }
  

• graphToList could be written a bit more succinctly as:

  return StreamSupport.stream(graph.spliterator(), false).collect(Collectors.toList());
  

• in bruteForceIsomorphism you could look whether the filling of list1 and list2 could be simplified by constructing the sublist explicitly and keeping a reference to it. Since I'm just writing this down without an IDE, I'm having trouble to reorganize this into a stream operation, but as far as I can tell, you're grouping these nodes by their degrees.
  As starting point, check out:

  List<List<DirectedGraphNode>> list1 = new ArrayList<>();
  List<List<DirectedGraphNode>> list2 = new ArrayList<>();
  List<DirectedGraphNode> sublist1 = new ArrayList<>();
  List<DirectedGraphNode> sublist2 = new ArrayList<>();
  
  sublist1.add(nodeList1.get(0));
  sublist2.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) {
          list1.add(sublist1);
          list2.add(sublist2);
          sublist1 = new ArrayList<>();
          sublist2 = new ArrayList<>();
  
          previousInDegree = currentInDegree;
          previousOutdegree = currentOutDegree;
      } else {
          sublist1.add(currentNode);
          sublist2.add(nodeList2.get(i);
      }
  }
  

• You're not using list1 and list2 after the initialization of the certainMap. I'm not quite sure why you're creating a defensive deep copy before passing them to findIsomorphismPermutation

• You can simplify the creation of permutationEnumeratorList in findIsomorphismPermutation by using streams like so:

  List<PermutationEnumerator> permutationEnumerators = groupList1.stream()
    .map(group -> new PermutationEnumerator(group.size())
    .collect(Collectors.toList());
  

Naming & Documentation

The documentation for all the code here is rather very sparse. Especically the implementation of the actual isomorphism finding is difficult to understand. What's also hard to understand is how the isIsomorphism check works exactly. The problem there is that the code is so different and much more verbose compared to the mathematical formulation.

Here's some names that really need to be better:

• addEdges is easier to understand as modifyEdgeCounter
• nodeList1 and nodeList2 are mediocre. Especially considering that they're actually just the nodes extracted from a graph, you might want to name them somewhat cleaner. graph1 and graph2 are also bad names. Even left and right would be somewhat better. Or source and target...
• In general you seem to like naming things by what they are. The List suffix to your variable names can nearly always be replaced by a pluralization. Something like sourceNodes is much more communicative than nodeList1. (more examples: groupList1, permutationEnumeratorList)
• comparator in getIsomorphism could be nodeDegreeComparator or something like that. It's much less general than the name implies...
• In bruteForceIsomorphism the names make it really hard to follow. list1 and list2 are the least semantically useful names possible for two lists... I have no clue what the lists are used for, actually. I just notice that these lists have to do with the degrees of the nodes you examine. Since they are sorted, I assume it has to do with which nodes could be mapped to one another...
• certainMap is a good start, but it might be better off as requiredMappings or something like that? That'd also make clearer why that map is passed to findIsomorphismPermutation.
• Utils is a name that's... not really saying anything at all. I'm also not sure, why the isIsomorphism check is not implemented in the AbstractGraphIsomorphismChecker... It would make a lot of sense there, IMO.

Algorithmic Curiosities

permute overwrites the current groupList state. That makes subsequent calls to permute use an already permuted state. I have not check whether all permutations from PermutationEnumerator are actually covered, even though they work off the previous permutation. There could be a way that they still cover all possible permutations, just in a different order. My gut feeling says they don't...

Instead of permuting the groupList state, you could directly access the permutation when building the isomorphismCandidate by permuting the access to groupList2 in the call to put, like so:

// generateIsomorphismCandidate
// note that I don't permute the groupList2 entries here
Map<DirectedGraphNode, DirectedGraphNode> isomorphismCandidate = new HashMap<>();

for (int groupIndex = 0; groupIndex < groupList1.size(); ++groupIndex) {
    int[] permutation = permutationEnumeratorList.get(groupIndex).indices;
    for (int nodeIndex = 0; nodeIndex < groupList1.get(groupIndex).size(); nodeIndex++) {
        isomorphismCandidate.put(
          groupList1.get(groupIndex).get(nodeIndex),
          groupList2.get(groupIndex).get(permutation[nodeIndex]));
    }
}

Design Considerations

I'm not fully convinced that the representation of graphs you chose makes that much sense. Following things feel a little weird about it:

• Nodes need to be told the Graph they belong to. (Why does a node know that?)
• The mechanism to create edges is very non-obvious and for some reason not actually part of the Graph interface. It feels weird to have the node know so much about the rest of the graph.

• I'm almost convinced that using an adjacency matrix for representation would make the permutation checks much easier. There should be similarly compelling ways to determine the degrees of a node, and the changes necessary to support weighted and/or undirected graphs would be minimal.

  Instead of creating permutations between nodes, an isomorphism would be described by a symmetric (for undirected graphs) permutation matrix.

• It's very unclear to me why PermutationEnumerator is not in it's own class. That thing is useful beyond just the TrivialGraphIsomorphismChecker.

• The way that cycling through all permutations of permutations is done is ... a hack. A really clever bit of code that made me smile, but it's really something that should be done in a better way. You could consider encapsulating the permutationEnumeratorList into it's own class that handles iteration of the permutations.