Class: DagPropagator

Inherits:
Object
  • Object
show all
Defined in:
lib/graphr/directed_graph.rb

Overview

Parallel propagation in directed acyclic graphs. Should be faster than traversing all links from each start node if the graph is dense so that many traversals can be merged.

Instance Method Summary collapse

Constructor Details

#initialize(directedGraph, startNodes, &propagationBlock) ⇒ DagPropagator

Returns a new instance of DagPropagator.



328
329
330
331
332
 
# File 'lib/graphr/directed_graph.rb', line 328

def initialize(directedGraph, startNodes, &propagationBlock)
  @graph, @block = directedGraph, propagationBlock
  init_start_nodes(startNodes)
  @visited = Hash.new
end

Instance Method Details

#init_start_nodes(startNodes) ⇒ Object 



334
335
336
 
# File 'lib/graphr/directed_graph.rb', line 334

def init_start_nodes(startNodes)
  @startnodes = startNodes
end

#propagate ⇒ Object 



338
339
340
341
 
# File 'lib/graphr/directed_graph.rb', line 338

def propagate
  @visited.clear
  propagate_recursive
end

#propagate_recursive ⇒ Object 



343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
 
# File 'lib/graphr/directed_graph.rb', line 343

def propagate_recursive
  next_start_nodes = Array.new
  @startnodes.each do |parent|
    @visited[parent] = true
    @graph.children(parent).each do |child|
	@block.call(parent, child)
	unless @visited[child] or next_start_nodes.include?(child)
 next_start_nodes.push(child)
	end
    end
  end
  if next_start_nodes.length > 0
    @startnodes = next_start_nodes
    propagate_recursive
  end
end