ndarrayで隣接リストを宣言したい

Question

ArrayList<Integer>[] list=new ArrayList[N];
for(int i=0;i<N;++i){
    list[i]=new ArrayList<>();
}
for(int i=0;i<M;++i){
    list[a[i]].add(b[i])
}

をpythonのnumpyのを使って書けないでしょか？

頂点数N、辺数M、辺a_i,b_iを入力として受け取って、
グラフの隣接リストを作りたいです。

（本当にやりたいのはmatoplotlibの2次元プロットですが、隣接リストとして説明した方が分かりやすい気がするのでこのように書いてます）

一次元の場合はnp.append()を使えばよかったのですが、2次元の場合は順次追加していく方法を見つけられませんでした。

ご存知の方ご教示ください。

Answer 1

networkx というライブラリを使うと隣接行列、隣接リストなど簡単に取得できます。

インストール

pip install networkx

サンプルコード

import matplotlib.pyplot as plt
import networkx as nx

nodes = [1, 2, 3, 4, 5]
edges = [(1, 2), (2, 1), (1, 4), (4, 1), (2, 4), (4, 2),
                   (4, 3), (3, 4), (4, 5), (5, 4), (3, 5), (5, 3)]

# 有向グラフを作成する。
G = nx.DiGraph()
# ノード一覧を追加する。
G.add_nodes_from(nodes)
# エッジ一覧を追加する。
G.add_edges_from(edges)

# 隣接行列を返す。
adj_mat = nx.to_numpy_matrix(G)
print(adj_mat)
# [[0. 1. 0. 1. 0.]
#  [1. 0. 0. 1. 0.]
#  [0. 0. 0. 1. 1.]
#  [1. 1. 1. 0. 1.]
#  [0. 0. 1. 1. 0.]]

# 隣接リストを返す。
adj_list = nx.to_dict_of_lists(G)
print(adj_list)
# {1: [2, 4], 2: [1, 4], 3: [4, 5], 4: [1, 2, 3, 5], 5: [4, 3]}

# jupyte notebook を使っていれば、画像が表示される。
# 使用には apt-get install -y graphviz-dev && pip install pygraphviz が必要
from IPython.display import Image
A = nx.nx_agraph.to_agraph(G)
Image(A.draw(format='png', prog='dot'))

追記

標準ライブラリのみを使った隣接リスト作成の例

edges = [(1, 2), (2, 1), (1, 4), (4, 1), (2, 4), (4, 2),
         (4, 3), (3, 4), (4, 5), (5, 4), (3, 5), (5, 3)]

adj_list = {}
from itertools import groupby
for key, group in groupby(sorted(edges), key=lambda x: x[0]):
    conn_to = [g[1] for g in group]  # edge=key が接続しているノード一覧
    adj_list[key] = conn_to

print(adj_list)

{1: [2, 4], 2: [1, 4], 3: [4, 5], 4: [1, 2, 3, 5], 5: [3, 4]}

Comments

[ruei]

ありがとうございます。
標準ライブラリの機能では難しいでしょうか。

[tiitoi]

隣接リスト作成するだけなら標準ライブラリでもできます。
回答に追記しました。

numpy は標準ライブラリではないので、サードパーティのライブラリを使うのであれば、グラフ構造は networkx が便利なので紹介しました。

[ruei]

ありがとうございます！