слишком большой уровень стека (SystemStackError) DFS

Question

У меня проблема с stack level too deep при выполнении алгоритма DFS , чтобы найти самый большой компонент.Дело в том, что я преобразовываю файл карты (.osm) в график.И я хочу найти самый большой компонент.Тем не менее, при работе с небольшой картой (масштаб больше) она работает, но при увеличении графика это приводит к ошибке состояния выше, вы можете мне помочь?Вот мой код DFS, который вызывает проблему:

def dfsFunction (vertex)
    @dfs[vertex] = true
    @component[@componentIndex] << vertex
    adjectenVertices = []
    @edges.each do |edge|
        if edge.v1.id == vertex.id
            adjectenVertices << edge.v2
        elsif edge.v2.id == vertex.id
            adjectenVertices << edge.v1
        end
    end
    adjectenVertices.each_with_index do |vertex|
        if @dfs[vertex] == false
            dfsFunction(vertex)
        end
    end
end




@dfs = {}
    @vertices.each do |id,vertex|
        @dfs[vertex] = false
    end
    @component = {}
    @componentIndex = -1
    @dfs.each do |vertex, boolean|
        if @dfs[vertex] == false
            @componentIndex = @componentIndex +1
            @component[@componentIndex] = []
            dfsFunction(vertex)
        end
    end

Answer 1

В МРТ оптимизация хвостовой рекурсии отключена по умолчанию.Но его можно включить:

RubyVM::InstructionSequence.compile_option = {
 tailcall_optimization: true,
 trace_instruction: false
}

также, сам код должен использовать хвостовую рекурсию, например:

  def test(v)
    return unless v > 0
    p v
    test(v-1) 
  end

Вместо:

def test(v)
  test(v-1) if v > 0
  p v
end

Answer 2

Проблема здесь в том, что вы используете рекурсию, и она становится глубокой для сложных графов.Для каждой рекурсии стек должен быть увеличен для хранения значения результата.Чтобы решить эту проблему, вы можете сделать две вещи: перейти на цикл или переписать рекурсию, оптимизированную с помощью хвостового вызова, и включить оптимизацию хвостового вызова для ruby ​​(для некоторых объяснений посмотрите здесь: http://nithinbekal.com/posts/ruby-tco/).

IЯ сделал небольшую версию, которая использует цикл while. Надеюсь, это поможет ...

class Edge
  attr_reader :left, :right

  def initialize(left, right)
    @left, @right = left, right
  end

  def vertexes
    [left, right]
  end
end

class Graph
  attr_reader :vertexes, :edges

  def initialize(vertexes, edges)
    @vertexes, @edges = vertexes, edges
  end

  def add_edges(new_edges)
    new_edges.each { |edge| add_edge(edge) }
  end

  def add_edge(edge)
    add_vertex(edge.left)
    add_vertex(edge.right)
    @edges << edge
    @edges.uniq!
    edge
  end

  def add_vertex(vertex)
    @vertexes << vertex
    @vertexes.uniq!
    vertex
  end

  def edges_for(vertex) 
    edges.select { |edge| edge.left == vertex || edge.right == vertex }
  end
end

module DFS
  def self.components(graph)
    vertexes = graph.vertexes.clone
    graph.vertexes.map do |vertex|
      next unless vertexes.delete(vertex)
      component = Graph.new([vertex], [])
      edges = graph.edges_for(vertex)
      while (new_vertexes = edges.map(&:vertexes).flatten & vertexes).any? do
        component.add_edges(edges)
        edges = new_vertexes.map { |new_vertex| graph.edges_for(new_vertex) }.flatten
        vertexes -= new_vertexes
      end
      component.add_edges(edges)
      component
    end.compact
  end
end