Recursively accumulate a path to an array from a Javascript Object

Question

I am trying to find all the child elements of a node in the following Javascript Object.

var graphObj = {

        a : {
            'true' : ['e', 'i'],
            'false' : ['u'],
            'blah' : 'extra key'
        },
        e : {
            'true' : ['o'],
            'false' : ['v'],
            'blah' : 'extra key'
        },
        f : {
            'true' : [],
            'false' : [],
            'blah' : 'extra key'
        },
        i : {
            'true' : [],
            'false' : ['f'],
            'blah' : 'extra key'
        },
        o : {
            'true' : [],
            'false' : [],
            'blah' : 'extra key'
        },
        u: {
            'true': [],
            'false': [],
            'blah' : 'extra key'
        },
        v: {
            'true': [],
            'false': [],
            'blah' : 'extra key'
        },
        z: {
            'true': [],
            'false': [],
            'blah' : 'extra key'
        },

    };

This method will return the children of a given node

var getChilds = function (opId) {


            var r;

            if (graphObj.hasOwnProperty(opId)) {

                var t = graphObj[opId].true.slice();
                var f = graphObj[opId].false.slice();

                r = t.concat(f);


            } else {
                console.log('No node found with the ID');
            }

            return r;

        }

        console.log(getChilds('a'));

current [output] => ['e', 'i', 'u']

But I need a way to accumulate all the child nodes by recursively traversing the graph.

required output => ['e', 'i', 'u', 'o', 'v', 'f']

Can anyone help me?

Note : This is a directed graph. No loops. Also true and false are the only keys on the node storing edge types.

Could you provide one sample function call based on the graphObj for the function you want? As in, define a unit test case? — Andrew Templeton
– Andrew Templeton, Commented Jan 10, 2016 at 4:26
Do your graphs always look like this? i.e. at the top level you have an object, at the second level several objects and at the third level arrays that contain strings? — Tesseract
– Tesseract, Commented Jan 10, 2016 at 4:30
Is this the exact order you want? Does order matter at all? Right now, it looks like you at least want it partitioned by traversal minimum distance. — Andrew Templeton
– Andrew Templeton, Commented Jan 10, 2016 at 4:34

Andrew Templeton · Accepted Answer · 2016-01-10 04:54:51Z

1

I took your "order does not matter" comment into consideration and also made sure to only include ['true', 'false'] as edge type keys to traverse on.

var graphObj = {

        a : {
            'true' : ['e', 'i'],
            'false' : ['u']
        },
        e : {
            'true' : ['o'],
            'false' : ['v']
        },
        f : {
            'true' : [],
            'false' : []
        },
        i : {
            'true' : [],
            'false' : ['f']
        },
        o : {
            'true' : [],
            'false' : []
        },
        u: {
            'true': [],
            'false': []
        },
        v: {
            'true': [],
            'false': []
        }
    };
console.log(getChildren('a')); // [ 'e', 'o', 'v', 'i', 'f', 'u' ]


function getChildren(entry) {
    var visited = {};
    var children = {};
    traverse(entry);
    return Object.keys(children);
    function traverse (entry) {
        if (visited[entry]) {
            return;
        }
        if (!graphObj[entry]) {
            throw new Error('Node "' + entry + '" does not exist in graph!');
        }
        var edgeTypes = ['true', 'false'];
        // USE THIS LINE FOR ARBITRARY EDGE TYPES
        // var edgeTypes = Object.keys(graphObj[entry]);
        visited[entry] = true;
        edgeTypes.forEach(function(edgeType) {
            var nodeList = graphObj[entry][edgeType] || [];
            nodeList.forEach(function(nodeLetter) {
                children[nodeLetter] = true;
                traverse(nodeLetter);
            });
        });
    }
}

edited Jan 10, 2016 at 4:54

answered Jan 10, 2016 at 4:44

Andrew Templeton

1,69610 silver badges13 bronze badges

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

3 Comments

Fawzan Over a year ago

This solution provides the exact behaviour I wanted. Kudos.

Andrew Templeton Over a year ago

No problem :) Please update your actual question to reflect that (1) the graph is not strictly a tree and (2) true and false are the only keys on the node storing edge types, so that the question and answer make sense for future readers

Fawzan Over a year ago

Sure. I will modify it now.

Collectives™ on Stack Overflow

Recursively accumulate a path to an array from a Javascript Object

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related