pythonにて、数字の参照から、array を取り出したいです。

Question

前提・実現したいこと

node = {0: (0.0, 0.0), 1: (5.0, 4.0), 2: (2.0, 8.0), 3: (9.0, 1.0), 4: (8.0, 10.0)}
edge={0: (0, 1), 1: (2 , 3 ), 2: (1, 2), 3: (3, 0)}

という数字の列があり、ノードは点の座標
（点１は（ｘ、ｙ）＝（０，０）、点３は　（ｘ、ｙ）＝（９，１）にあるという意味です）
エッジは、それぞれのノードとノードをつなぐ線を表しています。
（エッジー１はノード０からノード１へ）

上記の数字から、ノードをエッジでつなげて一周させるというプログラムを書いています。

ここで、エッジ０は、(0,1)へ、次にエッジ３は(1,2)へ、と円を描いていくように、ノードの位置を見つけていくプログラムをつくっています。

上の例のものだと、
エッジ　０ー＞２ー＞１－＞３
ノード　(0.0, 0.0)ー＞(5.0, 4.0)ー＞(2.0, 8.0)ー＞(9.0, 1.0)ー＞(0.0, 0.0)
という結果をだしたいです。

ノードの順番を探すコードは、

###コード

'''File Open'''
pos_array=np.loadtxt("test_data.txt", dtype='float')
edge_array=np.loadtxt("edge.txt", dtype='int')
pos = {}
edge = {}


# ndarrayの情報を「(x,y)」という値に変換する
for i in range(len(pos_array)):
    pos[i] = (pos_array[i][0], pos_array[i][1])
for i in range(len(edge_array)):
    edge[i] = (edge_array[i][0], edge_array[i][1])


find_x = 0
start = 0
i=0
'''
import array
a = array.array(int, [])
a.append(1)
a.append(5)
print(a,"a")
sys.exit(1)
#==> (i,[1,5]) How can I change i to the interger?
'''
J = np.zeros((len(edge_array),len(edge_array)))
j=0
k=0
while True:
    print(i,"i")
    if edge[i][0]==find_x:
            find_x=edge[i][1]
            k=k+1
            print(find_x)
            i=0
            if find_x==start:
                print("find a loop")
                break
            continue
    i=i+1

と、書いてみました。これにより、エッジが一周できるようにコードを書いたつもりです。
ここで、このエッジを、どうやってノードの座標として表示するか迷っています。

いくつか試した方法としては、

a = array.array("i", [])
a.append(i)
print(node[i])

と、エッジから次の見つけた時点で配列aに保存できるようにしました。
ですが、この問題はいくつ円ができるかわからないものなので、二次元配列を使わないといけないとおもったのですが、うまく実装できませんでした。

できれば、配列に
array[0]=０ー＞２ー＞１－＞３
array[1]=５－＞７－＞６－＞９＞８
array[2]=１３－＞１７－＞１２－＞３０
などそれぞれの円を保存をし、
array[0]=nodes[０]ー＞nodes[１]ー＞nodes[２]－＞nodes[３]
array[1]=nodes[５]ー＞nodes[７]ー＞nodes[６]－＞nodes[９]ー＞nodes[８]
array[2]nodes[１３]ー＞nodes[１７]－＞nodes[１２]ー＞nodes[３０]
から、(0.0, 0.0)ー＞(5.0, 4.0)ー＞(2.0, 8.0)ー＞(9.0, 1.0)ー＞(0.0, 0.0)
....
...
という座標による表示ができるようになりたいです。

どのようにしたらarray[0]とすると、残りのノードの順番[0,2,1,3]が出てくるような
ものができるでしょうか。
二次元配列のコードもかいてみたのですが、円のおおきさがひとつひとつ違うので、うまく実装することができませんでした。

よろしくお願いします。

Comments

[toast-uz]

エッジ　０: (0, 1)ー＞２: (1, 2)ー＞１:(2 , 3 )－＞３:(3, 0)
は理解できるのですが、そうすると
ノード　0: (0.0, 0.0) の次は　2: (2.0, 8.0) ではなく、1: (5.0, 4.0) が正しいのではないでしょうか？

[tamago_yaki]

仰る通りです。問題について勘違いをしていました。修正させて頂きます。

Answer 1

Graphillionはいかがでしょうか？
これも実際に使ったわけではありませんが、性能向上、複数のグラフをまとめて操作して最適なグラフを探索、など、要望の特性を備えているように思われます。

Answer 2

実際に使っていないので参考程度ですが、自ら実装しないでグラフ構造を表すライブラリを利用するのが近道ではないでしょうか。
https://qiita.com/asi1007/items/d38c7a13b193726b1b2f　など

Comments

[tamago_yaki]

networkXも考えたのですが、O（n）またはＯ（nlogn)での実装を求めています。
また、ノード数の多い順と、ノードの最初の数が小さい順で並べ替えなければならないので、
networkXは使えませんでした、、
もし何か他にノードとエッジに対するサンプルアルゴリズムなどあれば、教えていただけると幸いです、