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 :

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

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 :

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

• javascript
• algorithm

• Not certain interpret Question correctly ? Only out property traversed ? Why would [alpha, b, e, g] contain e ? – guest271314 Commented Nov 29, 2015 at 2:02
• Node g has a self loop. – Sam Segers Commented Nov 29, 2015 at 2:06
• thanks fior the pinter @SamSegers – Fawzan Commented Nov 29, 2015 at 5:54

2 Answers 2

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

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