Class: Grandprix::Graph::Sort

Inherits:
Object
  • Object
show all
Defined in:
lib/grandprix/graph.rb

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ Sort

Returns a new instance of Sort.



7
8
9
10
11
 
# File 'lib/grandprix/graph.rb', line 7

def initialize(graph)
  @graph = graph
  @preds_count = PredecessorCount.new graph
  @successors  = SuccessorTable.new graph
end

Instance Method Details

#solve ⇒ Object 



13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
# File 'lib/grandprix/graph.rb', line 13

def solve
  def visit(queue, ordered_vertices)
    return ordered_vertices if queue.empty?
    current, *rest = queue

    successors = @successors.of(current)
    @preds_count.decrement_all successors

    new_queue = rest + @preds_count.zeroes_among(successors)
    visit new_queue, ordered_vertices.push(current)
  end

  check_for_cycles visit(initial_queue, [])
end

#visit(queue, ordered_vertices) ⇒ Object 



14
15
16
17
18
19
20
21
22
23
 
# File 'lib/grandprix/graph.rb', line 14

def visit(queue, ordered_vertices)
  return ordered_vertices if queue.empty?
  current, *rest = queue

  successors = @successors.of(current)
  @preds_count.decrement_all successors

  new_queue = rest + @preds_count.zeroes_among(successors)
  visit new_queue, ordered_vertices.push(current)
end