Сортировка по родителю (топологическая сортировка) и важности элемента в массиве

Question

Ну, у меня есть массив с объектами, где некоторые элементы зависят от других элементов.

Итак, мне нужно упорядочить по важности (зависимости от родителя), чтобы сохранить это в базе данных и заменить все дочерние свойства parent на соответствующие родительские id.

Пример массива:

[
    {
        "id": 1,
        "email": "a@b.com", // unique
        "parent": "c@b.com" // is nullable
    },
    {
        "id": 2,
        "email": "b@b.com",
        "parent": null
    },
    {
        "id": 3,
        "email": "c@b.com",
        "parent": "b@b.com"
    },
    {
        "id": 4,
        "email": "d@b.com",
        "parent": "a@b.com"
    },
    ...
]

Графический пример зависимости:

Ожидаемый результат: Упорядочено по зависимости (родитель):

[
    {
        "id": 2,
        "email": "b@b.com",
        "parent": null
    },
    {
        "id": 3,
        "email": "c@b.com",
        "parent": 2
    },
    {
        "id": 1,
        "email": "a@b.com",
        "parent": 3 
    },
    {
        "id": 4,
        "email": "d@b.com",
        "parent": 1
    },
    ...
]

Для установки соответствующего родителя id Я использую (но нет упорядочения по родительскому уровню: родитель, дети, внуки ...):

let users = [
{
    "id": 1,
    "email": "a@b.com", // unique
    "parent": "c@b.com" // is nullable
},
{
    "id": 2,
    "email": "b@b.com",
    "parent": null
},
{
    "id": 3,
    "email": "c@b.com",
    "parent": "b@b.com"
},
{
    "id": 4,
    "email": "d@b.com",
    "parent": "a@b.com"
}
];

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

P.S: В этом случае понятие importance относится к уровню parent. Итак, сначала мне нужны родители, потом дети, внуки и так далее ...

Прошу прощения, если эта ветка плоха в объяснениях, если у вас есть сомнения, я буду искать лучший способ выразить идею.

Answer 1

Я подойду к этому, сначала сгенерировав новый вход с заменой parent email на parent id и новым свойством уровня узла, связанным с деревом, которому они принадлежат. Затем мы можем отсортировать узлы по этому свойству level, а по равному level мы отсортируем по id.

const input = [
    {"id": 1, "email": "a@b.com", "parent": "c@b.com"},
    {"id": 2, "email": "b@b.com", "parent": null},
    {"id": 3, "email": "c@b.com", "parent": "b@b.com"},
    {"id": 4, "email": "d@b.com", "parent": "a@b.com"},
    {"id": 5, "email": "x@b.com", "parent": "b@b.com"},
    {"id": 6, "email": "z@b.com", "parent": "x@b.com"},
    {"id": 7, "email": "y@b.com", "parent": null},
    {"id": 8, "email": "m@b.com", "parent": "y@b.com"}
];

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

Answer 2

Ниже приведен итеративный подход (в отличие от рекурсивного решения), который вы можете использовать для достижения своего результата. По сути, начните с поиска корневого элемента, а затем переберите исходный массив, ища элементы, у которых текущий элемент является родительским.

Чтобы добиться замены родительской электронной почты идентификатором, просто сохраните карту родительских имен с идентификаторами:

var data = [{
  "id": 1,
  "email": "a@b.com", // unique
  "parent": "c@b.com" // is nullable
}, {
  "id": 2,
  "email": "b@b.com",
  "parent": null
}, {
  "id": 3,
  "email": "c@b.com",
  "parent": "b@b.com"
}, {
  "id": 4,
  "email": "d@b.com",
  "parent": "a@b.com"
}]

//Map email addresses to IDs
var map = data.reduce((accum, el) => {
  accum[el.email] = {
    id: el.id
  }
  return accum;
}, {});


var [root] = data.filter(el => !el.parent);
var users = [root];
var cur;
var children;
while (users.length < data.length) {
  cur = users[users.length - 1];
  //Find elments that have cur as parent
  children = data.filter(el => el.parent === cur.email);
  children.forEach(el => {
    users.push({
      id: el.id,
      email: el.email,
      parent: map[el.parent].id
    });
  });
}

console.log(users)

Answer 3

вы можете использовать рекурсивную функцию

const data = [{
    "id": 1,
    "email": "a@b.com", // unique
    "parent": "c@b.com" // is nullable
  },
  {
    "id": 2,
    "email": "b@b.com",
    "parent": null
  },
  {
    "id": 3,
    "email": "c@b.com",
    "parent": "b@b.com"
  },
  {
    "id": 4,
    "email": "d@b.com",
    "parent": "a@b.com"
  },

]

const order = (arr, level) => {
  const children = arr.filter(e => e.parent === level); // get the elements that have the same parent ( level )
  const parent = arr.find(e => e.email === level); // get the parent
  
  return children.length 
    ? [
        ...children.map(e => 
          ({ ...e,
            parent: parent ? parent.id : null // update the parent to the id instead of email
          })),
        ...order(arr, children[0].email) // call the same function with the email of the first child of the current children array, it will become a parent
      ] 
    : children // otherwise return the array
}

const result = order(data, null)

console.log(result)