隣接リストまたはエッジペアとして表される有向非巡回グラフ(DAG)における任意の2ノード間のすべてのパス(グラフGにおけるソースからターゲットへのすべての単純なパス)

Ruby: Finding all paths between 2 nodes of directed acyclic graph (DAG) represented as adjacency list or edge pairs – StackOverflow

処理としては単にDFSだが,Pythonではnetworkxがリーズナブルチョイス.

import networkx as nx


l = [[1, 2], [1, 3], [2, 4], [2, 7], [3, 4], [4, 5], [4, 6], [5, 7], [6, 7]]
G = nx.DiGraph()
G.add_edges_from(l)
list(nx.all_simple_paths(G, 1, 7))
[[1, 2, 4, 5, 7], [1, 2, 4, 6, 7], [1, 2, 7], [1, 3, 4, 5, 7], [1, 3, 4, 6, 7]]
カテゴリー: 未分類 パーマリンク

コメントを残す

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

WordPress.com ロゴ

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

Google フォト

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

Twitter 画像

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

Facebook の写真

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

%s と連携中

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