class Roby::Relations::BidirectionalDirectedAdjacencyGraph

A RGL-compatible bidirectional version of the adjacency graph, with edge information

Unlike RGL classes, it does not raise if trying to query a vertex that is not in the graph, e.g.

graph.out_neighbours(random_object) -> Set.new

Attributes

backward_edges[R]
forward_edges_with_info[R]

Public Class Methods

[](*a) click to toggle source

Shortcut for creating a DirectedAdjacencyGraph:

RGL::DirectedAdjacencyGraph[1,2, 2,3, 2,4, 4,5].edges.to_a.to_s =>
  "(1-2)(2-3)(2-4)(4-5)"
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 24
def self.[](*a)
    result = new
    a.each_slice(2) do |u, v|
        result.add_edge(u, v)
    end
    result
end
new() click to toggle source

Returns a new empty DirectedAdjacencyGraph which has as its edgelist class the given class. The default edgelist class is Set, to ensure set semantics for edges and vertices.

If other graphs are passed as parameters their vertices and edges are added to the new graph.

# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 51
def initialize
    @forward_edges_with_info = IdentityHash.new
    @backward_edges = IdentityHash.new
end

Public Instance Methods

==(other) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 131
def ==(other)
    equal?(other)
end
add_edge(u, v, i = nil) click to toggle source

See MutableGraph#add_edge.

# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 274
def add_edge(u, v, i = nil)
    if u == v
        raise ArgumentError, "cannot add self-referencing edges"
    end

    u_out = (@forward_edges_with_info[u] ||= IdentityHash.new)
    @backward_edges[u] ||= IdentityHash.new
    @forward_edges_with_info[v] ||= IdentityHash.new
    v_in = (@backward_edges[v] ||= IdentityHash.new)

    u_out[v] = i
    v_in[u] = nil
end
add_vertex(v) click to toggle source

See MutableGraph#add_vertex.

If the vertex is already in the graph (using eql?), the method does nothing.

# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 267
def add_vertex(v)
    @forward_edges_with_info[v] ||= IdentityHash.new
    @backward_edges[v] ||= IdentityHash.new
end
adjacent_vertices(v)
Alias for: out_neighbours
clear() click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 333
def clear
    @forward_edges_with_info.clear
    @backward_edges.clear
end
dedupe(source) click to toggle source

Make sure that self and source share identical hashes when possible

# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 80
def dedupe(source)
    all_identical = (@forward_edges_with_info.size == source.forward_edges_with_info.size)
    @forward_edges_with_info.keys.each do |v|
        self_out_edges   = @forward_edges_with_info[v]
        source_out_edges = source.forward_edges_with_info[v]
        if self_out_edges.empty?
            all_indentical &&= source_out_edges.empty?
            @forward_edges_with_info[v] = @@identity_hash_singleton
        elsif self_out_edges == source_out_edges
            @forward_edges_with_info[v] = source_out_edges.freeze
        else
            all_identical = false
        end
    end

    if all_identical
        @forward_edges_with_info = source.forward_edges_with_info.freeze
        @backward_edges = source.backward_edges.freeze
        return
    end

    @backward_edges.keys.each do |v|
        self_in_edges   = @backward_edges[v]
        source_in_edges = source.backward_edges[v]
        if self_in_edges.empty?
            @backward_edges[v] = @@identity_hash_singleton
        elsif self_in_edges == source_in_edges
            @backward_edges[v] = source_in_edges.freeze
        end
    end
end
difference(other_graph, self_vertices, &mapping) click to toggle source

Returns a set of removed edges and a set of new edges between elements of vertices in self and other_graph.

If a block is given, vertices are vertices in graph and this block is used to translate them into vertices in other_graph. Otherwise, we assume that both graphs include the same vertices. other_graph can only be self itself in the first case, and if the set of vertices in self have no intersection with the set of vertices in other_graph)

The method returns [new, removed, updated], where new is the set of edges that are in self and not in other_graph, removed the set of edges that are in other_graph but not in self and updated the set of edges for which the info parameter changed between the two graphs.

Each set is a Set of pairs

[source_vertex, sink_vertex]

The vertices are vertices of self for new and updated, and vertices of other_graph for removed

# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 424
def difference(other_graph, self_vertices, &mapping)
    mapping ||= lambda { |v| v }
    other_vertices = Set.new

    new, removed, updated = Array.new, Array.new, Array.new

    seen_vertices    = IdentityHash.new
    seen_connections = IdentityHash.new
    for self_v in self_vertices
        other_v = mapping[self_v]
        other_vertices << other_v

        each_in_neighbour(self_v) do |self_parent|
            # If we already worked on +self_parent+, this connection has
            # already been taken into account
            next if seen_vertices.has_key?(self_parent)

            other_parent = mapping[self_parent]
            if other_graph.has_edge?(other_parent, other_v)
                if other_graph.edge_info(other_parent, other_v) != edge_info(self_parent, self_v)
                    updated << [self_parent, self_v]
                end
                (seen_connections[other_parent] ||= IdentityHash.new)[other_v] = nil
            else
                new << [self_parent, self_v]
            end
        end

        each_out_neighbour(self_v) do |self_child|
            # If we already worked on +self_child+, this connection has
            # already been taken into account
            next if seen_vertices.has_key?(self_child)

            other_child = mapping[self_child]
            if other_graph.has_edge?(other_v, other_child)
                if other_graph.edge_info(other_v, other_child) != edge_info(self_v, self_child)
                    updated << [self_v, self_child]
                end
                (seen_connections[other_v] ||= IdentityHash.new)[other_child] = nil
            else
                new << [self_v, self_child]
            end
        end

        seen_vertices[self_v] = nil
    end

    seen_vertices.clear
    for other_v in other_vertices
        other_graph.each_in_neighbour(other_v) do |other_parent|
            next if seen_vertices.has_key?(other_parent)
            if !(out_seen = seen_connections[other_parent]) || !out_seen.has_key?(other_v)
                removed << [other_parent, other_v]
            end
        end
        other_graph.each_out_neighbour(other_v) do |other_child|
            next if seen_vertices.has_key?(other_child)
            if !(out_seen = seen_connections[other_v]) || !out_seen.has_key?(other_child)
                removed << [other_v, other_child]
            end
        end
        seen_vertices[other_v] = nil
    end

    return new, removed, updated
end
directed?() click to toggle source

Returns true.

# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 239
def directed?
    true
end
each_adjacent(v, &b)
Alias for: each_out_neighbour
each_edge() { |u, v, info| ... } click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 118
def each_edge
    return enum_for(__method__) if !block_given?
    @forward_edges_with_info.each do |u, out_edges|
        out_edges.each do |v, info|
            yield(u, v, info)
        end
    end
end
each_in_neighbour(v, &b) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 191
def each_in_neighbour(v, &b)
    if v_in = @backward_edges[v]
        v_in.each_key(&b)
    elsif !block_given?
        enum_for(__method__, v)
    end
end
each_out_neighbour(v, &b) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 170
def each_out_neighbour(v, &b)
    if v_out = @forward_edges_with_info[v]
        v_out.each_key(&b)
    elsif !block_given?
        enum_for(__method__, v)
    end
end
Also aliased as: each_adjacent
each_vertex(&b) click to toggle source

Iterator for the keys of the vertices list hash.

# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 114
def each_vertex(&b)
    @forward_edges_with_info.each_key(&b)
end
edge_info(parent, child) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 338
def edge_info(parent, child)
    @forward_edges_with_info.fetch(parent).fetch(child)
rescue KeyError
    raise ArgumentError, "no edge #{parent} => #{child} in #{self}"
end
eql?(other) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 139
def eql?(other)
    equal?(other)
end
has_edge?(u, v) click to toggle source

Complexity is O(1), if a Set is used as adjacency list. Otherwise, complexity is O(out_degree(v)).


MutableGraph interface.

# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 256
def has_edge? (u, v)
    if v_out = @forward_edges_with_info[u]
        v_out.has_key?(v)
    end
end
has_vertex?(v) click to toggle source

Complexity is O(1), because the vertices are kept in a Hash containing as values the lists of adjacent vertices of v.

# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 246
def has_vertex?(v)
    @forward_edges_with_info.has_key?(v)
end
hash() click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 135
def hash
    object_id
end
in_degree(v) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 203
def in_degree(v)
    if v_in = @backward_edges[v]
        v_in.size
    else 0
    end
end
in_neighbours(v) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 199
def in_neighbours(v)
    each_in_neighbour(v).to_a
end
initialize_copy(orig) click to toggle source

Copy internal vertices_dict

Calls superclass method
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 58
def initialize_copy(orig)
    super
    @forward_edges_with_info, forward_edges_with_info =
        IdentityHash.new, @forward_edges_with_info
    forward_edges_with_info.each do |u, out_edges|
        mapped_out_edges = IdentityHash.new
        out_edges.each do |v, info|
            info = info.dup if info
            mapped_out_edges[v] = info
        end
        @forward_edges_with_info[u] = mapped_out_edges
    end

    @backward_edges, backward_edges =
        IdentityHash.new, @backward_edges
    backward_edges.each do |v, in_edges|
        @backward_edges[v] = in_edges.dup
    end
end
leaf?(v) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 219
def leaf?(v)
    out_degree(v) == 0
end
merge(graph) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 314
def merge(graph)
    g_forward  = graph.instance_variable_get(:@forward_edges_with_info)
    g_backward = graph.instance_variable_get(:@backward_edges)
    g_forward.each do |g_u, g_out_edges|
        if !(out_edges = @forward_edges_with_info[g_u])
            @forward_edges_with_info[g_u] = g_out_edges.dup
        else
            out_edges.merge!(g_out_edges)
        end
    end
    g_backward.each do |g_v, g_in_edges|
        if !(in_edges = @backward_edges[g_v])
            @backward_edges[g_v] = g_in_edges.dup
        else
            in_edges.merge!(g_in_edges)
        end
    end
end
move_edges(source, target) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 147
def move_edges(source, target)
    source_out = @forward_edges_with_info[source]
    return if !source_out
    source_in = @backward_edges[source]

    target_out = (@forward_edges_with_info[target] ||= IdentityHash.new)
    target_in  = (@backward_edges[target] ||= IdentityHash.new)

    source_out.each_key do |child|
        child_in = @backward_edges[child]
        child_in.delete(source)
        child_in[target] = nil
    end
    source_in.each_key do |parent|
        child_out = @forward_edges_with_info[parent]
        child_out[target] = child_out.delete(source)
    end
    target_out.merge!(source_out)
    target_in.merge!(source_in)
    source_out.clear
    source_in.clear
end
num_edges() click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 231
def num_edges
    @forward_edges_with_info.each_value.inject(0) do |count, out_edges|
        count + out_edges.size
    end
end
num_vertices() click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 227
def num_vertices
    @forward_edges_with_info.size
end
out_degree(v) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 184
def out_degree(v)
    if v_out = @forward_edges_with_info[v]
        v_out.size
    else 0
    end
end
out_neighbours(v) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 179
def out_neighbours(v)
    each_out_neighbour(v).to_a
end
Also aliased as: adjacent_vertices
remove_edge(u, v) click to toggle source

See MutableGraph::remove_edge.

# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 306
def remove_edge(u, v)
    u_out = @forward_edges_with_info[u]
    if u_out
        u_out.delete(v)
        @backward_edges[v].delete(u)
    end
end
remove_vertex(v) click to toggle source

See MutableGraph#remove_vertex.

# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 290
def remove_vertex(v)
    v_out = @forward_edges_with_info.delete(v)
    return if !v_out
    v_in  = @backward_edges.delete(v)

    v_out.each_key do |child|
        @backward_edges[child].delete(v)
    end
    v_in.each_key do |parent|
        @forward_edges_with_info[parent].delete(v)
    end
    return !v_out.empty? || !v_in.empty?
end
replace(g) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 210
def replace(g)
    @forward_edges_with_info.replace(g.instance_variable_get(:@forward_edges_with_info))
    @backward_edges.replace(g.instance_variable_get(:@backward_edges))
end
reverse() click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 354
def reverse
    result = dup
    result.reverse!
    result
end
reverse!() click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 360
def reverse!
    @forward_edges_with_info.each do |u, out_edges|
        out_edges.each do |v, info|
            @backward_edges[v][u] = info
            out_edges[v] = nil
        end
    end
    @forward_edges_with_info, @backward_edges =
        @backward_edges, @forward_edges_with_info
end
root?(v) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 215
def root?(v)
    in_degree(v) == 0
end
same_structure?(graph) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 143
def same_structure?(graph)
    graph.instance_variable_get(:@backward_edges) == backward_edges
end
set_edge_info(parent, child, info) click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 344
def set_edge_info(parent, child, info)
    parent_out = @forward_edges_with_info.fetch(parent)
    if !parent_out.has_key?(child)
        raise ArgumentError, "no edge #{parent} => #{child} in #{self}"
    end
    parent_out[child] = info
rescue KeyError
    raise ArgumentError, "no edge #{parent} => #{child} in #{self}"
end
to_a() click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 127
def to_a
    @forward_edges_with_info.keys
end
verify_consistency() click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 373
def verify_consistency
    @forward_edges_with_info.each do |v, out_edges|
        if !@backward_edges.has_key?(v)
            raise Inconsistent, "#{v} has an entry in the forward-edge set, but not in the backward-edge"
        end

        out_edges.each do |out_e, _info|
            if !@backward_edges.has_key?(out_e)
                raise Inconsistent, "#{out_e} is listed as an out-neighbour of #{v} but #{out_e} is not included in the graph"
            elsif !@backward_edges[out_e].has_key?(v)
                raise Inconsistent, "#{out_e} is listed as an out-neighbour of #{v} but #{out_e} does not list it as in-neighbour"
            end
        end
    end
    @backward_edges.each do |v, in_edges|
        if !@forward_edges_with_info.has_key?(v)
            raise Inconsistent, "#{v} has an entry in the forward-edge set, but not in the backward-edge"
        end

        in_edges.each do |in_e, _|
            if !@forward_edges_with_info[in_e]
                raise Inconsistent, "#{in_e} is listed as an in-neighbour of #{v} but is not included in the graph"
            elsif !@forward_edges_with_info[in_e].has_key?(v)
                raise Inconsistent, "#{in_e} is listed as an in-neighbour of #{v} but #{in_e} does not list it as out-neighbour"
            end
        end
    end
end
vertices() click to toggle source
# File lib/roby/relations/bidirectional_directed_adjacency_graph.rb, line 223
def vertices
    @forward_edges_with_info.keys
end