Ruby TSort: Detecting Cyclic Dependencies

12 Apr 2025 - Gagan Shrestha

Understanding Ruby’s TSort for Dependency Resolution

Ruby’s standard library includes a powerful module called TSort that elegantly solves the problem of dependency ordering and cycle detection. Whether you’re building a package manager, implementing a build system, or simply dealing with complex object relationships, TSort provides a straightforward way to detect cycles and sort elements in dependency order.

What is TSort?

TSort implements a topological sort algorithm for directed graphs. In simple terms, it helps you arrange nodes in a graph such that for every directed edge from node A to node B, node A comes before node B in the ordering. This is particularly useful for dependency resolution where certain tasks or components must be processed before others.

Key Features of TSort

• Dependency detection: Determine the correct order to process interdependent elements
• Cycle detection: Identify circular dependencies that would make ordering impossible
• Simple interface: Just implement two methods to use the module

Using TSort in Your Code

To use TSort, you need to include the module in your class and implement two required methods:

1. tsort_each_node: Yields each node in the graph
2. tsort_each_child: Yields each child node for a given node

Let’s look at a practical example to see how TSort can detect cyclic dependencies.

Example: Detecting Circular Dependencies

Imagine we’re building a simple package manager where packages can depend on other packages. We need to ensure there are no circular dependencies before attempting installation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
require 'tsort'

class DependencyResolver
  include TSort

  def initialize
    @dependencies = {}
  end

  def add_package(name, depends_on = [])
    @dependencies[name] = depends_on
  end

  # TSort implementation
  def tsort_each_node(&block)
    @dependencies.keys.each(&block)
  end

  def tsort_each_child(node, &block)
    (@dependencies[node] || []).each(&block)
  end

  # Get installation order
  def installation_order
    tsort
  rescue TSort::Cyclic => e
    raise "Circular dependency detected: #{e.message}"
  end

  # Check for cycles
  def has_cycles?
    begin
      tsort
      return false
    rescue TSort::Cyclic
      return true
    end
  end

  # Get strongly connected components (cycles)
  def cycles
    strongly_connected_components.select { |component| component.size > 1 }
  end
end

Now, let’s use this class to detect some circular dependencies:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Create a new resolver
resolver = DependencyResolver.new

# Add packages and their dependencies
resolver.add_package('app', ['database', 'logger'])
resolver.add_package('database', ['config'])
resolver.add_package('logger', ['config'])
resolver.add_package('config')

# This should work fine
puts "Installation order: #{resolver.installation_order.join(', ')}"
# Output: Installation order: config, database, logger, app

# Now let's introduce a cycle
resolver = DependencyResolver.new
resolver.add_package('a', ['b'])
resolver.add_package('b', ['c'])
resolver.add_package('c', ['a'])

# Check for cycles
if resolver.has_cycles?
  puts "Circular dependencies detected!"
  resolver.cycles.each do |cycle|
    puts "Cycle: #{cycle.join(' -> ')}"
  end
else
  puts "No cycles detected. Installation order: #{resolver.installation_order.join(', ')}"
end
# Output:
# Circular dependencies detected!
# Cycle: a -> b -> c

How TSort Works Behind the Scenes

TSort uses Tarjan’s algorithm for finding strongly connected components in a graph. This algorithm visits each node exactly once, making it efficient with a time complexity of O(V+E), where V is the number of vertices and E is the number of edges.

When a cycle is detected, TSort raises a TSort::Cyclic exception, which we can catch to handle the error gracefully.

Practical Applications

TSort is useful in many scenarios:

1. Build systems: Determining the order to compile interdependent files
2. Package managers: Resolving dependencies between packages
3. Task scheduling: Ordering tasks with prerequisites
4. Database migrations: Managing schema changes that depend on each other
5. Loading configurations: Ensuring settings are loaded in the correct order

Conclusion

Ruby’s TSort module provides an elegant solution for dependency management and cycle detection. By implementing just two methods, you get access to powerful algorithms that can save you from the headaches of manually managing complex dependency relationships.

The next time you’re working with interdependent components in Ruby, remember TSort—it might just be the tool you need to keep your dependencies in order and detect those pesky circular references before they cause problems.