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

Question

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

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

Я храню отношение как булева матрица есть 1 если элементы связаны другим образом 0 как на графиках.

Спасибо.

Answer 1

Гораздо более простой алгоритм, чем моя версия 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 2

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

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

Answer 3

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