Graph implementation using Ruby

graph.rb

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