Class: SimpleGraph::Graph

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

Overview

A class representing a unweighted, undirected graph

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph



26
27
28
29
30
31
32
33
 
# File 'lib/simple_graph.rb', line 26

def initialize
  # Our array of internal nodes
  @nodes = []
  # Helper hash lookup table
  @nodes_by_id = {}
  # Tracks the highest used id for autoincrement
  @last_id = 0
end

Instance Method Details

#add_node(id: nil, data: {}) ⇒ Object

Add a new node to the graph



41
42
43
44
45
46
47
 
# File 'lib/simple_graph.rb', line 41

def add_node(id: nil, data: {})
  id ||= next_id
  node = Graph::Node.new(id: id, data: data)
  @nodes << node
  @nodes_by_id[id] = node
  node
end

#are_connected?(first, second) ⇒ Boolean

Check if two nodes are connected by an edge

Returns:

  • (Boolean) 


87
88
89
 
# File 'lib/simple_graph.rb', line 87

def are_connected?(first, second)
  @nodes_by_id[first].neighbors.include?(@nodes_by_id[second])
end

#clear ⇒ Object

Remove all nodes from the graph



36
37
38
 
# File 'lib/simple_graph.rb', line 36

def clear
  initialize
end

#connect_nodes(first, second) ⇒ Object

Method to connect 2 nodes



76
77
78
79
 
# File 'lib/simple_graph.rb', line 76

def connect_nodes(first, second)
  @nodes_by_id[first].add_neighbor(@nodes_by_id[second])
  @nodes_by_id[second].add_neighbor(@nodes_by_id[first])
end

#delete_node(node) ⇒ Object

Delete a node from the graph



50
51
52
53
54
55
56
57
 
# File 'lib/simple_graph.rb', line 50

def delete_node(node)
  # Remove all edges connected with this node
  node.neighbors.each do |neighbor|
    neighbor.neighbors.delete(node)
  end
  # Remove the node itself
  @nodes.delete(node)
end

#find_paths(source_id, terminal_id) ⇒ Object

Returns all the paths between two nodes as found by breadth-first-search



144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
 
# File 'lib/simple_graph.rb', line 144

def find_paths(source_id, terminal_id)
  found_paths = []

  # Path queue
  paths = Queue.new

  destination = @nodes_by_id[terminal_id]

  # Current Path
  path = [@nodes_by_id[source_id]]

  paths << path

  until paths.empty?
    path = paths.pop

    last = path.last

    found_paths << path if last == destination

    last.neighbors.each do |neighbor|
      next if path.include?(neighbor)
      # Note that this creates a copy of the current path.
      paths << path + [neighbor]
    end
  end

  found_paths.map { |found_path| found_path.map { |item| { item.id => item.data } } }
end

#include?(node_id) ⇒ Boolean

Checks whether the graph contains a node with the given ID

Returns:

  • (Boolean) 


82
83
84
 
# File 'lib/simple_graph.rb', line 82

def include?(node_id)
  @nodes_by_id.key?(node_id)
end

#load_from_json(str) ⇒ Object

Loads the graph from a JSON string Returns the number of Nodes imported



126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
 
# File 'lib/simple_graph.rb', line 126

def load_from_json(str)
  temp_hash = JSON.parse(str)
  nodes = temp_hash["nodes"]
  edges = temp_hash["edges"]

  nodes.each do |node_id, data|
    add_node(id: node_id, data: data)
  end

  edges.each do |node_pair|
    # Ignore duplicate edges for now
    connect_nodes(node_pair.first, node_pair.last) unless are_connected?(node_pair.first, node_pair.last)
  end

  nodes.length
end

#node_count ⇒ Object

Retrieve the amount of nodes in the graph



60
61
62
 
# File 'lib/simple_graph.rb', line 60

def node_count
  @nodes.length
end

#node_ids ⇒ Object

Retrieve a array of node ids in the graph



65
66
67
68
 
# File 'lib/simple_graph.rb', line 65

def node_ids
  # The .to_a call is used to return a copy of the array so it cannot be modified from the outside.
  @nodes_by_id.keys.to_a
end

#nodes ⇒ Object

Returns a hash of nodes in the graph mapped to node_id => node_data pairs



71
72
73
 
# File 'lib/simple_graph.rb', line 71

def nodes
  @nodes.map { |node| { node.id => node.data } }
end

#to_dot_string ⇒ Object

Retrieve the current graph in the DOT format to be used with Graphviz



92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/simple_graph.rb', line 92

def to_dot_string
  str = "strict graph {\n"

  @nodes.each do |node|
    node.neighbors.each do |neighbor|
      str << "    \"#{node.id}\" -- \"#{neighbor.id}\";\n"
    end
  end

  str << "}"
end

#to_json ⇒ Object

Dumps the graph to a JSON string



105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/simple_graph.rb', line 105

def to_json
  temp_hash = {
    nodes: {},
    edges: []
  }

  @nodes.each do |node|
    temp_hash[:nodes][node.id] = node.data
  end

  @nodes.each do |node|
    node.neighbors.each do |neighbor|
      temp_hash[:edges] << [node.id, neighbor.id]
    end
  end

  JSON.dump(temp_hash)
end