Class: Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/graph.rb,
lib/graphs/gdf.rb,
lib/graphs/json.rb

Overview

A graph with nodes and edges

Defined Under Namespace

Classes: Edge, EdgeArray, Node, NodeArray

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(nodes = nil, edges = nil) ⇒ Graph

Returns a new instance of Graph.

Parameters:

  • nodes (Array) (defaults to: nil) —

    Nodes of the graph

  • edges (Array) (defaults to: nil) —

    Edges of the graph



182
183
184
185
186
 
# File 'lib/graph.rb', line 182

def initialize(nodes=nil, edges=nil)
    @nodes = NodeArray.new(nodes || [])
    @edges = EdgeArray.new(edges || [])
    @attrs = { :directed => true }
end

Instance Attribute Details

#attrs ⇒ Hash

By default, the graph is directed, i.e. the :directed attribute is set to true.

Returns:

  • (Hash) —

    attributes of the current Graph (e.g. author, description, …).



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
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
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
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
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
 
# File 'lib/graph.rb', line 13

class Graph

    # Return a new Graph which is the intersection of every given graph.
    # Each node of the intersection is in every given graph (idem for edges).
    # The last argument may be a hash of options.
    # @option options [Boolean] :same_fields use only fields which are in every
    # graph to compare nodes/edges to perform the intersection
    # @see Graph#&
    # @see Graph::union
    # @see Graph::xor
    def Graph::intersection(*graphs)
         perform_graphs_group_op(*graphs, &:&)
    end

    # Return a new Graph which is the union of every given graph.
    # Each node of the union is in one or more given graph(s) (idem for edges).
    # The last argument may be a hash of options.
    # @option options [Boolean] :same_fields use only fields which are in every
    # graph to compare nodes/edges to perform the union
    # @see Graph#|
    # @see Graph::intersection
    # @see Graph::xor
    def Graph::union(*graphs)
        perform_graphs_group_op(*graphs, &:|)
    end

    # Perform a XOR operation on all given graphs, and returns the result.
    # The last argument may be a hash of options.
    # @option options [Boolean] :same_fields use only fields which are in every
    # graph to compare nodes/edges to perform the XOR operation
    # @see Graph#^
    # @see Graph::union
    # @see Graph::intersection
    def Graph::xor(*graphs)
        perform_graphs_group_op(*graphs, &:^)
    end

    # A node. This class is just a wrapper around a hash of
    # attributes since in version <= 0.1.5 nodes were simple hashes
    class Node

        attr_accessor :attrs

        def initialize(attrs=nil)
            @attrs = attrs || {}
        end

        # compare two nodes
        # @param other [Node]
        def ==(other)
            return false if !other.is_a?(Node)

            @attrs == other.attrs
        end

        def update(h)
            Node.new super(h)
        end

        def method_missing(method, *args, &block)

            return @attrs[method.to_sym] if @attrs.has_key? method.to_sym
            return @attrs[method.to_s] if @attrs.has_key? method.to_s

            @attrs.send(method, *args, &block)
        end

    end

    # An edge. This class is just a wrapper around a hash of
    # attributes since in version <= 0.1.5 edges were simple hashes
    class Edge

        attr_accessor :attrs

        def initialize(attrs=nil)
            @attrs = attrs || {}
        end

        # compare two edges
        # @param other [Edge]
        def ==(other)
            return false if !other.is_a?(Edge)

            @attrs == other.attrs
        end

        def update(h)
            Edge.new super(h)
        end

        def method_missing(method, *args, &block)

            return @attrs[method.to_sym] if @attrs.has_key? method.to_sym
            return @attrs[method.to_s] if @attrs.has_key? method.to_s

            @attrs.send(method, *args, &block)
        end

    end

    # An array of Node objects
    class NodeArray < Array

        def initialize(li)
            nodes = li.map { |n| n.is_a?(Node) ? n : Node.new(n) }
            super(nodes)
            @defaults = {}
        end

        # Set some default values for current elements.
        # @note This method can be called multiple times.
        # @example Set all nodes's 'created-at' value to '2012-05-03'
        #   myNodeList.set_default({'created-at'=>'2012-05-03'})
        def set_default(dict)
            @defaults.update(dict)
            self.map! { |e| e.update(@defaults) }
        end

        # Add the given node at the end of the list
        # @param n [Node]
        def push(n)
            if (!n.is_a?(Hash) && !n.is_a?(Node))
                raise TypeError.new "#{n.inspect} is not an Hash nor a Node!"
            end

            n = Node.new(n) if (n.is_a?(Hash))

            super(n.clone.update(@defaults))
        end

    end

    # An array of Edge objects
    class EdgeArray < Array
        def initialize(li)
            edges = li.map { |n| n.is_a?(Edge) ? n : Edge.new(n) }
            super(edges)
            @defaults = {}
        end

        # Set some default values for current elements.
        # @note This method can be called multiple times.
        # @example Set all edges's 'created-at' value to '2012-05-03'
        #   myEdgeList.set_default({'created-at'=>'2012-05-03'})
        # @param dict [Hash]
        def set_default(dict)
            @defaults.update(dict)
            self.map! { |e| e.update(@defaults) }
        end

        # Add the given edge at the end of the list
        # @param e [Edge]
        def push(e)
            if (!e.is_a?(Hash) && !e.is_a?(Edge))
                raise TypeError.new "#{e.inspect} is not an Hash nor an Edge!"
            end

            e = Edge.new(e) if (e.is_a?(Hash))

            super(e.clone.update(@defaults))
        end

    end

    attr_accessor :nodes, :edges, :attrs

    # @param nodes [Array] Nodes of the graph
    # @param edges [Array] Edges of the graph
    def initialize(nodes=nil, edges=nil)
        @nodes = NodeArray.new(nodes || [])
        @edges = EdgeArray.new(edges || [])
        @attrs = { :directed => true }
    end

    # Test if current graph has same nodes and edges as the other
    # graph.
    # @param other [Graph]
    def ==(other)
        if (!other.is_a?(Graph))
            return false
        end
        (self.nodes === other.nodes) && (self.edges === other.edges)
    end

    # Perform an intersection between the current graph and the other.
    # Returns a new Graph which nodes are both in the current graph and
    # the other (idem for edges).
    # @param other [Graph]
    # @see Graph#^
    # @see Graph::intersection
    def &(other)
        if (!other.is_a?(Graph))
            return nil
        end

        nodes = @nodes & other.nodes
        edges = @edges & other.edges

        Graph.new(nodes, edges)
    end

    # Perform a XOR operation between the current graph and the other. Returns a
    # new Graph which nodes are in the current graph or in the other, but not in
    # both (idem for edges).
    # @param other [Graph]
    # @see Graph#&
    def ^(other)
        if (!other.is_a?(Graph))
            return nil
        end

        nodes = (@nodes + other.nodes) - (@nodes & other.nodes)
        edges = (@edges + other.edges) - (@edges & other.edges)

        Graph.new(nodes, edges)
    end

    # Add two graphs, keeping duplicate nodes and edges
    # @param other [Graph]
    def +(other)
        if (!other.is_a?(Graph))
            return nil
        end

        nodes = @nodes + other.nodes
        edges = @edges + other.edges

        Graph.new(nodes, edges)
    end

    # Perform an OR operation on the current Graph and the given one. Returns a
    # new graph which every node is in the current Graph and/or the other
    # (idem for edges).
    # @param other [Graph]
    def |(other)
        if (!other.is_a?(Graph))
            return nil
        end
            
        nodes = @nodes | other.nodes
        edges = @edges | other.edges

        Graph.new(nodes, edges)
    end

    # Returns a new Graph, which is a copy of the current graph without nodes
    # and edges which are in the given Graph.
    # @param other [Graph]
    def -(other)
        if (!other.is_a?(Graph))
            return nil
        end

        nodes = @nodes - other.nodes
        edges = @edges - other.edges

        Graph.new(nodes, edges)
    end

    # @see Graph#-
    def not(other)
        self - other
    end

    # Return true if the Graph is directed.
    # @see Graph.attrs
    def directed?()
        self.attrs[:directed]
    end

    # Clone the current graph. All nodes and edges are also cloned. A new Graph
    # is returned.
    def clone()
        g = Graph.new
        g.nodes = self.nodes.clone
        g.edges = self.edges.clone

        g.nodes.map! {|h| h.clone}
        g.edges.map! {|h| h.clone}

        g
    end

    # Write the current Graph into a file.
    # @param filename [String] A valid filename
    # @param opts [Hash] A customizable set of options
    # @option opts [Boolean] :gephi Should be <tt>true</tt> if the file will be used with Gephi.
    def write(filename, opts=nil)

        has_ext = filename.split('.')
        ext = (has_ext.length>1) ? has_ext[-1] : 'unknow'

        m = (self.methods - Object.methods).map {|e| e.to_s}

        if (m.include? 'write_'+ext.downcase)
            self.send('write_'+ext.downcase, filename, opts)

        elsif (ext == 'unknow' || ext == 'yml')
            # YAML (default)
            nodes = self.nodes.to_a
            edges = self.edges.to_a

            data = {'nodes'=>nodes, 'edges'=>edges}.to_yaml
            f = open(filename, 'w')
            f.write(data)
            f.close
        else
            raise NoMethodError.new("No method to handle #{ext} file extension.")
        end

    end

    # Return the degree of the node n in the current graph, i.e. the number
    # of edges which are connected to this node. Note that this is useful
    # only for a undirected graph, for a directed one, you should use
    # Graph#in_degree_of and/or Graph#out_degree_of.
    #
    # Edges must have the 'node1' and 'node2' attributes, which must contain
    # the 'label' attributes of nodes.
    #
    # @param n [Node,String] A node or a label of one
    # @see Graph#in_degree_of
    # @see Graph#out_degree_of
    def degree_of(n)
        label = Graph::get_label(n)

        degree = 0

        # This is more efficient than in_degree_of(n)+out_degree_of(n)
        # since it goes only once through the edges array
        self.edges.each do |e|
            degree += 1 if (e['node1'] || e[:node1]).to_s == label
            degree += 1 if (e['node2'] || e[:node2]).to_s == label
        end

        degree
    end

    # Return the “in degree” of the node n in the current graph, i.e. the number
    # of edges which are directed to this node. Note that the graph must be oriented.
    #
    # Edges must have the 'node1' and 'node2' attributes, which must contain
    # the 'label' attributes of nodes.
    #
    # @param n [Node,String] A node or a label of one
    # @see Graph#degree_of
    # @see Graph#out_degree_of
    def in_degree_of(n)
        label = Graph::get_label(n)

        degree = 0

        self.edges.each do |e|
            degree += 1 if (e['node2'] || e[:node2]).to_s == label
        end

        degree
    end

    # Return the “out degree” of the node n in the current graph, i.e. the number
    # of edges which are directed from this node. Note that the graph must be oriented.
    #
    # Edges must have the 'node1' and 'node2' attributes, which must contain
    # the 'label' attributes of nodes.
    #
    # @param n [Node,String] A node or a label of one
    # @see Graph#degree_of
    # @see Graph#out_degree_of
    def out_degree_of(n)
        label = Graph::get_label(n)

        degree = 0

        self.edges.each do |e|
            degree += 1 if (e['node1'] || e[:node1]).to_s == label
        end

        degree
    end

    # return the first node which mach the given label in the current graph
    # @param label [String] A node's label
    def get_node(label)

        label = Graph::get_label(label)

        self.nodes.find { |n| n.label == label }

    end

    # return an array of the neighbours of a node in the current graph.
    # @param n [Node,String] A node with a 'label' or :label attribute, or a string
    def get_neighbours(n)

        label = Graph::get_label(n)
        neighbours = NodeArray.new []

        self.edges.each do |e|

            begin

                l1 = e.node1
                l2 = e.node2

            rescue NoMethodError; next; end

            if l2 && l1 == label

                n2 = self.get_node l2

                unless neighbours.include?(l2)

                    neighbours.push(n2)

                end
            
            end

            if l1 && l2 == label && !self.directed?

                n1 = self.get_node l1
            
                unless neighbours.include?(n1)

                    neighbours.push(n1)
                
                end
            
            end

        end

        neighbours

    end

    # return the label of a node. Raise a TypeError exception if the argument
    # is not a Node nor a String object.
    # @param n [Node,String] A node with a 'label' or :label attribute, or a string
    def Graph::get_label(n)
        label = n.is_a?(Node) \
                      ? n.label.to_s \
                      : n.is_a?(String) ? n : nil

        raise TypeError.new("#{n.inspect} must be a Node or String object.") if label.nil?

        label
    end

    # return the provided set of graphs, from which every node/edge label which
    # is not in all graphs has been removed. So every returned graph has same
    # node/edge labels than each other
    def Graph::keep_only_same_fields(*graphs)
            graphs.map! {|g| g.clone}

            # every first node of every graphs
            nodes_ref = graphs.map {|g| g.nodes[0] || {}}
            # every first edge of every graphs
            edges_ref = graphs.map {|g| g.edges[0] || {}}

            nodes_keys_ref = nodes_ref.map {|n| n.keys}
            edges_keys_ref = edges_ref.map {|e| e.keys}

            # keep only same keys
            nodes_keys_uniq = nodes_keys_ref.inject {|i,e| i &= e}
            edges_keys_uniq = edges_keys_ref.inject {|i,e| i &= e}

            graphs.map {|g|
                g.nodes.map! { |n|
                    
                    newnode = {}

                    n.each_key { |k|
                        newnode[k] = n[k] if nodes_keys_uniq.include?(k)
                    }

                    newnode
                }
                g.edges.map! { |n|
                    
                    newedge = {}

                    n.each_key { |k|
                        newedge[k] = n[k] if edges_keys_uniq.include?(k)
                    }

                    newedge
                }
                g
            }
    end

    # Perform an operation on a graphs group
    # @param block [Block] operation
    def Graph::perform_graphs_group_op(*graphs, &block)
        return nil if graphs.length == 0

        # options
        opts = {}

        # if the last arg is an hash, use it as a set of options and remove it
        # from the arguments
        if graphs[-1].is_a?(Hash)
            return nil if graphs.length == 1
            
            opts = graphs.pop
        end

        # return nil if one argument is not a graph
        graphs.each do |g|
                return nil if !g.is_a?(Graph)
        end

        # if :same_fields option is set, call `keep_only_same_fields` function
        graphs = keep_only_same_fields(*graphs) if opts[:same_fields]

        # perform an and operation on all graph list
        graphs.inject(&block)
    end

    private_class_method :keep_only_same_fields, :perform_graphs_group_op
end

#edges ⇒ EdgeArray

Returns array of current Graph’s edges.

Returns:

  • (EdgeArray) —

    array of current Graph’s edges



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
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
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
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
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
 
# File 'lib/graph.rb', line 13

class Graph

    # Return a new Graph which is the intersection of every given graph.
    # Each node of the intersection is in every given graph (idem for edges).
    # The last argument may be a hash of options.
    # @option options [Boolean] :same_fields use only fields which are in every
    # graph to compare nodes/edges to perform the intersection
    # @see Graph#&
    # @see Graph::union
    # @see Graph::xor
    def Graph::intersection(*graphs)
         perform_graphs_group_op(*graphs, &:&)
    end

    # Return a new Graph which is the union of every given graph.
    # Each node of the union is in one or more given graph(s) (idem for edges).
    # The last argument may be a hash of options.
    # @option options [Boolean] :same_fields use only fields which are in every
    # graph to compare nodes/edges to perform the union
    # @see Graph#|
    # @see Graph::intersection
    # @see Graph::xor
    def Graph::union(*graphs)
        perform_graphs_group_op(*graphs, &:|)
    end

    # Perform a XOR operation on all given graphs, and returns the result.
    # The last argument may be a hash of options.
    # @option options [Boolean] :same_fields use only fields which are in every
    # graph to compare nodes/edges to perform the XOR operation
    # @see Graph#^
    # @see Graph::union
    # @see Graph::intersection
    def Graph::xor(*graphs)
        perform_graphs_group_op(*graphs, &:^)
    end

    # A node. This class is just a wrapper around a hash of
    # attributes since in version <= 0.1.5 nodes were simple hashes
    class Node

        attr_accessor :attrs

        def initialize(attrs=nil)
            @attrs = attrs || {}
        end

        # compare two nodes
        # @param other [Node]
        def ==(other)
            return false if !other.is_a?(Node)

            @attrs == other.attrs
        end

        def update(h)
            Node.new super(h)
        end

        def method_missing(method, *args, &block)

            return @attrs[method.to_sym] if @attrs.has_key? method.to_sym
            return @attrs[method.to_s] if @attrs.has_key? method.to_s

            @attrs.send(method, *args, &block)
        end

    end

    # An edge. This class is just a wrapper around a hash of
    # attributes since in version <= 0.1.5 edges were simple hashes
    class Edge

        attr_accessor :attrs

        def initialize(attrs=nil)
            @attrs = attrs || {}
        end

        # compare two edges
        # @param other [Edge]
        def ==(other)
            return false if !other.is_a?(Edge)

            @attrs == other.attrs
        end

        def update(h)
            Edge.new super(h)
        end

        def method_missing(method, *args, &block)

            return @attrs[method.to_sym] if @attrs.has_key? method.to_sym
            return @attrs[method.to_s] if @attrs.has_key? method.to_s

            @attrs.send(method, *args, &block)
        end

    end

    # An array of Node objects
    class NodeArray < Array

        def initialize(li)
            nodes = li.map { |n| n.is_a?(Node) ? n : Node.new(n) }
            super(nodes)
            @defaults = {}
        end

        # Set some default values for current elements.
        # @note This method can be called multiple times.
        # @example Set all nodes's 'created-at' value to '2012-05-03'
        #   myNodeList.set_default({'created-at'=>'2012-05-03'})
        def set_default(dict)
            @defaults.update(dict)
            self.map! { |e| e.update(@defaults) }
        end

        # Add the given node at the end of the list
        # @param n [Node]
        def push(n)
            if (!n.is_a?(Hash) && !n.is_a?(Node))
                raise TypeError.new "#{n.inspect} is not an Hash nor a Node!"
            end

            n = Node.new(n) if (n.is_a?(Hash))

            super(n.clone.update(@defaults))
        end

    end

    # An array of Edge objects
    class EdgeArray < Array
        def initialize(li)
            edges = li.map { |n| n.is_a?(Edge) ? n : Edge.new(n) }
            super(edges)
            @defaults = {}
        end

        # Set some default values for current elements.
        # @note This method can be called multiple times.
        # @example Set all edges's 'created-at' value to '2012-05-03'
        #   myEdgeList.set_default({'created-at'=>'2012-05-03'})
        # @param dict [Hash]
        def set_default(dict)
            @defaults.update(dict)
            self.map! { |e| e.update(@defaults) }
        end

        # Add the given edge at the end of the list
        # @param e [Edge]
        def push(e)
            if (!e.is_a?(Hash) && !e.is_a?(Edge))
                raise TypeError.new "#{e.inspect} is not an Hash nor an Edge!"
            end

            e = Edge.new(e) if (e.is_a?(Hash))

            super(e.clone.update(@defaults))
        end

    end

    attr_accessor :nodes, :edges, :attrs

    # @param nodes [Array] Nodes of the graph
    # @param edges [Array] Edges of the graph
    def initialize(nodes=nil, edges=nil)
        @nodes = NodeArray.new(nodes || [])
        @edges = EdgeArray.new(edges || [])
        @attrs = { :directed => true }
    end

    # Test if current graph has same nodes and edges as the other
    # graph.
    # @param other [Graph]
    def ==(other)
        if (!other.is_a?(Graph))
            return false
        end
        (self.nodes === other.nodes) && (self.edges === other.edges)
    end

    # Perform an intersection between the current graph and the other.
    # Returns a new Graph which nodes are both in the current graph and
    # the other (idem for edges).
    # @param other [Graph]
    # @see Graph#^
    # @see Graph::intersection
    def &(other)
        if (!other.is_a?(Graph))
            return nil
        end

        nodes = @nodes & other.nodes
        edges = @edges & other.edges

        Graph.new(nodes, edges)
    end

    # Perform a XOR operation between the current graph and the other. Returns a
    # new Graph which nodes are in the current graph or in the other, but not in
    # both (idem for edges).
    # @param other [Graph]
    # @see Graph#&
    def ^(other)
        if (!other.is_a?(Graph))
            return nil
        end

        nodes = (@nodes + other.nodes) - (@nodes & other.nodes)
        edges = (@edges + other.edges) - (@edges & other.edges)

        Graph.new(nodes, edges)
    end

    # Add two graphs, keeping duplicate nodes and edges
    # @param other [Graph]
    def +(other)
        if (!other.is_a?(Graph))
            return nil
        end

        nodes = @nodes + other.nodes
        edges = @edges + other.edges

        Graph.new(nodes, edges)
    end

    # Perform an OR operation on the current Graph and the given one. Returns a
    # new graph which every node is in the current Graph and/or the other
    # (idem for edges).
    # @param other [Graph]
    def |(other)
        if (!other.is_a?(Graph))
            return nil
        end
            
        nodes = @nodes | other.nodes
        edges = @edges | other.edges

        Graph.new(nodes, edges)
    end

    # Returns a new Graph, which is a copy of the current graph without nodes
    # and edges which are in the given Graph.
    # @param other [Graph]
    def -(other)
        if (!other.is_a?(Graph))
            return nil
        end

        nodes = @nodes - other.nodes
        edges = @edges - other.edges

        Graph.new(nodes, edges)
    end

    # @see Graph#-
    def not(other)
        self - other
    end

    # Return true if the Graph is directed.
    # @see Graph.attrs
    def directed?()
        self.attrs[:directed]
    end

    # Clone the current graph. All nodes and edges are also cloned. A new Graph
    # is returned.
    def clone()
        g = Graph.new
        g.nodes = self.nodes.clone
        g.edges = self.edges.clone

        g.nodes.map! {|h| h.clone}
        g.edges.map! {|h| h.clone}

        g
    end

    # Write the current Graph into a file.
    # @param filename [String] A valid filename
    # @param opts [Hash] A customizable set of options
    # @option opts [Boolean] :gephi Should be <tt>true</tt> if the file will be used with Gephi.
    def write(filename, opts=nil)

        has_ext = filename.split('.')
        ext = (has_ext.length>1) ? has_ext[-1] : 'unknow'

        m = (self.methods - Object.methods).map {|e| e.to_s}

        if (m.include? 'write_'+ext.downcase)
            self.send('write_'+ext.downcase, filename, opts)

        elsif (ext == 'unknow' || ext == 'yml')
            # YAML (default)
            nodes = self.nodes.to_a
            edges = self.edges.to_a

            data = {'nodes'=>nodes, 'edges'=>edges}.to_yaml
            f = open(filename, 'w')
            f.write(data)
            f.close
        else
            raise NoMethodError.new("No method to handle #{ext} file extension.")
        end

    end

    # Return the degree of the node n in the current graph, i.e. the number
    # of edges which are connected to this node. Note that this is useful
    # only for a undirected graph, for a directed one, you should use
    # Graph#in_degree_of and/or Graph#out_degree_of.
    #
    # Edges must have the 'node1' and 'node2' attributes, which must contain
    # the 'label' attributes of nodes.
    #
    # @param n [Node,String] A node or a label of one
    # @see Graph#in_degree_of
    # @see Graph#out_degree_of
    def degree_of(n)
        label = Graph::get_label(n)

        degree = 0

        # This is more efficient than in_degree_of(n)+out_degree_of(n)
        # since it goes only once through the edges array
        self.edges.each do |e|
            degree += 1 if (e['node1'] || e[:node1]).to_s == label
            degree += 1 if (e['node2'] || e[:node2]).to_s == label
        end

        degree
    end

    # Return the “in degree” of the node n in the current graph, i.e. the number
    # of edges which are directed to this node. Note that the graph must be oriented.
    #
    # Edges must have the 'node1' and 'node2' attributes, which must contain
    # the 'label' attributes of nodes.
    #
    # @param n [Node,String] A node or a label of one
    # @see Graph#degree_of
    # @see Graph#out_degree_of
    def in_degree_of(n)
        label = Graph::get_label(n)

        degree = 0

        self.edges.each do |e|
            degree += 1 if (e['node2'] || e[:node2]).to_s == label
        end

        degree
    end

    # Return the “out degree” of the node n in the current graph, i.e. the number
    # of edges which are directed from this node. Note that the graph must be oriented.
    #
    # Edges must have the 'node1' and 'node2' attributes, which must contain
    # the 'label' attributes of nodes.
    #
    # @param n [Node,String] A node or a label of one
    # @see Graph#degree_of
    # @see Graph#out_degree_of
    def out_degree_of(n)
        label = Graph::get_label(n)

        degree = 0

        self.edges.each do |e|
            degree += 1 if (e['node1'] || e[:node1]).to_s == label
        end

        degree
    end

    # return the first node which mach the given label in the current graph
    # @param label [String] A node's label
    def get_node(label)

        label = Graph::get_label(label)

        self.nodes.find { |n| n.label == label }

    end

    # return an array of the neighbours of a node in the current graph.
    # @param n [Node,String] A node with a 'label' or :label attribute, or a string
    def get_neighbours(n)

        label = Graph::get_label(n)
        neighbours = NodeArray.new []

        self.edges.each do |e|

            begin

                l1 = e.node1
                l2 = e.node2

            rescue NoMethodError; next; end

            if l2 && l1 == label

                n2 = self.get_node l2

                unless neighbours.include?(l2)

                    neighbours.push(n2)

                end
            
            end

            if l1 && l2 == label && !self.directed?

                n1 = self.get_node l1
            
                unless neighbours.include?(n1)

                    neighbours.push(n1)
                
                end
            
            end

        end

        neighbours

    end

    # return the label of a node. Raise a TypeError exception if the argument
    # is not a Node nor a String object.
    # @param n [Node,String] A node with a 'label' or :label attribute, or a string
    def Graph::get_label(n)
        label = n.is_a?(Node) \
                      ? n.label.to_s \
                      : n.is_a?(String) ? n : nil

        raise TypeError.new("#{n.inspect} must be a Node or String object.") if label.nil?

        label
    end

    # return the provided set of graphs, from which every node/edge label which
    # is not in all graphs has been removed. So every returned graph has same
    # node/edge labels than each other
    def Graph::keep_only_same_fields(*graphs)
            graphs.map! {|g| g.clone}

            # every first node of every graphs
            nodes_ref = graphs.map {|g| g.nodes[0] || {}}
            # every first edge of every graphs
            edges_ref = graphs.map {|g| g.edges[0] || {}}

            nodes_keys_ref = nodes_ref.map {|n| n.keys}
            edges_keys_ref = edges_ref.map {|e| e.keys}

            # keep only same keys
            nodes_keys_uniq = nodes_keys_ref.inject {|i,e| i &= e}
            edges_keys_uniq = edges_keys_ref.inject {|i,e| i &= e}

            graphs.map {|g|
                g.nodes.map! { |n|
                    
                    newnode = {}

                    n.each_key { |k|
                        newnode[k] = n[k] if nodes_keys_uniq.include?(k)
                    }

                    newnode
                }
                g.edges.map! { |n|
                    
                    newedge = {}

                    n.each_key { |k|
                        newedge[k] = n[k] if edges_keys_uniq.include?(k)
                    }

                    newedge
                }
                g
            }
    end

    # Perform an operation on a graphs group
    # @param block [Block] operation
    def Graph::perform_graphs_group_op(*graphs, &block)
        return nil if graphs.length == 0

        # options
        opts = {}

        # if the last arg is an hash, use it as a set of options and remove it
        # from the arguments
        if graphs[-1].is_a?(Hash)
            return nil if graphs.length == 1
            
            opts = graphs.pop
        end

        # return nil if one argument is not a graph
        graphs.each do |g|
                return nil if !g.is_a?(Graph)
        end

        # if :same_fields option is set, call `keep_only_same_fields` function
        graphs = keep_only_same_fields(*graphs) if opts[:same_fields]

        # perform an and operation on all graph list
        graphs.inject(&block)
    end

    private_class_method :keep_only_same_fields, :perform_graphs_group_op
end

#nodes ⇒ NodeArray

Returns array of current Graph’s nodes.

Returns:

  • (NodeArray) —

    array of current Graph’s nodes



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
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
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
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
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
 
# File 'lib/graph.rb', line 13

class Graph

    # Return a new Graph which is the intersection of every given graph.
    # Each node of the intersection is in every given graph (idem for edges).
    # The last argument may be a hash of options.
    # @option options [Boolean] :same_fields use only fields which are in every
    # graph to compare nodes/edges to perform the intersection
    # @see Graph#&
    # @see Graph::union
    # @see Graph::xor
    def Graph::intersection(*graphs)
         perform_graphs_group_op(*graphs, &:&)
    end

    # Return a new Graph which is the union of every given graph.
    # Each node of the union is in one or more given graph(s) (idem for edges).
    # The last argument may be a hash of options.
    # @option options [Boolean] :same_fields use only fields which are in every
    # graph to compare nodes/edges to perform the union
    # @see Graph#|
    # @see Graph::intersection
    # @see Graph::xor
    def Graph::union(*graphs)
        perform_graphs_group_op(*graphs, &:|)
    end

    # Perform a XOR operation on all given graphs, and returns the result.
    # The last argument may be a hash of options.
    # @option options [Boolean] :same_fields use only fields which are in every
    # graph to compare nodes/edges to perform the XOR operation
    # @see Graph#^
    # @see Graph::union
    # @see Graph::intersection
    def Graph::xor(*graphs)
        perform_graphs_group_op(*graphs, &:^)
    end

    # A node. This class is just a wrapper around a hash of
    # attributes since in version <= 0.1.5 nodes were simple hashes
    class Node

        attr_accessor :attrs

        def initialize(attrs=nil)
            @attrs = attrs || {}
        end

        # compare two nodes
        # @param other [Node]
        def ==(other)
            return false if !other.is_a?(Node)

            @attrs == other.attrs
        end

        def update(h)
            Node.new super(h)
        end

        def method_missing(method, *args, &block)

            return @attrs[method.to_sym] if @attrs.has_key? method.to_sym
            return @attrs[method.to_s] if @attrs.has_key? method.to_s

            @attrs.send(method, *args, &block)
        end

    end

    # An edge. This class is just a wrapper around a hash of
    # attributes since in version <= 0.1.5 edges were simple hashes
    class Edge

        attr_accessor :attrs

        def initialize(attrs=nil)
            @attrs = attrs || {}
        end

        # compare two edges
        # @param other [Edge]
        def ==(other)
            return false if !other.is_a?(Edge)

            @attrs == other.attrs
        end

        def update(h)
            Edge.new super(h)
        end

        def method_missing(method, *args, &block)

            return @attrs[method.to_sym] if @attrs.has_key? method.to_sym
            return @attrs[method.to_s] if @attrs.has_key? method.to_s

            @attrs.send(method, *args, &block)
        end

    end

    # An array of Node objects
    class NodeArray < Array

        def initialize(li)
            nodes = li.map { |n| n.is_a?(Node) ? n : Node.new(n) }
            super(nodes)
            @defaults = {}
        end

        # Set some default values for current elements.
        # @note This method can be called multiple times.
        # @example Set all nodes's 'created-at' value to '2012-05-03'
        #   myNodeList.set_default({'created-at'=>'2012-05-03'})
        def set_default(dict)
            @defaults.update(dict)
            self.map! { |e| e.update(@defaults) }
        end

        # Add the given node at the end of the list
        # @param n [Node]
        def push(n)
            if (!n.is_a?(Hash) && !n.is_a?(Node))
                raise TypeError.new "#{n.inspect} is not an Hash nor a Node!"
            end

            n = Node.new(n) if (n.is_a?(Hash))

            super(n.clone.update(@defaults))
        end

    end

    # An array of Edge objects
    class EdgeArray < Array
        def initialize(li)
            edges = li.map { |n| n.is_a?(Edge) ? n : Edge.new(n) }
            super(edges)
            @defaults = {}
        end

        # Set some default values for current elements.
        # @note This method can be called multiple times.
        # @example Set all edges's 'created-at' value to '2012-05-03'
        #   myEdgeList.set_default({'created-at'=>'2012-05-03'})
        # @param dict [Hash]
        def set_default(dict)
            @defaults.update(dict)
            self.map! { |e| e.update(@defaults) }
        end

        # Add the given edge at the end of the list
        # @param e [Edge]
        def push(e)
            if (!e.is_a?(Hash) && !e.is_a?(Edge))
                raise TypeError.new "#{e.inspect} is not an Hash nor an Edge!"
            end

            e = Edge.new(e) if (e.is_a?(Hash))

            super(e.clone.update(@defaults))
        end

    end

    attr_accessor :nodes, :edges, :attrs

    # @param nodes [Array] Nodes of the graph
    # @param edges [Array] Edges of the graph
    def initialize(nodes=nil, edges=nil)
        @nodes = NodeArray.new(nodes || [])
        @edges = EdgeArray.new(edges || [])
        @attrs = { :directed => true }
    end

    # Test if current graph has same nodes and edges as the other
    # graph.
    # @param other [Graph]
    def ==(other)
        if (!other.is_a?(Graph))
            return false
        end
        (self.nodes === other.nodes) && (self.edges === other.edges)
    end

    # Perform an intersection between the current graph and the other.
    # Returns a new Graph which nodes are both in the current graph and
    # the other (idem for edges).
    # @param other [Graph]
    # @see Graph#^
    # @see Graph::intersection
    def &(other)
        if (!other.is_a?(Graph))
            return nil
        end

        nodes = @nodes & other.nodes
        edges = @edges & other.edges

        Graph.new(nodes, edges)
    end

    # Perform a XOR operation between the current graph and the other. Returns a
    # new Graph which nodes are in the current graph or in the other, but not in
    # both (idem for edges).
    # @param other [Graph]
    # @see Graph#&
    def ^(other)
        if (!other.is_a?(Graph))
            return nil
        end

        nodes = (@nodes + other.nodes) - (@nodes & other.nodes)
        edges = (@edges + other.edges) - (@edges & other.edges)

        Graph.new(nodes, edges)
    end

    # Add two graphs, keeping duplicate nodes and edges
    # @param other [Graph]
    def +(other)
        if (!other.is_a?(Graph))
            return nil
        end

        nodes = @nodes + other.nodes
        edges = @edges + other.edges

        Graph.new(nodes, edges)
    end

    # Perform an OR operation on the current Graph and the given one. Returns a
    # new graph which every node is in the current Graph and/or the other
    # (idem for edges).
    # @param other [Graph]
    def |(other)
        if (!other.is_a?(Graph))
            return nil
        end
            
        nodes = @nodes | other.nodes
        edges = @edges | other.edges

        Graph.new(nodes, edges)
    end

    # Returns a new Graph, which is a copy of the current graph without nodes
    # and edges which are in the given Graph.
    # @param other [Graph]
    def -(other)
        if (!other.is_a?(Graph))
            return nil
        end

        nodes = @nodes - other.nodes
        edges = @edges - other.edges

        Graph.new(nodes, edges)
    end

    # @see Graph#-
    def not(other)
        self - other
    end

    # Return true if the Graph is directed.
    # @see Graph.attrs
    def directed?()
        self.attrs[:directed]
    end

    # Clone the current graph. All nodes and edges are also cloned. A new Graph
    # is returned.
    def clone()
        g = Graph.new
        g.nodes = self.nodes.clone
        g.edges = self.edges.clone

        g.nodes.map! {|h| h.clone}
        g.edges.map! {|h| h.clone}

        g
    end

    # Write the current Graph into a file.
    # @param filename [String] A valid filename
    # @param opts [Hash] A customizable set of options
    # @option opts [Boolean] :gephi Should be <tt>true</tt> if the file will be used with Gephi.
    def write(filename, opts=nil)

        has_ext = filename.split('.')
        ext = (has_ext.length>1) ? has_ext[-1] : 'unknow'

        m = (self.methods - Object.methods).map {|e| e.to_s}

        if (m.include? 'write_'+ext.downcase)
            self.send('write_'+ext.downcase, filename, opts)

        elsif (ext == 'unknow' || ext == 'yml')
            # YAML (default)
            nodes = self.nodes.to_a
            edges = self.edges.to_a

            data = {'nodes'=>nodes, 'edges'=>edges}.to_yaml
            f = open(filename, 'w')
            f.write(data)
            f.close
        else
            raise NoMethodError.new("No method to handle #{ext} file extension.")
        end

    end

    # Return the degree of the node n in the current graph, i.e. the number
    # of edges which are connected to this node. Note that this is useful
    # only for a undirected graph, for a directed one, you should use
    # Graph#in_degree_of and/or Graph#out_degree_of.
    #
    # Edges must have the 'node1' and 'node2' attributes, which must contain
    # the 'label' attributes of nodes.
    #
    # @param n [Node,String] A node or a label of one
    # @see Graph#in_degree_of
    # @see Graph#out_degree_of
    def degree_of(n)
        label = Graph::get_label(n)

        degree = 0

        # This is more efficient than in_degree_of(n)+out_degree_of(n)
        # since it goes only once through the edges array
        self.edges.each do |e|
            degree += 1 if (e['node1'] || e[:node1]).to_s == label
            degree += 1 if (e['node2'] || e[:node2]).to_s == label
        end

        degree
    end

    # Return the “in degree” of the node n in the current graph, i.e. the number
    # of edges which are directed to this node. Note that the graph must be oriented.
    #
    # Edges must have the 'node1' and 'node2' attributes, which must contain
    # the 'label' attributes of nodes.
    #
    # @param n [Node,String] A node or a label of one
    # @see Graph#degree_of
    # @see Graph#out_degree_of
    def in_degree_of(n)
        label = Graph::get_label(n)

        degree = 0

        self.edges.each do |e|
            degree += 1 if (e['node2'] || e[:node2]).to_s == label
        end

        degree
    end

    # Return the “out degree” of the node n in the current graph, i.e. the number
    # of edges which are directed from this node. Note that the graph must be oriented.
    #
    # Edges must have the 'node1' and 'node2' attributes, which must contain
    # the 'label' attributes of nodes.
    #
    # @param n [Node,String] A node or a label of one
    # @see Graph#degree_of
    # @see Graph#out_degree_of
    def out_degree_of(n)
        label = Graph::get_label(n)

        degree = 0

        self.edges.each do |e|
            degree += 1 if (e['node1'] || e[:node1]).to_s == label
        end

        degree
    end

    # return the first node which mach the given label in the current graph
    # @param label [String] A node's label
    def get_node(label)

        label = Graph::get_label(label)

        self.nodes.find { |n| n.label == label }

    end

    # return an array of the neighbours of a node in the current graph.
    # @param n [Node,String] A node with a 'label' or :label attribute, or a string
    def get_neighbours(n)

        label = Graph::get_label(n)
        neighbours = NodeArray.new []

        self.edges.each do |e|

            begin

                l1 = e.node1
                l2 = e.node2

            rescue NoMethodError; next; end

            if l2 && l1 == label

                n2 = self.get_node l2

                unless neighbours.include?(l2)

                    neighbours.push(n2)

                end
            
            end

            if l1 && l2 == label && !self.directed?

                n1 = self.get_node l1
            
                unless neighbours.include?(n1)

                    neighbours.push(n1)
                
                end
            
            end

        end

        neighbours

    end

    # return the label of a node. Raise a TypeError exception if the argument
    # is not a Node nor a String object.
    # @param n [Node,String] A node with a 'label' or :label attribute, or a string
    def Graph::get_label(n)
        label = n.is_a?(Node) \
                      ? n.label.to_s \
                      : n.is_a?(String) ? n : nil

        raise TypeError.new("#{n.inspect} must be a Node or String object.") if label.nil?

        label
    end

    # return the provided set of graphs, from which every node/edge label which
    # is not in all graphs has been removed. So every returned graph has same
    # node/edge labels than each other
    def Graph::keep_only_same_fields(*graphs)
            graphs.map! {|g| g.clone}

            # every first node of every graphs
            nodes_ref = graphs.map {|g| g.nodes[0] || {}}
            # every first edge of every graphs
            edges_ref = graphs.map {|g| g.edges[0] || {}}

            nodes_keys_ref = nodes_ref.map {|n| n.keys}
            edges_keys_ref = edges_ref.map {|e| e.keys}

            # keep only same keys
            nodes_keys_uniq = nodes_keys_ref.inject {|i,e| i &= e}
            edges_keys_uniq = edges_keys_ref.inject {|i,e| i &= e}

            graphs.map {|g|
                g.nodes.map! { |n|
                    
                    newnode = {}

                    n.each_key { |k|
                        newnode[k] = n[k] if nodes_keys_uniq.include?(k)
                    }

                    newnode
                }
                g.edges.map! { |n|
                    
                    newedge = {}

                    n.each_key { |k|
                        newedge[k] = n[k] if edges_keys_uniq.include?(k)
                    }

                    newedge
                }
                g
            }
    end

    # Perform an operation on a graphs group
    # @param block [Block] operation
    def Graph::perform_graphs_group_op(*graphs, &block)
        return nil if graphs.length == 0

        # options
        opts = {}

        # if the last arg is an hash, use it as a set of options and remove it
        # from the arguments
        if graphs[-1].is_a?(Hash)
            return nil if graphs.length == 1
            
            opts = graphs.pop
        end

        # return nil if one argument is not a graph
        graphs.each do |g|
                return nil if !g.is_a?(Graph)
        end

        # if :same_fields option is set, call `keep_only_same_fields` function
        graphs = keep_only_same_fields(*graphs) if opts[:same_fields]

        # perform an and operation on all graph list
        graphs.inject(&block)
    end

    private_class_method :keep_only_same_fields, :perform_graphs_group_op
end

Class Method Details

.get_label(n) ⇒ Object

return the label of a node. Raise a TypeError exception if the argument is not a Node nor a String object.

Parameters:

  • n (Node, String) —

    A node with a ‘label’ or :label attribute, or a string

Raises:

  • (TypeError) 


453
454
455
456
457
458
459
460
461
 
# File 'lib/graph.rb', line 453

def Graph::get_label(n)
    label = n.is_a?(Node) \
                  ? n.label.to_s \
                  : n.is_a?(String) ? n : nil

    raise TypeError.new("#{n.inspect} must be a Node or String object.") if label.nil?

    label
end

.intersection(*graphs) ⇒ Object

Return a new Graph which is the intersection of every given graph. Each node of the intersection is in every given graph (idem for edges). The last argument may be a hash of options. graph to compare nodes/edges to perform the intersection

Parameters:

  • options (Hash) —

    a customizable set of options

See Also:

  • #&
  • union
  • xor


23
24
25
 
# File 'lib/graph.rb', line 23

def Graph::intersection(*graphs)
     perform_graphs_group_op(*graphs, &:&)
end

.union(*graphs) ⇒ Object

Return a new Graph which is the union of every given graph. Each node of the union is in one or more given graph(s) (idem for edges). The last argument may be a hash of options. graph to compare nodes/edges to perform the union

Parameters:

  • options (Hash) —

    a customizable set of options

See Also:

  • #|
  • intersection
  • xor


35
36
37
 
# File 'lib/graph.rb', line 35

def Graph::union(*graphs)
    perform_graphs_group_op(*graphs, &:|)
end

.xor(*graphs) ⇒ Object

Perform a XOR operation on all given graphs, and returns the result. The last argument may be a hash of options. graph to compare nodes/edges to perform the XOR operation

Parameters:

  • options (Hash) —

    a customizable set of options

See Also:

  • #^
  • union
  • intersection


46
47
48
 
# File 'lib/graph.rb', line 46

def Graph::xor(*graphs)
    perform_graphs_group_op(*graphs, &:^)
end

Instance Method Details

#&(other) ⇒ Object

Perform an intersection between the current graph and the other. Returns a new Graph which nodes are both in the current graph and the other (idem for edges).

Parameters:

See Also:

  • #^
  • intersection


204
205
206
207
208
209
210
211
212
213
 
# File 'lib/graph.rb', line 204

def &(other)
    if (!other.is_a?(Graph))
        return nil
    end

    nodes = @nodes & other.nodes
    edges = @edges & other.edges

    Graph.new(nodes, edges)
end

#+(other) ⇒ Object

Add two graphs, keeping duplicate nodes and edges

Parameters:



233
234
235
236
237
238
239
240
241
242
 
# File 'lib/graph.rb', line 233

def +(other)
    if (!other.is_a?(Graph))
        return nil
    end

    nodes = @nodes + other.nodes
    edges = @edges + other.edges

    Graph.new(nodes, edges)
end

#-(other) ⇒ Object

Returns a new Graph, which is a copy of the current graph without nodes and edges which are in the given Graph.

Parameters:



262
263
264
265
266
267
268
269
270
271
 
# File 'lib/graph.rb', line 262

def -(other)
    if (!other.is_a?(Graph))
        return nil
    end

    nodes = @nodes - other.nodes
    edges = @edges - other.edges

    Graph.new(nodes, edges)
end

#==(other) ⇒ Object

Test if current graph has same nodes and edges as the other graph.

Parameters:



191
192
193
194
195
196
 
# File 'lib/graph.rb', line 191

def ==(other)
    if (!other.is_a?(Graph))
        return false
    end
    (self.nodes === other.nodes) && (self.edges === other.edges)
end

#^(other) ⇒ Object

Perform a XOR operation between the current graph and the other. Returns a new Graph which nodes are in the current graph or in the other, but not in both (idem for edges).

Parameters:

See Also:



220
221
222
223
224
225
226
227
228
229
 
# File 'lib/graph.rb', line 220

def ^(other)
    if (!other.is_a?(Graph))
        return nil
    end

    nodes = (@nodes + other.nodes) - (@nodes & other.nodes)
    edges = (@edges + other.edges) - (@edges & other.edges)

    Graph.new(nodes, edges)
end

#clone ⇒ Object

Clone the current graph. All nodes and edges are also cloned. A new Graph is returned.



286
287
288
289
290
291
292
293
294
295
 
# File 'lib/graph.rb', line 286

def clone()
    g = Graph.new
    g.nodes = self.nodes.clone
    g.edges = self.edges.clone

    g.nodes.map! {|h| h.clone}
    g.edges.map! {|h| h.clone}

    g
end

#degree_of(n) ⇒ Object

Return the degree of the node n in the current graph, i.e. the number of edges which are connected to this node. Note that this is useful only for a undirected graph, for a directed one, you should use Graph#in_degree_of and/or Graph#out_degree_of.

Edges must have the ‘node1’ and ‘node2’ attributes, which must contain the ‘label’ attributes of nodes.

Parameters:

  • n (Node, String) —

    A node or a label of one

See Also:



337
338
339
340
341
342
343
344
345
346
347
348
349
350
 
# File 'lib/graph.rb', line 337

def degree_of(n)
    label = Graph::get_label(n)

    degree = 0

    # This is more efficient than in_degree_of(n)+out_degree_of(n)
    # since it goes only once through the edges array
    self.edges.each do |e|
        degree += 1 if (e['node1'] || e[:node1]).to_s == label
        degree += 1 if (e['node2'] || e[:node2]).to_s == label
    end

    degree
end

#directed? ⇒ Boolean

Return true if the Graph is directed.

Returns:

  • (Boolean)

See Also:



280
281
282
 
# File 'lib/graph.rb', line 280

def directed?()
    self.attrs[:directed]
end

#get_neighbours(n) ⇒ Object

return an array of the neighbours of a node in the current graph.

Parameters:

  • n (Node, String) —

    A node with a ‘label’ or :label attribute, or a string



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
438
439
440
441
442
443
444
445
446
447
448
 
# File 'lib/graph.rb', line 406

def get_neighbours(n)

    label = Graph::get_label(n)
    neighbours = NodeArray.new []

    self.edges.each do |e|

        begin

            l1 = e.node1
            l2 = e.node2

        rescue NoMethodError; next; end

        if l2 && l1 == label

            n2 = self.get_node l2

            unless neighbours.include?(l2)

                neighbours.push(n2)

            end
        
        end

        if l1 && l2 == label && !self.directed?

            n1 = self.get_node l1
        
            unless neighbours.include?(n1)

                neighbours.push(n1)
            
            end
        
        end

    end

    neighbours

end

#get_node(label) ⇒ Object

return the first node which mach the given label in the current graph

Parameters:

  • label (String) —

    A node’s label



396
397
398
399
400
401
402
 
# File 'lib/graph.rb', line 396

def get_node(label)

    label = Graph::get_label(label)

    self.nodes.find { |n| n.label == label }

end

#in_degree_of(n) ⇒ Object

Return the “in degree” of the node n in the current graph, i.e. the number of edges which are directed to this node. Note that the graph must be oriented.

Edges must have the ‘node1’ and ‘node2’ attributes, which must contain the ‘label’ attributes of nodes.

Parameters:

  • n (Node, String) —

    A node or a label of one

See Also:



361
362
363
364
365
366
367
368
369
370
371
 
# File 'lib/graph.rb', line 361

def in_degree_of(n)
    label = Graph::get_label(n)

    degree = 0

    self.edges.each do |e|
        degree += 1 if (e['node2'] || e[:node2]).to_s == label
    end

    degree
end

#not(other) ⇒ Object

See Also:



274
275
276
 
# File 'lib/graph.rb', line 274

def not(other)
    self - other
end

#out_degree_of(n) ⇒ Object

Return the “out degree” of the node n in the current graph, i.e. the number of edges which are directed from this node. Note that the graph must be oriented.

Edges must have the ‘node1’ and ‘node2’ attributes, which must contain the ‘label’ attributes of nodes.

Parameters:

  • n (Node, String) —

    A node or a label of one

See Also:



382
383
384
385
386
387
388
389
390
391
392
 
# File 'lib/graph.rb', line 382

def out_degree_of(n)
    label = Graph::get_label(n)

    degree = 0

    self.edges.each do |e|
        degree += 1 if (e['node1'] || e[:node1]).to_s == label
    end

    degree
end

#to_gdf(opts = nil) ⇒ Object

Returns a GDF version of the current graph

Parameters:

  • opts (Hash) (defaults to: nil) —

    A customizable set of options

See Also:

  • GDF::unparse


9
10
11
 
# File 'lib/graphs/gdf.rb', line 9

def to_gdf(opts=nil)
    GDF::unparse(self, opts)
end

#to_json(opts = nil) ⇒ Object

Returns a JSON version of the current graph

Parameters:

  • opts (Hash) (defaults to: nil) —

    A customizable set of options

See Also:

  • JSONGraph::unparse


11
12
13
 
# File 'lib/graphs/json.rb', line 11

def to_json(opts=nil)
    JSONGraph::unparse(self, opts)
end

#write(filename, opts = nil) ⇒ Object

Write the current Graph into a file.

Parameters:

  • filename (String) —

    A valid filename

  • opts (Hash) (defaults to: nil) —

    A customizable set of options

Options Hash (opts):

  • :gephi (Boolean) —

    Should be true if the file will be used with Gephi.



301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
 
# File 'lib/graph.rb', line 301

def write(filename, opts=nil)

    has_ext = filename.split('.')
    ext = (has_ext.length>1) ? has_ext[-1] : 'unknow'

    m = (self.methods - Object.methods).map {|e| e.to_s}

    if (m.include? 'write_'+ext.downcase)
        self.send('write_'+ext.downcase, filename, opts)

    elsif (ext == 'unknow' || ext == 'yml')
        # YAML (default)
        nodes = self.nodes.to_a
        edges = self.edges.to_a

        data = {'nodes'=>nodes, 'edges'=>edges}.to_yaml
        f = open(filename, 'w')
        f.write(data)
        f.close
    else
        raise NoMethodError.new("No method to handle #{ext} file extension.")
    end

end

#write_gdf(filename, opts = nil) ⇒ Object

Write the current graph into a GDF file. This method is used internally, use Graph#write instead.

Parameters:

  • filename (String) —

    a valid filename

See Also:

  • GDF::unparse


17
18
19
20
21
22
 
# File 'lib/graphs/gdf.rb', line 17

def write_gdf(filename, opts=nil)
    gdf = GDF::unparse(self, opts)
    f = File.open(filename, 'w')
    f.write(gdf)
    f.close
end

#write_json(filename, opts = nil) ⇒ Object

Write the current graph into a JSON file. This method is used internally, use Graph#write instead.

Parameters:

  • filename (String) —

    a valid filename

See Also:

  • JSON::unparse


19
20
21
22
23
24
 
# File 'lib/graphs/json.rb', line 19

def write_json(filename, opts=nil)
    json = JSONGraph::unparse(self, opts)
    f = File.open(filename, 'w')
    f.write(json)
    f.close
end

#|(other) ⇒ Object

Perform an OR operation on the current Graph and the given one. Returns a new graph which every node is in the current Graph and/or the other (idem for edges).

Parameters:



248
249
250
251
252
253
254
255
256
257
 
# File 'lib/graph.rb', line 248

def |(other)
    if (!other.is_a?(Graph))
        return nil
    end
        
    nodes = @nodes | other.nodes
    edges = @edges | other.edges

    Graph.new(nodes, edges)
end