Клик в питоне

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 занимает два узла).