Реализации алгоритмов/Алгоритм Брона — Кербоша

Алгоритм Брона — Кербоша — метод ветвей и границ для поиска всех клик (а также максимальных по включению независимых множеств вершин) неориентированного графа.

Вариации

Нахождение максимальных (по включению) независимых множеств вершин

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

Поэтому алгоритм Брона — Кербоша можно использовать для нахождения максимальных по включению независимых множеств вершин, если построить дополнение к исходному графу, либо изменив условие в основном цикле (условие остановки) и формирование новых множеств new_candidates и new_not:

1. Условие в основном цикле: not не должно содержать ни одной вершины, НЕ СОЕДИНЕННОЙ НИ С ОДНОЙ из вершин во множестве candidates
2. Для формирования new_candidates и new_not, необходимо удалять из candidates и not вершины, СОЕДИНЕННЫЕ с выбранной вершиной.

Реализация данной вариации алгоритма на языке Python:

def bron_kerbosch_max_by_inclusion(m):

    results = []

    def check(candidates, wrong):
        for i in wrong:
            q = True
            for j in candidates:
                if m[i][j]:
                    q = False
                    break
            if q: return False
        return True

    def extend(compsub, candidates, wrong):

        while candidates and check(candidates, wrong):

            v = candidates[0]
            compsub.append(v)

            new_candidates = [ i for i in candidates if not m[i][v] and i != v ]
            new_wrong = [ i for i in wrong if not m[i][v] and i != v ]

            if not new_candidates and not new_wrong:
                results.append(list(compsub))
            else:
                extend(compsub, new_candidates, new_wrong)

            candidates.remove(v)
            compsub.remove(v)
            wrong.append(v)

    extend([], list(range(len(m))), [])

    return results

Нахождение максимальной клики / независимого множества максимального размера (МНМ)

Для того, чтобы алгоритм искал максимальную по размеру клику/МНМ, необходимо:

1. завести еще одно множество max_comsub (начальное значение — пустое множество)
2. на шаге 4, когда найдена очередная клика/МНМ, сравнить размер (количество вершин) в comsub и в max_comsub и поместить в max_comsub множество с большим числом вершин.

Реализация на C++ с использованием стека.

 list<set<int> >kerbosh(int **&a,int SIZE)
 {
    set <int> M,G,K,P;
    list<set<int> > REZULT;
    for (int i=0; i<SIZE;i++)
    {
        K.insert(i);
    }
    int v,Count=0,cnt=0;
    int Stack1[100];
    std::set<int> Stack2[100];
    std::set<int>::iterator theIterator;
    theIterator=K.begin();
    while ((K.size()!=0)||(M.size()!=0))
    {
        if (K.size()!=0)
        {
            theIterator=K.begin();
            v=*theIterator;
            Stack2[++Count]=M;
            Stack2[++Count]=K;
            Stack2[++Count]=P;
            Stack1[++cnt]=v;
            M.insert(v);
            for (int i=0;i<SIZE;i++)
            {
                if (a[v][i])
                {
                    theIterator=K.find(i);
                    if (theIterator!=K.end())
                    {
                        K.erase(theIterator);
                    }
                    theIterator=P.find(i);
                    if (theIterator!=P.end())
                    {
                        P.erase(theIterator);
                    }
                }
            }
            theIterator=K.find(v);
            if (theIterator!=K.end())
            {
                K.erase(theIterator);
            }
        }
        else
        {
            if (P.size()==0)
            {
                REZULT.push_back(M);
            }
            v=Stack1[cnt--];
            P=Stack2[Count--];
            K=Stack2[Count--];
            M=Stack2[Count--];
            theIterator=K.find(v);
            if (theIterator!=K.end())
            {
                K.erase(theIterator);
            }
            P.insert(v);
        }
    }
    return  REZULT;
 }

Ссылки

• Реализация алгоритма Брона-Кербоша на Java
• Реализация алгоритма Брона-Кербоша на Python