Клик в питоне

Question

У меня есть эта проблема, и мне нужна помощь, это мой код:

      cliques=[clique for clique in nx.find_cliques(GC) if len(clique)>2]    

      for clique in cliques:
        if len (clique)==3:
        GC.remove_edge()
        print "Clique to appear: ",clique
      #draw the graph        
      nx.draw(GC)
      plt.show()

сначала я искал в своем графе, чтобы найти клики, после этого я проверял, есть ли клика длиной 3, если это правда, я хочу удалить одно ребро, поэтому я могу исключить complete-graph(3). Как я могу это сделать?

Спасибо

Answer 1

Я думаю, что самая сложная проблема здесь связана с общими краями. Вы не хотите искать клики каждый раз, когда удаляете ребро, и все же вам нужно помнить, какие ребра вы уже удалили.

Глядя на документацию, мы обнаруживаем, что find_cliques Функция является генератором.

Эта реализация является генератором списков, каждый из которых содержит членов максимальной клики

Означает ли это, что вы можете сгенерировать клику, удалить ребро, а затем сгенерировать следующую клику, и наш генератор будет знать, что мы удалили ребро?

Отвечая на этот вопрос другим вопросом: почему бы просто не выходить из генератора каждый раз, когда вы ломаете клику?

edge_removed = True
while edge_removed:
    edge_removed = False
    for clique in nx.find_cliques(GC):
        if len (clique)>=3:
            GC.remove_edge(clique[0], clique[1])
            edge_removed = True
            break # Gotta restart the generator now...

Вы должны иметь в виду, что ВСЕ, что вы делаете с кликами, потенциально может быть очень трудоемким, поскольку даже простое обнаружение клики в графе является NP-полным.

Answer 2

if len(clique)==3:
    GC.remove_edge(*clique[0:2])

или эквивалент)

if len(clique)==3:
    GC.remove_edge(clique[0], clique[1])

но я могу упустить что-то важное, потому что это кажется очевидным, и я не эксперт - я просто читаю документы networkx (которые говорят, что клика - это список узлов, и это remove_edge занимает два узла).