I have a tree represented by a Map<String, Stri...

# getting-started

[nkiesel]

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:

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]}

[ephemient]

if your tree was represented the other way around,

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))
}

[ephemient]

which could be done by a

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)
    }

[ephemient]

or

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) } },
    )

[Michael de Kaste]

I came up with this:

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

[nkiesel]

nice. thx a lot.