有向无环图中更快的周期检测？

我在Ruby 1.9.3中有一个构建RubyTree的程序 . 我的数据最好被描述为Directed Acyclic Graph（DAG）;请注意，它是 not 一个polytree . 好吧，至少数据应该是DAG，尽管用户尽最大努力用糟糕的数据来阻止我的程序 .

我通过解析XML文档动态构建DAG . XML文档未明确指定树结构，但确实提供了整数ID的交叉引用，这些整数ID用于在文档中的元素之间 Build 链接 .

我需要确保RubyTree不包含任何循环 . 源数据可能（错误地）有一个循环，如果有，我的程序需要知道它，而不是进入无限循环或崩溃 . 为了实现这一目标，我将Ruby标准库的TSort模块混合到RubyTree的 Tree::TreeNode 类中 . 这使用Tarjan的算法在每次添加节点时对图形执行拓扑排序 . 在拓扑排序期间，如果检测到循环，则会引发异常 - 正是我想要的 .

例如：

module Tree
  class TreeNode
    include TSort

    def tsort_each_node(&block)
      self.each(&block)
    end

    def tsort_each_child(node, &block)
      node.get_children().each { |child| yield child }
    end

    def add(child, at_index = -1)
      #The standard RubyTree implementation of add goes here
      begin
        self.tsort()
      rescue TSort::Cyclic => exce
        self.remove!(child)
        raise exce
      end
      return child
    end
  end
end

我也必须修改其他一些方法 . 基本上任何需要遍历树或子代的东西都需要实现TSort，或者摆脱它对遍历的依赖（例如，我简化了 Tree::TreeNode#to_s() 以返回 Tree::TreeNode#name . ）

现在，我的程序在功能上是正确的 . 我已经完成了重要的测试，结果工作正常：我所要做的就是在我的代码中的正确位置解救 TSort::Cyclic ，如果我尝试添加一个导致循环的节点，那么节点就会被移除，我可以在报告中记录问题以便稍后处理（通过修复源数据） .

问题是，在大小为75000左右的RubyTree上，边数非常接近等于顶点数减1， iteratively 运行Tarjan 's algorithm produces an algorithmic complexity that looks pretty quadratic. Tarjan' s本身是 O(|V| + |E|) ，在我的情况下是 O(2*|V|) ，但每个时间我调用 add() ， |V| 增加1，因为我按节点逐个构建图形 . 我最后可以't simply call Tarjan'，因为在read-compare-add循环期间我可能需要遍历图形或部分图形，并且任何遍历尝试可能会挂起程序或者如果实际存在循环则使其崩溃 . （不言而喻，我的代码是单线程的;如果它没有't, we' d有一个很大的问题 . 就目前而言，我依赖的事实是，如果有一个循环， add() 永远不会返回而不会引发异常，即使有 is 一个循环，一个节点被移除，以便在 add() 返回之前清除循环 . ）

But it's too slow! 从 ruby-perf 的结果判断，'s taking more than half an hour just for this one loop, and my program consists of several other steps that take their own fair share of time. But as it stands, just performing Tarjan'正在吃掉大部分表演 . 我尝试在RubyTree each 实现中从数组切换到链表，但它只通过删除 Array#concat 次调用来减少运行时间约1％ .

我发现了Tarjan发表的一篇很棒的论文，他发明了Ruby的 TSort 所依赖的强连通组件算法，而增量周期检测似乎是一个活跃的研究领域 . 然而，论文中的对话水平远远高于我的头脑，而且我发现了Ruby代码 . 不仅如此，通过阅读论文的备注部分，似乎他们的尽力而为算法具有相当令人担忧的最坏情况运行时间，因此它甚至可能不比我当前的方法更快，这取决于我的具体情况数据 .

我在这里错过了一些愚蠢的东西，或者我最好的选择是分析Tarjan的论文，并尝试提出其中一种算法的Ruby实现？请注意，我并不特别关心算法的拓扑排序方面;这是我真正想要的副作用 . 如果树没有进行拓扑排序，但仍然保证没有循环，我会非常高兴 .

另外值得注意的是，我的源数据中的循环有点罕见 . 也就是说，循环可能由于数据输入过程中的手动错误而发生，但它们永远不会故意发生，并且应该始终报告给程序，以便它可以告诉我，所以我可以通过billyclub击败有人进入错误的数据 . 另外，程序 absolutely must 即使检测到一个特别恶劣的循环也继续保持正常运行，所以我可以't just stick my head in the sand and hope there won' t是任何循环 .

实际问题是什么？

根据一些人的要求，这是一个演示，您可以运行以查看工作中的问题 .

安装稳定版本的RubyTree（我使用MRI 1.9.3） . 然后比较这两个程序的输出：

图表1：打印“第三次”后，主线程上100％CPU使用率永久挂起

require 'tree'

a = Tree::TreeNode.new('a', nil)
b = Tree::TreeNode.new('b', nil)
c = Tree::TreeNode.new('c', nil)
a.add(b)
a.add(c)
puts "First time"
b.add(c)
puts "Second time"
b.add(a)
puts "Third time"
c.add(b)
puts "Fourth time"
c.add(a)
puts "Fifth time"
puts "Done"

图表2：一直走完并打印“完成”，结果没有循环

请注意，我通常会在 rescue 块中执行操作以记录发生的周期，并对创建这些周期的人类犯罪者大声抱怨 .

require 'tree'
require 'tsort'

module Tree
  class TreeNode
    include TSort

    def tsort_each_node(&block)
      self.each(&block)
    end

    def tsort_each_child(node, &block)
      node.get_children().each { |child| yield child}
    end

    def to_s
      name
    end

    def get_children()
      return @children
    end

    def add(child, at_index = -1)
      unless child
        raise ArgumentError, "Attempting to add a nil node"  # Only handles the immediate child scenario
      end
      if self.equal?(child)
        raise TSort::Cyclic, "Cycle detected: [#{child.name}, #{child.name}]"
      end 

      # Lazy man's unique test, won't test if children of child are unique in this tree too.
      if @children_hash.include?(child.name)
        raise "Child #{child.name} already added!"
      end

      if insertion_range.include?(at_index)
        @children.insert(at_index, child)
      else
        raise "Attempting to insert a child at a non-existent location (#{at_index}) when only positions from #{insertion_range.min} to #{insertion_range.max} exist."
      end

      @children_hash[child.name] = child
      child.parent = self

      #CYCLE DETECTION - raises TSort::Cyclic if this caused a cycle
      begin
        self.tsort()
      rescue TSort::Cyclic => exce
        self.remove!(child)
        raise exce
      end
      return child
    end
  end
end

a = Tree::TreeNode.new('a', nil)
b = Tree::TreeNode.new('b', nil)
c = Tree::TreeNode.new('c', nil)
a.add(b)
a.add(c)
puts "First time"
b.add(c)
puts "Second time"
begin
  b.add(a)
rescue
end
puts "Third time"
begin
  c.add(b)
rescue
end
puts "Fourth time"
begin
  c.add(a)
rescue
end
puts "Fifth time"
puts "Done"

目标，为我，是开发功能上与图表2相同的代码，但是可以更好地扩展到更大数量的顶点（我预计不会有超过10 ^ 6个顶点，在这种情况下，我可以使用它需要几分钟（ "go get a cup of coffee"）在现代桌面工作站上，但不是几小时或更长时间 . ）