https://kotlinlang.org logo
#getting-started
Title
# getting-started
n

nkiesel

07/23/2022, 1:22 AM
I have a tree represented by a Map<String, String> mapping child node it to parent node id. I now want to compute all the paths for this tree, starting at given node of the tree. Right now I have the following code, but I have the nagging feeling that I'm missing some more functional approach for this:
Copy code
val tree = mapOf(2 to 1, 3 to 2, 4 to 3, 5 to 1)

fun allPath(tree: Map<Int, Int>, root: Int): Map<Int, List<Int>> {
    return (tree.keys.associateWith { path(it, tree, root) } + mapOf(root to listOf(root))).filterValues { it.isNotEmpty() }
}

fun path(start: Int, tree: Map<Int, Int>, root: Int): List<Int> {
    return buildList {
        var n: Int? = start
        while (n != null && n != root) { add(n); n = tree[n] }
        if (n == null) return emptyList()
        add(root)
    }.reversed()
}

println(allPath(tree, 1)) // prints {2=[1, 2], 3=[1, 2, 3], 4=[1, 2, 3, 4], 5=[1, 5], 1=[1]}
e

ephemient

07/23/2022, 6:39 AM
if your tree was represented the other way around,
Copy code
fun allPath(tree: Map<Int, Set<Int>>, root: Int): Map<Int, List<Int>> = buildMap {
    DeepRecursiveFunction<Pair<Int, List<Int>>, Unit> { (node, path) ->
        put(node, path)
        tree[node]?.forEach { child ->
            callRecursive(child to path + child)
        }
    }(root to listOf(root))
}
which could be done by a
Copy code
fun <K, V> Map<K, V>.invert(): Map<V, Set<K>> = entries
    .groupingBy { it.value }
    .aggregate<_, _, MutableSet<K>> { _, set, (key, _), _ ->
        set?.apply { add(key) } ?: mutableSetOf(key)
    }
or
Copy code
fun <K, V> Map<K, V>.invert(): Map<V, Set<K>> = entries
    .groupingBy { it.value }
    .fold(
        { _, (key, _) -> mutableSetOf(key) },
        { _, set, (key, _) -> set.apply { add(key) } },
    )
m

Michael de Kaste

07/25/2022, 9:19 AM
I came up with this:
Copy code
fun paths(tree: Map<Int, Int>, root: Int): Map<Int, List<Int>> = buildMap {
    fun path(key: Int): List<Int> = getOrPut(key){
        when(val next = tree[key]){
            null -> listOf(key)
            else -> path(next) + key
        }
    }
    tree.keys.forEach(::path)
}.filterValues { it.first() == root }
root can also be dynamic, you can just remove the filterValues at the end and then keep refiltering to get the paths for every root value. The map uses memoization so you don't recalculate stuff later
n

nkiesel

07/25/2022, 7:25 PM
nice. thx a lot.
👍 1