Determine equality of a DAG

Question

Given a fairly traditional node class (below), what's the best way to implement equality on a given graph?

If our node looks like this

public abstract class Node{
 private final Set<Node> predecessors = new HashSet<>();
 private final S<Node> successors = new HashSet<>(); 
 //we do have a visitor scheme
 public void accept(GraphVisitor visitor){ ... }
}

with several specializations:

public class NodeTypeOne extends Node{
 public int importantInteger = 42;
}
public class NodeTypeTwo extends Node{
 public double importantValue = 34;
}
//... and so on

And given two nodes (assumed to be roots), how do I determine if the two graphs corresponding to those roots are logically equal?

I'd like to avoid overriding equals if possible, but I recognize that it might be a necessary evil.

Currently, the only solution I've thought of is to traverse the graph and manually look-up your counterpart, and check its relatives:

public class EqualityVisitor implements GraphVisitor{
 private boolean result = true;
 private final Node otherRoot;
 public void visitEnter(Node node){
 Optional<Node> counterpartNode = findInGraph(otherRoot, node);
 result |= counterpartNode.isPresent();
 counterpartNode.ifPresent(counterpart -> {
 result |= setEquals(node.successors, counterpart.successors, this::customEquality);
 result |= setEquals(node.predecessors, counterpart.predecessors, this::customEquality);
 });
 }
 //annoyingly the customEquality method would have to do its own type-switch
 //(when the whole purpose of a visitor interface is to avoid such a type-switch)
}

this is cumbersome because:

• requires that manual type switch on the node's type to determine equality, though that can be mitigated if I'm willing to simply use the default equals and let each node override its equals method
• it is far from performant, being at least quadratic or even cubic if my graph approaches the complete graph

I believe a reasonably elegant and intuitive solution exists using a work-list and a fixed-point algorithm, I'm just not sure how to code it. Alternatively, I could use a multi-map to build an adjacency matrix and then assert that each row has exactly one corresponding set-equal row in the others table, but this again feels really heavy handed.

• Kevin Krumwiede: Some related keywords: automorphism, isomorphism.
• Groostav: So i believe that this is not quite the same as the question of isomorphism because more theoretical graph issues assume the nodes themselves are identified only by the number of edges they have. The algorithm I've outlined above doesn't have any of the characteristics of something taking exponential time complexity with either means its wrong, or I've got information more general isomorphic-graph-finding algorithms don't have.
• Frank: customEquality needs to take into accoutn successors of successors and so on. How do you handle that? How do you ensure termination? Your isomorphism problem may be hiding in there ...
• SpaceTrucker: Your API seems to be a bit strange. You want to model a graph, but there is no object of type graph. This exists only implicitly. So you are never sure if the graph is finite. It also seems to be difficult to add nodes to the graph because the nodes know about successors and predecessors at the same time. So when adding there is certainly a small amount of time where a node n1 specifies n2 as its successor but n1 is not yet a predecessor of n2.

Answer 1

If there is no explicit ordering of successors defined and the same value can occur at different nodes than every algorithm has an exponential worst case runtime.

Consider the following complete binary tree:

 1
 / \
1 2

So in order for this tree to determine equality with a copy of itself one has to check the values of the root node. Than one has to do the same pairwise check with the successors now being root nodes. Remember that iteration order of successors is not determined, so we may first end up comparing leafs with values 1 and 2 against each other.

So for a node that is m steps above a leaf the cost is O(2^m) in worst case. So for a complete binary tree of depth n we have runtime O(2^n). Such trees can be constructed by creating a complete binary tree where all nodes have equal value of 1 and the value of a single arbitrary leaf being changed to 2.

Answer 2

A directed graph can be expressed as a set of Node / Edge pairs (assuming nodes and edges have some kind of unique identity), to determine if two graphs are equivalent you can perform the symmetric difference on those two sets using HashSets. e.g. a.Except(b) and b.Except(a) if both sets are empty then the graphs are equivalent.

Your only challenge then is to implement a good hashing and equality comparer for node and edge pairs to optimise the hash lookup.