Fast cycle detection on an acyclic chart?

I have a program in Ruby 1.9.3 that creates a RubyTree . My data is best described as Directed Acyclic Graph (DAG); note that this is not a polygon. Well, at least the data should be a DAG, even though users are doing their best to frustrate my program with bad data.

I am creating a DAG dynamically by parsing an XML document. An XML document does not explicitly indicate a tree structure, but it provides cross-referenced integer identifiers that establish relationships between elements in the document.

I need to make sure the RubyTree does not contain loops. The original data may (erroneously) have a loop, and if so, my program needs to know about it and not introduce an infinite loop or crash. To accomplish this currently, I have mixed in the standard Ruby TSort library in the RubyTree class Tree::TreeNode

. This uses Tarjan's algorithm to perform a topological sort on the plot every time a node is added. During topological sorting, if a loop is found, an exception is thrown - exactly what I want.

For example:

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

      

        
        
        
      

    

I had to change a few more methods. Basically all it takes to traverse the tree or children needed to implement TSort, or get rid of its move dependency (for example, I simplified Tree::TreeNode#to_s()

it to get it back Tree::TreeNode#name

.)

My program is now functionally correct. I have done significant testing and the results are working fine: all I have to do is salvage TSort::Cyclic

at the correct points in my code, and if I ever try to add a node that calls the loop, the node is removed and I can log the problem to the report. to deal with later (by correcting the original data).

The problem is that on a RubyTree of 75,000 or so, where the number of edges is very close to the number of vertices minus 1, iteratively running Tarjan's algorithm creates an algorithmic complexity that looks rather quadratic. Tarjan itself O(|V| + |E|)

, which in my case is about O(2*|V|)

, but every time I call add()

it |V|

increments by 1 when I create a graph node on node. I can't just call Tarjan at the end, because I might need to traverse the graph or parts of it during the read-compare-add loop, and any attempt to traverse might hang the program or collapse if there is actually a loop. (It goes without saying that my code is single threaded, and if it weren't, we'd have a huge problem. At its core, I rely on the fact thatadd()

never returns without throwing an exception if there is a loop, and even if there is loop, and the node is removed in such a way as to clean up the loop before returning add()

.)

But this is too slow! It takes more than half an hour for this loop alone, and my program consists of several other steps that take their fair share of time. But, since it's worth it, just doing Tarjan eats up the lion's share of performance, judging by the results ruby-perf

. I tried switching from arrays to linked lists in RubyTree each

, but only reduced the execution time by about 1% by removing the call loads Array#concat

.

I found this awesome article by Tarjan who came up with the tightly coupled component algorithm that Ruby relies on TSort

, and it seems that incremental loop detection is an active area of ​​research. However, the level of dialogue in the document is much higher than my head, and I am sure that I lack the mathematical background to translate the results of my work into Ruby code. Not only that, but from reading the Notes section of the document, it seems that their best-effort algorithms have rather alarming worst time periods, so it might not even be faster than my current method, depending on the specifics of my data.

Am I missing something stupid here, or is it the best choice to put into mental work to analyze Tarjan's work and try to come up with a Ruby implementation of one of the algorithms? Note that I don't really care about the topological aspect of the sorting algorithm; this is a side effect of what I really want. If the tree weren't topologically sorted, but there were still no cycles guaranteed, I would be perfectly happy.

It's also worth noting that loops are somewhat rare in my original data. That is, loops can happen due to manual error in the data entry process, but they will never happen intentionally and must always be reported to the program so that he can tell me, so I can beat someone over the head with a billclub for entering incorrect data. ... Also, the program is absolutely obligated to keep smoking even if it detects a particularly nasty cycle, so I can't just stick my head in the sand and hope there won't be any cycles.

What's the problem?

At the request of some, here's a demo that you can run to see the problem at work.

Install the stable RubyTree version (I am using MRI 1.9.3). Then compare the output of the two programs:

Figure 1: Hangs permanently at 100% CPU usage on the main thread after printing "Third time"

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"

      

        
        
        
      

    

Figure 2: Goes all the way and prints "Done" and the result has no loop

Please note that I usually do things in blocks rescue

to log this cycle (s) and complain loudly about the person doing these cycles.

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 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"

      

        
        
        
      

    

The goal is to develop code that is functionally equivalent to Appendix 2, but scales better for more vertices (I don't expect more than 10 ^ 6 vertices, in which case I would be fine with it, taking a few minutes ("go to get a cup of coffee ") on a modern desktop workstation, but not hours or longer.)