Class: DagPropagator

Inherits:
Object
  • Object
show all
Defined in:
lib/fsm-0.0.0/graph/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.



336
337
338
339
340
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 336

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 



342
343
344
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 342

def init_start_nodes(startNodes)
  @startnodes = startNodes
end

#propagate ⇒ Object 



346
347
348
349
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 346

def propagate
  @visited.clear
  propagate_recursive
end

#propagate_recursive ⇒ Object 



351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
 
# File 'lib/fsm-0.0.0/graph/directed_graph.rb', line 351

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