Algoritmo per il controllo della transitività della relazione?

Question

Devo verificare se la relazione è transitiva o no?

Potresti suggerire qualche algoritmo per verificare la transitività delle relazioni?

Sto memorizzando la relazione come matrice booleana c'è 1 se gli elementi sono correlati in altri saggi 0 come nei grafici.

Grazie.

Answer 1

Algoritmo molto più semplice della versione di Map / Set (eliminata), ora con matrice booleana. Forse è più facile da capire, anche se non conosci 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

Nonostante ciò suona totalmente come i compiti ...

Dovresti archiviare le tue relazioni in modo da poterle cercare rapidamente dagli antecedenti. Quindi puoi scoprire relazioni transitive di tipo A- > B- > C, aggiungerle allo stesso archivio e continuare a cercare A- > B- > C- > D, ecc ecc. .

Answer 3

L'ordinamento topologico può essere la direzione giusta. La relazione è transitiva se non ci sono anelli nella sua rappresentazione grafica diretta. Se ti interessa la velocità, gli algoritmi grafici sono probabilmente la strada da percorrere.