Algoritmo para verificar a transitividade da relação?

Question

Eu preciso verificar se relação é transitiva ou não?

Você poderia por favor sugerir algum algoritmo para verificar a transitividade das relações?

Eu estou armazenando relação como um boolean matriz não é 1 se os elementos estão relacionados outro sábio 0 como em gráficos.

Graças.

Answer 1

Muito mais simples algoritmo como minha versão Mapa / Set (excluído), agora com matriz de boolean. Talvez este seja mais fácil de entender, mesmo se você não sabe Java?

public class Trans
{

  final static int SIZE = 4;

  static boolean isTransitive(boolean[][] function)
  {
    for (int i = 0; i < SIZE; i++)
    {
      for (int j = 0; j < SIZE; j++)
      {
        if (function[i][j])
        {
          for (int k = 0; k < SIZE; k++)
          {
            if (function[j][k] && !function[i][k])
            {
              return false;
            }
          }
        }
      }
    }
    return true;
  }

  public static void main(String[] args)
  {
    boolean[][] function = new boolean[SIZE][SIZE];
    for (int i = 0; i < SIZE; i++)
    {
      function[i] = new boolean[SIZE];
    }
    function[0][1] = true;
    function[1][2] = true;
    function[0][2] = true;
    function[0][3] = true;
    function[1][3] = true;   
    System.out.println(isTransitive(function));
  }
}

Answer 2

Apesar de isso soa totalmente como lição de casa ...

Você precisa para armazenar suas relações de modo que você pode procurá-los pelo antecedente muito rapidamente. Depois, você pode descobrir as relações transitivos do tipo A-> B-> C, adicioná-los ao mesmo armazenamento, e continuar a olhar para cima A-> B-> C-> D, etc etc ...

Answer 3

ordenação topológica pode ser a direção certa. A relação é transitória, se não houver circuitos na sua representação grafo orientado. Se você se preocupa com velocidade, algoritmos de grafos são provavelmente o caminho a percorrer.