pythonで完全グラフの判別を作っています。

Question

###pythonで完全グラフの判別を作っています。

頂点１と頂点２を結ぶ枝を”（頂点１、頂点２）”と表現し、それが複数存在する時の完全グラフの要素を表示したいです。

例
（0,1）、（0,3）、（0,4）、（1,3）、（1,4）、（2,4）、（3,4）という要素がある時、その中に存在する部分的な複数の完全グラフ(0,1,3,4)(2,4)という結果が出て欲しいです。

うまく説明できないのでイメージをのせました。
二つの赤丸のように分けたいです。

要素の多い部分完全グラフ(0,1,3,4)に完全に含まれる部分完全グラフ(0,1,3)や(0,4)などは除外しています。

この質問の意図は　0や１が文書を意味しており、文書間の類似度を出し、設定した閾値より高い文書の組み合わせを(0,1)のように表現しています。目標は類似度の高い文書を一つにまとめることで、そのためにこの方法をとりました。

わかりにくい質問ですみません、何かありました追記します。

該当のソースコード

list = [(0,1),(0,3),(0,4),(1,3),(1,4),(2,4),(3,4)]

試したこと

全投げになってしまって申し訳ないです。考えてはみたんですがアルゴリズムが思いつかないです

Comments

[tiitoi]

与えられたグラフが完全グラフかどうか判別したいということであればわかりますが、期待する結果が (0,1,3,4)(2,4) というのはどういうことでしょうか？この (0,1,3,4)(2,4) はなにを意味していますか？

[Isemoca]

追記しました。分からなければ質問ください

[tiitoi]

あるグラフの"完全グラフである"部分グラフを列挙するということであれば、(0, 1, 3), (0, 1, 4), (1, 4), ... のように他にも完全グラフを構成する部分グラフはあると思いますが、どういった規則でその2つだけ選ばれたのでしょうか？

[Isemoca]

要素の多い部分完全グラフ(0,1,3,4)に完全に含まれる部分完全グラフ(0,1,3)や(0,4)などは除外しています。

[Isemoca]

この質問の意図は　0や１が文書を意味しており、文書間の類似度を出し、設定した閾値より高い文書の組み合わせを(0,1)のように表現しています。目標は類似度の高い文書を一つにまとめることで、そのためにこの方法をとりました。

Answer 1

tiitoiさんの回答からnetworkxを使えばうまくいくと思い、試したところうまくいきそうです。

import networkx as nx
G = nx.Graph()
edgelist=[(0,1),(0,3),(0,4),(1,3),(1,4),(2,4),(3,4)]
G.add_edges_from(edgelist)

for i in nx.find_cliques(G):
    print(i)

# [4, 0, 1, 3]
# [4, 2]

ちなみにグラフを描画する場合は、nx.draw_networkx(G)を実行すると、質問に記載されるものと同じトポロジーのグラフが表示されます。

Answer 2

質問の内容をグラフ理論の用語で定義すると、

「あるグラフ G が与えられたとき、極大であるクリークを求める」**極大クリーク問題 (maximal clique problem)**ということになります。

• クリーク (clique): グラフ G の部分グラフのうち、完全グラフであるもの
• 極大 (maximum) である部分グラフ: 部分グラフのうち、他の部分グラフに含まれないもの

極大クリーク列挙のアルゴリズムとしては、「Bron-Kerbosch アルゴリズム」があるようです。

In computer science, the Bron–Kerbosch algorithm is an algorithm for finding maximal cliques in an undirected graph.

検索ワードとしては、「極大クリーク」「maximum cliques」で調べるとよいです。
上記以外にも いくつかのアルゴリズム があるようです。

GitHub とかで探せば実装例があるかもしれません。

Answer 3

ご自身でおっしゃっているとおりこの質問は「丸投げ」です。多少なりともご自分で考えた論理の断片を書けば丸投げにはならなかっただろうと思いますが・・・

実際にこういう論理が必要となって「どう実現しよう」というのが質問者さんの課題ならば「それについてのアルゴリズムを参照したり、それをやってくれるライブラリーを探す」というのが最も簡単に答えにたどり着ける方法だろうと思います。それについては既に回答がついているので、「それを実現するアルゴリズムを自分で考えてみる」というアプローチについて若干コメントしてみます。

まず問題を小さな問題に分割する

「グラフの中から最大クリークを全て列挙する」というのをいきなり考えても歯が立たないだろうと思います。大抵の問題で言えることですが「それを実現するための補題を設定しそれを考える」というふうに段階的に料理していきましょう。本件でいえば

(A) グラフの中から最大クリークを全て列挙する」
＝＞ (B1) グラフの中から特定の辺を含む最大クリークを求める
＝＝＞ (C1) グラフの中にあるクリークがあったとして、それに含まれないノードを追加したときそれが完全グラフ（クリーク）となっているかどうか検査する
＝＝＝＞ (D1) クリークを成すノード群とそこに含まれないあるノードが互いに接続されているかどうか検査する
＝＝＝＝＞ (E1) あるノードが別のノードと隣接しているか検査する
＝＞ (B2) グラフの中から特定のクリークを構成する辺を除く
・・・

このように段階的により小さくてより単純な補題に分解しながら考えていくのが一つのコツです。(A)をやるためには(B)がわかればよい、(B)をやるためには(C)がわかればよい・・・という感じですね。

アルゴリズムを言語機能を使って実装する

アルゴリズムを考えるときは大抵特定の言語とは関係ない抽象的な論理として考えます。それをコードに落とす際に具体的な言語、例えばPythonが持っている機能をどう応用すればよいかを考えることになります。例えば(E)ですけど

コード1

edges = [(0, 1), (0, 2)]

def is_connected(node0, node1):
    for edge in edges:
        if edge[0] == node0 and edge[1] == node1:
            return True
        if edge[1] == node0 and edge[0] == node1:
            return True
    return False

などとすればできそうです。しかしPythonに慣れてくると「こんな長ったらしいコードは必要ない」ということがだんだんわかってきます。

コード2

edges = [(0, 1), (0, 2)]

# edgesの中の辺は必ずノード番号の昇順のtupleになっていると仮定
def is_connected(node0, node1):
    edge = (node0, node1) if node0 < node1 else (node1, node0)
    return edge in edges

tupleはhashableなのでtupleの列(例えばlist)から特定のtupleが含まれるかどうかはin一発でよいというPythonの知識があればこういうふうに書けます。
さらに型の特徴の理解が深まればinはlistに対して探すよりsetに対して探す方が桁違いに早いということもわかってきます。(言語の特徴というよりlistは順番に要素を並べただけ、setは要素を高速に見つけられるようにhashアルゴリズムを使っているものというような一般アルゴリズムの知識がベースになるといった方がよいかも知れません)

コード3

edges = {(0, 1), (0, 2)}  # こう書くとsetになる

# edgesの中の辺は必ずノード番号の昇順のtupleになっていると仮定
def is_connected(node0, node1):
    edge = (node0, node1) if node0 < node1 else (node1, node0)
    return edge in edges

コードの行数自体はコード2もコード3も同じですが、辺の数が1000, 10000, 100000と増えていくとコード3の方がとてつもなく早いので「listとsetならsetを使うべき」という選択ができることは割と重要です。

---

さて他者が考えた論理、例えばアルゴリズムの解説などを読むことはかなりよい訓練になると思います。それは本回答に書いた「小さな問題に分割する」や「特定の言語機能をうまく使ってわかりやすく簡潔に論理を記述する」というお手本を自分の頭の中の引き出しに蓄える機会になるからです。ただし「ただ漠然と見ているだけ」では引き出しに知識が増えていきません。自分なりに考える（咀嚼する）というプロセスを大事にしてください。典型的には「その論理はどういうアプローチからきたものかを考える」「自分で整理して実際にコードを書いて期待どおりに動くかデバッグする」という繰り返しが大事です。そうしないと力がつきませんし力がついていかないと応用（アプリケーション）が書けるようになりません。

また最初にコメントしたように「質問するなら自分がどこまで考えたのか」を書くべきです。丸投げ質問ばかりしていると(初心者かどうかとは別の次元で)閲覧者にそっぽを向かれかねませんのでご注意を。