Class: Roby::Relations::Graph

Inherits:
BidirectionalDirectedAdjacencyGraph show all
Extended by:
Models::Graph, DRoby::Identifiable, DRoby::V5::DRobyConstant::Dump
Defined in:
lib/roby/relations/graph.rb,
lib/roby/droby/enable.rb

Overview

A relation graph

Relation graphs extend the base graph class BidirectionalDirectedAdjacencyGraph by adding the ability to arrange the graphs in a hierarchy (where a 'child' is a subgraph of a 'parent'), and the modification methods #add_relation and #remove_relation that maintain consistency in the hierarchy. Moreover, it allows to set an #observer object that listens to graph modifications (Roby uses it to emit relation hooks on plan objects when included in a ExecutablePlan).

Note that the underlying methods #add_edge and BidirectionalDirectedAdjacencyGraph#remove_edge are still available in cases where the hooks should not be called and hierarchy consistency is maintained by other means (e.g. when copying a plan).

Finally, it is possible for #add_edge to update an existing edge info. For this purpose, a subclass has to implement the #merge_info method which is called with the old and new info and should return the merged object. The default implementation raises ArgumentError

Instance Attribute Summary collapse

Attributes inherited from BidirectionalDirectedAdjacencyGraph

#backward_edges, #forward_edges_with_info

Instance Method Summary collapse

Methods included from DRoby::Identifiable

droby_id, initialize_copy

Methods included from DRoby::V5::DRobyConstant::Dump

droby_dump, droby_marshallable?

Methods inherited from BidirectionalDirectedAdjacencyGraph

#==, [], #add_or_update_edge, #add_vertex, #clear, #dedupe, #delete_vertex_if, #difference, #directed?, #each_edge, #each_in_neighbour, #each_out_neighbour, #each_vertex, #edge_info, #eql?, #freeze, #has_edge?, #has_vertex?, #hash, #in_degree, #in_neighbours, #initialize_copy, #leaf?, #merge, #move_edges, #num_edges, #num_vertices, #out_degree, #out_neighbours, #propagate_transitive_closure, #remove_edge, #remove_vertex_relations!, #replace, #reverse, #reverse!, #root?, #same_structure?, #to_a, #verify_consistency, #vertices

Methods included from DRoby::V5::BidirectionalGraphDumper

#droby_dump

Constructor Details

#initialize(observer: nil, distribute: self.class.distribute?, dag: self.class.dag?, weak: self.class.weak?, strong: self.class.strong?, copy_on_replace: self.class.copy_on_replace?, noinfo: !self.class.embeds_info?,, subsets: Set.new) ⇒ Graph

Creates a relation graph with the given name and options. The following options are recognized:

dag

if the graph is a DAG. If true, add_relation will check that no cycle is created

subsets

a set of Relations::Graph objects that are children of this one. See #superset_of.

distributed

if this relation graph should be seen by remote hosts



137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
 
# File 'lib/roby/relations/graph.rb', line 137

def initialize(
    observer: nil,
    distribute: self.class.distribute?,
    dag: self.class.dag?,
    weak: self.class.weak?,
    strong: self.class.strong?,
    copy_on_replace: self.class.copy_on_replace?,
    noinfo: !self.class.embeds_info?,
    subsets: Set.new
)

    @observer = observer
    @distribute = distribute
    @dag = dag
    @weak = weak
    @strong = strong
    @copy_on_replace = copy_on_replace
    @embeds_info = !noinfo

    # If the relation is a single-child relation, it expects to have
    # this ivar set
    if respond_to?(:single_child_accessor)
        @single_child_accessor = "@#{self.class.child_name}"
    end

    @subsets = Set.new
    subsets.each { |g| superset_of(g) }

    super()
end

Instance Attribute Details

#observer ⇒ Object (readonly)

An object that is called for relation modifications

The relation will call the following hooks.

Addition/removal hooks are called once per modification in the relation hierarchy. They get a 'relations' array which is the list of relation IDs (i.e. graph classes, e.g. TaskStructure::Dependency) which are concerned with the modification. This array is sorted from the downmost in the relation hierarchy (i.e. the most specialized) up to the upmost (the biggest superset).

adding_edge(from, to, relations, info)
added_edge(from, to, relations, info)

Before and after a new edge is added between two vertices in the graph. 'info' is the edge info that is set for the edge in the first element of 'relations' (the other relations get nil)

updating_edge(from, to, relation, info)
updated_edge(from, to, relation, info)

Before and after the edge info is set on a given edge. 'relation' is a single relation ID.

removing_edge(from, to, relations)
removed_edge(from, to, relations)

Before and after an edge has been removed.



125
126
127
 
# File 'lib/roby/relations/graph.rb', line 125

def observer
  @observer
end

#parent ⇒ Object

The relation parent (if any)

See Also:



87
88
89
 
# File 'lib/roby/relations/graph.rb', line 87

def parent
  @parent
end

#subsets ⇒ Object (readonly)

The set of graphs that are directly children of self in the graph hierarchy. They are subgraphs of self, but not all the existing subgraphs of self

See Also:



94
95
96
 
# File 'lib/roby/relations/graph.rb', line 94

def subsets
  @subsets
end

Instance Method Details

#add_edge(a, b, info) ⇒ Object

Add an edge between two objects

Unlike BidirectionalDirectedAdjacencyGraph#add_edge, it will update the edge info (using #merge_info) if the edge already exists.

Returns:

  • true if a new edge was created



308
309
310
311
312
313
 
# File 'lib/roby/relations/graph.rb', line 308

def add_edge(a, b, info)
    unless try_updating_existing_edge_info(a, b, info)
        super
        true
    end
end

#add_relation(from, to, info = nil) ⇒ Object

Add an edge between from and to. The relation is added on all parent relation graphs as well. If #dag? is true on self or on one of its parents, the method will raise CycleFoundError in case the new edge would create a cycle.

If from or to define the following hooks:

adding_parent_object(parent, relations, info)
adding_child_object(child, relations, info)
added_parent_object(parent, relations, info)
added_child_object(child, relations, info)

then these hooks get respectively called before and after having added the relation, where relations is the set of Relations::Graph instances where the edge has been added. It can be either [+self+] if the edge does not already exist in it, or [+self+, parent, parent.parent, ...] if the parent, grandparent, ... graphs do not include the edge either.



333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
 
# File 'lib/roby/relations/graph.rb', line 333

def add_relation(from, to, info = nil)
    # First check if we're trying to change the edge information
    # rather than creating a new edge
    if try_updating_existing_edge_info(from, to, info)
        return
    end

    new_relations = []
    new_relations_ids = []
    rel = self
    while rel
        unless rel.has_edge?(from, to)
            new_relations << rel
            new_relations_ids << rel.class
        end
        rel = rel.parent
    end

    unless new_relations.empty?
        observer&.adding_edge(from, to, new_relations_ids, info)
        for rel in new_relations
            rel.add_edge(from, to, (info if self == rel))
        end
        observer&.added_edge(from, to, new_relations_ids, info)
    end
end

#copy_on_replace? ⇒ Boolean

Whether edges in this relation should be copied on replacement or moved. The default is to move.

Returns:

  • (Boolean) 


73
74
75
 
# File 'lib/roby/relations/graph.rb', line 73

def copy_on_replace?
    @copy_on_replace
end

#copy_subgraph_to(graph, mappings) ⇒ Object

Copy a subgraph of self into another graph

This method allows to define a mapping of vertices from self (source set) into vertices of another graph (target set), and copies the edges that exist between the vertices of the source set to edges between the corresponding vertices of target set

Parameters:

  • graph (Graph) —

    the target graph

  • a (Hash<Object,Object>) —

    mapping from the subgraph vertices in self to the corresponding vertices in the target graph



202
203
204
205
206
207
208
209
210
211
 
# File 'lib/roby/relations/graph.rb', line 202

def copy_subgraph_to(graph, mappings)
    mappings.each do |v, mapped_v|
        each_out_neighbour(v) do |child|
            if mapped_child = mappings[child]
                graph.add_edge(mapped_v, mapped_child,
                               edge_info(v, child))
            end
        end
    end
end

#copy_to(target) ⇒ Object 



540
541
542
543
 
# File 'lib/roby/relations/graph.rb', line 540

def copy_to(target)
    Roby.warn_deprecated "Graph#copy_to is deprecated, use #merge instead (WARN: a.copy_to(b) is b.merge(a) !"
    target.merge(self)
end

#dag? ⇒ Boolean

True if this relation graph is a DAG

This property is not enforced by the Graph class itself as in a lot of cases it would be too expensive. When used in Roby, it is either enforced by ExecutablePlan or when committing a transaction

Returns:

  • (Boolean) 


34
35
36
 
# File 'lib/roby/relations/graph.rb', line 34

def dag?
    @dag
end

#each_child_vertex(object, &block) ⇒ Object 



535
536
537
538
 
# File 'lib/roby/relations/graph.rb', line 535

def each_child_vertex(object, &block)
    Roby.warn_deprecated "#each_child_vertex has been replaced by #each_out_neighbour"
    each_out_neighbour(object, &block)
end

#each_parent_vertex(object, &block) ⇒ Object 



530
531
532
533
 
# File 'lib/roby/relations/graph.rb', line 530

def each_parent_vertex(object, &block)
    Roby.warn_deprecated "#each_parent_vertex has been replaced by #each_in_neighbour"
    each_in_neighbour(object, &block)
end

#embeds_info? ⇒ Boolean

If this relation embeds information in its edges

This is as optimization,

Returns:

  • (Boolean) 


67
68
69
 
# File 'lib/roby/relations/graph.rb', line 67

def embeds_info?
    @embeds_info
end

#find_edge_difference(graph, mapping) ⇒ Object 



213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
 
# File 'lib/roby/relations/graph.rb', line 213

def find_edge_difference(graph, mapping)
    if graph.num_edges != num_edges
        return [:num_edges_differ]
    end

    each_edge do |parent, child|
        m_parent, m_child = mapping[parent], mapping[child]
        if !m_parent
            return [:missing_mapping, parent]
        elsif !m_child
            return [:missing_mapping, child]
        elsif !graph.has_vertex?(m_parent) || !graph.has_vertex?(m_child) || !graph.has_edge?(m_parent, m_child)
            return [:missing_edge, parent, child]
        elsif edge_info(parent, child) != graph.edge_info(m_parent, m_child)
            return [:differing_edge_info, parent, child]
        end
    end
    nil
end

#has_edge_in_hierarchy?(source, target) ⇒ Boolean

Tests the presence of an edge in this graph or in its supersets

See #superset_of for a description of the parent mechanism

Returns:

  • (Boolean) 


482
483
484
 
# File 'lib/roby/relations/graph.rb', line 482

def has_edge_in_hierarchy?(source, target)
    root_graph.has_edge?(source, target)
end

#ignore_in_replacement? ⇒ Boolean

Whether this relation should be ignored during replacements

This is a predicate computed from #strong? and #copy_on_replace?

Returns:

  • (Boolean) 


80
81
82
 
# File 'lib/roby/relations/graph.rb', line 80

def ignore_in_replacement?
    strong? && !copy_on_replace?
end

#include?(object) ⇒ Boolean

Returns:

  • (Boolean) 


550
551
552
553
 
# File 'lib/roby/relations/graph.rb', line 550

def include?(object)
    Roby.warn_deprecated "Graph#include? is deprecated, use #has_vertex? instead"
    has_vertex?(object)
end

#inspect ⇒ Object 



188
189
190
 
# File 'lib/roby/relations/graph.rb', line 188

def inspect
    to_s
end

#leaf_relation? ⇒ Boolean

True if this relation has no subset graph

Returns:

  • (Boolean) 


458
459
460
 
# File 'lib/roby/relations/graph.rb', line 458

def leaf_relation?
    subsets.empty?
end

#link(a, b, info) ⇒ Object 



515
516
517
518
 
# File 'lib/roby/relations/graph.rb', line 515

def link(a, b, info)
    Roby.warn_deprecated "Graph#link is deprecated, use #add_edge instead"
    add_edge(a, b, info)
end

#linked?(parent, child) ⇒ Boolean

Returns:

  • (Boolean) 


520
521
522
523
 
# File 'lib/roby/relations/graph.rb', line 520

def linked?(parent, child)
    Roby.warn_deprecated "Graph#linked? is deprecated, use #add_edge instead"
    has_edge?(parent, child)
end

#linked_in_hierarchy?(source, target) ⇒ Boolean

Deprecated.

use #has_edge_in_hierarchy?

Returns:

  • (Boolean) 


556
557
558
559
 
# File 'lib/roby/relations/graph.rb', line 556

def linked_in_hierarchy?(source, target)
    Roby.warn_deprecated "#linked_in_hierarchy? is deprecated, use #has_edge_in_hierarchy? instead"
    has_edge_in_hierarchy?(source, target)
end

#merge!(graph) ⇒ Object

Add the vertices and edges of a graph in self

Parameters:

  • graph (Graph) —

    the graph whose relations should be added to self



269
270
271
272
 
# File 'lib/roby/relations/graph.rb', line 269

def merge!(graph)
    merge(graph)
    graph.clear
end

#merge_info(from, to, old, new) ⇒ nil, Object

Method used in #add_relation and #add_edge to merge existing information with new information

It is safe to raise from within this method

Returns:

  • (nil, Object) —

    if nil, the update is aborted. If non-nil, it is the new information

Raises:

  • (ArgumentError) 


374
375
376
 
# File 'lib/roby/relations/graph.rb', line 374

def merge_info(from, to, old, new)
    raise ArgumentError, "cannot update edge information in #{self}: #merge_info is not implemented"
end

#reachable?(u, v) ⇒ Boolean

Tests whether a vertex is reachable from this one

This is at worst O(E), i.e. the number of vertices that are reachable from the source vertex.

If you want to do a lot of these queries, or if you want to check for acyclicity, RGL offers better alternatives.

Parameters:

  • u (Object) —

    the origin vertex

  • v (Object) —

    the vertex whose reachability we want to test from 'u'

Returns:

  • (Boolean) 


179
180
181
182
 
# File 'lib/roby/relations/graph.rb', line 179

def reachable?(u, v)
    depth_first_visit(u) { |o| return true if o == v }
    false
end

#recursive_subsets ⇒ Object

Compute the set of all graphs that are subsets of this one in the subset hierarchy



441
442
443
444
445
446
447
448
449
450
 
# File 'lib/roby/relations/graph.rb', line 441

def recursive_subsets
    result = Set.new
    queue = subsets.to_a.dup
    until queue.empty?
        g = queue.shift
        result << g
        queue.concat(g.subsets.to_a)
    end
    result
end

#remove(vertex) ⇒ Object 



510
511
512
513
 
# File 'lib/roby/relations/graph.rb', line 510

def remove(vertex)
    Roby.warn_deprecated "Graph#remove is deprecated, use #remove_vertex instead"
    remove_vertex(vertex)
end

#remove_relation(from, to) ⇒ Object

Remove the relation between from and to, in this graph and in its parent graphs as well.

If from or to define the following hooks:

removing_child_object(child, relations)
removed_child_object(child, relations)

then these hooks get respectively called once before and once after having removed the relation, where relations is the set of Relations::Graph instances where the edge has been removed. It is always [self, parent, parent.parent, ...] up to the root relation which is a superset of self.



419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
 
# File 'lib/roby/relations/graph.rb', line 419

def remove_relation(from, to)
    unless has_edge?(from, to)
        return
    end

    rel = self
    relations, relations_ids = [], []
    while rel
        relations << rel
        relations_ids << rel.class
        rel = rel.parent
    end

    observer&.removing_edge(from, to, relations_ids)
    for rel in relations
        rel.remove_edge(from, to)
    end
    observer&.removed_edge(from, to, relations_ids)
end

#remove_vertex(object) ⇒ Object 



380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
 
# File 'lib/roby/relations/graph.rb', line 380

def remove_vertex(object)
    unless observer
        return super
    end

    rel = self
    relations, relations_ids = [], []
    while rel
        relations << rel
        relations_ids << rel.class
        rel = rel.parent
    end

    removed_relations = []
    in_neighbours(object).each { |parent| removed_relations << parent << object }
    out_neighbours(object).each { |child| removed_relations << object << child }

    removed_relations.each_slice(2) do |parent, child|
        observer.removing_edge(parent, child, relations_ids)
    end
    relations.each { |rel| rel.remove_vertex!(object) }
    removed_relations.each_slice(2) do |parent, child|
        observer.removed_edge(parent, child, relations_ids)
    end
    !removed_relations.empty?
end

#remove_vertex! ⇒ Object 



378
 
# File 'lib/roby/relations/graph.rb', line 378

alias remove_vertex! remove_vertex

#replace_vertex(from, to, remove: true) ⇒ Object

Moves a vertex relations onto another

Parameters:

  • from (Object) —

    the vertex whose relations are going to be moved

  • to (Object) —

    the vertex on which the relations will be added

  • remove (Boolean) (defaults to: true) —

    whether 'from' should be removed from the graph after replacement



241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
 
# File 'lib/roby/relations/graph.rb', line 241

def replace_vertex(from, to, remove: true)
    edges = []
    each_in_neighbour(from) do |parent|
        if parent != to
            add_edge(parent, to, edge_info(parent, from))
            edges << [parent, from]
        end
    end
    each_out_neighbour(from) do |child|
        if to != child
            add_edge(to, child, edge_info(from, child))
            edges << [from, child]
        end
    end

    edges.each do |parent, child|
        remove_relation(parent, child)
    end

    if remove
        remove_vertex(from)
    end
end

#root_graph ⇒ Object

The root in this graph's hierarchy



471
472
473
474
475
476
477
 
# File 'lib/roby/relations/graph.rb', line 471

def root_graph
    g = self
    while g.parent
        g = g.parent
    end
    g
end

#root_relation? ⇒ Boolean

True if this relation does not have a parent

Returns:

  • (Boolean) 


453
454
455
 
# File 'lib/roby/relations/graph.rb', line 453

def root_relation?
    !parent
end

#set_edge_info(from, to, info) ⇒ Object

Set the information of an object relation



361
362
363
364
365
 
# File 'lib/roby/relations/graph.rb', line 361

def set_edge_info(from, to, info)
    observer&.updating_edge_info(from, to, self.class, info)
    super
    observer&.updated_edge_info(from, to, self.class, info)
end

#size ⇒ Object 



545
546
547
548
 
# File 'lib/roby/relations/graph.rb', line 545

def size
    Roby.warn_deprecated "Graph#size is deprecated, use #num_vertices instead"
    num_vertices
end

#strong? ⇒ Boolean

If this relation is strong

Strong relations mark parts of the plan that can't be removed or exchanged bit-by-bit. I.e. Plan#replace_task will never remove one of those relations and quarantine code will keep them as well.

In practice, strong relations that have copy_on_replace set to false are totally ignored during replacement. Set copy_on_replace: true to have them copied.

Examples are error handling or execution agent relations

Returns:

  • (Boolean) 


60
61
62
 
# File 'lib/roby/relations/graph.rb', line 60

def strong?
    @strong
end

#subset?(relation) ⇒ Boolean

Returns true if relation is included in this relation (i.e. it is either the same relation or one of its children)

See also #superset_of

Returns:

  • (Boolean) 


466
467
468
 
# File 'lib/roby/relations/graph.rb', line 466

def subset?(relation)
    self.eql?(relation) || subsets.any? { |subrel| subrel.subset?(relation) }
end

#superset_of(relation) ⇒ Object

Declare that self is a superset of relation. Once this is done, the system manages two constraints:

  • new relations added with #add_relation are also added in self
  • a relation can only exist in one subset of self

One single graph can be the superset of multiple subgraphs (these are stored in the #subsets attribute), but one graph can have only one parent #parent.

This operation can be called only if the new subset is empty (no edges and no vertices)

Parameters:

  • relation (Graph) —

    the relation that should be added as a subset of self

Raises:

  • (ArgumentError) —

    if 'relation' is not empty



501
502
503
504
505
506
507
508
 
# File 'lib/roby/relations/graph.rb', line 501

def superset_of(relation)
    unless relation.empty?
        raise ArgumentError, "cannot pass a non-empty graph to #superset_of"
    end

    relation.parent = self
    subsets << relation
end

#to_s ⇒ Object 



184
185
186
 
# File 'lib/roby/relations/graph.rb', line 184

def to_s
    "#{self.class.name}:#{object_id.to_s(16)}"
end

#try_updating_existing_edge_info(from, to, info) ⇒ 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.

Updates the edge information of an existing info, or does nothing if the edge does not exist

If the edge has a non-nil info already, the graph's #merge_info is called to merge the existing and new information. If #merge_info returns nil, the update is aborted

Parameters:

  • from —

    the edge parent object

  • to —

    the edge child object

  • info —

    the new edge info

Returns:

  • (Boolean) —

    true if the edge existed and false otherwise



287
288
289
290
291
292
293
294
295
296
297
298
299
 
# File 'lib/roby/relations/graph.rb', line 287

def try_updating_existing_edge_info(from, to, info)
    return false unless has_edge?(from, to)

    unless (old_info = edge_info(from, to)).nil?
        if old_info == info
            return true
        elsif !(info = merge_info(from, to, old_info, info))
            raise ArgumentError, "trying to change edge information in #{self} for #{from} => #{to}: old was #{old_info} and new is #{info}"
        end
    end
    set_edge_info(from, to, info)
    true
end

#unlink(parent, child) ⇒ Object 



525
526
527
528
 
# File 'lib/roby/relations/graph.rb', line 525

def unlink(parent, child)
    Roby.warn_deprecated "Graph#unlink is deprecated, use #remove_edge instead"
    remove_edge(parent, child)
end

#weak? ⇒ Boolean

If this relation is weak

Weak relations do not encode dependency, i.e. they will not be considered for garbage collection ordering for instance.

Returns:

  • (Boolean) 


45
46
47
 
# File 'lib/roby/relations/graph.rb', line 45

def weak?
    @weak
end