Determina a igualdade de um DAG

5

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.

    
por Groostav 16.02.2016 / 01:29
fonte

1 resposta

1

Se não houver ordenação explícita de sucessores definidos e o mesmo valor puder ocorrer em nós diferentes do que todos os algoritmos têm um tempo de execução exponencial do pior caso.

Considere a seguinte árvore binária completa:

  1
 / \
1   2

Portanto, para que essa árvore determine a igualdade com uma cópia de si mesma, é necessário verificar os valores do nó raiz. Do que se tem que fazer a mesma verificação emparelhada com os sucessores agora sendo nós raiz. Lembre-se de que a ordem de sucessores de iteração não é determinada, portanto, podemos primeiro comparar as folhas com os valores 1 e 2 entre si.

Portanto, para um nó que tenha m etapas acima de uma folha, o custo será O(2^m) no pior caso. Portanto, para uma árvore binária completa de profundidade n , temos tempo de execução O(2^n) . Tais árvores podem ser construídas criando uma árvore binária completa onde todos os nós têm igual valor de 1 e o valor de uma única folha arbitrária sendo alterada para 2 .

    
por 17.05.2017 / 14:07
fonte