class SimpleGraph::Graph
A class representing a unweighted, undirected graph
Public Class Methods
new()
click to toggle source
# 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
Public Instance Methods
add_node(id: nil, data: {})
click to toggle source
Add a new node to the graph
# 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)
click to toggle source
Check if two nodes are connected by an edge
# File lib/simple_graph.rb, line 87 def are_connected?(first, second) @nodes_by_id[first].neighbors.include?(@nodes_by_id[second]) end
clear()
click to toggle source
Remove all nodes from the graph
# File lib/simple_graph.rb, line 36 def clear initialize end
connect_nodes(first, second)
click to toggle source
Method to connect 2 nodes
# 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)
click to toggle source
Delete a node from the graph
# 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)
click to toggle source
Returns all the paths between two nodes as found by breadth-first-search
# 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)
click to toggle source
Checks whether the graph contains a node with the given ID
# File lib/simple_graph.rb, line 82 def include?(node_id) @nodes_by_id.key?(node_id) end
load_from_json(str)
click to toggle source
Loads the graph from a JSON string Returns the number of Nodes imported
# 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()
click to toggle source
Retrieve the amount of nodes in the graph
# File lib/simple_graph.rb, line 60 def node_count @nodes.length end
node_ids()
click to toggle source
Retrieve a array of node ids in the graph
# 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()
click to toggle source
Returns a hash of nodes in the graph mapped to node_id => node_data pairs
# File lib/simple_graph.rb, line 71 def nodes @nodes.map { |node| { node.id => node.data } } end
to_dot_string()
click to toggle source
Retrieve the current graph in the DOT format to be used with Graphviz
# 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()
click to toggle source
Dumps the graph to a JSON string
# 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
Private Instance Methods
next_id()
click to toggle source
Helper method to autoincrement generated node IDs
# File lib/simple_graph.rb, line 177 def next_id @last_id += 1 while @nodes_by_id.keys.include?(@last_id + 1) @last_id += 1 end