Class: Graphshaper::UndirectedGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/graphshaper/undirected_graph.rb

Overview

A Graph is undirected when its edges do not have a direction.

Instance Method Summary collapse

Constructor Details

#initialize(number_of_vertices, options_hash = {}) ⇒ UndirectedGraph

Create a graph with a given number of vertices and no edges.

Parameters:

  • number_of_vertices (Integer)

    The number of vertices that the generated graph should have

  • options_hash (Hash) (defaults to: {})

    The options to create an undirected graph

Options Hash (options_hash):

  • :adapters (Array<Object>)

    An array of adapters you want to use


13
14
15
16
17
18
19
20
21
# File 'lib/graphshaper/undirected_graph.rb', line 13

def initialize(number_of_vertices, options_hash = {})
  @adapters = options_hash[:adapters] if options_hash.has_key? :adapters

  @vertex_degrees = []
  @unconnected_vertices = Set.new

  number_of_vertices.times { add_vertex }
  @edges = Set.new
end

Instance Method Details

#add_edge(first_vertex_id, second_vertex_id) ⇒ Object

Add a new edge to the graph between two existing vertices.

Parameters:

  • first_vertex_id (Integer)
  • second_vertex_id (Integer)

Raises:

  • (RuntimeError)

    The method throws a RuntimeError if you try to add a self-referential edge or an edge with a non-existing vertex.


81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
# File 'lib/graphshaper/undirected_graph.rb', line 81

def add_edge(first_vertex_id, second_vertex_id)
  if first_vertex_id == second_vertex_id
    raise "No Self-Referential Edge"
  elsif first_vertex_id >= order || second_vertex_id >= order
    raise "ID doesn't exist"
  else
    @unconnected_vertices.delete first_vertex_id
    @vertex_degrees[first_vertex_id] += 1
    @unconnected_vertices.delete second_vertex_id
    @vertex_degrees[second_vertex_id] += 1
    @edges << [first_vertex_id, second_vertex_id].sort

    unless @adapters.nil?
      @adapters.each do |adapter|
        adapter.add_edge @edges.length - 1, first_vertex_id, second_vertex_id
      end
    end
  end
end

#add_vertex {|preferential_attachment| ... } ⇒ Integer

Add a new vertex to the graph. If you call it with a block {|preferential_attachment| … }, the block will be called for every existing vertex: An edge from the new vertex to this vertex will be created if and only if the block returns true.

Yields:

  • (preferential_attachment)

    The block that tests if the edge should be added.

Yield Parameters:

  • preferential_attachment (Float)

    The preferential attachment of the existing vertex

Yield Returns:

  • (Boolean)

    Should the edge be added?

Returns:

  • (Integer)

    ID of the newly created vertex.


55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
# File 'lib/graphshaper/undirected_graph.rb', line 55

def add_vertex(&block)
  new_vertex_id = @vertex_degrees.length

  @vertex_degrees << 0
  @unconnected_vertices << new_vertex_id

  unless @adapters.nil?
    @adapters.each do |adapter|
      adapter.add_vertex new_vertex_id
    end
  end

  if block_given?
    each_vertex_with_preferential_attachment do |vertex_id, preferential_attachment|
      add_edge new_vertex_id, vertex_id if block.call(preferential_attachment)
    end
  end

  new_vertex_id
end

#connect_all_verticesObject

Connect all orphans with existing nodes


38
39
40
41
42
43
44
45
# File 'lib/graphshaper/undirected_graph.rb', line 38

def connect_all_vertices
  while number_of_orphans > 0
    vertex_orphan = orphans.shuffle.first
    while vertex_orphan == (random_vertex = rand(order)); end

    add_edge vertex_orphan, random_vertex
  end
end

#degree_distributionArray<Integer>

Calculates the distribution of degrees in the graph. The value at the n-th position of the returned array is the number of vertices with n edges.

Returns:

  • (Array<Integer>)

    The degree distribution as an array of Integers.


135
136
137
138
139
140
141
142
143
144
145
# File 'lib/graphshaper/undirected_graph.rb', line 135

def degree_distribution
  degree_distribution = []
  @vertex_degrees.each do |vertex_degree|
    if degree_distribution[vertex_degree]
      degree_distribution[vertex_degree] += 1
    else
      degree_distribution[vertex_degree] = 1
    end
  end
  degree_distribution
end

#each_vertex_with_preferential_attachment {|vertex_id, preferential_attachment| ... } ⇒ Object

Iterate over all vertices of the graph. Call it with a block {|vertex_id, preferential_attachment| … }.

Yields:

  • (vertex_id, preferential_attachment)

    The block that tests if the edge should be added.

Yield Parameters:

  • vertex_id (Integer)

    The preferential attachment of the existing vertex

  • preferential_attachment (Float)

    The preferential attachment of the existing vertex


159
160
161
162
163
164
165
166
167
168
# File 'lib/graphshaper/undirected_graph.rb', line 159

def each_vertex_with_preferential_attachment(&block)
  if sum_of_all_degrees > 0
    preferential_attachments = @vertex_degrees.map { |degree| degree.round(1) / sum_of_all_degrees }
    vertex_id = 0
    preferential_attachments.each do |preferential_attachment|
      block.call vertex_id, preferential_attachment
      vertex_id += 1
    end
  end
end

#edge_between?(first_vertex_id, second_vertex_id) ⇒ Boolean

Tests, if an edge between the two vertices exists.

Parameters:

  • first_vertex_id (Integer)
  • second_vertex_id (Integer)

Returns:

  • (Boolean)

    Does the vertex exist?


106
107
108
# File 'lib/graphshaper/undirected_graph.rb', line 106

def edge_between?(first_vertex_id, second_vertex_id)
  @edges.include? [first_vertex_id, second_vertex_id]
end

#number_of_orphansInteger

The number of vertices without edges.

Returns:

  • (Integer)

    Number of vertices without edges.


113
114
115
# File 'lib/graphshaper/undirected_graph.rb', line 113

def number_of_orphans
  @unconnected_vertices.to_a.length
end

#orderInteger

The number of vertices.

Returns:

  • (Integer)

    Number of vertices.


26
27
28
# File 'lib/graphshaper/undirected_graph.rb', line 26

def order
  @vertex_degrees.length
end

#orphansArray<Integer>

The vertices without edges as an array.

Returns:

  • (Array<Integer>)

    IDs of the Vertices without edges.


120
121
122
# File 'lib/graphshaper/undirected_graph.rb', line 120

def orphans
  @unconnected_vertices.to_a
end

#sizeInteger

The number of edges.

Returns:

  • (Integer)

    Number of edges.


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

def size
  @edges.length
end

#sum_of_all_degreesInteger

Return the sum of all degrees.

Returns:

  • (Integer)

    Sum of all degrees


150
151
152
# File 'lib/graphshaper/undirected_graph.rb', line 150

def sum_of_all_degrees
  @edges.length * 2
end

#vertex_degree_for(vertex_id) ⇒ Integer

Return the vertex degree for the vertex with the given ID.

Parameters:

  • vertex_id (Integer)

Returns:

  • (Integer)

    Degree of the given vertex


128
129
130
# File 'lib/graphshaper/undirected_graph.rb', line 128

def vertex_degree_for(vertex_id)
  @vertex_degrees[vertex_id]
end