python3 データの関係性

Question

データの関係性を表したいのですが、どういった処理が必要なのか分からない状態です。

データの構図　画像
https://mathtrain.jp/wp-content/uploads/2017/02/deltamatroid2.png

F=[[1,2],[2,3],[2,4],[4,5]]

望む出力
[[1,2,4,5],[2,3,4,5]]

Comments

[jun68ykt]

質問の画像は、こちら、https://mathtrain.jp/deltamatroid の記事に掲載されているものと思いますが、ご質問の趣旨は、このURLのページに掲載の 頂点集合E={1,2,3,4,5} から、F={∅,{1,2},{2,3},{2,4},{4,5}{1,2,4,5},{2,3,4,5}} 　を作り出すためのアルゴリズムを知りたいということでしょうか？

[SpecialTukimiya]

はい。そうです。

Answer 1

直接の回答になりませんが、参考になりそうな情報提供です。

F=[[1,2],[2,3],[2,4],[4,5]]

からネットワーク図を描画する方法としてnetworkxというモジュールを使う方法があります。

import networkx as nx

fig = nx.Graph()
fig.add_edges_from(F)

nx.draw_networkx(fig)
plt.show()

上記において生成したグラフ（fig）をnetworkxのいろいろな関数に入力すると、クリークや最短パスなどが取得できるので、目的に応じて活用してはいかがでしょうか？

単純に目的とする配列を取得するのであれば、以下のようなコードもあり得ます。

ff = nx.simple_paths.all_simple_paths(fig,source=1,target=5)
for i in ff :
    print(i)
# [1,2,4,5]

上記は、グラフの端にあたるnode=1とnode=5をつなぐすべてのパスを取得するものです。したがって、figから端にあたるnodeの組み合わせを識別して上記の関数に入力すれば、一応、答えを得ることができます。

私はご質問の背景にあるアルゴリズムをわかっていないので、どの関数を活用するといいのかわかりませんが、参考になれば幸いです。

Comments

[SpecialTukimiya]

情報提供ありがとうございます。