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

The class guarantees that there can’t be duplicate edges

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.



76
77
78
79
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 76

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

Instance Attribute Details

#backward_edges ⇒ Hash<Object,Hash<Object,Object>> (readonly)

Set of in neighbours for a particular vertex

The hash value associated with the in-neighbour is not used. A hash is used for optimization only

That is,

in_neighbours = backward_edges[target]
in_neighbours.keys # => list of in neighbours for 'target'
in_neighbours.key?(v) # test if 'v' is a in-neighbour of target
in_neighbours[v] # => always nil

Returns:



42
43
44
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 42

def backward_edges
  @backward_edges
end

#forward_edges_with_info ⇒ Hash<Object,Hash<Object,Object>> (readonly)

Mapping from a vertex to the association of out neighbours

That is,

out_neighbours = forward_edges_with_info[source]
out_neighbours.keys # => list of out neighbours for 'source'
out_neighbours[target] # => info for the source -> target edge

Returns:



28
29
30
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 28

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



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

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 



160
161
162
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 160

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

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

See MutableGraph#add_edge.

Raises:

  • (ArgumentError) 


299
300
301
302
303
304
305
306
307
308
309
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 299

def add_edge(u, v, i = nil)
    raise ArgumentError, "cannot add self-referencing edges" if u == v

    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.



292
293
294
295
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 292

def add_vertex(v)
    @forward_edges_with_info[v] ||= IdentityHash.new
    @backward_edges[v] ||= IdentityHash.new
end

#clear ⇒ Object 



357
358
359
360
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 357

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



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
134
135
136
137
138
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 105

def dedupe(source)
    all_identical = (@forward_edges_with_info.size ==
                     source.forward_edges_with_info.size)
    # Use #keys.each instead of #each_key as we are modifying in-place
    @forward_edges_with_info.keys.each do |v| # rubocop:disable Style/HashEachMethods
        self_out_edges   = @forward_edges_with_info[v]
        source_out_edges = source.forward_edges_with_info[v]
        if self_out_edges.empty?
            all_identical &&= 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

    # Use #keys.each instead of #each_key as we are modifying in-place
    @backward_edges.keys.each do |v| # rubocop:disable Style/HashEachMethods
        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



472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 472

def difference(other_graph, self_vertices, &mapping)
    mapping ||= ->(v) { v }
    other_vertices = Set.new

    new = []
    removed = []
    updated = []

    seen_vertices    = IdentityHash.new
    seen_connections = IdentityHash.new
    self_vertices.each do |self_v|
        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.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.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
    other_vertices.each do |other_v|
        other_graph.each_in_neighbour(other_v) do |other_parent|
            next if seen_vertices.key?(other_parent)

            if !(out_seen = seen_connections[other_parent]) || !out_seen.key?(other_v)
                removed << [other_parent, other_v]
            end
        end
        other_graph.each_out_neighbour(other_v) do |other_child|
            next if seen_vertices.key?(other_child)

            if !(out_seen = seen_connections[other_v]) || !out_seen.key?(other_child)
                removed << [other_v, other_child]
            end
        end
        seen_vertices[other_v] = nil
    end

    [new, removed, updated]
end

#directed? ⇒ Boolean

Returns true.

Returns:

  • (Boolean) 


266
267
268
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 266

def directed?
    true
end

#each_edge ⇒ Object 



146
147
148
149
150
151
152
153
154
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 146

def each_edge
    return enum_for(__method__) unless 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 



221
222
223
224
225
226
227
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 221

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 



199
200
201
202
203
204
205
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 199

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.



142
143
144
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 142

def each_vertex(&b)
    @forward_edges_with_info.each_key(&b)
end

#edge_info(parent, child) ⇒ Object 



362
363
364
365
366
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 362

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) 


168
169
170
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 168

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

#freeze ⇒ Object 



439
440
441
442
443
444
445
446
447
448
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 439

def freeze
    return if frozen?

    @forward_edges_with_info.transform_values!(&:freeze)
    @forward_edges_with_info.freeze
    @backward_edges.transform_values!(&:freeze)
    @backward_edges.freeze

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


283
284
285
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 283

def has_edge?(u, v)
    @forward_edges_with_info[u]&.key?(v)
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) 


273
274
275
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 273

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

#hash ⇒ Object 



164
165
166
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 164

def hash
    object_id
end

#in_degree(v) ⇒ Object 



233
234
235
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 233

def in_degree(v)
    @backward_edges[v]&.size || 0
end

#in_neighbours(v) ⇒ Object 



229
230
231
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 229

def in_neighbours(v)
    each_in_neighbour(v).to_a
end

#initialize_copy(orig) ⇒ Object

Copy internal vertices_dict



83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 83

def initialize_copy(orig)
    super
    forward_edges_with_info = @forward_edges_with_info
    @forward_edges_with_info = IdentityHash.new
    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
    @backward_edges = IdentityHash.new
    backward_edges.each do |v, in_edges|
        @backward_edges[v] = in_edges.dup
    end
end

#leaf?(v) ⇒ Boolean

Returns:

  • (Boolean) 


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

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

#merge(graph) ⇒ Object 



338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 338

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 



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

def move_edges(source, target)
    source_out = @forward_edges_with_info[source]
    return unless 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 



258
259
260
261
262
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 258

def num_edges
    @forward_edges_with_info.each_value.inject(0) do |count, out_edges|
        count + out_edges.size
    end
end

#num_vertices ⇒ Object 



254
255
256
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 254

def num_vertices
    @forward_edges_with_info.size
end

#out_degree(v) ⇒ Object 



213
214
215
216
217
218
219
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 213

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 



208
209
210
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 208

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

#propagate_transitive_closure(from, to) ⇒ Object

Incremental update of a transitive closure, adding the from -> to edge



546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 546

def propagate_transitive_closure(from, to)
    from_in_neighbours = @backward_edges[from]
    # Adds 'from_in_neighbours' to 'to's in neighbors
    @backward_edges[to].merge!(from_in_neighbours)
    @forward_edges_with_info[to].each_key do |v|
        # Adds 'from_in_neighbours' to 'to_out_neighbors's in neighbors
        @backward_edges[v].merge!(from_in_neighbours)

        # Adds 'from' to 'to_out_neighbors's in neighbors
        v_in = (@backward_edges[v] ||= IdentityHash.new)
        @forward_edges_with_info[v] ||= IdentityHash.new
        v_in[from] = nil
    end

    to_out_neighbours = @forward_edges_with_info[to]
    # Adds 'to_out_neighbors' to 'from's out neighbors
    @forward_edges_with_info[from].merge!(to_out_neighbours)
    @backward_edges[from].each_key do |u|
        # Adds 'to_out_neighbors' to 'from_in_neighbors's out neighbors
        @forward_edges_with_info[u].merge!(to_out_neighbours)

        # Adds 'to' to 'from_in_neighbors's out neighbors
        u_out = (@forward_edges_with_info[u] ||= IdentityHash.new)
        @backward_edges[u] ||= IdentityHash.new
        u_out[to] = nil
    end
end

#remove_edge(u, v) ⇒ Object

See MutableGraph::remove_edge.



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

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.



313
314
315
316
317
318
319
320
321
322
323
324
325
326
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 313

def remove_vertex(v)
    v_out = @forward_edges_with_info.delete(v)
    return unless 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
    !v_out.empty? || !v_in.empty?
end

#replace(g) ⇒ Object 



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

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 



379
380
381
382
383
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 379

def reverse
    result = dup
    result.reverse!
    result
end

#reverse! ⇒ Object 



385
386
387
388
389
390
391
392
393
394
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 385

def reverse!
    @forward_edges_with_info.each do |u, out_edges|
        out_edges.each do |v, info|
            @backward_edges[v][u] = info
        end
        out_edges.transform_values! { nil }
    end
    @forward_edges_with_info, @backward_edges =
        @backward_edges, @forward_edges_with_info
end

#root?(v) ⇒ Boolean

Returns:

  • (Boolean) 


242
243
244
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 242

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

#same_structure?(graph) ⇒ Boolean

Returns:

  • (Boolean) 


172
173
174
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 172

def same_structure?(graph)
    graph.instance_variable_get(:@backward_edges) == backward_edges
end

#set_edge_info(parent, child, info) ⇒ Object 



368
369
370
371
372
373
374
375
376
377
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 368

def set_edge_info(parent, child, info)
    parent_out = @forward_edges_with_info.fetch(parent)
    unless parent_out.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 



156
157
158
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 156

def to_a
    @forward_edges_with_info.keys
end

#verify_consistency ⇒ Object 



398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 398

def verify_consistency
    @forward_edges_with_info.each do |v, out_edges|
        unless @backward_edges.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.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].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|
        unless @forward_edges_with_info.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].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 



250
251
252
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 250

def vertices
    @forward_edges_with_info.keys
end