Class: Abuelo::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/abuelo/graph.rb

Overview

Class Graph provides a representation of a directed graph.

A graph consists of nodes (= vertices, points) and edges (= lines, arcs). The graph may be undirected or directed. For the sake of simplicity Abuelo sticks with the same vocabulary (nodes, edges) for directed and undirected graphs in contrast to theoretical graph theory.

Author:

Instance Method Summary collapse

Constructor Details

#initialize(opts = {}) ⇒ Graph

Returns a new instance of Graph.

Examples:

Build a graph with the help of an adjacency matrix

adjacency_matrix = <<-matrix
   0 42  0
  42  0 23
   0 23  0
  matrix
graph = Abuelo::Graph.new(adjacency_matrix: adjacency_matrix)

Parameters:

  • opts (Hash) (defaults to: {}) —

    the options to create a graph with

Options Hash (opts):

  • :directed (Boolean) —

    defines if the graph is directed or undirected. (defaults to false == undirected)

  • :adjacency_matrix (String) —

    a representation of the graph in form of an adjacency matrix



28
29
30
31
32
33
 
# File 'lib/abuelo/graph.rb', line 28

def initialize(opts = {})
  @nodes = {} # @nodes = { node_name => node_object }
  @edges = {} # @edges = { node_object => { node_object => edge }}
  @directed = opts.fetch(:directed, false)
  init_by_adjacency_matrix(opts[:adjacency_matrix]) if opts[:adjacency_matrix]
end

Instance Method Details

#add_edge(edge, opts = {}) ⇒ Abuelo::Graph

Adds an edge to the graph. Auto-adds the symmetric counterpart if graph is undirected.

Parameters:

Returns:

Raises:



154
155
156
157
158
159
160
161
162
163
164
165
 
# File 'lib/abuelo/graph.rb', line 154

def add_edge(edge, opts = {})
  raise Abuelo::Exceptions::EdgeAlreadyExistsError if has_edge?(edge)

  @edges[edge.node_1] ||= {}
  @edges[edge.node_1][edge.node_2] = edge

  if undirected? && !opts[:symmetric]
    add_edge(edge.symmetric, symmetric: true)
  end

  self
end

#add_node(node) ⇒ Abuelo::Graph

Adds a node to the graph.

Parameters:

Returns:

Raises:



80
81
82
83
84
85
86
87
 
# File 'lib/abuelo/graph.rb', line 80

def add_node(node)
  raise Abuelo::Exceptions::NodeAlreadyExistsError if has_node?(node)

  @nodes[node.name] = node
  node.graph = self

  self
end

#directed? ⇒ Boolean

Returns true if the graph is directed, false if it is undirected.

Returns:

  • (Boolean) —

    true if the graph is directed, false if it is undirected



38
39
40
 
# File 'lib/abuelo/graph.rb', line 38

def directed?
  @directed
end

#edges ⇒ Array<Abuelo::Edge>, Array<Array(Abuelo::Edge, Abuelo::Edge)>

Returns list of edges of the graph if directed, list of list of symmetric pairs of edges of the graph if undirected.

Examples:

directed graph

"graph.edges" #=> [edge_from_node_1_to_node_2]

undirected graph

"graph.edges" #=> [[edge_from_node_1_to_node_2, edge_from_node_2_to_node_1]]

Returns:



133
134
135
136
137
138
139
140
141
 
# File 'lib/abuelo/graph.rb', line 133

def edges
  edges = @edges.keys.flat_map { |key| @edges[key].values }

  if directed?
    edges
  else
    edges.each_slice(2).to_a
  end
end

#edges_for_node(node) ⇒ Array<Abuelo::Edge>

Returns all edges that start from the given node.

Parameters:

Returns:

  • (Array<Abuelo::Edge>) —

    list of edges that start from the given node



197
198
199
 
# File 'lib/abuelo/graph.rb', line 197

def edges_for_node(node)
  Hash(@edges[node]).values
end

#find_edge(node_1, node_2) ⇒ Abuelo::Edge?

Returns the edge if there is one between the two given nodes.

Parameters:

Returns:



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

def find_edge(node_1, node_2)
  @edges[node_1][node_2] if @edges[node_1]
end

#find_node_by_name(name) ⇒ Abuelo::Node?

Returns the node with the given name if it is contained in the graph.

Parameters:

  • name (String) —

    of the node

Returns:



118
119
120
 
# File 'lib/abuelo/graph.rb', line 118

def find_node_by_name(name)
  @nodes[name]
end

#has_edge?(edge) ⇒ Boolean

Checks if the given edge is contained in the graph.

Parameters:

Returns:

  • (Boolean) 


174
175
176
 
# File 'lib/abuelo/graph.rb', line 174

def has_edge?(edge)
  !find_edge(edge.node_1, edge.node_2).nil?
end

#has_node?(node) ⇒ Boolean

Checks if the given node is contained in the graph.

Parameters:

Returns:

  • (Boolean) 


96
97
98
 
# File 'lib/abuelo/graph.rb', line 96

def has_node?(node)
  has_node_with_name?(node.name)
end

#has_node_with_name?(name) ⇒ Boolean

Checks if a node with the given name is contained in the graph.

Parameters:

  • name (String) —

    of the node

Returns:

  • (Boolean) 


107
108
109
 
# File 'lib/abuelo/graph.rb', line 107

def has_node_with_name?(name)
  !find_node_by_name(name).nil?
end

#nodes ⇒ Array<Abuelo::Node>

Returns list of nodes of the graph.

Returns:



66
67
68
 
# File 'lib/abuelo/graph.rb', line 66

def nodes
  @nodes.values
end

#order ⇒ Integer

Returns the order of the graph == the number of nodes.

Returns:

  • (Integer) —

    the order of the graph == the number of nodes



52
53
54
 
# File 'lib/abuelo/graph.rb', line 52

def order
  nodes.count
end

#size ⇒ Integer

Returns the size of the graph == the number of edges.

Returns:

  • (Integer) —

    the size of the graph == the number of edges



59
60
61
 
# File 'lib/abuelo/graph.rb', line 59

def size
  edges.count
end

#undirected? ⇒ Boolean

Returns true if the graph is undirected, false if it is directed.

Returns:

  • (Boolean) —

    true if the graph is undirected, false if it is directed



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

def undirected?
  !directed?
end