Class: RandomGraph::Graph

Inherits:
Object
  • Object
show all
Extended by:
RandomGenerators
Includes:
Enumerable, GraphAlgorithms
Defined in:
lib/random_graph/graph.rb

Overview

Graph class implements basic graph object and relevant instance methods

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from RandomGenerators

erdos_renyi_gnm, erdos_renyi_gnp, preferential_attachment, random_grid, watts_strogatz

Methods included from GraphAlgorithms

#BFS_distance, #average_case_diameter, #clustering_coefficient, #connected_component, #number_of_components, #worst_case_diameter

Constructor Details

#initialize(size = 0) ⇒ Graph

We will used the adjacency list representation of a graph default to size 0



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

def initialize(size = 0)
  @viz_counter = 0
  @size = size
  @nodes = Array.new(size) { [] }
end

Instance Attribute Details

#nodes ⇒ Object

Returns the value of attribute nodes.



13
14
15
 
# File 'lib/random_graph/graph.rb', line 13

def nodes
  @nodes
end

#size ⇒ Object (readonly)

Returns the value of attribute size.



12
13
14
 
# File 'lib/random_graph/graph.rb', line 12

def size
  @size
end

#viz_counter ⇒ Object

Returns the value of attribute viz_counter.



14
15
16
 
# File 'lib/random_graph/graph.rb', line 14

def viz_counter
  @viz_counter
end

Instance Method Details

#add_edge(from, to) ⇒ Object

add edge between two nodes



48
49
50
51
52
53
54
55
 
# File 'lib/random_graph/graph.rb', line 48

def add_edge(from, to)
  fail ArgumentError.new('invalid node') if from >= @size || from < 0
  fail ArgumentError.new('invalid node') if to >= @size || to < 0
  unless to == from
    @nodes[from] << to unless @nodes[from].include?(to)
    @nodes[to] << from unless @nodes[to].include?(from)
  end
end

#add_node ⇒ Object 



37
38
39
40
41
 
# File 'lib/random_graph/graph.rb', line 37

def add_node
  new_node = []
  @nodes << new_node
  @size += 1
end

#adjacent_nodes(v) ⇒ Object 



74
75
76
 
# File 'lib/random_graph/graph.rb', line 74

def adjacent_nodes(v)
  @nodes[v]
end

#average_degree ⇒ Object 



93
94
95
 
# File 'lib/random_graph/graph.rb', line 93

def average_degree
  2.0 * edge_number / size
end

#degree(node) ⇒ Object 



62
63
64
 
# File 'lib/random_graph/graph.rb', line 62

def degree(node)
  @nodes[node].size
end

#each ⇒ Object 



43
44
45
 
# File 'lib/random_graph/graph.rb', line 43

def each
  @nodes.each { |v| yield v }
end

#edge?(from, to) ⇒ Boolean

is there an edge between two nodes?

Returns:

  • (Boolean) 


79
80
81
82
83
 
# File 'lib/random_graph/graph.rb', line 79

def edge?(from, to)
  # check if nodes are valid?
  invalid_nodes = from >= @size || from < 0 || to >= @size || to < 0
  @nodes[from].include?(to) unless invalid_nodes
end

#edge_number ⇒ Object 



85
86
87
88
89
90
91
 
# File 'lib/random_graph/graph.rb', line 85

def edge_number
  count = 0
  @nodes.each do |n|
    count += n.size
  end
  count / 2
end

#max_degree ⇒ Object 



66
67
68
69
70
71
72
 
# File 'lib/random_graph/graph.rb', line 66

def max_degree
  max_deg = 0
  @nodes.each do |v|
    max_deg = v.size if max_deg < v.size
  end
  max_deg
end

#remove_edge(from, to) ⇒ Object 



57
58
59
60
 
# File 'lib/random_graph/graph.rb', line 57

def remove_edge(from, to)
  @nodes[from].delete(to) if @nodes[from].include?(to)
  @nodes[to].delete(from) if @nodes[to].include?(from)
end

#visualize ⇒ Object 



24
25
26
27
28
29
30
31
32
33
34
35
 
# File 'lib/random_graph/graph.rb', line 24

def visualize
  g = GraphViz.new(:G, type: :graph)
  real_nodes = Array.new(@size)
  (0...@size).each { |i| real_nodes[i] = g.add_nodes("#{i}") }
  (0...@size).each do |i|
    @nodes[i].each do |n|
      g.add_edges(real_nodes[i], real_nodes[n]) if i < n
    end
  end
  g.output(png: "graph_#{@viz_counter}.png")
  @viz_counter += 1
end