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
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.
The relation parent (if any)
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
Public Class Methods
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. Seesuperset_of
. distributed
-
if this relation graph should be seen by remote hosts
Roby::Relations::BidirectionalDirectedAdjacencyGraph::new
# 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 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
Roby::Relations::BidirectionalDirectedAdjacencyGraph#add_edge
# 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 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 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
# 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
# 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
# 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
# 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
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
# 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
# File lib/roby/relations/graph.rb, line 155 def inspect; to_s end
# 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
# 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
@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
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
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
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
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
# 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 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
Roby::Relations::BidirectionalDirectedAdjacencyGraph#remove_vertex
# 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
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
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
True if this relation does not have a parent
# File lib/roby/relations/graph.rb, line 430 def root_relation?; !parent end
Set
the information of an object relation
Roby::Relations::BidirectionalDirectedAdjacencyGraph#set_edge_info
# 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
# File lib/roby/relations/graph.rb, line 515 def size Roby.warn_deprecated "Graph#size is deprecated, use #num_vertices instead" num_vertices end
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
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
# File lib/roby/relations/graph.rb, line 151 def to_s "#{self.class.name}:#{object_id.to_s(16)}" end
@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
# 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