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

Methods inherited from BidirectionalDirectedAdjacencyGraph

#==, [], #add_vertex, #clear, #dedupe, #difference, #directed?, #each_edge, #each_in_neighbour, #each_out_neighbour, #each_vertex, #edge_info, #eql?, #has_edge?, #has_vertex?, #hash, #in_degree, #in_neighbours, #initialize_copy, #leaf?, #merge, #move_edges, #num_edges, #num_vertices, #out_degree, #out_neighbours, #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



105
106
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
 
# File 'lib/roby/relations/graph.rb', line 105

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.



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

def observer
  @observer
end

#parent ⇒ Object

The relation parent (if any)

See Also:



55
56
57
 
# File 'lib/roby/relations/graph.rb', line 55

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:



62
63
64
 
# File 'lib/roby/relations/graph.rb', line 62

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



273
274
275
276
277
278
 
# File 'lib/roby/relations/graph.rb', line 273

def add_edge(a, b, info)
    if !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.



298
299
300
301
302
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
 
# File 'lib/roby/relations/graph.rb', line 298

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
        if !rel.has_edge?(from, to)
            new_relations << rel
            new_relations_ids << rel.class
        end
        rel = rel.parent
    end

    if !new_relations.empty?
        if observer
            observer.adding_edge(from, to, new_relations_ids, info)
        end
        for rel in new_relations
            rel.add_edge(from, to, (info if self == rel))
        end
        if observer
            observer.added_edge(from, to, new_relations_ids, info)
        end
    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:

  • the target graph

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



167
168
169
170
171
172
173
174
175
176
 
# File 'lib/roby/relations/graph.rb', line 167

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 



178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
 
# File 'lib/roby/relations/graph.rb', line 178

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:



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:



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 



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

def inspect; to_s 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:



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:



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:

  • the graph whose relations should be added to self



234
235
236
237
 
# File 'lib/roby/relations/graph.rb', line 234

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:

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

Raises:



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

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:

  • the origin vertex

  • the vertex whose reachability we want to test from ‘u’

Returns:



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

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



418
419
420
421
422
423
424
425
426
427
 
# File 'lib/roby/relations/graph.rb', line 418

def recursive_subsets
    result = Set.new
    queue = subsets.to_a.dup
    while !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.



392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
 
# File 'lib/roby/relations/graph.rb', line 392

def remove_relation(from, to)
    if !has_edge?(from, to)
        return
    end

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

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

#remove_vertex(object) ⇒ Object 



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

def remove_vertex(object)
    if !observer
        return super
    end

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

    removed_relations = Array.new
    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 



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

alias :remove_vertex! :remove_vertex

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

Moves a vertex relations onto another

Parameters:

  • the vertex whose relations are going to be moved

  • the vertex on which the relations will be added

  • (defaults to: true)

    whether ‘from’ should be removed from the graph after replacement



206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
 
# File 'lib/roby/relations/graph.rb', line 206

def replace_vertex(from, to, remove: true)
    edges = Array.new
    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:



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

def root_relation?; !parent end

#set_edge_info(from, to, info) ⇒ Object

Set the information of an object relation



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

def set_edge_info(from, to, info)
    if observer
        observer.updating_edge_info(from, to, self.class, info)
    end
    super
    if observer
        observer.updated_edge_info(from, to, self.class, info)
    end
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:



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:

  • the relation that should be added as a subset of self

Raises:

  • 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)
    if !relation.empty?
        raise ArgumentError, "cannot pass a non-empty graph to #superset_of"
    end

    relation.parent = self
    subsets << relation
end

#to_s ⇒ Object 



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

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:

  • the edge parent object

  • the edge child object

  • the new edge info

Returns:

  • true if the edge existed and false otherwise

API:

  • private



252
253
254
255
256
257
258
259
260
261
262
263
264
 
# File 'lib/roby/relations/graph.rb', line 252

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

    if !(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