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



35
36
37
38
39
40
41
42
43
44
 
# 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

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



24
25
26
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 24

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



10
11
12
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 10

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.



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

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



28
29
30
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 28

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



20
21
22
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 20

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



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

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’



77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# 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) ⇒ 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) 


93
94
95
96
97
98
99
100
101
102
103
104
 
# 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) ⇒ 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. 



148
149
150
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 148

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. 



140
141
142
 
# 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) ⇒ 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. 



106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
# 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) ⇒ 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. 



125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
# 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) ⇒ 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. 



144
145
146
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 144

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. 



46
47
48
 
# File 'lib/roby/relations/fork_merge_visitor.rb', line 46

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