I have a general tree class with: myTree = new Tree(string), appendChildNode(node), createChildNode(string), myTree.print() functions and myTree.name, myTree.children, etc attributes.
I also have a multimap with data which I want to decompose and put into a tree object. Lets assume, the data has no circles in it. My idea is to let the recursion build the subbranches. For some reason the recursion does not work and I cannot figure out why. The return inside forEach gives me an 'undefined'
my multimap:
aaaa -> [b, c, d]
c -> [f]
f -> [g]
r -> [p]
So my resulting tree for "aaaa" should be:
aaaa
b c d
f
g
my main function:
myMultiMap ... <multimap defined here>
myTree = new Tree('End2End') // my tree object
// lets just pick the 'aaaa' to start with
myMultiMap.get('aaaa').forEach((entry) => {
newNode = new Tree(entry)
myTree.appendChildNode(recurse(newNode))
})
// show the tree after it was built
myTree.print()
recurse function
function recurse (node) {
// if the element is in the multimap, it has one or more children
if(myMultiMap.has(node.name)) {
// iterate through all children of the node in the multimap
myMultiMap.get(node.name).forEach((child) => {
// build a new node from the child
newChildnode = new Tree(child);
// build a subtree recursively, since this child could have children itself
return node.appendChildNode(recurse(newChildnode))
})
// if the node is not in the multimap, thus it has no children, so just return the node
} else {
return node
}
}
Info: I took this tree implementation: https://github.com/beforesemicolon/tutorials-files/blob/master/tree-generic.js
Using a trivial tree implementation and using a Map of strings to arrays of strings in place of your MultiMap implementation, we can see the structure fairly clearly:
const tree = (name, children) => ({name, children})
const mapToTree = (multiMap) => (root) =>
tree (root, (multiMap .get (root) || []) .map (mapToTree (multiMap)))
const myMultiMap = new Map ([
['aaaa', ['b', 'c', 'd']],
['c', ['f']],
['f', ['g']],
['r', ['p']]
])
console .log (mapToTree (myMultiMap) ('aaaa')).as-console-wrapper {max-height: 100% !important; top: 0}If you want an external wrapper node, End2End, we can just wrap one more call to tree:
const myTree = tree ('End2End', mapToTree (myMultiMap) ('aaaa'))
The return inside forEach gives me an 'undefined'
Yes, you cannot return out of a forEach callback. But that's not what you want to do anyway. Instead, after performing the loop, you want return node:
function recurse(node) {
if (myMultiMap.has(node.name)) {
myMultiMap.get(node.name).forEach((child) => {
const newChildnode = new Tree(child);
node.appendChildNode(recurse(newChildnode))
})
return node;
} else {
return node;
}
}
or simply
function recurse(node) {
if (myMultiMap.has(node.name)) {
myMultiMap.get(node.name).forEach((child) => {
const newChildnode = new Tree(child);
node.appendChildNode(recurse(newChildnode))
})
}
return node;
}
Alternatively, don't return the node at all, just write
function recurse(node) {
if (myMultiMap.has(node.name)) {
myMultiMap.get(node.name).forEach((child) => {
const newChildnode = new Tree(child);
recurse(newChildnode);
node.appendChildNode(newChildnode);
})
}
}
or maybe nicer, instead move the node creation inside the recurse function:
function recurse(name) {
const node = new Tree(name);
if (myMultiMap.has(name)) {
myMultiMap.get(name).forEach((child) => {
node.appendChildNode(recurse(child))
})
}
return node;
}
Btw, in your main code you don't need to duplicate the loop. Simplify it to
const myMultiMap = …; // multimap defined here
const myTree = recurse(new Tree('aaaa'));
myTree.print();
or for my last version, respectively
const myMultiMap = …; // multimap defined here
const myTree = recurse('aaaa');
myTree.print();