Как мне перечислить все * максимальные * клики в графе, используя networkx + python? - PullRequest
Новая
       16

Как мне перечислить все * максимальные * клики в графе, используя networkx + python?

0 голосов
/ 14 февраля 2019

Если вы посмотрите на https://en.wikipedia.org/wiki/Clique_problem,, вы заметите, что есть различие между кликами и максимальными кликами.Максимальная клика содержится не в другой клике, кроме самой себя.Так что я хочу эти клики, но networkx, кажется, предоставляет только:

networkx.algorithms.clique.enumerate_all_cliques(G)

Поэтому я попробовал простой механизм фильтрации петель (см. Ниже). 

def filter_cliques(self, cliques):
    # TODO: why do we need this?  Post in forum...
    res = []
    for C in cliques:
        C = set(C)
        for D in res:
            if C.issuperset(D) and len(C) != len(D):
                res.remove(D)
                res.append(C)
                break
            elif D.issuperset(C):
                break
        else:
            res.append(C)
    res1 = []
    for C in res:
        for D in res1:
            if C.issuperset(D) and len(C) != len(D):
                res1.remove(D)
                res1.append(C)
            elif D.issuperset(C):
                break
        else:
            res1.append(C)     
    return res1

Я хочу отфильтровать все нужные субклики.Но, как вы можете видеть, это отстой, потому что мне пришлось фильтровать его дважды.Это не очень элегантно.Итак, проблема в том, что, учитывая список списков объектов (целых чисел, строк), которые были метками узлов в графе;enumerate_all_cliques(G) возвращает именно этот список списков меток.Теперь, учитывая этот список списков, отфильтруйте все правильные подклики.Так, например:

[[a, b, c], [a, b], [b, c, d]] => [[a, b, c], [b, c, d]]

Какой самый быстрый питонский способ сделать это?

1 Ответ

0 голосов
/ 14 февраля 2019

Для этого есть функция: networkx.algorithms.clique.find_cliques, и да, она возвращает только максимальные клики, несмотря на отсутствие «максимального» в названии.Он должен работать намного быстрее, чем любой подход к фильтрации.

Если вы считаете, что имя сбивает с толку (я так понимаю), вы можете переименовать его: 

from networkx.algorithms.clique import find_cliques as maximal_cliques
...