Skip to content

Instantly share code, notes, and snippets.

@amiralles
Created November 29, 2018 18:50
Show Gist options
  • Save amiralles/9d6a4f0ecf3e7fa887f288d60e4cd6c8 to your computer and use it in GitHub Desktop.
Save amiralles/9d6a4f0ecf3e7fa887f288d60e4cd6c8 to your computer and use it in GitHub Desktop.
Graph implementation using Ruby
require_relative "./linked_list.rb"
require_relative "./set.rb"
# Here we monkey patched LinkedList to add a method
# that allows us to remove vertices in constant time.
class LinkedList
# Removes the node that is right next
# to the specified node.
# Complexity O(1).
def remove_next prev_node
return nil unless self.length > 0
unless prev_node
# remove head.
self.head = self.head.next
else
if prev_node.next == prev_node
self.head = nil
else
old = prev_node.next
prev_node.next = prev_node.next&.next
if (old == self.head)
self.head = old.next
end
end
end
self.length -= 1
end
end
class Graph
class Vertex
attr_accessor :key, :edges
def initialize key
self.key = key
self.edges = Set.new
end
def to_s
self.key.to_s
end
end
# Initializes an empty graph.
def initialize
@vertices = LinkedList.new
end
# Finds a vertext based on its key.
# Complexity O(n)
def find_vertex key
@vertices.find_first { |v| v.data.key == key }
end
# Inserts a new vertex (node) into the graph.
# Complexity O(n) where n is the number
# of vertices in the graph.
def insert_vertex key
# No dupes allowed.
return if find_vertex key
vertex = Vertex.new key
@vertices.insert vertex
end
# Inserts an edge into the graph
# to connect two nodes.
# Complexity O(n) where n is the number
# of vertices in the graph.
def insert_edge key1, key2
# The graph must contains vertices.
v1 = find_vertex key1
return unless v1
v2 = find_vertex key2
return unless v2
v1.data.edges.insert v2.data.key
end
# Removes a vertex from the graph.
# Complexity O(n + e) where *n* is the number
# of vertices in the graph and *e* is the number
# of edges.
def remove_vertex key
# Have we found the target vertex?
found = false
# This points to the vertex that
# we want to remove.
target = nil
# This point to the node that is
# previous to the one that holds
# the vertex we want to remove on
# the vertices lits.
prev = nil
@vertices.each do |v|
# Can't remove if the node it's referenced
# by other vertices.
return if v.data.edges.contains? key
if v.data.key == key
found = true
target = v.data
end
prev = v unless found
end
return unless found
# Can't remove if the node contains
# references to other vertices.
return unless target.edges.length == 0
# Here we use remove_next to delete
# the vertex in constant time.
@vertices.remove_next prev
end
# Removes an edge from the graph.
# Complexity O(n) where n is the number
# of vertices in the graph.
def remove_edge key1, key2
vertex = find_vertex(key1)&.data
return unless vertex
vertex.edges.remove key2
end
# Tells if two vertices (nodes) are adjacent or not.
# Complexity O(n) where n is the number
# of vertices in the graph.
def adjacent? key1, key2
vertex = find_vertex(key1)&.data
return true if vertex&.edges.contains? key2
return false
end
# Print the contents of the current graph.
# Complexity O(n + e) where *n* is the number
# of vertices in the graph and *e* is the number
# of edges.
def print
@vertices.each do |v|
puts "#{v.data} (vertex)"
v.data.edges.each do |e|
puts " #{e.data} (edge)"
end
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment