Как создать ориентированный граф из массива элементов?

Question

У меня есть массив объектов.

input = [ 
    {id:1, from:h, to:l}, 
    {id:2, from:b, to:e}, 
    {id:3, from:p, to:q}, 
    {id:4, from:e, to:h}, 
    {id:5, from:e, to:g}, 
    {id:6, from:l, to:m}, 
    {id:7, from:m, to:k}, 
    {id:8, from:k, to:i}, 
    {id:9, from:g, to:i}, 
    {id:10, from:i, to:b} 
] 

элементов в массиве сортируется по атрибуту под названием id.

Атрибут id является уникальным.

Узлы на графике должны быть соединены атрибутами from и to каждого элемента массива.

Пример (не основаны в приведенном выше массиве):

{id:1, from:a, to:b} --> {id:2, from:b,to:c} --> {id:3, from:c, to:a} 

Выход алгоритма должен быть таким:

output = [ 
    {id:1, from:h, to:l, next: [object with id = 6]}, 
    {id:2, from:b, to:e, next: [object with id = 4, object with id = 5]}, 
    {id:3, from:p, to:q, next: [null]}, 
    {id:4, from:e, to:h, next: [object with id = 1]}, 
    {id:5, from:e, to:g, next: [object with id = 9]}, 
    {id:6, from:l, to:m, next: [object with id = 7]}, 
    {id:7, from:m, to:k, next: [object with id = 8]}, 
    {id:8, from:k, to:i, next: [object with id = 10]}, 
    {id:9, from:g, to:i, next: [object with id = 10]}, 
    {id:10, from:i, to:b, next: [object with id = 2]} 
] 

Таким образом, конечный ориентированный граф должен выглядеть следующим образом:

Answer 1

Ваша первоначальная структура данных - это список ребрами и является довольно стандартным способом представления диаграммной структуры данных. Я думаю, вы путаете края с узлами. В вашем списке идентификатор уникально идентифицирует ребро, а строчные буквы однозначно идентифицируют узлы.

Graphviz - отличный язык для обозначения графиков. В переводе на GraphViz, ваш график можно записать так:

digraph G { 
h -> l 
b -> e 
p -> q 
e -> h 
e -> g 
l -> m 
m -> k 
k -> i 
g -> i 
i -> b 
} 

Вы можете использовать онлайн-инструмент, как http://www.webgraphviz.com/, чтобы сделать это графически. Это даст результат, как показано ниже. Как вы можете видеть, это сильно отличается от графика, который вы нарисовали.