ruby - 有向无环图中的循环检测更快？

Question

我有一个Ruby1.9.3中的程序，它构造了一个RubyTree。我的数据最好被描述为一个Directed Acyclic Graph（dag）；请注意，它不是一个polytree。好吧，至少数据应该是DAG，尽管用户尽最大努力用坏数据来屏蔽我的程序。
我通过解析xml文档动态构建dag。XML文档没有显式地指定树结构，但提供了整数ID的交叉引用，这些ID在文档中的元素之间建立链接。
我需要确保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左右的红宝石树上，边的数目非常接近等于顶点的数目减去1，迭代运行tarjan的算法会产生一个看起来相当二次的算法复杂性。Tarjan的本身是 O(|V| + |E|)，在我的例子中是 O(2*|V|)，但是每次我调用 add()， |V|都会增加1，因为我一个节点一个节点地构建图形。我不能简单地在结尾调用tarjan's，因为在read-compare-add循环期间，我可能需要遍历该图或其中的一部分，并且任何遍历尝试都可能挂起程序，或者在实际上存在循环的情况下使其崩溃。（不用说，我的代码是单线程的；如果不是，我们会遇到一个巨大的问题。从目前的情况来看，我依赖于这样一个事实：如果存在一个循环，则 add()永远不会返回，而不会引发异常；即使存在一个循环，节点也会被移除，以便在 add()返回之前清除该循环。）
但是太慢了！仅仅这一个循环就要花上半个多小时，我的程序还包括其他几个步骤，它们占用了自己相当多的时间。但就目前的情况来看，从 ruby-perf的结果来看，仅仅表演Tarjan的节目就已经占据了大部分的演出份额。在rubytree each实现中，我尝试从数组切换到链表，但通过移除 Array#concat调用的负载，它只减少了大约1%的运行时间。
我发现了Tarjan写的一篇很棒的论文，他发明了Ruby所依赖的强连接组件算法，而且增量循环检测似乎是一个活跃的研究领域。然而，论文中的对话水平明显超出了我的想象，我很确定我缺乏将论文发现转化为ruby代码的数学背景。不仅如此，通过阅读论文的备注部分，他们的尽力而为算法似乎有自己相当令人担忧的最坏情况运行时，因此它甚至可能不会比我当前的方法快，这取决于我的数据的具体情况。
我是不是遗漏了一些愚蠢的东西，还是我最好的办法是花点脑力去分析Tarjan的论文，并尝试用Ruby实现其中一个算法？注意，我并不特别关心算法的拓扑排序方面；这是我真正想要的东西的副作用。如果这棵树不是按拓扑顺序排列的，但仍然保证没有周期，我会非常高兴的。
同样值得注意的是，周期在我的源数据中有些罕见。也就是说，由于数据输入过程中的手动错误，周期可能会发生，但它们绝不会故意发生，而且应该始终报告给程序，以便程序能够告诉我，这样我就可以用billyclub打某人的头，因为他输入了错误的数据。此外，即使程序检测到一个特别糟糕的循环，它也必须继续运行，所以我不能只是把头伸进沙子里，希望不会有任何循环。
实际的问题是什么？
根据一些人的要求，这里有一个演示，您可以运行它来查看工作中的问题。
安装稳定版本的rubytree（我使用mri 1.9.3）。然后比较这两个程序的输出：
图表1：打印“第三次”后，主线程上的CPU使用率为100%，永远挂起

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：一路打印“完成”，结果没有循环
请注意，我通常会在 TSort块中做一些事情来记录发生的周期，并大声抱怨创建这些周期的人类罪犯。

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个顶点，在这种情况下，我可以在一个现代化的桌面工作站上花上几分钟（去喝杯咖啡），而不是几个小时或更长时间。）

Answer 1

ruby的Plexusgem似乎解决了我最糟糕的问题。我以前试过gratr，但它不会加载，因为它与ruby 1.9.3不兼容，但是plexus是gratr的一个分支，可以与1.9.3兼容。
我的问题是我使用的数据结构（rubytree）不是设计用来处理循环的，但是plexus有向图实际上可以继续处理循环。api的设计考虑到了它们。
我采用的解决方案非常简单：基本上，现在我的图形数据结构不依赖于循环，我可以在图形生成例程的末尾调用tarjan的算法——实际上，有一个很好的wrapperacyclic?方法，但它只是在幕后调用topsort()，并使用tarjan的强连接组件算法实现拓扑排序，非常类似于ruby的stdlibTSort。不过，它确实使用自己的实现，而不是TSort。我不确定为什么。
不幸的是，现在我面临着开发一个实现minimum feedback arc set problem（最小fas问题）的np难的挑战。最小fas问题是必需的，因为我需要删除图中最少侵入的弧数以使其非循环。
我现在的计划是从plexus中获取强连接组件列表，这是一个数组数组；如果任何二级数组包含多个元素，则该数组根据强连接组件的定义，使用循环来描述元素。然后我必须（使用最小fas或近似值）移除边和/或顶点以使图无循环，并迭代运行tarjan's，直到每个scc子数组的长度为1。
我认为暴力可能是解决最小fas的最佳方法：我不需要太聪明，因为我的数据集中任何scc中的节点数几乎永远不会超过5或6。指数在5或6是好的。我严重怀疑我是否会有一个由数百个节点组成的scc集，其中包含数十个不同的周期；这将是一个极端病态的最坏情况，我认为这种情况不会发生。不过，如果是这样的话，运行时间会很长。
基本上，我需要尝试删除图的弧的幂集，一次删除一个子集，子集按子集大小升序排序，然后“猜测并检查”图是否仍然是循环的（tarjan的），然后如果该幂集不能修复循环，则添加边。
如果边和节点的数量小于20个左右（这几乎是可以保证的），则不会占用大量运行时间。
去掉迭代的tarjan绝对解决了我在happy path中的复杂性问题（没有周期或者只有一个小周期），这真的是让我最心痛的地方——不是花25分钟来构建图表，而是花了15秒。
经验教训：如果你的程序很慢，可能是因为你做了很多不必要的工作。在我的例子中，不必要的工作是在每次向图中添加新顶点时执行tarjan的拓扑排序，这只是因为我最初选择对数据建模的库的实现细节而需要的。