Traversing a tree javascript

Question

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.
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

Not certain interpret Question correctly ? Only out property traversed ? Why would [alpha, b, e, g] contain e ? — guest271314
– guest271314, Commented Nov 29, 2015 at 2:02

ferry · Accepted Answer · 2015-11-29 06:45:04Z

16

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

edited Nov 29, 2015 at 6:45

answered Nov 29, 2015 at 2:09

ferry

4371 gold badge4 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

sqykly Over a year ago

first code block's for enumerates the keys of the array, not the elements as it appears you intend.

ferry Over a year ago

in JS, for (var i in <Array>) causes i to take successive indices of the elements of the array, hence cki for "child key index". Actually, though, there's a different mistake in the code.

sqykly Over a year ago

aha, I didn't notice that the i went back to being an index. My bad.

Fawzan Over a year ago

@ferry can you please edit the functions to return the 2D array?

ferry Over a year ago

@Fawzan Not sure what you mean. Do you mean the adjacency information in the .out property? The function is recursive, do you want it to accumulate that information?

|

sqykly · Accepted Answer · 2015-11-29 07:04:14Z

1

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"]]

answered Nov 29, 2015 at 7:04

sqykly

1,59611 silver badges16 bronze badges

Collectives™ on Stack Overflow

Traversing a tree javascript

2 Answers 2

6 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related