Considerando uma classe de nó bastante tradicional (abaixo), qual é a melhor maneira de implementar a igualdade em um determinado gráfico?
Se o nosso nó se parece com isso
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){ ... }
}
com várias especializações:
public class NodeTypeOne extends Node{
public int importantInteger = 42;
}
public class NodeTypeTwo extends Node{
public double importantValue = 34;
}
//... and so on
E considerando dois nós (assumidos como raízes), como eu determino se os dois gráficos correspondentes a essas raízes são logicamente iguais?
Gostaria de evitar a substituição de equals , se possível, mas reconheço que pode ser um mal necessário.
Atualmente, a única solução em que pensei é percorrer o gráfico e procurar manualmente seu equivalente e verificar seus parentes:
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)
}
isso é complicado porque:
- requer que o tipo manual alterne no tipo do nó para determinar a igualdade, embora isso possa ser atenuado se eu estiver disposto a simplesmente usar os iguais iguais e deixar que cada nó substitua seu método equals
- está longe de ter desempenho, sendo pelo menos quadrático ou mesmo cúbico se meu gráfico se aproximar do gráfico completo
Eu acredito que uma solução razoavelmente elegante e intuitiva existe usando uma lista de trabalho e um algoritmo de ponto fixo, eu não tenho certeza de como codificá-lo. Alternativamente, eu poderia usar um multi-mapa para construir uma matriz de adjacência e, em seguida, afirmar que cada linha tem exatamente uma linha correspondente de igual para igual na outra tabela, mas isso novamente parece muito pesado.