#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