Graph

// Demo Graph: adjacency list vs matrix, directed/undirected, weighted.

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

    fun addVertex(v: T) {
        if (v !in adjacency) adjacency[v] = mutableListOf()
    }

    fun addEdge(from: T, to: T) {
        addVertex(from)
        addVertex(to)
        adjacency[from]!!.add(to)
        if (!directed) adjacency[to]!!.add(from)
    }

    fun neighbors(v: T): List<T> = adjacency[v]?.toList() ?: emptyList()

    fun vertices(): List<T> = adjacency.keys.toList()

    fun edgeCount(): Int = adjacency.values.sumOf { it.size } / if (directed) 1 else 2

    fun adjacencyListString(): String =
        adjacency.entries.joinToString("\n") { (v, n) -> "$v -> $n" }
}

// === Graph dengan adjacency matrix ===
class GraphMatrix(val n: Int, val directed: Boolean = false) {
    private val matrix = Array(n) { IntArray(n) }

    fun addEdge(from: Int, to: Int, weight: Int = 1) {
        matrix[from][to] = weight
        if (!directed) matrix[to][from] = weight
    }

    fun hasEdge(from: Int, to: Int): Boolean = matrix[from][to] != 0

    fun weight(from: Int, to: Int): Int = matrix[from][to]

    fun printMatrix() {
        print("    ")
        for (j in 0 until n) print("$j ")
        println()
        for (i in 0 until n) {
            print("$i | ")
            for (j in 0 until n) print("${matrix[i][j]} ")
            println()
        }
    }
}

// === Weighted graph ===
class WeightedGraph<T>(val directed: Boolean = false) {
    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 (!directed) adj.getOrPut(to) { mutableListOf() }.add(from to weight)
        if (from !in adj) adj[from] = mutableListOf()
        if (to !in adj) adj[to] = mutableListOf()
    }

    fun neighborsWithWeight(v: T): List<Pair<T, Int>> = adj[v]?.toList() ?: emptyList()

    fun vertices(): List<T> = adj.keys.toList()
}

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

    println("--- Graph tak berarah (undirected) dengan adjacency list ---")
    val gList = GraphList<Char>()
    listOf('A' to 'B', 'A' to 'C', 'B' to 'D', 'C' to 'D', 'D' to 'E').forEach {
        gList.addEdge(it.first, it.second)
    }
    println(gList.adjacencyListString())
    println("Neighbors A: ${gList.neighbors('A')}")
    println("Neighbors D: ${gList.neighbors('D')}")
    println("Vertices: ${gList.vertices()}")
    println("Edge count: ${gList.edgeCount()}")

    println()
    println("--- Graph berarah (directed) ---")
    val gDirected = GraphList<Char>(directed = true)
    listOf('A' to 'B', 'B' to 'C', 'C' to 'A', 'A' to 'C').forEach {
        gDirected.addEdge(it.first, it.second)
    }
    println(gDirected.adjacencyListString())
    println("Neighbors A: ${gDirected.neighbors('A')}")

    println()
    println("--- Adjacency matrix ---")
    val gMatrix = GraphMatrix(5, directed = false)
    listOf(0 to 1, 0 to 2, 1 to 3, 2 to 3, 3 to 4).forEach {
        gMatrix.addEdge(it.first, it.second)
    }
    gMatrix.printMatrix()
    println("Edge 0-1: ${gMatrix.hasEdge(0, 1)}")
    println("Edge 1-4: ${gMatrix.hasEdge(1, 4)}")

    println()
    println("--- Weighted graph ---")
    val gWeight = WeightedGraph<String>(directed = true)
    gWeight.addEdge("Jakarta", "Bandung", 150)
    gWeight.addEdge("Jakarta", "Semarang", 400)
    gWeight.addEdge("Bandung", "Surabaya", 700)
    gWeight.addEdge("Semarang", "Surabaya", 350)

    println("Vertices: ${gWeight.vertices()}")
    println("Edges with weight:")
    for (v in gWeight.vertices()) {
        println("  $v -> ${gWeight.neighborsWithWeight(v)}")
    }
}

=== Demo Graph ===
--- Graph tak berarah (undirected) dengan adjacency list ---
A -> [B, C]
B -> [A, D]
C -> [A, D]
D -> [B, C, E]
E -> [D]
Neighbors A: [B, C]
Neighbors D: [B, C, E]
Vertices: [A, B, C, D, E]
Edge count: 5

--- Graph berarah (directed) ---
A -> [B, C]
B -> [C]
C -> [A]
Neighbors A: [B, C]

--- Adjacency matrix ---
    0 1 2 3 4 
0 | 0 1 1 0 0 
1 | 1 0 0 1 0 
2 | 1 0 0 1 0 
3 | 0 1 1 0 1 
4 | 0 0 0 1 0 
Edge 0-1: true
Edge 1-4: false

--- Weighted graph ---
Vertices: [Jakarta, Bandung, Semarang, Surabaya]
Edges with weight:
  Jakarta -> [(Bandung, 150), (Semarang, 400)]
  Bandung -> [(Surabaya, 700)]
  Semarang -> [(Surabaya, 350)]
  Surabaya -> []