Using recursion for calculating an incremental value in tree alike structure

Question

I have a data structure as depicted below, basically data is an array containing a list of nodes, each node can be connected with a parent node, creating a tree alike structure.

Each node has a rotation_relative property, this it is its relative rotation.

As nodes can be nested at any level I need to calculate property rotation_absolute for every node based on its parents, (I have added the final result for each node in the tree below).

Basically leaves should have a rotation_absolute equals to the sum of their parents in the right path.

Considering that:

The node in data array can be placed at any order.
There could be an unlimited number of nesting (node inside a node).
Data could contain hundred of nodes

Could you advice any algorithm to solve the problem?

A
|_B
| |_F (rotation_absolute = -20)
|
|_C
  |_D (rotation_absolute = 20)
    |_E (rotation_absolute = 40)

X (rotation_absolute = 20)
|_J (rotation_absolute = 0)
|_Y (rotation_absolute = 40)

Code example

 <!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <title>Test</title>
    <script>
        window.app = {
            data: [
                {
                    id: 'j',
                    parent: 'x',
                    rotation_relative: 20,
                    rotation_absolute: null
                },
                {
                    id: 'y',
                    parent: 'x',
                    rotation_relative: 20,
                    rotation_absolute: null
                },
                {
                    id: 'a',
                    parent: '',
                    rotation_relative: 0,
                    rotation_absolute: null
                },
                {
                    id: 'f',
                    parent: 'b',
                    rotation_relative: -20,
                    rotation_absolute: null
                },
                {
                    id: 'b',
                    parent: 'a',
                    rotation_relative: 0,
                    rotation_absolute: null
                },
                {
                    id: 'e',
                    parent: 'd',
                    rotation_relative: 20,
                    rotation_absolute: null
                },
                {
                    id: 'x',
                    parent: '',
                    rotation_relative: 20,
                    rotation_absolute: null
                },
                {
                    id: 'c',
                    parent: 'a',
                    rotation_relative: 0,
                    rotation_absolute: null
                },
                {
                    id: 'd',
                    parent: 'c',
                    rotation_relative: 20,
                    rotation_absolute: null
                },
            ],
            start: function () {
                // get root
                var get1Level = function (parent) {
                    var nodes1L = this.data.filter(function (item) {
                        if (item.parent === parent) {
                            return true;
                        } else {
                            return false;
                        }
                    }, this);
                    return nodes1L;
                }.bind(this);

                var recursion = function (id) {
                    var nodes = get1Level(id);
                    nodes.forEach(function (item) {
                        console.log(item);
                        recursion.call(this, item.id);
                        console.log('--');
                    }, this);

                }.bind(this);


                var roots = recursion.call(this, '');
            }
        };
    </script>
</head>

Notes:

I realize the title could be really descriptive, please feel free to suggest me a better one. Thanks all.

This is an example of recursion I am working on but I have some problem with adding of value part.

https://jsbin.com/qexeqasema/1/edit?html,console,output

Well the first thing to do (probably) is to actually build the data structure. What you've got there is an array whose contents imply a data structure, but it's structurally and computationally just a flat list. — Pointy
– Pointy, Commented Aug 17, 2015 at 11:46
@Pointy thanks for sharing, would you able to provide me an example? Thanks in advance for your time on this. — GibboK
– GibboK, Commented Aug 17, 2015 at 11:48
look at the answer for this question, that should help you understand the data structure, and there are some recursive functions there to get you started. Find / delete / add / update objects in nested json — WhiteHat
– WhiteHat, Commented Aug 17, 2015 at 12:05
so far I have tried this script, it is in a early state jsbin.com/cugiyekedu/edit?html,output — GibboK
– GibboK, Commented Aug 17, 2015 at 12:09
@WhiteHat thanks for your comment, are you sure that link is relevant? For my understanding they are using a nested structure not the parent id concept — GibboK
– GibboK, Commented Aug 17, 2015 at 12:27

potatopeelings · Accepted Answer · 2015-08-17 13:21:25Z

If you don't mind using a method, you can do this

function rotation_absolute() {
    return this.rotation_relative + (this.parentNode ? this.parentNode.rotation_absolute() : 0);
}

var result = {};
var address = {};
window.app.data.forEach(function (e) {
    address[e.id] = e;
    e.rotation_absolute = rotation_absolute.bind(e);

    // see if we have a set of (preceding) nodes with this one as parent
    if (result[e.id] instanceof Array) {
        result[e.id].forEach(function (c) {
            c.parentNode = e;
            e[c.id] = c;
        });
        delete result[e.id];
    }

    // top level nodes
    if (e.parent === "") {
        result[e.id] = e;
    }
    else
    {
        var parent = address[e.parent]
        if (parent !== undefined) {
            // add to parent
            parent[e.id] = e;
            e.parentNode = parent;
        }
        else {
            // add to top level temporary array
            result[e.parent] = result[e.parent] || [];
            result[e.parent].push(e);
        }
    }

    // don't actually need to do this - I just added it to remove the clutter in the console
    delete e.rotation_rotation;
    delete e.parent;
})

console.log(result)
console.log(result.a.c.d.e.rotation_absolute())

Or you could just recurse through the built hierarchy and set the value using the method.

Cybercartel · Accepted Answer · 2015-08-17 12:07:06Z

0

If you can limit the dimension of the tree you can try nesting for-loops. Each level of the tree is then one for-loop. Unlimited dimension of tree isn't easy. Maybe you can try a recursive algorithm.

answered Aug 17, 2015 at 12:07

Cybercartel

12.6k7 gold badges39 silver badges73 bronze badges

Comments

GibboK · Accepted Answer · 2015-08-18 07:34:58Z

I was able to solve my answer using recursion plus some additional logic for handling rotation for sibling elements.

Working example

  <!DOCTYPE html>
    <html>
    <head>
        <meta charset="utf-8">
        <title>Test</title>
        <script>
            window.app = {
                data: [
                    {
                        id: 'a',
                        parent: 'area',
                        rotation_relative: 0,
                        rotation_absolute: null
                    },
                        {
                            id: 'b',
                            parent: 'a',
                            rotation_relative: 0,
                            rotation_absolute: null
                        },
                            {
                                id: 'c',
                                parent: 'b',
                                rotation_relative: -10,
                                rotation_absolute: null
                            },
                        {
                            id: 'd',
                            parent: 'a',
                            rotation_relative: 0,
                            rotation_absolute: null
                        },
                            {
                                id: 'e',
                                parent: 'd',
                                rotation_relative: 0,
                                rotation_absolute: null
                            },
                                {
                                    id: 'f',
                                    parent: 'e',
                                    rotation_relative: 10,
                                    rotation_absolute: null
                                },
                                    {
                                        id: 'g',
                                        parent: 'f',
                                        rotation_relative: 10,
                                        rotation_absolute: null
                                    },
            {
                id: 'area',
                parent: '',
                rotation_relative: 0,
                rotation_absolute: null
            },
                {
                    id: 'h',
                    parent: 'area',
                    rotation_relative: 10,
                    rotation_absolute: null
                },
                    {
                        id: 'i',
                        parent: 'h',
                        rotation_relative: -10,
                        rotation_absolute: null
                    },
                    {
                        id: 'l',
                        parent: 'h',
                        rotation_relative: 10,
                        rotation_absolute: null
                    },
            {
                id: 'x',
                parent: 'area',
                rotation_relative: 0,
                rotation_absolute: null
            },
                {
                    id: 'y',
                    parent: 'x',
                    rotation_relative: -10,
                    rotation_absolute: null
                },
                    {
                        id: 'q',
                        parent: 'y',
                        rotation_relative: 10,
                        rotation_absolute: null
                    },
                        {
                            id: 'o',
                            parent: 'q',
                            rotation_relative: -10,
                            rotation_absolute: null
                        },

            {
                id: 'w',
                parent: 'area',
                rotation_relative: 10,
                rotation_absolute: null
            },

                {
                    id: 'z',
                    parent: 'w',
                    rotation_relative: -10,
                    rotation_absolute: null
                },
                {
                    id: 'j',
                    parent: 'w',
                    rotation_relative: -10,
                    rotation_absolute: null
                },

            {
                id: 's',
                parent: 'area',
                rotation_relative: 10,
                rotation_absolute: null
            },
                {
                    id: 't',
                    parent: 's',
                    rotation_relative: -10,
                    rotation_absolute: null
                },
                {
                    id: 'v',
                    parent: 's',
                    rotation_relative: 10,
                    rotation_absolute: null
                },

            {
                id: 'm',
                parent: 'area',
                rotation_relative: -10,
                rotation_absolute: null
            },
                {
                    id: 'n',
                    parent: 'm',
                    rotation_relative: 10,
                    rotation_absolute: null
                },
                {
                    id: 'i',
                    parent: 'm',
                    rotation_relative: 10,
                    rotation_absolute: null
                },
                ],
                getById: function (id) {
                    var result = null;
                    for (var i = 0, len = this.data.length; i < len; i++) {
                        var item = this.data[i];
                        if (item.id === id) {
                            result = item;
                        }
                    }
                    return result;
                },
                start: function () {
                    // get root
                    var get1Level = function (parent) {
                        var nodes1L = this.data.filter(function (item) {
                            if (item.parent === parent) {
                                return true;
                            } else {
                                return false;
                            }
                        }, this);
                        return nodes1L;
                    }.bind(this);

                    var increment = 0;
                    var parent = null;

                    var recursion = function (id) {
                        var nodes = get1Level(id);
                        nodes.forEach(function (item) {
                            if (!parent) {
                                parent = item.parent;
                            }
                            if (parent && parent === item.parent) {
                                var targetParent = this.getById(parent);
                                increment = targetParent.rotation_relative;
                                increment += item.rotation_relative;
                                item.rotation_absolute = increment;

                            }
                            if (parent && parent !== item.parent) {
                                parent = item.parent;
                                var targetParent = this.getById(parent);
                                increment = targetParent.rotation_absolute ? targetParent.rotation_absolute : 0;
                                increment += item.rotation_relative;
                                item.rotation_absolute = increment;
                            }



                            console.log(item);
                            recursion.call(this, item.id);
                            console.log('---');
                        }, this);

                        //increment = 0;
                        //parent = null;

                    }.bind(this);


                    recursion.call(this, 'area');



                }
            };
        </script>
    </head>
    <body onload="window.app.start();">
    </body>
    </html>

Collectives™ on Stack Overflow

Using recursion for calculating an incremental value in tree alike structure

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related