11

ウェブ上のどこでクリークを見つけるためのブロン・ケルボッシュアルゴリズムの説明を見つけることができるか、またはここでそれがどのように機能するかを説明できますか?

「アルゴリズム 457: 無向グラフのすべてのクリークを見つける」という本に掲載されていることは知っていますが、アルゴリズムを説明する無料のソースが見つかりません。

アルゴリズムのソース コードは必要ありません。アルゴリズムの仕組みの説明が必要です。

4

7 に答える 7

8

アルゴリズムの説明はここにあります：http ：//www.dfki.de/~neumann/ie-seminar/presentations/finding_cliques.pdf それは良い説明です...しかし、C＃でのライブラリまたは実装が必要です-.- '

于 2010-03-30T16:38:57.740 に答える
4

ペーパーのコピーを提供できる ACM 学生アカウントを持っている人を探してみてください。

ダウンロードしたばかりで、長さはわずか 2 ページで、実装は Algol 60 です。

于 2008-09-27T09:03:07.700 に答える
2

また、Bron-Kerbosch アルゴリズムに頭を悩ませようとしていたので、Python で独自の実装を作成しました。これには、テスト ケースといくつかのコメントが含まれます。お役に立てれば。

class Node(object):

    def __init__(self, name):
        self.name = name
        self.neighbors = []

    def __repr__(self):
        return self.name

A = Node('A')
B = Node('B')
C = Node('C')
D = Node('D')
E = Node('E')

A.neighbors = [B, C]
B.neighbors = [A, C]
C.neighbors = [A, B, D]
D.neighbors = [C, E]
E.neighbors = [D]

all_nodes = [A, B, C, D, E]

def find_cliques(potential_clique=[], remaining_nodes=[], skip_nodes=[], depth=0):

    # To understand the flow better, uncomment this:
    # print (' ' * depth), 'potential_clique:', potential_clique, 'remaining_nodes:', remaining_nodes, 'skip_nodes:', skip_nodes

    if len(remaining_nodes) == 0 and len(skip_nodes) == 0:
        print 'This is a clique:', potential_clique
        return

    for node in remaining_nodes:

        # Try adding the node to the current potential_clique to see if we can make it work.
        new_potential_clique = potential_clique + [node]
        new_remaining_nodes = [n for n in remaining_nodes if n in node.neighbors]
        new_skip_list = [n for n in skip_nodes if n in node.neighbors]
        find_cliques(new_potential_clique, new_remaining_nodes, new_skip_list, depth + 1)

        # We're done considering this node.  If there was a way to form a clique with it, we
        # already discovered its maximal clique in the recursive call above.  So, go ahead
        # and remove it from the list of remaining nodes and add it to the skip list.
        remaining_nodes.remove(node)
        skip_nodes.append(node)

find_cliques(remaining_nodes=all_nodes)
于 2014-06-25T17:59:03.260 に答える
2

ここにアルゴリズムがあり、セット R、P、X として Java リンクリストを使用して書き直しました。

アルゴリズムを書き直すときの最適化の問題のため、実装について少し考えることをお勧めします

于 2008-10-11T21:20:10.193 に答える
0

価値のあるものとして、Java 実装を見つけました: http://joelib.cvs.sourceforge.net/joelib/joelib2/src/joelib2/algo/clique/BronKerbosch.java?view=markup

HTH。

于 2008-09-27T11:51:37.937 に答える
0

Boost::Graph には、Bron-Kerbosh アルゴリズムの優れた実装があります。チェックしてみてください。

于 2012-06-17T12:41:18.713 に答える
0

この論文で指定されている両方のバージョンを実装しました。最適化されていないバージョンを再帰的に解決すると、アルゴリズムを理解するのに大いに役立つことがわかりました。バージョン 1 (最適化されていない) の Python 実装は次のとおりです。

def bron(compsub, _not, candidates, graph, cliques):
    if len(candidates) == 0 and len(_not) == 0:
        cliques.append(tuple(compsub))
        return
    if len(candidates) == 0: return
    sel = candidates[0]
    candidates.remove(sel)
    newCandidates = removeDisconnected(candidates, sel, graph)
    newNot = removeDisconnected(_not, sel, graph)
    compsub.append(sel)
    bron(compsub, newNot, newCandidates, graph, cliques)
    compsub.remove(sel)
    _not.append(sel)
    bron(compsub, _not, candidates, graph, cliques)

そして、次の関数を呼び出します。

graph = # 2x2 boolean matrix
cliques = []
bron([], [], graph, cliques)

変数cliquesには、見つかったクリークが含まれます。

これを理解すれば、最適化されたものを実装するのは簡単です。

于 2012-01-28T16:54:02.760 に答える