Algoritmo para verificar la transitividad de la relación?

Question

¿Necesito verificar si la relación es transitiva o no?

¿Podría sugerir algún algoritmo para verificar la transitividad de las relaciones?

Estoy almacenando la relación como una matriz booleana hay 1 si los elementos están relacionados de otra manera 0 como en los gráficos.

Gracias.

Answer 1

Algoritmo mucho más simple como mi versión Map / Set (eliminada), ahora con matriz booleana. ¿Quizás esto sea más fácil de entender, incluso si no conoce 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

A pesar de esto suena totalmente como tarea ...

Necesitaría almacenar sus relaciones para poder buscarlas por el antecedente muy rápidamente. Luego puede descubrir relaciones transitivas del tipo A- > B- > C, agregarlas al mismo almacenamiento y seguir buscando A- > B- > C- > D, etc. .

Answer 3

La clasificación topológica puede ser la dirección correcta. La relación es transitiva si no hay bucles en su representación gráfica dirigida. Si le importa la velocidad, los algoritmos de gráficos son probablemente el camino a seguir.