Как сформировать транзитивное замыкание множества кортежей?

Question

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

Пример:

• вход Set((1, 2), (2, 3), (3, 4), (5, 0))
• Выход Set((1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (5, 0))

Answer 1

//one transitive step
def addTransitive[A, B](s: Set[(A, B)]) = {
  s ++ (for ((x1, y1) <- s; (x2, y2) <- s if y1 == x2) yield (x1, y2))
}

//repeat until we don't get a bigger set
def transitiveClosure[A,B](s:Set[(A,B)]):Set[(A,B)] = {
  val t = addTransitive(s)
  if (t.size == s.size) s else transitiveClosure(t)
}

println(transitiveClosure(Set((1,2), (2,3), (3,4))))

Это не очень эффективная реализация, но она проста.

Answer 2

С помощью unfold,

def unfoldRight[A, B](seed: B)(f: B => Option[(A, B)]): List[A] = f(seed) match {
  case Some((a, b)) => a :: unfoldRight(b)(f)
  case None => Nil
}

def unfoldLeft[A, B](seed: B)(f: B => Option[(B, A)]) = {
  def loop(seed: B)(ls: List[A]): List[A] = f(seed) match {
    case Some((b, a)) => loop(b)(a :: ls)
    case None => ls
  }

  loop(seed)(Nil)
}

становится довольно просто:

def transitiveClosure(input: Set[(Int, Int)]) = {
    val map = input.toMap
    def closure(seed: Int) = unfoldLeft(map get seed) {
        case Some(`seed`) => None
        case Some(n)      => Some(seed -> n -> (map get n))
        case _            => None
    }
    map.keySet flatMap closure
}

Еще один способ написания closure это:

def closure(seed: Int) = unfoldRight(seed) {
    case n if map.get(n) != seed => map get n map (x => seed -> x -> x)
    case _ => None
}

Я сам не уверен, какой путь мне больше нравится. Мне нравится элегантность тестирования для Some(seed) чтобы избежать петель, но, к тому же, мне также нравится элегантность отображения результата map get n,

Ни одна версия не возвращается seed -> seed для циклов, так что вам придется добавить, если это необходимо. Вот:

    def closure(seed: Int) = unfoldRight(map get seed) {
        case Some(`seed`) => Some(seed -> seed -> None)
        case Some(n)      => Some(seed -> n -> (map get n))
        case _            => None
    }

Answer 3

Смоделируйте задачу как ориентированный граф следующим образом:

Представьте числа в кортежах как вершины графа. Тогда каждый кортеж (x, y) представляет направленное ребро от x до y. После этого используйте алгоритм Варшалла, чтобы найти транзитивное замыкание графа.

Для полученного графа каждое направленное ребро затем преобразуется в кортеж (x, y). Это транзитивное замыкание набора кортежей.

Answer 4

Предполагая, что у вас есть DAG (в ваших примерах данных нет циклов), вы можете использовать приведенный ниже код. Он ожидает DAG в виде карты от T до List[T], которую вы можете получить из своего ввода, используя

input.groupBy(_._1) mapValues ( _ map (_._2) )

Вот транзитивное закрытие:

def transitiveClosure[T]( dag: Map[ T, List[T] ] ) = {
  var tc = Map.empty[ T, List[T] ]
  def getItemTC( item:T ): List[T] = tc.get(item) match {
    case None =>
      val itemTC = dag(item) flatMap ( x => x::getItemTC(x) )
      tc += ( item -> itemTC )
      itemTC
    case Some(itemTC) => itemTC
  }
  dag.keys foreach getItemTC
  tc
}

Этот код определяет замыкание для каждого элемента только один раз. Тем не мение:

• Этот код может вызвать переполнение стека, если через DAG достаточно длинных путей (рекурсия не является хвостовой рекурсией).
• Для большого графика вам, вероятно, было бы лучше сделать tc изменчивой картой, а затем преобразовать ее в конце, если вы хотите неизменную карту.
• Если ваши элементы были действительно маленькими целыми числами, как в вашем примере, вы могли бы значительно улучшить производительность, используя массивы, а не карты, хотя это усложнило бы некоторые вещи.

Чтобы устранить проблему переполнения стека (для групп обеспечения доступности баз данных), вы можете выполнить топологическую сортировку, обратить ее вспять и обработать элементы по порядку. Но смотрите также эту страницу:

самый известный алгоритм транзитивного замыкания для графа