Клики в питоне

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

      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, если это правда, я хочу удалить одно ребро, поэтому я могу удалить полный граф (3). Как я могу это сделать?

Спасибо


python networkx graph-theory clique
person Python    schedule 15.03.2012    source источник
comment
В вашем примере нет допустимого отступа. Пожалуйста, убедитесь, что вы публикуете примеры с допустимым отступом при публикации кода Python.   -  person Eduardo Ivanec    schedule 15.03.2012
comment
Все клики с size >= 3 будут содержать complete_graph(3). Вам все равно на остальное?   -  person Avaris    schedule 15.03.2012
comment
Итак, как я могу написать код для поиска всех K3 и исключить их, удалив одно ребро из всех k3 на графе?   -  person Python    schedule 15.03.2012
comment
Нет, я работал над проектом и это его малая часть.   -  person Python    schedule 15.03.2012

Ответы (2)


arrow_upward
4
arrow_downward

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

Глядя на документацию, мы обнаруживаем, что функция 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-полным.

person machine yearning    schedule 15.03.2012
comment
Глядя на исходный код, если я не ошибаюсь , генератор работает со статическими значениями. Он не узнает, что вы изменили график. Но клики, возвращаемые find_cliques, могут иметь общие ребра. - person Avaris; 15.03.2012
comment
Добро пожаловать, не стесняйтесь принять ответ, если он решит вашу проблему. :) - person machine yearning; 15.03.2012
comment
@machineyearning Не могли бы вы проверить этот вопрос stackoverflow.com/questions/45766241/ - person Liza; 19.08.2017

arrow_upward
0
arrow_downward 

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

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

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

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

person andrew cooke    schedule 15.03.2012
comment
Вот что я получил: Traceback (последний последний вызов): Файл C:Graph1.py, строка 119, в ‹module› GC.remove_edge(clique[0], clique[1]) Файл C:\Python27\lib\ site-packages\networkx-1.6-py2.7.egg\networkx\classes\graph.py, строка 859, в remove_edge поднять NetworkXError(Ребро %s-%s не находится на графике%(u,v)) NetworkXError : Ребро 2-11 отсутствует в графе - person Python; 15.03.2012