Class: Roby::Relations::ForkMergeVisitor Private

Inherits:
RGL::DFSVisitor
  • Object
show all
Defined in:
lib/roby/relations/fork_merge_visitor.rb

Overview

This class is part of a private API. You should avoid using this class if possible, as it may be removed or be changed in the future.

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

Defined Under Namespace

Classes: SubgraphDegreeCounter

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph, object, origin, origin_neighbours = graph.out_neighbours(origin)) ⇒ ForkMergeVisitor

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Returns a new instance of ForkMergeVisitor.

Parameters:

  • graph —

    the directed graph we propagate the value in

  • origin —

    the vertex from which to propagate

  • origin_neighbours (#include?) (defaults to: graph.out_neighbours(origin)) —

    the neighbours of ‘origin’ to propagate towards

  • object (#fork, #merge) —

    the object to propagate in the graph



37
38
39
40
41
42
43
44
45
46
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 37

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] = [] }

    @in_degree, @out_degree = compute_in_out_degrees(origin, origin_neighbours)
end

Instance Attribute Details

#in_degree ⇒ Object (readonly)

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

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



26
27
28
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 26

def in_degree
  @in_degree
end

#origin ⇒ Object (readonly)

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

The vertex from which we start visiting



12
13
14
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 12

def origin
  @origin
end

#origin_neighbours ⇒ Object (readonly)

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

The neighbours of this vertex that should be visited.



15
16
17
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 15

def origin_neighbours
  @origin_neighbours
end

#out_degree ⇒ Object (readonly)

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

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



30
31
32
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 30

def out_degree
  @out_degree
end

#pending_merges ⇒ Object (readonly)

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

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



22
23
24
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 22

def pending_merges
  @pending_merges
end

#vertex_to_object ⇒ Object (readonly)

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

A mapping from vertex to the propagated object for this vertex



18
19
20
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 18

def vertex_to_object
  @vertex_to_object
end

Instance Method Details

#compute_in_out_degrees(origin, origin_neighbours) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Computes the in and out degree of the subgraph starting at ‘origin’, following the out-edges of ‘origin’ that go towards ‘origin_neighbours’



82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 82

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
    [in_degree, out_degree]
end

#follow_edge?(u, v) ⇒ Boolean

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Returns:

  • (Boolean) 


99
100
101
102
103
104
105
106
107
108
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 99

def follow_edge?(u, v)
    return if u == origin && !origin_neighbours.include?(v)

    degree = in_degree[v]
    if degree == 1
        true
    else
        (pending_merges[v].size + 1) == degree
    end
end

#fork_object(obj) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future. 



150
151
152
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 150

def fork_object(obj)
    obj.fork
end

#handle_back_edge(u, v) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future. 



142
143
144
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 142

def handle_back_edge(u, v)
    raise "#handle_back_edge should never happen in a fork-merge traversal"
end

#handle_forward_edge(u, v) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future. 



110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 110

def handle_forward_edge(u, v)
    return if u == origin && !origin_neighbours.include?(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
        pending_merges[v] << obj
    else
        vertex_to_object[v] = obj
    end
end

#handle_tree_edge(u, v) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future. 



127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 127

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) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future. 



146
147
148
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 146

def propagate_object(u, v, obj)
    obj
end

#visit ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future. 



48
49
50
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 48

def visit
    graph.depth_first_visit(origin, self) {}
end