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



185
186
187
188
189
 
# File 'lib/graph.rb', line 185

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, …).



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
 
# File 'lib/graph.rb', line 14

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.is_a?(Node) ? attrs.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.is_a?(Edge) ? attrs.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) + (other.nodes - @nodes)
        edges = (@edges - other.edges) + (other.edges - @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|

            l1 = e[:node1] || e['node1']
            l2 = e[:node2] || e['node2']

            if l2 && l1 == label

                n2 = self.get_node l2

                unless n2.nil? || neighbours.include?(n2)

                    neighbours.push(n2)

                end
            
            end

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

                n1 = self.get_node l1
            
                unless n1.nil? || 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



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
 
# File 'lib/graph.rb', line 14

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.is_a?(Node) ? attrs.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.is_a?(Edge) ? attrs.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) + (other.nodes - @nodes)
        edges = (@edges - other.edges) + (other.edges - @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|

            l1 = e[:node1] || e['node1']
            l2 = e[:node2] || e['node2']

            if l2 && l1 == label

                n2 = self.get_node l2

                unless n2.nil? || neighbours.include?(n2)

                    neighbours.push(n2)

                end
            
            end

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

                n1 = self.get_node l1
            
                unless n1.nil? || 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



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
 
# File 'lib/graph.rb', line 14

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.is_a?(Node) ? attrs.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.is_a?(Edge) ? attrs.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) + (other.nodes - @nodes)
        edges = (@edges - other.edges) + (other.edges - @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|

            l1 = e[:node1] || e['node1']
            l2 = e[:node2] || e['node2']

            if l2 && l1 == label

                n2 = self.get_node l2

                unless n2.nil? || neighbours.include?(n2)

                    neighbours.push(n2)

                end
            
            end

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

                n1 = self.get_node l1
            
                unless n1.nil? || 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) 


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

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


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

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


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

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


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

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


207
208
209
210
211
212
213
214
215
216
 
# File 'lib/graph.rb', line 207

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:



236
237
238
239
240
241
242
243
244
245
 
# File 'lib/graph.rb', line 236

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:



265
266
267
268
269
270
271
272
273
274
 
# File 'lib/graph.rb', line 265

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:



194
195
196
197
198
199
 
# File 'lib/graph.rb', line 194

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:



223
224
225
226
227
228
229
230
231
232
 
# File 'lib/graph.rb', line 223

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

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

    Graph.new(nodes, edges)
end

#clone ⇒ Object

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



289
290
291
292
293
294
295
296
297
298
 
# File 'lib/graph.rb', line 289

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:



340
341
342
343
344
345
346
347
348
349
350
351
352
353
 
# File 'lib/graph.rb', line 340

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:



283
284
285
 
# File 'lib/graph.rb', line 283

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



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
 
# File 'lib/graph.rb', line 409

def get_neighbours(n)

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

    self.edges.each do |e|

        l1 = e[:node1] || e['node1']
        l2 = e[:node2] || e['node2']

        if l2 && l1 == label

            n2 = self.get_node l2

            unless n2.nil? || neighbours.include?(n2)

                neighbours.push(n2)

            end
        
        end

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

            n1 = self.get_node l1
        
            unless n1.nil? || 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



399
400
401
402
403
404
405
 
# File 'lib/graph.rb', line 399

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:



364
365
366
367
368
369
370
371
372
373
374
 
# File 'lib/graph.rb', line 364

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:



277
278
279
 
# File 'lib/graph.rb', line 277

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:



385
386
387
388
389
390
391
392
393
394
395
 
# File 'lib/graph.rb', line 385

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


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

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.



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

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


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

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:



251
252
253
254
255
256
257
258
259
260
 
# File 'lib/graph.rb', line 251

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

    Graph.new(nodes, edges)
end