Почему не работает алгоритм Брона-Кербоша?

Question

[lemonlimelike]

Разрабатываю алгоритм нахождения внутреннего устойчевого подмножества. Использую алгоритм Брона-Кербоша из Википедии

Почему-то для графа, который представлен в коде [[1,2],[1,4],[1,3],[2,4],[3,4],[4,5]], алгоритм возвращает такие множества [5], [1,4], [1,4], что естественно не правильно. Но вроде все по инструкции делаю

Изменил функцию check. Она работала не правильно. Теперь она возвращает смежные вершины с вершиной item. Она использует сам граф, который представлен в алгебраическом виде.

Но результат самого алгоритма все равно неверный

def check(item):
  temp = []
  for i in range(6):
    if item in graf[i]:
      if graf[i][0] not in temp:
        temp.append(graf[i][0])
      if graf[i][1] not in temp:
        temp.append(graf[i][1])

  return temp

def alg(s,add,exists):
    for item in add:
        s.append(item) # добавляем вершину item из множества add 
        new_add = [v for v in add if v not in check(item)] # формируем новое множество вершин удаляя из него всех соседей вершины item (функция check вовзращает всех соседей вершины item)
        new_exists = [v for v in exists if v not in check(item)] # тут тоже самое как для new_add
        if len(new_add) == 0 and len(new_exists) == 0:
            print(s)
            return s
        else:
            alg(s,new_add,new_exists)
        s.remove(item)
        add.remove(item)
        exists.append(item)

if __name__ == '__main__':
    graf = [[1,2],[1,4],[1,3],[2,4],[3,4],[4,5]]

    count_vershin = 5
    count_reber = 6

    # создание вложенного списка - двумерный массив
    matrix = [[0] * count_vershin for i in range(count_vershin)]

    # создание матрицы смежности
    for i in range(count_reber):
        k = graf[i-1][0]
        j = graf[i-1][1]
        # print(k,j)
        matrix[k-1][j-1] = 1
        matrix[j-1][k-1] = 1

    # вывод матрицы смежности
    for i in range(count_vershin):
        for j in range(count_vershin):
            print(matrix[i][j], end=' ')
        print()

    s = [] # множество, содержащее на каждом шаге рекурсии независимое множество для данного шага. Строится рекурсивно.
    add = [] # множество вершин, которые могут увеличить 
    exists = [] #  множество вершин, которые уже использовались для расширения  на предыдущих шагах алгоритма.

    for item in graf:
        if item[0] not in add:
            add.append(item[0])

        if item[1] not in add:
            add.append(item[1])


    print(add) # по сути тут у нас список исходных вершин
    print(alg(s, add, exists))

Comments

[Алан Гибизов]

Я бы советовал откомментировать код более подробно. Мало кто захочет разбираться во всех этих i, j, k, s и count_vershin.

[lemonlimelike]

Алан Гибизов, Добавил комментарии

[Ищю в поисковиках]

VicTHOR, или на использование стека, что будет куда ближе

[o5a]

lemonlimelike, насколько я понял алгоритм, вижу 2 ошибки
1. check должна возвращать соседние вершины, а по факту возвращает соседей и саму вершину
2. в new_add, new_exists должно быть пересечение множеств, а у вас наоборот - not in check(item)

[Алан Гибизов]

lemonlimelike, в общем, я порылся, посмотрел - и мне кажется, что ваш алгоритм несколько не соответствует тому, что в Википедии. Или я не так понял его...

В частности:

ПОКА candidates НЕ пусто И not НЕ содержит вершины, СОЕДИНЕННОЙ СО ВСЕМИ вершинами из candidates,
ВЫПОЛНЯТЬ:
1 Выбираем вершину v из candidates и добавляем её в compsub

Т.е. должно быть что-то вроде:

def v_not_in_not(_not, candidates):
     """проверка условия '_not НЕ содержит вершины, СОЕДИНЕННОЙ СО ВСЕМИ вершинами из candidates'"""
    return True or False

while (len(candidates) > 0) and (v_not_in_not(_not, candidates)):
    alg(compsub, candidates, _not)

Конечно, сбивает с толку, что у вас наименования переменных не соответствуют таковым в алгоритме в Википедии...

Answer 1

[Wataru]

У вас две большие ошибки с языком питон. Вы в цикле в alg итерируетесь по списку add, меняя его. Так делать нельзя. Ломаются итераторы и вы пропускаете половину элементов.

Вместо этого используйте цикл while:

while add:
  item = add[0]
  add.remove(item)
  s.append(item)
...

Вторая большая ошибка, в питоне списки передаются по ссылке! Поэтому s, который у вас параметр рекурсивной функции, на каждом уровне один и тот же список. Но при выводе множества вы сразу же возвращаетесь из функции, не удаляя item из s. Вам надо чтобы все изменения в s были отменены по выходу их функции. Перед return делайте s.remove(item).

С этими двумя изменениями должно работать. Ну, и у вас главная оптимизация алгоритма не реализована. Надо в начале цикла проверить, что среди оставшихся вершин в add есть хоть одна соединенная с каждой вершиной из exists. Если таковых нет - нужно вывалится из цикла.

Еще по коду:
range(n) в python возвращает 0..5. У вас там цикл по ребрам в __main__ и там идет обращение к i-1 в массиве graf. Т.е. обращение к [-1]. Вряд ли вы это хотели. Работает по чистой случайности, потому что в питоне a[-1] дает последний элемент.

И вообще, вы матрицу смежности строите, но нигде не используете.

Вместо функции check(), вы сделайте нормальный список смежности один раз, а то просто глаз режет от неоптимальности.

neighbors = [[] for i in range(count_vershin)]
for edge in graf:
  neighbors[edge[0]-1].append(edge[1]-1)
  neighbors[edge[1]-1].append(edge[0]-1)

Comments

[lemonlimelike]

Да, цикл while как раз подходит. Я чет не подумал об этом.

А вот тут

Вторая большая ошибка, в питоне списки передаются по ссылке! Поэтому s, который у вас параметр рекурсивной функции, на каждом уровне один и тот же список. Но при выводе множества вы сразу же возвращаетесь из функции, не удаляя item из s. Вам надо чтобы все изменения в s были отменены по выходу их функции. Перед return делайте s.remove(item).

я так и не понял
s.remove(item) я попробовал поставить перед print(s) то вывелось что-то не понятное.

[Wataru]

lemonlimelike, После вывода удаляйте же. Но то return.