アイテムの配列から有向グラフを作成する方法は？

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

オリジナルのデータ構造は、グラフデータ構造を表現するためのかなり標準的な方法です。私はあなたがノードとエッジを混同していると思います。あなたのリストでは、idはエッジを一意に識別し、小文字はノードを一意に識別します。

グラフビズはグラフの表記言語です。 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/のようなオンラインツールを使用することができます。これにより、以下のような結果が得られます。ご覧のとおり、これはあなたが描いたグラフとはまったく異なります。