Clique 찾기를위한 Bron-Kerbosch 알고리즘

StackOverflow https://stackoverflow.com/questions/143140

  •  02-07-2019
  •  | 
  •  

문제

누구든지 웹에서 Bron-Kerbosch 알고리즘에 대한 설명을 찾거나 여기서 어떻게 작동하는지 설명 할 수 있습니까?

나는 그것이 "Algorithm 457 : 방향없는 그래프의 모든 클릭 찾기"책에 게시되었다는 것을 알고 있지만 알고리즘을 설명 할 무료 소스를 찾을 수는 없습니다.

알고리즘에 대한 소스 코드가 필요하지 않으므로 작동 방식에 대한 설명이 필요합니다.

도움이 되었습니까?

해결책

ACM 학생 계정이있는 사람을 찾아서 여기에 있습니다. http://portal.acm.org/citation.cfm?doid=362342.362367

방금 다운로드했는데 Algol 60에서 구현하면서 단지 2 페이지에 불과합니다!

다른 팁

여기에서 알고리즘에 대한 설명이 있습니다. http://www.dfki.de/~neumann/ie-seminar/presentations/finding_cliques.pdf좋은 설명이지만 ... C# -.-의 라이브러리 나 구현이 필요합니다.

알고리즘이 맞습니다 여기 Java LinkedLists를 세트 R, P, X로 사용하여 다시 작성했으며 매력처럼 작동합니다 (O 좋은 것은 알고리즘에 따라 설정 작업을 수행 할 때 "retainall"함수를 사용하는 것입니다).

알고리즘을 다시 작성할 때 최적화 문제로 인해 구현에 대해 조금 생각하는 것이 좋습니다.

나는 또한 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)

가치가있는 것에 대해 Java 구현을 찾았습니다. http://joelib.cvs.sourceforge.net/joelib/joelib2/src/joelib2/algo/clique/bronkerbosch.java?view=markup

HTH.

논문에 지정된 두 버전을 구현했습니다. 나는 최적화되지 않은 버전이 해결되면 재귀 적으로 알고리즘을 이해하는 데 많은 도움이된다는 것을 배웠다. 다음은 버전 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 발견 된 파벌이 포함되어 있습니다.

이것을 이해하면 최적화 된 것을 쉽게 구현할 수 있습니다.

Boost :: Graph는 Bron-Kerbosh 알고리즘의 우수한 구현을 가지고 있으며 확인하십시오.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top