Selecting the appropriate algorithm for creating and calculating permutations of element-sharing pairs

Selecting the appropriate algorithm for creating and calculating permutations of element-sharing pairs – StackOverflow

質問がわからないから適当に考える.

import networkx as nx
from graphviz import Source


strings = '(A, B), (B, C), (C, D), (D, E), (A, D), (E, A), (A, C)'
lst = re.findall(r'([A-Z]), ([A-Z])', strings)

G=nx.Graph()
G.add_edges_from(lst)
nx.drawing.nx_pydot.write_dot(G, 'graph1.dot')
Source.from_file('graph1.dot')

Screenshot 2019-10-28 at 15.09.42.png

今,どのノードからも起点へのエッジがあるので,起点とのエッジがあるかどうか気にする必要はない.無向で起点と終点が同じになる様なパスを考えるので,深さ優先ですべてを通る経路,カットオフを決めて,任意の最大長のルートを得れば良い.

list(nx.dfs_edges(G, 'A'))
[('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E')]
res1 = max(nx.all_simple_paths(G, 'A', 'E', 7), key=lambda x: len(x))+ ['A']
res2 = ['A'] + max(nx.all_simple_paths(G, 'D', 'A', 7), key=lambda x: len(x))
res1, res2
(['A', 'B', 'C', 'D', 'E', 'A'], ['A', 'D', 'C', 'B', 'A'])
カテゴリー: 未分類 パーマリンク

コメントを残す

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

WordPress.com ロゴ

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

Google フォト

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

Twitter 画像

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

Facebook の写真

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

%s と連携中

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