Brazing Order and the Topology of Dependencies

A bicycle frame isn’t brazed in arbitrary order. You do the head tube to top tube first, then the down tube, then the bottom bracket. The seat stays come last. Why? Because every time you heat a joint, nearby finished joints risk re-melting. The frame’s topology — which tubes connect to which — dictates the sequence.

This is the same problem make solved in 1976. You can’t compile main.o before utils.o if main depends on utils. Topological sort finds a valid ordering of tasks when some must precede others, or tells you there’s a cycle (a deadlock, an impossible frame).

Elixir’s recursive approach builds the order by peeling off nodes with no dependencies:

defmodule Topo do
  def sort(graph) do
    case Enum.find(graph, fn {_, deps} -> deps == [] end) do
      nil -> if graph == %{}, do: [], else: :cycle
      {node, _} ->
        rest = graph |> Map.delete(node) 
                     |> Map.new(fn {k, v} -> {k, v -- [node]} end)
        [node | sort(rest)]
    end
  end
end

Topo.sort(%{seat_stays: [:seat_tube], seat_tube: [:bottom_bracket], 
            bottom_bracket: [:head_tube], head_tube: []})
# [:head_tube, :bottom_bracket, :seat_tube, :seat_stays]

Bash had this built-in since the ’70s via tsort, originally written for ordering object files:

printf "bottom_bracket seat_tube\nseat_tube seat_stays\n" | tsort
# bottom_bracket
# seat_tube  
# seat_stays

The algorithm dates to Kahn’s 1962 paper, but it became essential when software grew complex enough that humans couldn’t track build order. Brazing a frame and compiling a program share the same structure: a directed acyclic graph where some nodes must come before others, and getting the order wrong means starting over.