Graph Algorithms

// Demo Graph Algorithms: BFS, DFS, Dijkstra, topological sort.

// === Graph adjacency list berarah ===
class GraphAL<T>(val directed: Boolean = false) {
    private val adj = mutableMapOf<T, MutableList<T>>()

    fun addEdge(from: T, to: T) {
        adj.getOrPut(from) { mutableListOf() }.add(to)
        if (from !in adj) adj[from] = mutableListOf()
        if (!directed) adj.getOrPut(to) { mutableListOf() }.add(from)
        if (to !in adj) adj[to] = mutableListOf()
    }

    fun neighbors(v: T): List<T> = adj[v] ?: emptyList()
    fun vertices(): List<T> = adj.keys.toList()
}

// === BFS: Breadth-First Search ===
fun <T> bfs(graph: GraphAL<T>, start: T): List<T> {
    val visited = mutableSetOf<T>()
    val queue = ArrayDeque<T>()
    val result = mutableListOf<T>()
    queue.addLast(start)
    visited.add(start)
    while (queue.isNotEmpty()) {
        val curr = queue.removeFirst()
        result.add(curr)
        for (next in graph.neighbors(curr)) {
            if (next !in visited) {
                visited.add(next)
                queue.addLast(next)
            }
        }
    }
    return result
}

// === BFS: shortest path (unweighted) ===
fun <T> bfsShortestPath(graph: GraphAL<T>, start: T, target: T): List<T>? {
    val visited = mutableSetOf<T>()
    val queue = ArrayDeque<T>()
    val parent = mutableMapOf<T, T?>()
    queue.addLast(start)
    visited.add(start)
    parent[start] = null
    while (queue.isNotEmpty()) {
        val curr = queue.removeFirst()
        if (curr == target) {
            val path = mutableListOf<T>()
            var node: T? = curr
            while (node != null) {
                path.add(node)
                node = parent[node] as? T
            }
            return path.reversed()
        }
        for (next in graph.neighbors(curr)) {
            if (next !in visited) {
                visited.add(next)
                parent[next] = curr
                queue.addLast(next)
            }
        }
    }
    return null
}

// === DFS: Depth-First Search (iteratif) ===
fun <T> dfs(graph: GraphAL<T>, start: T): List<T> {
    val visited = mutableSetOf<T>()
    val stack = ArrayDeque<T>()
    val result = mutableListOf<T>()
    stack.addLast(start)
    while (stack.isNotEmpty()) {
        val curr = stack.removeLast()
        if (curr in visited) continue
        visited.add(curr)
        result.add(curr)
        for (next in graph.neighbors(curr)) {
            if (next !in visited) stack.addLast(next)
        }
    }
    return result
}

// === DFS rekursif ===
fun <T> dfsRec(graph: GraphAL<T>, start: T): List<T> {
    val visited = mutableSetOf<T>()
    val result = mutableListOf<T>()
    fun visit(node: T) {
        if (node in visited) return
        visited.add(node)
        result.add(node)
        for (next in graph.neighbors(node)) visit(next)
    }
    visit(start)
    return result
}

// === Dijkstra: shortest path weighted (non-negative) ===
class WGraph<T> {
    private val adj = mutableMapOf<T, MutableList<Pair<T, Int>>>()
    fun addEdge(from: T, to: T, weight: Int) {
        adj.getOrPut(from) { mutableListOf() }.add(to to weight)
        if (from !in adj) adj[from] = mutableListOf()
        if (to !in adj) adj[to] = mutableListOf()
    }
    fun neighbors(v: T): List<Pair<T, Int>> = adj[v] ?: emptyList()
    fun vertices(): List<T> = adj.keys.toList()
}

fun <T> dijkstra(graph: WGraph<T>, start: T): Map<T, Int> {
    val dist = mutableMapOf<T, Int>()
    dist[start] = 0
    val visited = mutableSetOf<T>()
    // Simple priority queue using sorted list
    val pq = java.util.PriorityQueue<Pair<Int, T>>(compareBy { it.first })
    pq.add(0 to start)
    while (pq.isNotEmpty()) {
        val (d, u) = pq.poll()
        if (u in visited) continue
        visited.add(u)
        for ((v, w) in graph.neighbors(u)) {
            val newDist = d + w
            if (newDist < (dist[v] ?: Int.MAX_VALUE)) {
                dist[v] = newDist
                pq.add(newDist to v)
            }
        }
    }
    return dist
}

// === Topological sort (Kahn's algorithm) ===
fun topologicalSort(graph: GraphAL<String>): List<String> {
    val inDegree = mutableMapOf<String, Int>()
    for (v in graph.vertices()) inDegree[v] = 0
    for (v in graph.vertices()) {
        for (u in graph.neighbors(v)) inDegree[u] = (inDegree[u] ?: 0) + 1
    }
    val queue = ArrayDeque<String>()
    for ((v, d) in inDegree) if (d == 0) queue.addLast(v)
    val result = mutableListOf<String>()
    while (queue.isNotEmpty()) {
        val curr = queue.removeFirst()
        result.add(curr)
        for (next in graph.neighbors(curr)) {
            inDegree[next] = (inDegree[next] ?: 0) - 1
            if (inDegree[next] == 0) queue.addLast(next)
        }
    }
    return result
}

fun main() {
    println("=== Demo Graph Algorithms ===")

    val g = GraphAL<Char>()
    listOf(
        'A' to 'B', 'A' to 'C',
        'B' to 'D', 'B' to 'E',
        'C' to 'F',
        'D' to 'G', 'E' to 'G', 'F' to 'G'
    ).forEach { g.addEdge(it.first, it.second) }

    println("--- BFS dari A ---")
    println("Order: ${bfs(g, 'A')}")

    println()
    println("--- BFS shortest path A ke G ---")
    val path = bfsShortestPath(g, 'A', 'G')
    println("Path: $path")

    println()
    println("--- DFS iteratif dari A ---")
    println("Order: ${dfs(g, 'A')}")

    println()
    println("--- DFS rekursif dari A ---")
    println("Order: ${dfsRec(g, 'A')}")

    println()
    println("--- Dijkstra shortest path (weighted) ---")
    val wg = WGraph<Char>()
    listOf(
        Triple('A', 'B', 4),
        Triple('A', 'C', 2),
        Triple('B', 'C', 5),
        Triple('B', 'D', 10),
        Triple('C', 'E', 3),
        Triple('E', 'D', 4),
        Triple('D', 'F', 11),
        Triple('E', 'F', 8)
    ).forEach { wg.addEdge(it.first, it.second, it.third) }
    val dist = dijkstra(wg, 'A')
    println("Jarak terpendek dari A:")
    dist.forEach { (v, d) -> println("  A -> $v = $d") }

    println()
    println("--- Topological sort (DAG) ---")
    val dag = GraphAL<String>(directed = true)
    listOf(
        " fundamentals" to "oop",
        "fundamentals" to "data_structures",
        "data_structures" to "algorithms",
        "oop" to "design_patterns",
        "algorithms" to "design_patterns",
        "design_patterns" to "architecture"
    ).forEach { dag.addEdge(it.first.trim(), it.second.trim()) }
    println("Topological order: ${topologicalSort(dag)}")
}

=== Demo Graph Algorithms ===
--- BFS dari A ---
Order: [A, B, C, D, E, F, G]

--- BFS shortest path A ke G ---
Path: [A, B, D, G]

--- DFS iteratif dari A ---
Order: [A, C, F, G, E, B, D]

--- DFS rekursif dari A ---
Order: [A, B, D, G, E, F, C]

--- Dijkstra shortest path (weighted) ---
Jarak terpendek dari A:
  A -> A = 0
  A -> B = 4
  A -> C = 2
  A -> E = 5
  A -> D = 9
  A -> F = 13

--- Topological sort (DAG) ---
Topological order: [fundamentals, oop, data_structures, algorithms, design_patterns, architecture]