Пример цикла в ориентированном графе

Мне нужен алгоритм, который дает один экземпляр цикла в ориентированном графе, если таковой имеется. Может ли кто-нибудь показать мне направление? В псевдокоде или, что предпочтительнее, в Ruby?

Ранее я задавал похожий вопрос и, следуя приведенным там предложениям, реализовал алгоритм Кана в Ruby, который определяет, есть ли в графе цикл, но я хочу не только того, есть ли у него цикл, но и один возможный экземпляр такого цикла.

example_graph = [[1, 2], [2, 3], [3, 4], [3, 5], [3, 6], [6, 2]]

Алгоритм Кана

def cyclic? graph
  ## The set of edges that have not been examined
  graph = graph.dup
  n, m = graph.transpose
  ## The set of nodes that are the supremum in the graph
  sup = (n - m).uniq
  while sup_old = sup.pop do
    sup_old = graph.select{|n, _| n == sup_old}
    graph -= sup_old
    sup_old.each {|_, ssup| sup.push(ssup) unless graph.any?{|_, n| n == ssup}}
  end
  !graph.empty?
end

Приведенный выше алгоритм сообщает, есть ли в графе цикл:

cyclic?(example_graph) #=> true

но я хочу не только это, но и пример такого цикла:

#=> [[2, 3], [3, 6], [6, 2]]

Если бы я вывел переменную graph в приведенном выше коде в конце проверки, это дало бы:

#=> [[2, 3], [3, 4], [3, 5], [3, 6], [6, 2]]

который включает в себя нужный мне цикл, но также включает в себя дополнительные ребра, которые не имеют отношения к циклу.


ruby directed-acyclic-graphs algorithm
person sawa    schedule 15.03.2012    source источник

Ответы (2)


arrow_upward
5
arrow_downward

Я задал тот же вопрос на сайте обмена математическими стеками и получил ответ. Оказалось, что алгоритм Тарьяна хорош для решения этой задачи. Я реализовал это в Ruby следующим образом:

module DirectedGraph; module_function
    ## Tarjan's algorithm
    def strongly_connected_components graph
        @index, @stack, @indice, @lowlink, @scc = 0, [], {}, {}, []
        @graph = graph
        @graph.flatten(1).uniq.each{|v| strong_connect(v) unless @indice[v]}
        @scc
    end
    def strong_connect v
        @indice[v] = @index
        @lowlink[v] = @index
        @index += 1
        @stack.push(v)
        @graph.each do |vv, w|
            next unless vv == v
            if !@indice[w]
                strong_connect(w)
                @lowlink[v] = [@lowlink[v], @lowlink[w]].min
            elsif @stack.include?(w)
                @lowlink[v] = [@lowlink[v], @indice[w]].min
            end
        end
        if @lowlink[v] == @indice[v]
            i = @stack.index(v)
            @scc.push(@stack[i..-1])
            @stack = @stack[0...i]
        end
    end
end

Поэтому, если я применю его к приведенному выше примеру, я получу список сильно связанных компонентов графа:

example_graph = [[1, 2], [2, 3], [3, 4], [3, 5], [3, 6], [6, 2]]
DirectedGraph.strongly_connected_components(example_graph)
#=> [[4], [5], [2, 3, 6], [1]]

Выбирая те компоненты, которые длиннее единицы, я получаю циклы:

DirectedGraph.strongly_connected_components(example_graph)
.select{|a| a.length > 1}
#=> [[2, 3, 6]]

И далее, если я выбираю из графа ребра, обе вершины которых входят в компоненты, я получаю решающие ребра, составляющие циклы:

DirectedGraph.strongly_connected_components(example_graph)
.select{|a| a.length > 1}
.map{|a| example_graph.select{|v, w| a.include?(v) and a.include?(w)}}
#=> [[[2, 3], [3, 6], [6, 2]]]
person sawa    schedule 16.03.2012

arrow_upward
2
arrow_downward

Поиск в глубину, где вы отслеживаете посещенные вершины, а родитель дает вам цикл. Если вы видите ребро к ранее посещенной вершине, значит, вы обнаружили цикл между вашим родителем, вами и этой вершиной. Небольшая проблема, с которой вы можете столкнуться, заключается в том, что если это цикл длины > 3, вы сможете указать только три задействованные вершины, и вам придется провести некоторое исследование, чтобы найти остальные вершины в цикле.

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

person Justin    schedule 15.03.2012