ノードの座標を表すリストからツリー構造を作成

if I want to make a tree structure from the string? – StackOverflow

ノードの座標を表すリストが与えられた時,ツリー構造を構築する効率的な方法を考える.特に仮定(条件)が明示されていないので,xy座標面で上から下へツリー構造となる様に仮定すると,座標リストをy軸で降順にソートして,最短エッジを求めていけば良い事が分かる.各ノードの番号は,質問の通り,リスト内の順番で振っていくと,

from collections import defaultdict
import networkx as nx


lst = [[5, 3], [11, 5], [13, 3], [3, 5], [6, 1], [1, 3], [8, 6], [7, 2], [2, 2]]
idx_d = {tuple(v): k for k, v in enumerate(lst, 1)}

dd = defaultdict(set)
for v, k in sorted(lst, key=lambda x: -x[1]):
    dd[k].add(v)

G = nx.Graph()
G.add_nodes_from(range(1, len(lst)+1))
for i in G:
    G.node[i]['pos'] = lst[i-1]

b = None
for k, v in dd.items():
    if b is not None:
        f = lambda e: min((s for s in b[0]), key=lambda x: abs(x-e))
        l = [(idx_d[f(e), b[1]], idx_d[e, k]) for e in v]
        G.add_edges_from(l)
    b = (v, k)

pos = nx.get_node_attributes(G, 'pos')
nx.draw(G, pos, with_labels=True)

download

広告
カテゴリー: 未分類 パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください