Блог

Главная - Вопросы по программированию - Сортировка графических данных по столбцам

Сортировка графических данных по столбцам

#javascript #graph

#javascript #График

Вопрос:

У меня есть эти данные:

 const main = 'a';
const data = [{
  from: 'a',
  to: 'b'
}, {
  from: 'b',
  to: 'c'
}, {
  from: 'c',
  to: 'd'
}, {
  from: 'b',
  to: 'd'
},
 {
   from: 'd',
   to: 'e'
 },
  {
    from: 'a',
    to: 'e'
  }
];

я хочу отформатировать его так, чтобы получилось что-то вроде:

 {
  col1: [b, ""],
  col2: [c, "", ""],
  col3: [d, ""],
  col4: [e]
}

Этот макет будет использоваться для размещения узлов на их позициях.

График должен выглядеть следующим образом (извините за мои плохие навыки рисования):

введите описание изображения здесь

Пустые строки представляют «невидимые узлы», которые я буду использовать для соединения других узлов путями. На графике будут фиксированные позиции узлов.

Как я могу добиться указанного выше формата? Спасибо

Комментарии:

1. Я не думаю, что эта структура данных имеет большой смысл. Подобные столбцы применимы, только если вы знаете некоторый порядок (прямо сейчас, т. Е. в алфавитном порядке). Может быть, вы можете подробнее объяснить, каков ваш вариант использования и чего вы пытаетесь достичь (проблема может возникнуть только при сборе надлежащего требования и решения)

2. Я думаю, вы могли бы каким-то образом уменьшить массив (например, запомнить свой текущий узел и обработать ребро, если оно выходит за пределы текущего узла, а затем установить новый узел …)

3. @JSHelp у вас есть пример того, как вы могли бы добиться этого в этом случае?

4. Как вы представляете соединение между узлами? Что произойдет, если я удалю соединение A -> B -> C? Я могу создать функцию, которая возвращает именно тот пример, который вы ищете, но она будет работать, только если все узлы соединены в алфавитном порядке…

Ответ №1:

Вот краткий пример решения.

  • Предположение: порядок расположения узлов ( from и to ) соответствует порядку их нахождения в data

  • Предостережение: это порядка O(m * n) 

     const main = 'a';
const data = [...];

let order = [];
let res = {};

data.forEach(i => {
    if (!order.includes(i.from)) {
        order.push(i.from);
        res[i.from] = 0;
    }
    if (!order.includes(i.to)) {
        order.push(i.to);
        res[i.to] = 0;
    }
    for (let temp = order.indexOf(i.from)   1; temp < order.indexOf(i.to); temp  )
        res[order[temp]]  ;
});

Вы можете удалять a из res , изменять структуру данных по своему усмотрению и так далее.