class Roby::Relations::Graph

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 {#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

Attributes

observer[R]

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.

parent[RW]

The relation parent (if any)

@see superset_of recursive_subsets

subsets[R]

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 superset_of recursive_subsets

Public Class Methods

new( 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) click to toggle source

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

# 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

Public Instance Methods

add_edge(a, b, info) click to toggle source

Add an edge between two objects

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

@return true if a new edge was created

# 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) click to toggle source

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.

# 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) click to toggle source

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

@param [Graph] graph the target graph @param [Hash<Object,Object>] a mapping from the subgraph vertices

in self to the corresponding vertices in the target graph
# 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) click to toggle source
# 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) click to toggle source
# 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) click to toggle source
# 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) click to toggle source
# 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) click to toggle source

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

See superset_of for a description of the parent mechanism

# File lib/roby/relations/graph.rb, line 452
def has_edge_in_hierarchy?(source, target)
    root_graph.has_edge?(source, target)
end
include?(object) click to toggle source
# 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() click to toggle source
# File lib/roby/relations/graph.rb, line 155
def inspect; to_s end
linked?(parent, child) click to toggle source
# 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) click to toggle source

@deprecated use {#has_edge_in_hierarchy?}

# 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) click to toggle source

Add the vertices and edges of a graph in self

@param [Graph] graph the graph whose relations should be added to

self
# File lib/roby/relations/graph.rb, line 234
def merge!(graph)
    merge(graph)
    graph.clear
end
merge_info(from, to, old, new) click to toggle source

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

It is safe to raise from within this method

@return [nil,Object] if nil, the update is aborted. If non-nil,

it is the new information
# 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) click to toggle source

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.

@param [Object] u the origin vertex @param [Object] v the vertex whose reachability we want to test

from 'u'
# 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() click to toggle source

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

# 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) click to toggle source
# 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) click to toggle source

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.

# 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) click to toggle source
# 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
Also aliased as: remove_vertex!
remove_vertex!(object)
Alias for: remove_vertex
replace_vertex(from, to, remove: true) click to toggle source

Moves a vertex relations onto another

@param [Object] from the vertex whose relations are going to be

moved

@param [Object] to the vertex on which the relations will be

added

@param [Boolean] remove whether 'from' should be removed from the

graph after replacement
# 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() click to toggle source

The root in this graph's hierarchy

# File lib/roby/relations/graph.rb, line 441
def root_graph
    g = self
    while g.parent
        g = g.parent
    end
    g
end
root_relation?() click to toggle source

True if this relation does not have a parent

# File lib/roby/relations/graph.rb, line 430
def root_relation?; !parent end
set_edge_info(from, to, info) click to toggle source

Set the information of an object relation

# 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() click to toggle source
# 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) click to toggle source

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

# File lib/roby/relations/graph.rb, line 436
def subset?(relation)
    self.eql?(relation) || subsets.any? { |subrel| subrel.subset?(relation) }
end
superset_of(relation) click to toggle source

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)

@param [Graph] relation the relation that should be added as a

subset of self

@raise [ArgumentError] if 'relation' is not empty

# 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() click to toggle source
# 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) click to toggle source

@api private

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

@param from the edge parent object @param to the edge child object @param info the new edge info @return [Boolean] true if the edge existed and false otherwise

# 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