Alright, let's get our hands dirty. We've talked about data structures, but today I want us to actually build something that feels like a real-world engineering problem: a dependency graph resolver. Imagine we're building a plugin system for a game engine. Some plugins need other plugins to be loaded first. If we just load them in alphabetical order, the whole thing crashes because the "Physics Engine" plugin tried to start before the "Core Math" plugin was ready.

Trying the "Naive" Approach

My first instinct is usually to just keep it simple. I'll represent the dependencies as a map where the key is the plugin name and the value is a list of things it depends on. Let's see if a simple loop can handle this.

val dependencies = mapOf(
    "Physics" to listOf("Math"),
    "Input" to listOf("Core"),
    "GameLogic" to listOf("Physics", "Input"),
    "Math" to emptyList(),
    "Core" to emptyList()
)

val loadOrder = mutableListOf<String>()
dependencies.keys.forEach { plugin ->
    loadOrder.add(plugin)
}
println(loadOrder) 
// Output: [Physics, Input, GameLogic, Math, Core]

Yeah, that's useless. It just gives me the keys in whatever order the map feels like. I need the things with zero dependencies to come first. I could try to find all plugins with empty lists, add them, then remove them from the other lists... but that feels like I'm fighting the data structure. There's a more elegant way: recursion.

Going Down the Recursive Rabbit Hole

If I want to load "GameLogic", I first need to load everything "GameLogic" depends on. That sounds like a recursive function. Let's try to write a resolver that dives deep into the dependency chain before adding the plugin to the list.

val resolved = mutableListOf<String>()

fun resolve(plugin: String) {
    val deps = dependencies[plugin] ?: emptyList()
    for (dep in deps) {
        resolve(dep)
    }
    resolved.add(plugin)
}

dependencies.keys.forEach { resolve(it) }
println(resolved)
// Output: [Math, Physics, Core, Input, Core, Input, Math, Physics, Input, Core, GameLogic]

Wait, look at that output. It's a mess. "Core" and "Input" are showing up multiple times. Why? Because multiple plugins depend on them, and my function blindly resolves them every single time it encounters them. I'm treating the graph like a tree, but it's actually a graph—multiple paths can lead to the same node. I need to keep track of what I've already "visited."

Stopping the Infinite Loop

A simple `Set` should fix the duplicates. If I've already resolved a plugin, I'll just skip it. But while I'm adding that, I realized something: what happens if "Plugin A" depends on "Plugin B", and "Plugin B" depends on "Plugin A"?

If I just use a `visited` set, I might avoid duplicates, but if I hit a circular dependency, my recursive function will just call itself until the JVM throws a StackOverflowError. I need two sets: one for plugins that are completely finished, and one for plugins currently in the "process" of being resolved.

val resolved = mutableListOf<String>()
val visited = mutableSetOf<String>()
val visiting = mutableSetOf<String>()

fun resolve(plugin: String) {
    if (plugin in visiting) throw IllegalStateException("Circular dependency detected at $plugin!")
    if (plugin in visited) return

    visiting.add(plugin)
    
    val deps = dependencies[plugin] ?: emptyList()
    for (dep in deps) {
        resolve(dep)
    }
    
    visiting.remove(plugin)
    visited.add(plugin)
    resolved.add(plugin)
}

Now we're talking. The visiting set acts as a breadcrumb trail. If I encounter a node that is already in the visiting set, I've just walked in a circle. By moving the plugin to the visited set only after its dependencies are handled, I ensure the load order is mathematically sound (this is essentially a Topological Sort).

Final Polish and Logic Check

One last thing. In a real app, I wouldn't want these sets and lists floating around as global variables. I'll wrap this into a class. This makes the resolver reusable and prevents state from leaking between different resolution attempts. I'll also make the dependency map a constructor parameter so I can test it with different scenarios.

class DependencyResolver(private val graph: Map<String, List<String>>) {
    fun resolveAll(): List<String> {
        val resolved = mutableListOf<String>()
        val visited = mutableSetOf<String>()
        val visiting = mutableSetOf<String>()

        fun walk(node: String) {
            if (node in visiting) throw IllegalStateException("Cycle detected: $node")
            if (node in visited) return

            visiting.add(node)
            graph[node]?.forEach { walk(it) }
            visiting.remove(node)
            visited.add(node)
            resolved.add(node)
        }

        graph.keys.forEach { walk(it) }
        return resolved
    }
}

This is much cleaner. I've used a local function (a function inside a function) to encapsulate the recursion while still giving it access to the tracking sets. It's a pattern I use often in Kotlin when the helper function doesn't need to be exposed to the rest of the class.

📋 Practical Task

Exercise: Implement a Mod-Load Order Validator

You are building a tool for a game modding community. Some mods are "core" mods (no dependencies), and some are "add-ons" that require specific core mods to function. If a user tries to load a set of mods that have a circular dependency (e.g., Mod A needs Mod B, and Mod B needs Mod A), the game will crash on startup.

Your Task:

• Create a class called ModLoadValidator.
• Implement a method calculateLoadOrder(mods: Map<String, List<String>>): List<String>.
• The method should return the correct order of mods to load.
• If a circular dependency is detected, it must throw a custom exception called CircularDependencyException (which you will also need to define).

Test your implementation with these two scenarios:

1. Valid: "UI_Fix" -> ["Core_Lib"], "Combat_Overhaul" -> ["Core_Lib", "UI_Fix"], "Core_Lib" -> [] (Should return a list where Core_Lib is first).
2. Invalid: "Mod_A" -> ["Mod_B"], "Mod_B" -> ["Mod_C"], "Mod_C" -> ["Mod_A"] (Should throw CircularDependencyException).