I am using graphology which is a library that provides a graph object made of nodes and edges. I have a structure similar to the one in the image attached.

Each edge has a direction associated with it. I would like to create a function (likely recursive) that will return the parents of a node selected. Eg. parentsOfFunction(6) should return

[
  [4,1],
  [5,
      [2,3],
  ]
]

Where each time there is a branching of edges from a node, a new child element is made in the array. I believe this to be the best way to store the results to then be iterated over later, but am happy to change the structure so long as the structure can be inferred. Currently my function only returns [4,5] which are the first level of parents of 6. The console.log values are correct but I am unable to work out how to store this in a variable. Any help appreciated, TIA.

EDIT: I have actually worked out a function for this? Would this be a suitable/efficient way of doing the above? Thanks again.

Updated codesandbox

Code:

import Graph from "graphology";
const graph = new Graph({
  multi: false,
  allowSelfLoops: false,
  type: "directed"
});

graph.addNode("1");
graph.addNode("2");
graph.addNode("3");
graph.addNode("4");
graph.addNode("5");
graph.addNode("6");

graph.addEdge("1", "4", { name: "a" });
graph.addEdge("2", "5", { name: "b" });
graph.addEdge("3", "5", { name: "c" });
graph.addEdge("4", "6", { name: "d" });
graph.addEdge("5", "6", { name: "e" });

let parents = [];

function getNodes(node) {
  return graph.inboundNeighbors(node);
}

function recursive(startingNode) {
  let list = getNodes(startingNode);
  if (list.length < 0) {
    parents[0] = list;
  } else {
    for (let i = 0; i < list.length; i  ) {
      parents[i] = [list[i], getNodes(list[i])];
    }
  }
}
recursive(6);
console.log(parents);

CodePudding user response：

Your recursive function isn't actually recursive, so your code doesn't work. It just produces two-level deep output that happens to look fairly OK-ish (but not quite) on the example test. Try other test cases.

Also, the expected output is a very unusual data structure since it mixes types. This is an antipattern that you should avoid if possible. It also omits the root, which makes the recursive logic a bit awkward to write. I used an extra inner function to strip off the root.

Here's one approach that uses a mixed-type return value and a test to determine how many parents we have. The logic for a given call is as follows:

• If this node has no parents, it's a leaf node. Return it directly, without an array wrapper.
• If this node has one parent, it should be returned in an array directly alongside its parent subtree.
• If this node has multiple parents, it should be returned in an array with its parents' subtrees in a subarray.

const buildTreeFromParents = (graph, start) => {
  const recurse = start => {
    const parents = graph.inboundNeighbors(start);

    if (parents.length === 0) {
      return start;
    }
    else if (parents.length === 1) {
      return [start, recurse(parents[0])];
    }

    return [start, parents.map(recurse)];
  };

  return graph.inboundNeighbors(start).map(recurse);
};

const graph = new graphology.Graph({
  multi: false,
  allowSelfLoops: false,
  type: "directed"
});
graph.addNode(1);
graph.addNode(2);
graph.addNode(3);
graph.addNode(4);
graph.addNode(5);
graph.addNode(6);
graph.addEdge(1, 4, {name: "a"});
graph.addEdge(2, 5, {name: "b"});
graph.addEdge(3, 5, {name: "c"});
graph.addEdge(4, 6, {name: "d"});
graph.addEdge(5, 6, {name: "e"});
console.log(buildTreeFromParents(graph, 6));

<script src="https://cdnjs.cloudflare.com/ajax/libs/graphology/0.21.0/graphology.umd.min.js"></script>

Try to avoid global variables when writing functions, which should be purely self-contained to avoid bugs and confusing state modification and dependencies.

Based on the comments, here's the code that addresses a couple of the awkward issues mentioned above. It's still a mixed-type structure, but at least the root is included and the parent nesting makes more sense as no special condition is taken when there's only one parent.

const buildTreeFromParents = (graph, start) => {
  const parents = graph.inboundNeighbors(start);

  if (parents.length === 0) {
    return start;
  }

  return [start, parents.map(e => buildTreeFromParents(graph, e))];
};

const graph = new graphology.Graph({
  multi: false,
  allowSelfLoops: false,
  type: "directed"
});
graph.addNode(1);
graph.addNode(2);
graph.addNode(3);
graph.addNode(4);
graph.addNode(5);
graph.addNode(6);
graph.addEdge(1, 4, {name: "a"});
graph.addEdge(2, 5, {name: "b"});
graph.addEdge(3, 5, {name: "c"});
graph.addEdge(4, 6, {name: "d"});
graph.addEdge(5, 6, {name: "e"});
console.log(buildTreeFromParents(graph, 6));

<script src="https://cdnjs.cloudflare.com/ajax/libs/graphology/0.21.0/graphology.umd.min.js"></script>