I am trying to traverse a graph in javascript. My job is to traverse and parse all the possible outcomes of the following graph.
This is how I am storing the graph in a JS object.
var graph = {
alpha: {
in: [],
out: ['a', 'b']
},
a: {
in: ['alpha'],
out: []
},
b: {
in: ['alpha'],
out: ['c', 'e']
},
c: {
in: ['b'],
out: ['d']
},
d: {
in: ['c'],
out: []
},
e: {
in: ['b'],
out: ['f', 'g']
},
f: {
in: ['e'],
out: []
},
g: {
in: ['e'],
out: []
}
};
I need to parse it to get the following output.
output = [
['alpha', 'a'],
['alpha', 'b', 'c', 'd'],
['alpha', 'b', 'e', 'f'],
['alpha', 'b', 'e', 'g']
];
Key things to note are :
alpha
is always the parent node. one
input connection and maximum of n
-number of output connectionsRight now my approach is to use recursion. BUt I just can't get my head around it. Can anyone give me a hand here?
var getChild = function (Obj) {
if ( Obj['out'].length == 0){
console.log('END');
return
}else{
var shifted = Obj['out'].shift();
console.log(shifted);
return getChild(graph[shifted]);
}
}
Can anyone guide me to traverse the graph in maximum efficient way
You could traverse your tree in a Depth First manner as follow:
var traverse = function(tree, current) {
//process current node here
//visit children of current
for (var cki in current.out) {
var ck = current.out[cki];
var child = tree[ck];
traverse(tree, child);
}
}
//call on root node
traverse(graph, graph["alpha"]);
[edit: mistake just above]
However, is there any particular reason for the flat layout of the tree? JS allows you to nest data arbitrarily, so you could just have
var graph = {
alpha: {
a: {},
b: {
c: {
d: {}
},
e: {
f: {},
g: {}
}
}
}
}
Now you are only dealing with the nodes themselves, and you don't need references. This makes loops (which would break the above function) impossible. To traverse this tree, you can simplify the traverse function to only passing the current node:
var traverse2 = function(current) {
//process current node here
console.log('visiting ' + current);
//visit children of current
for (var ck in current) {
var child = current[ck];
traverse2(child);
}
}
//call on root node
traverse(graph);
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With