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

Author:

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



10
11
12
13
 
# File 'lib/abuelo/graph.rb', line 10

def initialize
  @nodes = {} # @nodes = { node_name => node_object }
  @edges = {} # @edges = { node_object => { node_object => edge }}
end

Instance Method Details

#add_edge(edge) ⇒ Abuelo::Graph

Adds an edge to the graph.

Parameters:

Returns:

Raises:



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

def add_edge(edge)
  raise Abuelo::Exceptions::EdgeAlreadyExistsError if has_edge?(edge)

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

#add_node(node) ⇒ Abuelo::Graph

Adds a node to the graph.

Parameters:

Returns:

Raises:



33
34
35
36
37
38
39
 
# File 'lib/abuelo/graph.rb', line 33

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

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

#edges ⇒ Array<Abuelo::Edge>

Returns list of edges of the graph.

Returns:



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

def edges
  edges = @edges.keys.map { |key| @edges[key].values }
  edges.flatten
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



120
121
122
123
124
 
# File 'lib/abuelo/graph.rb', line 120

def edges_for_node(node)
  edges = []
  edges += @edges[node].values.to_a if @edges[node]
  edges
end

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

Checks if there is an edge between the two given nodes.

Parameters:

Returns:



109
110
111
 
# File 'lib/abuelo/graph.rb', line 109

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

#has_edge?(edge) ⇒ Boolean

Checks if the given edge is contained in the graph.

Parameters:

Returns:

  • (Boolean) 


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

def has_edge?(edge)
  find_edge(edge.node_1, edge.node_2) ? true : false
end

#has_node?(node) ⇒ Boolean

Checks if the given node is contained in the graph.

Parameters:

Returns:

  • (Boolean) 


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

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) 


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

def has_node_with_name?(name)
  @nodes[name] ? true : false
end

#nodes ⇒ Array<Abuelo::Node>

Returns list of nodes of the graph.

Returns:



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

def nodes
  @nodes.values
end