class Roby::Relations::ForkMergeVisitor
@api private
A graph visitor which propagates a value through a subgraph of an acyclic graph, copying the value using fork at graph forks, and merging them back with merge when reaching a merge point
Attributes
The in-degree of each node in the subgraph defined by {#origin} and {#origin_neighbours}
The vertex from which we start visiting
The neighbours of this vertex that should be visited.
The out-degree of each node in the subgraph defined by {#origin} and {#origin_neighbours}
The pending merges, i.e. a collection of objects gathered so far at a merge point
A mapping from vertex to the propagated object for this vertex
Public Class Methods
@param graph the directed graph we propagate the value in @param origin the vertex from which to propagate @param [#include?] origin_neighbours
the neighbours of 'origin' to
propagate towards
@param [#fork,#merge] object the object to propagate in the graph
# File lib/roby/relations/fork_merge_visitor.rb, line 35 def initialize(graph, object, origin, origin_neighbours = graph.out_neighbours(origin)) super(graph) @origin = origin @origin_neighbours = origin_neighbours @vertex_to_object = Hash[origin => object] @pending_merges = Hash.new { |h, k| h[k] = Array.new } @in_degree, @out_degree = compute_in_out_degrees(origin, origin_neighbours) end
Public Instance Methods
Computes the in and out degree of the subgraph starting at 'origin', following the out-edges of 'origin' that go towards 'origin_neighbours'
# File lib/roby/relations/fork_merge_visitor.rb, line 77 def compute_in_out_degrees(origin, origin_neighbours) visitor = SubgraphDegreeCounter.new(graph) origin_neighbours.each do |v| next if visitor.color_map[v] != :WHITE graph.depth_first_visit(v, visitor) { } end in_degree, out_degree = visitor.in_degree, visitor.out_degree in_degree[origin] = 0 out_degree[origin] = origin_neighbours.size origin_neighbours.each do |v| in_degree[v] += 1 end return in_degree, out_degree end
# File lib/roby/relations/fork_merge_visitor.rb, line 93 def follow_edge?(u, v) if u == origin return if !origin_neighbours.include?(v) end degree = in_degree[v] if degree == 1 true else (pending_merges[v].size + 1) == degree end end
# File lib/roby/relations/fork_merge_visitor.rb, line 148 def fork_object(obj) obj.fork end
# File lib/roby/relations/fork_merge_visitor.rb, line 140 def handle_back_edge(u, v) raise "#handle_back_edge should never happen in a fork-merge traversal" end
# File lib/roby/relations/fork_merge_visitor.rb, line 106 def handle_forward_edge(u, v) if u == origin return if !origin_neighbours.include?(v) end obj = vertex_to_object.fetch(u) if obj if out_degree[u] > 1 obj = fork_object(obj) end obj = propagate_object(u, v, obj) end if in_degree[v] > 1 pending_merges[v] << obj else vertex_to_object[v] = obj end end
# File lib/roby/relations/fork_merge_visitor.rb, line 125 def handle_tree_edge(u, v) obj = vertex_to_object.fetch(u) if obj if out_degree[u] > 1 obj = fork_object(obj) end obj = propagate_object(u, v, obj) end if in_degree[v] > 1 obj = (pending_merges.delete(v) << obj).compact.inject { |a, b| a.merge(b) } end vertex_to_object[v] = obj end
# File lib/roby/relations/fork_merge_visitor.rb, line 144 def propagate_object(u, v, obj) obj end
# File lib/roby/relations/fork_merge_visitor.rb, line 46 def visit graph.depth_first_visit(origin, self) {} end