Implementing Graphs in Ruby
There are two main ways to implement graphs in Ruby:
1. Hash-Based Adjacency List
Graphs can be implemented effectively using a hash-based adjacency list approach. Each node is stored as a key, with its adjacent nodes represented as values in an array or set.
- This method is efficient for sparse networks and allows for easy traversal and manipulation of graph structures.
- Examples of graphs include social networks, transportation networks, and computer networks.
- With this implementation, you can easily add nodes, create connections between them, and perform various graph algorithms to analyze the relationships between entities.
Approach:
In this code, we are using a method called hashing to store information about connections between different points.
- Imagine you have a bunch of points on a map, and each point has some nearby points connected to it.
- We use a special table (like a list of keys and values) called a hash table.
- Each point’s name is like a key in this table, and the nearby points connected to it are stored as values linked to that key.
- So, it’s like having a list where you can quickly look up any point and see which other points are nearby.
- This method helps us efficiently keep track of how different points are connected in a graph.
Example:
class Graph
def initialize
@nodes = Hash.new { |hash, key| hash[key] = [] }
end
def add_node(value)
raise ArgumentError, "Node value cannot be nil" if value.nil?
@nodes[value]
end
def add_edge(node1, node2)
raise ArgumentError, "Nodes #{node1} and #{node2}
do not exist" unless @nodes[node1] && @nodes[node2]
@nodes[node1] << node2
# For undirected graphs, add the edge in the opposite
# direction as well
@nodes[node2] << node1
end
def print_graph
@nodes.each do |node, neighbors|
puts "#{node} => #{neighbors.join(', ')}"
end
end
end
# Example usage:
graph = Graph.new
graph.add_node(1)
graph.add_node(2)
graph.add_node(3)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(3, 1)
graph.print_graph
Output:
2. Adjacency Matrix
This method represents connections between nodes using a grid like structure. Each node corresponds to both a row and a column in a two-dimensional array.
- The value at a particular row-column intersection indicates whether there is an edge (usually represented by 1) or no connection (typically represented by 0) between the corresponding nodes.
- It is efficient for quickly checking connections in networks with many edges, also known as dense networks.
Approach: The adjacency matrix is a grid, like a table, where the rows and columns represent different points, or nodes, in the graph.
- If there is a connection between two points, a “1” is placed where the row for one point and the column for the other point intersect.
- This “1” indicates that there is a link between those two points.
- So, by looking at this grid, you can quickly see which points are connected to each other without needing to search through a lot of information.
- It is like a simple way to represent connections between different points in the graph using a two dimensional array.
Example:
class Graph
def initialize(num_nodes)
@num_nodes = num_nodes
@matrix = Array.new(num_nodes) { Array.new(num_nodes, 0) }
end
def add_edge(node1, node2)
raise ArgumentError, "Invalid nodes" unless valid_node?(node1) &&
valid_node?(node2)
@matrix[node1][node2] = 1
# For undirected graphs
@matrix[node2][node1] = 1
end
def print_graph
@matrix.each do |row|
puts row.join(' ')
end
end
private
def valid_node?(node)
node >= 0 && node < @num_nodes
end
end
# Example usage:
graph = Graph.new(4)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.print_graph
Output:
How to Implement Graph in Ruby?
Graphs are basic data structures that represent the connections between different items. They are made up of edges (links) that show the connections between the entities and vertices (nodes) that represent the entities themselves. Numerous applications, such as social networks, navigation systems, routing algorithms, scheduling issues, and more, heavily rely on graphs.
Table of Content
- What is a Graph?
- Types of Graphs
- Implementing Graphs in Ruby
- Conclusion
Contact Us