Sort by parent (topological sort) and importance of element on array

Question

Well, I have an array with objects where some elements depends of others elements.

So, I need to order it by importance (dependency of parent) to store this on a database and replace all the children's parent property by the respective parent id.

Example of the array:

[
    {
        "id": 1,
        "email": "[email protected]", // unique
        "parent": "[email protected]" // is nullable
    },
    {
        "id": 2,
        "email": "[email protected]",
        "parent": null
    },
    {
        "id": 3,
        "email": "[email protected]",
        "parent": "[email protected]"
    },
    {
        "id": 4,
        "email": "[email protected]",
        "parent": "[email protected]"
    },
    ...
]

Graphical example of dependency:

Expected result: Ordered by dependency (parent):

[
    {
        "id": 2,
        "email": "[email protected]",
        "parent": null
    },
    {
        "id": 3,
        "email": "[email protected]",
        "parent": 2
    },
    {
        "id": 1,
        "email": "[email protected]",
        "parent": 3 
    },
    {
        "id": 4,
        "email": "[email protected]",
        "parent": 1
    },
    ...
]

To set respective parent id I'm using (but it no ordering by parent level: parent, children, grandchildren...):

let users = [
{
    "id": 1,
    "email": "[email protected]", // unique
    "parent": "[email protected]" // is nullable
},
{
    "id": 2,
    "email": "[email protected]",
    "parent": null
},
{
    "id": 3,
    "email": "[email protected]",
    "parent": "[email protected]"
},
{
    "id": 4,
    "email": "[email protected]",
    "parent": "[email protected]"
}
];

users = users.map(user => {
    user.parent = _.findIndex(users, i => user.parent === i.email);
    return user;
});

P.S: In this case, the importance concept refers to parent level. So, First I need the parents, then the children, grandchildren, and so on...

I am sorry if this thread is poor in explanations, if you have doubts, I will look for the best way to express the idea.

Answer 1

I will approach this by first generating a new input with the replacement of parent email by the parent id and a new property of the node level related to the tree they belong. Then we can sort the nodes by this level property, and on equal level we sort by the id.

const input = [
    {"id": 1, "email": "[email protected]", "parent": "[email protected]"},
    {"id": 2, "email": "[email protected]", "parent": null},
    {"id": 3, "email": "[email protected]", "parent": "[email protected]"},
    {"id": 4, "email": "[email protected]", "parent": "[email protected]"},
    {"id": 5, "email": "[email protected]", "parent": "[email protected]"},
    {"id": 6, "email": "[email protected]", "parent": "[email protected]"},
    {"id": 7, "email": "[email protected]", "parent": null},
    {"id": 8, "email": "[email protected]", "parent": "[email protected]"}
];

const findParent = (mail) => input.find(x => x.email === mail);

const getLevel = (mail, lvl) =>
{    
    return mail ? getLevel(findParent(mail).parent, lvl + 1) : lvl;
}

let newInput = input.map(({id, email, parent}) =>
{
    return {
        id: id,
        email: email,
        parent: findParent(parent) ? findParent(parent).id : null,
        lvl: getLevel(parent, 0)
    };
});

let sortedInput = newInput.sort((a, b) =>
{
    return (a.lvl - b.lvl) ? a.lvl - b.lvl : a.id - b.id;
});

console.log(sortedInput);