JavaScript building a breadth-first tree from multimap (which data has cycles)

Question

Prerequisites: I have a general tree class with: myTree = new Tree(string), appendChildNode(node), createChildNode(string)->node, myTree.print() functions and myTree.name, myTree.children, myTree.depth, etc attributes.

I also have a multimap with data which I want to decompose and put into a tree object. The data has occasionally cycles on further depth. For that reason I want to build a bredth-first tree structure which I can query. At a leaf, where a cycle reference is found I want the branching to stop. So I built a simple function that uses a queue. It pulls an element from the multimap, gets its children and puts them into the queue. That works fine.

My problem is: When putting an element into the queue, I am losing the information about which parent it had when it was added. So when I want to add a new node I end up with a flat tree.

Question: Would I need also to store the information about the parent in the queue somehow? Or how else would I go about it? Maybe I store an object in the queue that holds {childname, parentNode}?

Bonus question: Is this problem maybe better solved with some kind of cyclic graph? (due to cycles in data)

my multimap (just an example here)

aaaa -> [b, c, d]
b    -> [f]
f    -> [g]
g    -> [c]  (//this is the circle: g points back to higher node 'c')
d    -> [e]
e    -> [m,n]
r    -> [p]

Here is the tree, if you start tracing the multimap from 'aaaa'. Notice, r->p is irrelevant if you start with 'aaaa'.

The result of myTree.print() should look like like this in the console:

My Diagrams
1   aaaa   (8 descendants)
2    b     (2 descendants)
3     f    (1 descendants)
4      g   (0 descendants) [hint: terminating here, g points back to 'c'] //in red
2    c     (0 descendants)
2    d     (3 descendants)
3     e    (2 descendants)
4      m   (0 descendants)
4      n   (0 descendants)

So: Depth, Nodename, Amount of siblings below + note if it is a terminal node due to a circle reference Edit: g could have other children than c as trincot noted. In that case the tree should continue for those children. It should be possible to see that there was a reference to c from g and it stopped there. Idea: Maybe append a special node under g that represents c, but stops there. That special node below g would be shown red in console.

function calcEnd2End(multiMap) {
  queue = [];
  resultTree = new Tree("My Diagrams");
  queue.push("aaaa");

  buildWideTreeFromMM("aaaa");
  resultTree.print();

  function buildWideTreeFromMM() {
    counter = 0;
    depth   = 0;
    node    = resultTree;

    // as long as queue has elements go on
    while (queue.length != 0) {
     
      // get oldest element
      someParentStr = queue[0];

      // if element is in multimap, check if it has children
      if (multiMap.has(someParentStr)) {
        // since it has children, depth is +1
        depth++;
        // iterate through all children
        multiMap.get(someParentStr).forEach((childNameStr) => {

          // check if this child points to higher element already in tree, if yes,
          // set attribute 'isTerminalElement' to know later which nodes were circular ones
          // set attribute 'setCircleReference' to know which higher sibling the reference pointed to, to show in hint message
          // checkIfElemetIsInTree checks if there is already a node with that name in the tree (I have not written this func yet)
          if (checkIfElemetIsInTree) {
            node.createChildNode(childNameStr).setDepth(depth).setIsTerminalElement(true).setCircleReference(someParent)
            // This is terminal element, no need to queue it
            return
          }
          // childname is not in tree, so push it into queue to be checked on some next iteration
          queue.push(child);
          // create a new node and set its depth property
          // PROBLEM IS HERE...
          node.createChildNode(child).setDepth(depth)
        });

        queue.shift();

      // if element is not in multimap, it has no children, so remove it from queue
      } else {
        queue.shift();
      }
    }
  }

}

Answer 1

Some comments:

• Declare your variables with explicit scope, so with const, let or var. Not doing that makes them global variables, which is bad practice
• In your BFS loop, depth keeps increasing even if the dequeued name corresponds to the same depth as the previously dequeued name.
• You should not have a return in the loop, as this will break any further processing of the queue.
• As createChildNode is called on the node that becomes the parent, there should be no need to pass a depth argument. It can be derived from the parent's depth property.
• You would not need a separate property to flag a terminal node when you already have another property that gives the node to which such terminal references. That second property is enough to know whether we have a terminal node or not.
• The desired output has a "hint" next to the g node, but this cannot be generally applied like that, because g is not a terminal node. The terminal node is an extra node that was created with label c. In general g could have a mix of terminal children and normal children. So the hint would be better placed at the terminal children. I would therefore suggest that the output has another indented line below g with c (duplicate) with a hint that explains this is a back reference to the "real" c.

Here is an implementation with some more ideas included:

class Tree {
    constructor(name, backReference) { 
        this.name = name;
        this.backReference = backReference ?? null;
        this.children = [];
        this.parent = null;
        this.depth = 0;
        this.descendantCount = 0;
    }
    createChildNode(name, backReference) {
        let node = new Tree(name, backReference); 
        // Deal with depth, parent, children, descendantCount
        node.parent = this;
        node.depth = this.depth + 1;
        this.children.push(node);
        if (!backReference) {
            // Adjust the descendant count in all ancestor nodes
            for (let node = this; node; node = node.parent) {
                node.descendantCount++;
            }
        }
        return node;
    }
    print() {
        console.log(`${"  ".repeat(this.depth)}${this.name} ${
            this.backReference ? "[hint: terminating here; this is a backreference]" : `(${this.descendantCount} descendants)`
        }`);
        for (const child of this.children) child.print();
    }
}

function calcEnd2End(multiMap, start="aaaa") { // Provide starting point
    // declare your variables with explicit scope!
    const root = new Tree(start); // Don't create a dummy root. Just create one for the start node
    const visited = new Map().set(start, root); // For keying node instances by their name
    const queue = [root];

    while (queue.length) {
        const node = queue.shift();  // Immediately shift it out
        if (multiMap.has(node.name)) {
            for (const childName of multiMap.get(node.name)) {
                const child = node.createChildNode(childName, visited.get(childName));
                if (!child.backReference) {
                    visited.set(childName, child);
                    queue.push(child);
                }
            }
        }
    }
    return root;
}

// Example run
const multiMap = new Map([
    ["aaaa", ["b", "c", "d"]],
    ["b", ["f"]],
    ["f", ["g"]],
    ["g", ["c"]],  // this is the cycle
    ["d", ["e"]],
    ["e", ["m","n"]],
    ["r", ["p"]]
]);

const root = calcEnd2End(multiMap, "aaaa");
root.print();