← All tasks Task 4 of 12 unsolved

4. Cycle Detection in FK Graph

Graph DFS ~25 min

Detect all cycles in a directed graph of foreign-key relationships and return them. Use DFS with three colors: WHITE (unvisited), GRAY (in current path), BLACK (fully explored). A back-edge to a GRAY node means a cycle was found.

In Synthesized.io's pipeline, cycles must be detected before topological sort — a cycle implies an unresolvable load order, and the user has to break it manually (e.g., load with FK constraints disabled, then re-enable).

Setup (folded above the editor — click + to view): data class FK(val child: String, val parent: String), plus main() with the test cases.

Tests this task must pass

No cycles — linear chain a → b → c returns an empty list.
Self-reference — FK("employees","employees") is detected as a cycle containing employees.
Mutual reference — a ↔ b is reported.
Cycle alongside non-cycle — graph with a → b → c → a and d → e; cycle is found, isolated edge doesn't confuse the algorithm.

data class FK(val child: String, val parent: String) //sampleStart fun findCycles(tables: List<String>, fks: List<FK>): List<List<String>> { // DFS with three colors: WHITE (unvisited), GRAY (in path), BLACK (done) // Back edge to GRAY node = cycle // Return list of cycles (each cycle = list of table names) TODO() } //sampleEnd fun main() { // Test 1: No cycles val r1 = findCycles(listOf("a","b","c"), listOf(FK("b","a"), FK("c","b"))) check(r1.isEmpty()) { "FAIL: no cycles expected" } println("✅ Test 1: No cycles") // Test 2: Self-reference val r2 = findCycles(listOf("employees"), listOf(FK("employees","employees"))) check(r2.isNotEmpty()) { "FAIL: self-reference is a cycle" } check(r2.any { "employees" in it }) { "FAIL: employees in cycle" } println("✅ Test 2: Self-reference detected") // Test 3: Mutual reference val r3 = findCycles(listOf("a","b"), listOf(FK("a","b"), FK("b","a"))) check(r3.isNotEmpty()) { "FAIL: mutual reference is a cycle" } println("✅ Test 3: Mutual reference detected") // Test 4: Cycle + non-cycle val r4 = findCycles( listOf("a","b","c","d","e"), listOf(FK("a","b"), FK("b","c"), FK("c","a"), FK("d","e")) ) check(r4.isNotEmpty()) { "FAIL: cycle exists" } check(r4.any { it.containsAll(listOf("a","b","c")) || it.size >= 2 }) { "FAIL: a-b-c cycle" } println("✅ Test 4: Cycle found among non-cycle nodes") println("\n🎉 ALL TESTS PASSED!") }

Solution

fun findCycles(tables: List<String>, fks: List<FK>): List<List<String>> {
    val children = mutableMapOf<String, MutableList<String>>()
    for (fk in fks) children.getOrPut(fk.parent) { mutableListOf() }.add(fk.child)

    val WHITE = 0; val GRAY = 1; val BLACK = 2
    val color = tables.associateWith { WHITE }.toMutableMap()
    val cycles = mutableListOf<List<String>>()
    val path = mutableListOf<String>()

    fun dfs(node: String) {
        color[node] = GRAY
        path.add(node)
        for (child in children[node].orEmpty()) {
            when (color[child]) {
                WHITE -> dfs(child)
                GRAY -> {
                    val idx = path.indexOf(child)
                    if (idx >= 0) cycles.add(path.subList(idx, path.size).toList() + child)
                }
                else -> {} // BLACK — done, skip
            }
        }
        color[node] = BLACK
        path.removeAt(path.size - 1)
    }

    for (t in tables) if (color[t] == WHITE) dfs(t)
    return cycles
}

← Previous Next: Chunked IN-Clause →