Алгоритм проверки транзитивности отношения?

Question

Мне нужно проверить, является ли отношение транзитивным или нет?

Не могли бы вы предложить какой-нибудь алгоритм для проверки транзитивности отношений?

Я сохраняю отношение в виде логической матрицы , если * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *1001* * * * *

Спасибо.

Answer 1

Топологическая сортировка может иметь правильное направление. Отношение является транзитивным, если в его ориентированном графе нет циклов. Если вам небезразлична скорость, возможно, вам подойдут графовые алгоритмы.

Answer 2

Гораздо более простой алгоритм, чем моя версия Map / Set (удалена), теперь с булевой матрицей. Может быть, это легче понять, даже если вы не знаете 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 3

Несмотря на то, что это звучит как домашнее задание ...

Вам нужно будет хранить ваши отношения, чтобы вы могли быстро найти их у антецедента. Затем вы можете обнаружить переходные отношения типа A-> B-> C, добавить их в то же хранилище и продолжить искать A-> B-> C-> D и т. Д. И т. Д.