Удаление циклических зависимостей на ориентированном графе с фиксированными ребрами - PullRequest
Новая
       29

Удаление циклических зависимостей на ориентированном графе с фиксированными ребрами

4 голосов
/ 17 июня 2009

У меня есть ориентированный циклический граф. Некоторые края ИСПРАВЛЕНЫ и не могут быть удалены. Другие ребра могут быть удалены, чтобы разорвать цикл.

Как лучше всего удалить циклы на этом графике? Обход должен быть как можно больше DFS и начинаться с данного узла.

Ответы [ 3 ]

3 голосов
/ 17 июня 2009

Что вы можете сделать, это использовать алгоритм Дейкстры: начните с графика, содержащего только ФИКСИРОВАННЫЕ ребра. Затем примените адаптацию алгоритма, начиная с графика, который у вас уже есть:

  1. Начните с начального узла и всех ИСПРАВЛЕННЫХ ребер в компоненте начального узла. Предположим, что это дерево.
  2. Добавьте ближайший к дереву узел.
  3. Также добавьте все фиксированные ребра в компоненте узла, который вы только что добавили.
  4. Если все узлы в дереве, конец. В противном случае перейдите к шагу 4.

Это, конечно, предполагает, что граф, состоящий только из фиксированных ребер, не содержит циклов. Если это так, решения не существует (то есть подграфа без ребер, но содержащего все ИСПРАВЛЕННЫЕ ребра).

Для ориентированных графов это немного сложнее. В этом случае любой компонент графа ФИКСИРОВАННЫХ ребер должен быть деревом. В алгоритме, подобном Dijkstra, кандидатами для добавления в дерево должны быть только корни этих узлов.

0 голосов
/ 24 июня 2009

Я использовал следующий алгоритм для решения своей проблемы:

Начните с графика всех фиксированных ребер, отмеченных как подтверждено

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

После описанного выше шага я использую алгоритм Тарьяна для нахождения сильно связанных компонентов, оставшихся на графике (это можно сделать за время O (V + E)). Количество сильно связанных компонентов в моих случаях будет очень небольшим, поэтому я просто просматриваю каждый сильно связанный компонент и удаляю по одному съемному краю каждый. Затем я делаю этот шаг снова, пока на графике не останется больше циклов.

Это работает нормально и достаточно быстро.

0 голосов
/ 19 июня 2009

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

Если график не должен оставаться связанным, просто обойдите все ребра и удалите все нефиксированные. Это удаляет все циклы, которые вы можете удалить, не удаляя ИСПРАВЛЕННЫЕ края.

Если вы хотите, чтобы простой жадный алгоритм удалял ребра, которые являются чисто DFS, вы можете использовать что-то вроде этого, ЕСЛИ граф остается подключенным также при удалении некоторых нефиксированных ребер: 

proc recurse(vertex n, vertex_set ns)
  if (n appers_in ns) // it is a cycle
    return BREAK_CYCLE
  else for (e in list_outgoing_edges_from(n))
    np = e.destination
    result = recurse(np, add_to_set(ns, np))
    if (result == BREAK_CYCLE)
      if (e.FIXED)
        return BREAK_CYCLE
      else
        [remove e from the graph]
        return RETRY
      else if (result == RETRY)
        return recurse(n, ns)
    return FINISHED

if (recurse (your_initial_node, empty_vertex_set()))
  [graph contains a cycle through only FIXED edges]
else
  [the reachable component from initial_node has no longer cycles]
...