Class: DagPropagator

Inherits:
Object show all
Defined in:
lib/rpdf2txt-rockit/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.



256
257
258
259
260
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 256

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 



262
263
264
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 262

def init_start_nodes(startNodes)
  @startnodes = startNodes
end

#propagate ⇒ Object 



266
267
268
269
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 266

def propagate
  @visited.clear
  propagate_recursive
end

#propagate_recursive ⇒ Object 



271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
 
# File 'lib/rpdf2txt-rockit/directed_graph.rb', line 271

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