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

Direct Known Subclasses

EventRelationGraph, TaskRelationGraph

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_vertex, #clear, #dedupe, #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, #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



107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
 
# File 'lib/roby/relations/graph.rb', line 107

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.



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

def observer
  @observer
end

#parent ⇒ Object

The relation parent (if any)

See Also:



57
58
59
 
# File 'lib/roby/relations/graph.rb', line 57

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:



64
65
66
 
# File 'lib/roby/relations/graph.rb', line 64

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



278
279
280
281
282
283
 
# File 'lib/roby/relations/graph.rb', line 278

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.



303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
 
# File 'lib/roby/relations/graph.rb', line 303

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_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



172
173
174
175
176
177
178
179
180
181
 
# File 'lib/roby/relations/graph.rb', line 172

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 



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

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

#each_child_vertex(object, &block) ⇒ Object 



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

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 



500
501
502
503
 
# File 'lib/roby/relations/graph.rb', line 500

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

#find_edge_difference(graph, mapping) ⇒ Object 



183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
 
# File 'lib/roby/relations/graph.rb', line 183

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) 


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

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

#include?(object) ⇒ Boolean

Returns:

  • (Boolean) 


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

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

#inspect ⇒ Object 



158
159
160
 
# File 'lib/roby/relations/graph.rb', line 158

def inspect
    to_s
end

#leaf_relation? ⇒ Boolean

True if this relation has no subset graph

Returns:

  • (Boolean) 


428
429
430
 
# File 'lib/roby/relations/graph.rb', line 428

def leaf_relation?
    subsets.empty?
end

#link(a, b, info) ⇒ Object 



485
486
487
488
 
# File 'lib/roby/relations/graph.rb', line 485

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) 


490
491
492
493
 
# File 'lib/roby/relations/graph.rb', line 490

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) 


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

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



239
240
241
242
 
# File 'lib/roby/relations/graph.rb', line 239

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) 


344
345
346
 
# File 'lib/roby/relations/graph.rb', line 344

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) 


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

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



411
412
413
414
415
416
417
418
419
420
 
# File 'lib/roby/relations/graph.rb', line 411

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 



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

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.



389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
 
# File 'lib/roby/relations/graph.rb', line 389

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 



350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
 
# File 'lib/roby/relations/graph.rb', line 350

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 



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

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



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

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



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

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) 


423
424
425
 
# File 'lib/roby/relations/graph.rb', line 423

def root_relation?
    !parent
end

#set_edge_info(from, to, info) ⇒ Object

Set the information of an object relation



331
332
333
334
335
 
# File 'lib/roby/relations/graph.rb', line 331

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 



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

def size
    Roby.warn_deprecated "Graph#size is deprecated, use #num_vertices instead"
    num_vertices
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) 


436
437
438
 
# File 'lib/roby/relations/graph.rb', line 436

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



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

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 



154
155
156
 
# File 'lib/roby/relations/graph.rb', line 154

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



257
258
259
260
261
262
263
264
265
266
267
268
269
 
# File 'lib/roby/relations/graph.rb', line 257

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 



495
496
497
498
 
# File 'lib/roby/relations/graph.rb', line 495

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