Data una classe di nodo abbastanza tradizionale (sotto), qual è il modo migliore per implementare l'uguaglianza su un dato grafico?
Se il nostro nodo appare così
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){ ... }
}
con diverse specializzazioni:
public class NodeTypeOne extends Node{
public int importantInteger = 42;
}
public class NodeTypeTwo extends Node{
public double importantValue = 34;
}
//... and so on
E dati due nodi (presupposti come radici), come faccio a determinare se i due grafici corrispondenti a quelle radici sono logicamente uguali?
Vorrei evitare di sovrascrivere equals se possibile, ma riconosco che potrebbe essere un male necessario.
Attualmente, l'unica soluzione che ho pensato è di attraversare il grafico e cercare manualmente la tua controparte e controllare i suoi parenti:
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)
}
questo è macchinoso perché:
- richiede lo switch di tipo manuale sul tipo del nodo per determinare l'uguaglianza, sebbene possa essere mitigato se sono disposto a utilizzare semplicemente l'equals di default e lasciare che ogni nodo esegua l'override del suo metodo di uguaglianza
- è lontano dal performante, essendo almeno quadratico o anche cubico se il mio grafico si avvicina al grafico completo
Credo che esista una soluzione ragionevolmente elegante e intuitiva usando una lista di lavoro e un algoritmo a punto fisso, non sono sicuro di come codificarlo. In alternativa, potrei usare una multi-mappa per costruire una matrice di adiacenza e poi asserire che ogni riga ha esattamente una riga corrispondente uguale all'altra nella tabella degli altri, ma questa volta sembra davvero pesante.