Directed graph isomorphism in Java

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 the actual graph node implementation type.
*/
public abstract class AbstractGraphNode> {

private final String name;
private Graph 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 ownerGraph) {
if (this.getOwnerGraph() != null) {
clear();
this.getOwnerGraph().removeNode(this);
}

this.ownerGraph = ownerGraph;
}

public Graph getOwnerGraph() {
return ownerGraph;

Java based suggestions

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

Comparator 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> list1 = new ArrayList<>();
List> list2 = new ArrayList<>();
List sublist1 = new ArrayList<>();
List 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 ();
        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 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 `Permutation

StackExchange Code Review Q#107223, answer score: 2