CODEWITHSUNDEEP
javascriptalgorithm
Fawzan
Fawzan

Reputation: 4849

Traversing a tree javascript

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 a rough visualization of the 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 :

  1. alpha is always the parent node.
  2. any node can have only one input connection and maximum of n-number of output connections

Right 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

Upvotes: 9

Views: 17547

Answers (2)

sqykly
sqykly

Reputation: 1586

Using ES5 only I would stick to the guarantee of no cycles in your graph and "parse" with array methods:

function pathsFrom(vertex) {
    if (vertex.out.length === 0) return [[vertex]];
    var pathsOfEachChild = vertex.out.map(pathsFrom),
        flatListOfPaths = pathsOfEachChild.reduce(function (flat, branch) {
            return flat.concat(branch);
        }),
        withVertexPrepended = flatListOfPaths.map(function (path) {
            return [vertex].concat(path);
        });
    return withVertexPrepended;
}

ran a test (took the liberty of giving vertices a toString) and got

[["alpha", "a"], ["alpha", "b", "c", "d"], ["alpha", "b", "e", "f"], ["alpha", "b", "e", "g"]]

Upvotes: 1

ferry
ferry

Reputation: 437

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);

Upvotes: 16

Related Questions