Class: Roby::Relations::BidirectionalDirectedAdjacencyGraph

Inherits:
Object
  • Object
show all
Includes:
RGL::Graph, 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

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.



79
80
81
82
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 79

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 in_neighbours.keys # => list of in neighbours for 'target' in_neighbours.key?(v) # test if 'v' is a in-neighbour of target in_neighbours # => always nil

Returns:



44
45
46
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 44

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 out_neighbours.keys # => list of out neighbours for 'source' out_neighbours # => info for the source -> target edge

Returns:



30
31
32
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 30

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



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

def self.[](*a)
    result = new
    (a.size / 2).times do |i|
        result.add_edge(a[i * 2], a[i * 2 + 1])
    end
    result.add_vertex(a[-1]) if a.size.odd?
    result
end

Instance Method Details

#==(other) ⇒ Object 



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

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

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

See MutableGraph#add_edge.

Raises:

  • (ArgumentError) 


302
303
304
305
306
307
308
309
310
311
312
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 302

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_or_update_edge(u, v, _init_edge_value = nil) {|edge_value| ... } ⇒ Object

Add an edge if it does not exist, or offer to update its edge info if it does

Parameters:

  • u —

    the source vertex of the edge

  • v —

    the target vertex of the edge

Yield Parameters:

  • edge_value —

    the existing edge value if the edge already exists, nil otherwise

Yield Returns:

  • the value to use as the new edge value

Raises:

  • (ArgumentError) 


322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 322

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

    u_out = (@forward_edges_with_info[u] ||= IdentityHash.new)
    if u_out.key?(v)
        u_out[v] = yield(u_out[v]) if block_given?
        return
    end

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

    info = yield if block_given?
    u_out[v] = info
    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.



295
296
297
298
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 295

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

#clear ⇒ Object 



406
407
408
409
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 406

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



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
139
140
141
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 108

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

#delete_vertex_if ⇒ Object 



340
341
342
343
344
345
346
347
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 340

def delete_vertex_if
    @forward_edges_with_info.delete_if do |v, v_out|
        next unless yield(v)

        remove_vertex_relations!(v, v_out)
        true
    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



521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
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
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 521

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) 


269
270
271
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 269

def directed?
    true
end

#each_edge ⇒ Object 



149
150
151
152
153
154
155
156
157
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 149

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 



224
225
226
227
228
229
230
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 224

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 



202
203
204
205
206
207
208
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 202

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.



145
146
147
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 145

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

#edge_info(parent, child) ⇒ Object 



411
412
413
414
415
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 411

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) 


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

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

#freeze ⇒ Object 



488
489
490
491
492
493
494
495
496
497
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 488

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) 


286
287
288
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 286

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) 


276
277
278
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 276

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

#hash ⇒ Object 



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

def hash
    object_id
end

#in_degree(v) ⇒ Object 



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

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

#in_neighbours(v) ⇒ Object 



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

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

#initialize_copy(orig) ⇒ Object

Copy internal vertices_dict



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

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) 


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

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

#merge(graph) ⇒ Object 



387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 387

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 



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

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 



261
262
263
264
265
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 261

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

#num_vertices ⇒ Object 



257
258
259
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 257

def num_vertices
    @forward_edges_with_info.size
end

#out_degree(v) ⇒ Object 



216
217
218
219
220
221
222
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 216

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 



211
212
213
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 211

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



595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 595

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.



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

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.



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

def remove_vertex(v)
    v_out = @forward_edges_with_info.delete(v)
    return unless v_out

    v_in = remove_vertex_relations!(v, v_out)
    !v_in.empty? || !v_out.empty?
end

#remove_vertex_relations!(v, v_out) ⇒ Object

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Delete the vertex in all relations it is part of, but without updating the vertex itself

It is a helper for methods that remove vertices from the graph



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

def remove_vertex_relations!(v, 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_in
end

#replace(g) ⇒ Object 



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

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 



428
429
430
431
432
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 428

def reverse
    result = dup
    result.reverse!
    result
end

#reverse! ⇒ Object 



434
435
436
437
438
439
440
441
442
443
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 434

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) 


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

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

#same_structure?(graph) ⇒ Boolean

Returns:

  • (Boolean) 


175
176
177
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 175

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

#set_edge_info(parent, child, info) ⇒ Object 



417
418
419
420
421
422
423
424
425
426
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 417

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 



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

def to_a
    @forward_edges_with_info.keys
end

#verify_consistency ⇒ Object 



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
 
# File 'lib/roby/relations/bidirectional_directed_adjacency_graph.rb', line 447

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 



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

def vertices
    @forward_edges_with_info.keys
end