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

in_degree[R]

The in-degree of each node in the subgraph defined by {#origin} and {#origin_neighbours}

origin[R]

The vertex from which we start visiting

origin_neighbours[R]

The neighbours of this vertex that should be visited.

out_degree[R]

The out-degree of each node in the subgraph defined by {#origin} and {#origin_neighbours}

pending_merges[R]

The pending merges, i.e. a collection of objects gathered so far at a merge point

vertex_to_object[R]

A mapping from vertex to the propagated object for this vertex

Public Class Methods

new(graph, object, origin, origin_neighbours = graph.out_neighbours(origin)) click to toggle source

@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

Calls superclass method
# 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

compute_in_out_degrees(origin, origin_neighbours) click to toggle source

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
follow_edge?(u, v) click to toggle source
# 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
fork_object(obj) click to toggle source
# File lib/roby/relations/fork_merge_visitor.rb, line 148
def fork_object(obj)
    obj.fork
end
handle_back_edge(u, v) click to toggle source
# 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
handle_forward_edge(u, v) click to toggle source
# 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
handle_tree_edge(u, v) click to toggle source
# 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
propagate_object(u, v, obj) click to toggle source
# File lib/roby/relations/fork_merge_visitor.rb, line 144
def propagate_object(u, v, obj)
    obj
end
visit() click to toggle source
# File lib/roby/relations/fork_merge_visitor.rb, line 46
def visit
    graph.depth_first_visit(origin, self) {}
end