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

Create a new Graph from one set of nodes and one set of edges

Parameters:

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

    Nodes of the graph

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

    Edges of the graph



212
213
214
215
216
 
# File 'lib/graph.rb', line 212

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

Instance Attribute Details

#attrs ⇒ Hash

Returns the graph’s attributes.

Returns:

  • (Hash) —

    the graph’s attributes



207
208
209
 
# File 'lib/graph.rb', line 207

def attrs
  @attrs
end

#edges ⇒ EdgeArray

Returns the graph’s edges.

Returns:



204
205
206
 
# File 'lib/graph.rb', line 204

def edges
  @edges
end

#nodes ⇒ NodeArray

Returns the graph’s nodes.

Returns:



201
202
203
 
# File 'lib/graph.rb', line 201

def nodes
  @nodes
end

Class Method Details

.get_label(n) ⇒ String

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

Returns:

  • (String) 


486
487
488
489
490
491
492
493
494
495
496
 
# File 'lib/graph.rb', line 486

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

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

    label
end

.intersection(*graphs) ⇒ 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.

Parameters:

  • options (Hash) —

    a customizable set of options

Returns:

See Also:



19
20
21
 
# File 'lib/graph.rb', line 19

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

.union(*graphs) ⇒ Graph

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.

Parameters:

  • options (Hash) —

    a customizable set of options

Returns:

See Also:



33
34
35
 
# File 'lib/graph.rb', line 33

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

.xor(*graphs) ⇒ Graph

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

Returns:

See Also:



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

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

Instance Method Details

#&(other) ⇒ Graph

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:

Returns:

See Also:



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

def &(other)
    return unless other.is_a?(Graph)

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

    Graph.new(nodes, edges)
end

#+(other) ⇒ Graph

Add two graphs, keeping duplicate nodes and edges

Parameters:

Returns:



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

def +(other)
    return unless other.is_a?(Graph)

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

    Graph.new(nodes, edges)
end

#-(other) ⇒ Graph

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

Parameters:

Returns:



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

def -(other)
    return unless other.is_a?(Graph)

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

    Graph.new(nodes, edges)
end

#==(other) ⇒ Boolean

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

Parameters:

Returns:

  • (Boolean) 


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

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

#^(other) ⇒ Graph

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:

Returns:

See Also:



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

def ^(other)
    return unless other.is_a?(Graph)

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

    Graph.new(nodes, edges)
end

#clone ⇒ Graph

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

Returns:

  • (Graph) —

    a new graph



314
315
316
317
318
319
320
321
322
323
 
# File 'lib/graph.rb', line 314

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) ⇒ Integer

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

Returns:

  • (Integer)

See Also:



367
368
369
370
371
372
373
374
375
376
377
378
379
380
 
# File 'lib/graph.rb', line 367

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:



307
308
309
 
# File 'lib/graph.rb', line 307

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

#get_neighbours(n) ⇒ Array<Node>

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

Returns:



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

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) ⇒ Node

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

Parameters:

  • label (String) —

    A node’s label

Returns:



431
432
433
434
435
 
# File 'lib/graph.rb', line 431

def get_node(label)
    label = Graph::get_label(label)

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

#in_degree_of(n) ⇒ Integer

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

Returns:

  • (Integer)

See Also:



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

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) ⇒ Graph

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

Parameters:

Returns:



300
301
302
 
# File 'lib/graph.rb', line 300

def not(other)
    self - other
end

#out_degree_of(n) ⇒ Integer

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 node’s label

Returns:

  • (Integer)

See Also:



416
417
418
419
420
421
422
423
424
425
426
 
# File 'lib/graph.rb', line 416

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) ⇒ String

Returns a GDF version of the current graph

Parameters:

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

    A customizable set of options

Returns:

  • (String)

See Also:



12
13
14
 
# File 'lib/graphs/gdf.rb', line 12

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

#to_json(opts = nil) ⇒ String

Returns a JSON version of the current graph

Parameters:

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

    A customizable set of options

Returns:

  • (String)

See Also:



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

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.

Returns:



331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
 
# File 'lib/graph.rb', line 331

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

Returns:

See Also:



21
22
23
24
25
26
 
# File 'lib/graphs/gdf.rb', line 21

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

Returns:

See Also:

  • JSON.unparse


21
22
23
24
25
26
 
# File 'lib/graphs/json.rb', line 21

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

#|(other) ⇒ Graph

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:

Returns:



277
278
279
280
281
282
283
284
 
# File 'lib/graph.rb', line 277

def |(other)
    return unless other.is_a?(Graph)

    nodes = @nodes | other.nodes
    edges = @edges | other.edges

    Graph.new(nodes, edges)
end