Алгоритм Брона-Кербоша для поиска клики
-
02-07-2019 - |
Вопрос
Кто-нибудь может сказать мне, где в Интернете я могу найти объяснение алгоритма Брона-Кербоша для поиска кликов или объяснить здесь, как это работает?
Я знаю, что это было опубликовано в "Алгоритме 457:поиск всех кликов неориентированного графа", но я не могу найти бесплатный источник, который будет описывать алгоритм.
Мне не нужен исходный код алгоритма, мне нужно объяснение того, как он работает.
Решение
Попробуйте найти кого-нибудь с учетной записью ACM student, кто может предоставить вам копию статьи, которая находится здесь: http://portal.acm.org/citation.cfm?doid=362342.362367
Я только что скачал его, и он занимает всего две страницы, с реализацией на Algol 60!
Другие советы
я нахожу объяснение алгоритма здесь: http://www.dfki.de /~neumann/ie-семинар/презентации/finding_cliques.pdf это хорошее объяснение...но мне нужна библиотека или реализация на C # -.-'
Есть правильный алгоритм здесь Я переписал его, используя Java linkedlists в качестве наборов R, P, X, и это работает как шарм (o хорошая вещь - использовать функцию "retainAll" при выполнении операций с набором в соответствии с алгоритмом).
Я предлагаю вам немного подумать о реализации из-за проблем с оптимизацией при переписывании алгоритма
Я также пытался разобраться в алгоритме Брона-Кербоша, поэтому написал свою собственную реализацию на 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
ХТХ.
Я реализовал обе версии, указанные в документе.Я узнал, что неоптимизированная версия, если ее решать рекурсивно, очень помогает понять алгоритм.Вот реализация python для версии 1 (неоптимизированная):
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 имеет отличную реализацию алгоритма Брона-Кербоша, проверьте это.