Нахождение максимальных кликов и удаление узлов?

Question

Я пытаюсь найти максимальный клик для набора предметов.

В настоящее время я использую библиотеку networkx из python и функцию find_cliques(), чтобы найти все максимальные клики, как показано ниже:

import newtworkx as nx

G = nx.Graph()
E = [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [2,6], [2,5], [5,6]]

G.add_edges_from(E)
#G.edges()

lst = list(nx.find_cliques(G))
lst

Out [] : [[2, 1, 3, 4], [2, 5, 6]]

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

В приведенном выше примере я ожидаю получить [2, 1, 3, 4] и затем удалить эти узлы, так что останутся только 5 и 6, что будет другой кликой [5, 6] .

Обновить

Мы можем использовать G.remove_node (), он удаляет узел, а также все соседние ребра, как и ожидалось.

G = nx.Graph()
E = [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [2,6], [2,5], [5,6], [3,5], [5,7]]
G.add_edges_from(E)

list1 = list(nx.find_cliques(G))
#list1   gives [[2, 3, 1, 4], [2, 3, 5], [2, 6, 5], [7, 5]]

n = nx.number_of_nodes(G)
#n

[G.remove_node(nd) for nd in list1[0]]
list2 = list(nx.find_cliques(G))
#list2    gives [[5, 6], [5, 7]]

[G.remove_node(nd) for nd in list2[0]]
list3 = list(nx.find_cliques(G))
#list3    gives [[7]]

Но каждый раз, когда узлы удаляются, новые максимальные клики обнаруживаются и сохраняются в новом списке и так далее. Как его можно запустить в цикле while, пока в графе G не останется ребра, т. Е. Число узлов равно 0 или 1.

Answer 1

Ты можешь использовать G.remove_node удалить узлы (и связанные ребра) из вашего графика.

Как удалить все узлы первого клика:

lst = list(nx.find_cliques(G))
[G.remove_node(nd) for nd in lst[0]]

Чтобы повторно удалить узлы первой клики, пока не останется клик:

lst = list(nx.find_cliques(G))
while len(lst) > 0:
    [G.remove_node(nd) for nd in lst[0]]
    lst = list(nx.find_cliques(G))

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

lst = list(nx.find_cliques(G))
while len(lst) > 0:

    # This flattens the list of cliques into one list. `set` reduces to unique values.
    flattened = set([nd for cl in lst for nd in cl])

    [G.remove_node(nd) for nd in flattened]
    lst = list(nx.find_cliques(G))

Наконец, если есть определенный порядок, в котором вы хотите удалить клики (например, сначала максимальный клик), вы можете сделать это, отсортировав lst соответственно:

lst = list(nx.find_cliques(G))
while len(lst) > 0:
    lst.sort(key=len, reverse=True)       # Sort maximum clique to the front
    [G.remove_node(nd) for nd in lst[0]]
    lst = list(nx.find_cliques(G))

Редактировать: для полноты, вот как можно сохранить клики перед их удалением (согласно вашему комментарию, @Ankie):

out = []
lst = list(nx.find_cliques(G))
while len(lst) > 0:
    out.append(lst[0])
    [G.remove_node(nd) for nd in lst[0]]
    lst = list(nx.find_cliques(G))

В качестве дополнительного примечания следует отметить, что эти операции в основном "разрушают" граф G, Если график понадобится позже и его создание займет много времени, имеет смысл поработать с копией графика, чтобы сохранить оригинал. Копия может быть сделана так:

G2 = G.copy()