Class: Roby::Relations::BidirectionalDirectedAdjacencyGraph

Inherits:
Object
  • Object
show all
Includes:
RGL::MutableGraph, DRoby::V5::BidirectionalGraphDumper
Defined in:
lib/roby/relations/bidirectional_directed_adjacency_graph.rb,
lib/roby/droby/enable.rb

Overview

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

Direct Known Subclasses

Graph

Defined Under Namespace

Classes: IdentityHash, Inconsistent

Constant Summary collapse

@@identity_hash_singleton =

This singleton is used in #dedupe to have only one single empty hash

IdentityHash.new

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from DRoby::V5::BidirectionalGraphDumper

#droby_dump

Constructor Details

#initialize ⇒ BidirectionalDirectedAdjacencyGraph

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.



51
52
53
54
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 51

def initialize
    @forward_edges_with_info = IdentityHash.new
    @backward_edges = IdentityHash.new
end

Instance Attribute Details

#backward_edges ⇒ Object (readonly)

Returns the value of attribute backward_edges.



17
18
19
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 17

def backward_edges
  @backward_edges
end

#forward_edges_with_info ⇒ Object (readonly)

Returns the value of attribute forward_edges_with_info.



16
17
18
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 16

def forward_edges_with_info
  @forward_edges_with_info
end

Class Method Details

.[](*a) ⇒ Object

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)"



24
25
26
27
28
29
30
 
# 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

Instance Method Details

#==(other) ⇒ Object 



131
132
133
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 131

def ==(other)
    equal?(other)
end

#add_edge(u, v, i = nil) ⇒ Object

See MutableGraph#add_edge.



274
275
276
277
278
279
280
281
282
283
284
285
286
 
# 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) ⇒ Object

See MutableGraph#add_vertex.

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



267
268
269
270
 
# 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

#clear ⇒ Object 



333
334
335
336
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 333

def clear
    @forward_edges_with_info.clear
    @backward_edges.clear
end

#dedupe(source) ⇒ Object

Make sure that self and source share identical hashes when possible



80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
# 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) ⇒ Object

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



424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
 
# 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? ⇒ Boolean

Returns true.

Returns:

  • (Boolean) 


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

def directed?
    true
end

#each_edge ⇒ Object 



118
119
120
121
122
123
124
125
 
# 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) ⇒ Object 



191
192
193
194
195
196
197
 
# 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) ⇒ Object Also known as: each_adjacent 



170
171
172
173
174
175
176
 
# 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

#each_vertex(&b) ⇒ Object

Iterator for the keys of the vertices list hash.



114
115
116
 
# 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) ⇒ Object 



338
339
340
341
342
 
# 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) ⇒ Boolean

Returns:

  • (Boolean) 


139
140
141
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 139

def eql?(other)
    equal?(other)
end

#has_edge?(u, v) ⇒ Boolean

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

MutableGraph interface.

Returns:

  • (Boolean) 


256
257
258
259
260
 
# 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) ⇒ Boolean

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

Returns:

  • (Boolean) 


246
247
248
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 246

def has_vertex?(v)
    @forward_edges_with_info.has_key?(v)
end

#hash ⇒ Object 



135
136
137
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 135

def hash
    object_id
end

#in_degree(v) ⇒ Object 



203
204
205
206
207
208
 
# 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) ⇒ Object 



199
200
201
 
# 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) ⇒ Object

Copy internal vertices_dict



58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
# 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) ⇒ Boolean

Returns:

  • (Boolean) 


219
220
221
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 219

def leaf?(v)
    out_degree(v) == 0
end

#merge(graph) ⇒ Object 



314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
 
# 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) ⇒ Object 



147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
 
# 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 ⇒ Object 



231
232
233
234
235
 
# 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 ⇒ Object 



227
228
229
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 227

def num_vertices
    @forward_edges_with_info.size
end

#out_degree(v) ⇒ Object 



184
185
186
187
188
189
 
# 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) ⇒ Object Also known as: adjacent_vertices 



179
180
181
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 179

def out_neighbours(v)
    each_out_neighbour(v).to_a
end

#remove_edge(u, v) ⇒ Object

See MutableGraph::remove_edge.



306
307
308
309
310
311
312
 
# 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) ⇒ Object

See MutableGraph#remove_vertex.



290
291
292
293
294
295
296
297
298
299
300
301
302
 
# 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) ⇒ Object 



210
211
212
213
 
# 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 ⇒ Object 



354
355
356
357
358
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 354

def reverse
    result = dup
    result.reverse!
    result
end

#reverse! ⇒ Object 



360
361
362
363
364
365
366
367
368
369
 
# 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) ⇒ Boolean

Returns:

  • (Boolean) 


215
216
217
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 215

def root?(v)
    in_degree(v) == 0
end

#same_structure?(graph) ⇒ Boolean

Returns:

  • (Boolean) 


143
144
145
 
# 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) ⇒ Object 



344
345
346
347
348
349
350
351
352
 
# 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 ⇒ Object 



127
128
129
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 127

def to_a
    @forward_edges_with_info.keys
end

#verify_consistency ⇒ Object 



373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
 
# 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 ⇒ Object 



223
224
225
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 223

def vertices
    @forward_edges_with_info.keys
end