shortestPath.kt

import java.util.*

/** Graph node for undirected graphs.
 *
 * @property value the value of the node.
 * @property adjacent a set of the adjacent nodes for this one.
 **/

class Node(
    private val value: Any,
    private val adjacent: MutableSet<Node> = mutableSetOf()
) {
    override fun toString(): String = "<${this.value}>"

    /** Connect this node to others. */
    fun connectTo(vararg others: Node) {
        others.forEach {
            this.adjacent.add(it)
            it.adjacent.add(this)
        }
    }

    fun traverse() {
        val seen = mutableSetOf<Node>()
        val toVisit: Queue<Node> = LinkedList()
        toVisit.add(this)

        while (toVisit.isNotEmpty()) {
            val node = toVisit.poll()
            if (node in seen) continue
            seen.add(node)
            println(node)
            node.adjacent.forEach { toVisit.add(it) }
        }
    }

    /** Build "predecessors map" starting at this node.
     *
     *              / B - D \
     *   start  A -|         | E
     *             \ C -----/
     *
     * @param stopAt: if provided, stop traversing at this node
     * @returns map of {B:A, C:A, D:B, E:C} (the best path to E is from C)
     */

    private fun buildPredecessors(stopAt: Node? = null): Map<Node, Node> {

        // strategy: breadth-first search starting at this node, noting the
        // first time we've seen each node, since in a BFS, the node that found
        // it is it's "predecessor".

        val nodeToFoundBy = mutableMapOf<Node, Node>()
        val seen = mutableSetOf<Node>()
        val toVisit: Queue<Node> = LinkedList()
        toVisit.add(this)

        while (toVisit.isNotEmpty()) {
            val node = toVisit.poll()
            if (node in seen) continue
            if (node == stopAt) break

            seen.add(node)

            for (adj in node.adjacent) {
                nodeToFoundBy.putIfAbsent(adj, node)
                if (adj !in seen) toVisit.add(adj)
            }
        }

        return nodeToFoundBy
    }

    /** Find the shortest path from this node to `sought`.
     *
     *              / B - D \
     *   start  A -|         | E  sought
     *             \ C -----/

     * @returns List<Node> like [A, C, E]
     */

    fun shortestPathTo(sought: Node): List<Node> {
        val predecessors = buildPredecessors()
        val pathRev = mutableListOf(sought)
        var node = sought

        while (node != this) {
            node = predecessors.getValue(node)
            pathRev.add(node)
        }

        return pathRev.reversed()
    }

    // since we're an undirected graph, we can also reverse this easily
    fun shortestPathFrom(end: Node) : List<Node> = end.shortestPathTo(this)
}


fun main() {
    val a = Node("A")
    val b = Node("B")
    val c = Node("C")
    val d = Node("D")
    val e = Node("E")
    val f = Node("F")
    a.connectTo(b, c)
    b.connectTo(d)
    c.connectTo(e)
    d.connectTo(e)

    // example of invoking a method
    f.traverse()

    println(a.shortestPathTo(e))
    println(e.shortestPathFrom(a))
}