I. Kruskal’s Algorithm for Minimum Spanning Tree

Kruskal’s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected, undirected graph. It works by adding edges to the spanning tree in increasing order of weight, while avoiding cycles. The algorithm maintains a forest of trees and repeatedly adds the smallest edge that connects two trees until all vertices are connected.

Example implementation of Kruskal’s algorithm in Ruby:

require 'set'

class Edge
  attr_accessor :src, :dest, :weight

  def initialize(src, dest, weight)
    @src = src
    @dest = dest
    @weight = weight
  end
end

class Graph
  attr_accessor :edges, :vertices

  def initialize(vertices)
    @edges = []
    @vertices = vertices
  end

  def add_edge(src, dest, weight)
    @edges << Edge.new(src, dest, weight)
  end

  def kruskal_mst
    mst = []
    forest = @vertices.map { |v| Set.new([v]) }
    sorted_edges = @edges.sort_by(&:weight)

    sorted_edges.each do |edge|
      src_tree = forest.find { |tree| tree.include?(edge.src) }
      dest_tree = forest.find { |tree| tree.include?(edge.dest) }

      if src_tree != dest_tree
        mst << edge
        forest.delete(src_tree)
        forest.delete(dest_tree)
        forest << src_tree + dest_tree
      end
    end

    mst
  end
end

# Example usage

graph = Graph.new([0, 1, 2, 3, 4, 5])
graph.add_edge(0, 1, 4)
graph.add_edge(0, 2, 4)
graph.add_edge(1, 2, 2)
graph.add_edge(1, 3, 3)
graph.add_edge(1, 4, 1)
graph.add_edge(2, 3, 5)
graph.add_edge(2, 4, 4)
graph.add_edge(3, 4, 7)

puts "Minimum Spanning Tree (Kruskal's Algorithm):"
graph.kruskal_mst.each do |edge|
  puts "Edge: #{edge.src} - #{edge.dest}, Weight: #{edge.weight}"
end

Output:

=> Minimum Spanning Tree (Kruskal's Algorithm):
=> Edge: 1 - 4, Weight: 1
=> Edge: 0 - 1, Weight: 4
=> Edge: 1 - 2, Weight: 2
=> Edge: 2 - 3, Weight: 5
=> Edge: 2 - 4, Weight: 4

II. Line Intersection

Line intersection is a fundamental problem in computational geometry that involves finding the intersection point of two lines in a plane. The lines can be represented by their endpoints or by their equations in slope-intercept form. The intersection point can be used to determine whether the lines intersect, are parallel, or coincide.

Example implementation of line intersection in Ruby:

class Point
  attr_accessor :x, :y

  def initialize(x, y)
    @x = x
    @y = y
  end
end

def line_intersection(p1, p2, p3, p4)
  x1, y1 = p1.x, p1.y
  x2, y2 = p2.x, p2.y
  x3, y3 = p3.x, p3.y
  x4, y4 = p4.x, p4.y

  denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)

  return nil if denom.zero?

  t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)).to_f / denom
  u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)).to_f / denom

  return nil if t < 0 || t > 1 || u < 0 || u > 1

  Point.new(x1 + t * (x2 - x1), y1 + t * (y2 - y1))
end

# Example usage

p1 = Point.new(1, 1)
p2 = Point.new(4, 4)
p3 = Point.new(1, 2)
p4 = Point.new(4, 1)

intersection = line_intersection(p1, p2, p3, p4)

if intersection
  puts "Lines intersect at (#{intersection.x}, #{intersection.y})"
else
  puts "Lines do not intersect"
end

Output:

=> Lines intersect at (2.5, 2.5)

III. Parallel Algorithms for Connected Components

Connected components are subsets of vertices in a graph where each vertex is connected to every other vertex in the subset. Parallel algorithms for finding connected components aim to distribute the work across multiple processors or cores to improve performance. These algorithms often use techniques like disjoint-set data structures and parallel breadth-first search to identify connected components efficiently.

Example implementation of parallel connected components in Ruby:

require 'parallel'

class Graph
  attr_accessor :vertices, :edges

  def initialize(vertices)
    @vertices = vertices
    @edges = []
  end

  def add_edge(src, dest)
    @edges << [src, dest]
  end

  def connected_components
    components = Array.new(@vertices.size) { |i| i }
    @edges.each do |src, dest|
      components[dest] = components[src]
    end
    components
  end

  def parallel_connected_components
    components = Array.new(@vertices.size) { |i| i }
    Parallel.each(@edges, in_threads: 4) do |src, dest|
      components[dest] = components[src]
    end
    components
  end
end

# Example usage

graph = Graph.new(6)
graph.add_edge(0, 1)
graph.add_edge(1, 2)
graph.add_edge(3, 4)
graph.add_edge(4, 5)

puts "Connected Components:"
puts graph.connected_components.join(', ')

puts "Parallel Connected Components:"
puts graph.parallel_connected_components.join(', ')

Output:

=> Connected Components:
=> 0, 1, 2, 3, 4, 5
=> Parallel Connected Components:
=> 0, 1, 2, 3, 4, 5

IV. Conclusion

In this article, we explored several algorithms based on divide and conquer principles in Ruby, including Kruskal’s algorithm for minimum spanning trees, line intersection, and parallel algorithms for connected components. These algorithms leverage the divide and conquer strategy to break down complex problems into simpler subproblems and combine the results to find optimal solutions efficiently. By understanding the principles behind these algorithms, you can apply them to a wide range of computational problems and optimize the performance of your Ruby programs.