给在一个有向图一个周期的一个例子 [英] Giving an example of a cycle in a directed graph
问题描述
欲一种算法,给出了一个循环的一个实例在一个有向图,如果有的话。谁能给我一个方向?在伪code或preferably,在Ruby中?
I want an algorithm that gives one instance of a cycle in a directed graph if there is any. Can anyone show me a direction? In pseudo-code, or preferably, in Ruby?
我previously问过类似的问题,并按照建议还有,我实现了卡恩的算法,在Ruby中,如果检测的曲线图具有一个周期,但我想不仅它是否有一个周期,而且这样的循环中的一个可能的实例。
I previously asked a similar question, and following the suggestions there, I implemented Kahn's algorithm in Ruby that detects if a graph has a cycle, but I want not only whether it has a cycle, but also one possible instance of such cycle.
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
以上算法讲述了一个图是否有一个循环:
The above algorithm tells whether a graph has a cycle:
cyclic?(example_graph) #=> true
但我想不仅如此,但像这样一个循环的例子:
but I want not only that but an example of a cycle like this:
#=> [[2, 3], [3, 6], [6, 2]]
如果我要输出在上述code在考试结束的变量图
,它会给:
If I were to output the variable graph
in the above code at the end of examination, it will give:
#=> [[2, 3], [3, 4], [3, 5], [3, 6], [6, 2]]
,它包括我想要的周期,但它也包括额外的边缘是无关的周期
which includes the cycle I want, but it also includes extra edges that are irrelevant to the cycle.
推荐答案
我问同样的问题在数学stackexchange网站,并得到一个答案。原来的Tarjan的算法是很好的解决这个问题。我实现了它在Ruby中,如下所示:
I asked the same question in the math stackexchange site, and got an answer. It turned out that Tarjan's algorithm is good for solving this problem. I implemented it in Ruby as follows:
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
所以,如果我将其应用到上面的例子,我得到的曲线图中的强连通分量的列表:
So if I apply it to the example above, I get a list of strongly connected components of the graph:
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]]
通过选择这些组件是超过一长,我得到的循环:
By selecting those components that are longer than one, I get the cycles:
DirectedGraph.strongly_connected_components(example_graph)
.select{|a| a.length > 1}
#=> [[2, 3, 6]]
和进一步如果我从图中选择的边的两个顶点都包括在组分,我得到构成该循环的关键边缘:
And further if I select from the graph the edges whose both vertices are included in the components, I get the crucial edges that constitute the cycles:
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]]]
这篇关于给在一个有向图一个周期的一个例子的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!