Получите область, затронутую, добавляя край в направленном графике acycli c - PullRequest
Новая
       74

Получите область, затронутую, добавляя край в направленном графике acycli c

0 голосов
/ 24 марта 2020

Я использую направленный граф ацикли c (DAG), предоставленный JGraphT. Этот DAG динамически поддерживает топологическое упорядочение вершин. После добавления ребра в группу доступности баз данных мне нужно эффективно найти первый индекс, который изменился в топологическом порядке. Согласно документам существует класс Region , который используется DAG для внутреннего отслеживания затронутой области, но не публикуется c.

Есть ли способ получить первый индекс, который изменился из-за addEdge для DAG в JGraphT?

Я считаю, что addEdge(from, to) влияет на топологический порядок, только если from -> to является обратным край. В этом случае to < from и первый индекс, который изменился, будет getTopologicalIndex​(to). Но я не уверен, всегда ли это так?

Исходя из вышеизложенной идеи, я мог бы реализовать ее, как показано в приведенном ниже фрагменте кода (который использует JGraphT в Scala). Единственная проблема заключается в том, что topoOrderMap является частным членом DirectedAcyclicGraph, поэтому это не работает. 

def addEdgeAndReturnIdxOfFirstChange (g: DirectedAcyclicGraph[String, DefaultEdge], 
                                      from: String, 
                                      to: String): Option[Int] = {
  // -1 because getTopologicalIndex starts from 1 instead of 0
  val fromIdx = g.topoOrderMap.getTopologicalIndex (from) - 1
  val toIdx = g.topoOrderMap.getTopologicalIndex (to) - 1

  g.addEdge(from, to)

  if (fromIdx > toIdx) {
    // back edge will at least swap `from` and `to`
    Some(toIdx)
  }
  else {
    None // no change
  }
}

Обратите внимание, что эта информация присутствует внутри, поэтому поиск уязвимой области должен быть в O (1) , поскольку я не могу позволить сравнить новый топологический порядок со старым, чтобы найти область поражения.

...