Gráficos y rutas: algoritmo de Bron-Kerbosch, grupos máximos

Por qué es necesario?

Sally va a dar una fiesta. Invitó a Max, Sue, Tom y Jake. Entonces Tom llamó a Ryan, que vino con Jess, y Jess llamó a Lou, que conoce a los amigos de Tom. Jake es muy extrovertido, por lo que también conoce a Jess y Ryan. Y luego vino Joe. Joe conoce a Lou pero no a Sally, y en realidad ya no conoce a ninguno de los invitados, pero aún así, en  teoría,  también es un invitado. Vinieron otros tres invitados al azar, Liz, T y Jay, porque la fiesta promete ser ruidosa. Finalmente, Erin, que llega muy elegantemente tarde como de costumbre, llega con Amy y Jack.

Nuestra tarea es encontrar todos los grupos máximos de personas en los que todos se conocen.

Apliquemos el algoritmo básico de Bron-Kerbosch a este sistema de relaciones sociales, o en otras palabras, resolvamos este problema aplicando  el método de retroceso recursivo a la fiesta en O(3^n/3). Los problemas NP-completos se resuelven rápidamente, pero son difíciles. Por lo tanto, resolvemos nuestro problema usando subgrafos.

Mira las tapas de "Jack", "Amy", "Erin" y "Sally".

Aquí vemos dos grupos máximos: (1) Amy, Jack y Erin. (2) Sally y Erín.

Nuestro cerebro tiene un gran potencial y es capaz de reconocer rápidamente estos grupos. Las computadoras también tienen un alto potencial y pueden reconocer estos grupos si los parámetros se configuran correctamente.

¿Qué parámetros le debemos poner al ordenador para que empiece a ver lo que nosotros vemos?

Comencemos eligiendo un vértice. Digamos que es Jack.

Ahora necesitamos ejecutar una llamada recursiva al "Jack" superior y considerar  solo a  sus vecinos.

A continuación, seleccione cualquiera de los vértices adyacentes a Jack.

Tomemos la parte superior de "Amy".

En el siguiente nivel, debe elegir un vértice que pertenezca tanto al conjunto de vértices vecinos de Jack como al conjunto de vértices vecinos de Amy.

Esta es Erín.

Para indicar que la ubicación "pertenece  tanto al conjunto de vértices vecinos del vértice "Jack"  como  al conjunto de vértices vecinos del vértice "Amy", existe el término " intersección ".

En la tercera etapa, al nivel del vértice "Erin", no hay vértices vecinos que se crucen.

Tenga en cuenta que Sally no está incluida en este grupo, ya que Sally no conoce a Jack y Amy.

El escenario principal puede considerarse correcto. Grupo encontrado.

Ahora pasemos a  los métodos de retroceso  y exclusión.

Subamos un nivel.

Encontramos el grupo máximo en el conjunto con vértices "Jack" y "Amy", quizás en el conjunto con vértices "Jack" y "Erin".

Elegimos a otro vecino de Jack: Erin. Elimina a Amy y sigue un nuevo camino.

Hacemos dos llamadas recursivas, verificamos si hay vértices vecinos que se cruzan con los vértices "Erin" y "Jack".

En este caso, es Amy, pero el vértice "Amy" está en la intersección excluida  .

El escenario principal se considera incorrecto esta vez, ya que es imposible formar un grupo con un vértice vecino excluido.

Subamos un nivel.

Todos los vecinos de Jack fueron examinados. Nos elevamos de nuevo al más alto nivel.

En el nivel superior,  excluya a  Jack y elija cualquier otro vértice.

Escojamos a Amy esta vez.

Bajemos un nivel y miremos a los vecinos de Amy (que no fueron excluidos).

Amy conoce a Erin.

Bajemos un nivel más y verifiquemos si Amy y Erin tienen vecinos en común.

El único vértice de este tipo en el conjunto es el vértice "Jack", que está excluido, por lo que tampoco hay grupos máximos aquí.

Comenzamos la búsqueda con un regreso  al nivel superior.

Amy sigue a Jack (y alcanza el conjunto de vértices excluidos) y comenzamos la búsqueda desde otro vértice arbitrario.

Tomemos la cumbre de Erin.

Considere a los vecinos no excluidos de Erin: esta es Sally.

Se selecciona el vértice, la recursividad baja un nivel, la búsqueda continúa.

Evaluamos el escenario principal.

(1) ¿Hay vértices adicionales que intersecan con conjuntos vecinos? No.

(2) ¿Hay vértices que se encuentran entre las intersecciones excluidas con conjuntos vecinos? No.

Tenga en cuenta que el vértice "Sally" está conectado a "Erin" y no a Jack o Amy, y es por esta razón que los vértices excluidos "Jack" y "Amy" no están incluidos en este  conjunto de intersección .

Encontramos un grupo.

Y ahora comenzamos  la búsqueda con retroceso .

A Erin no le quedan más picos con los que formar un grupo, por lo que sigue a Jack y Amy (y termina en muchas eliminaciones).

Sally se queda solo con una conexión con Erin, y Erin ya está expulsada.

Excluyendo a Sally también.

Nadie  más a quien excluir .  El algoritmo se ha completado.

Cómo funciona

El algoritmo de Bron-Kerbosch funciona en tres conjuntos: R, P y X.

El algoritmo de Bron-Kerbosch ejecuta las siguientes operaciones en los conjuntos P, R y X:

Pseudocódigo:

Descripción más detallada de los conjuntos:

Traduzcamos el pseudocódigo a C++:

void bronKerbosch(set<node*> R, set<node*> P, set<node*> X) {
  if(P.empty() && X.empty()) {
    cout<<"Clique found: ";
    set_print(R);
  }
  set<node*>::iterator v = P.begin();
  while(!P.empty()  && v!=P.end()){
    set<node*> singleton = { (*v) };
    bronKerbosch(
      set_union(R,singleton), 
      set_intersection(P,(*v)->friends),
      set_intersection(X,(*v)->friends));
    P = set_difference(P,singleton);
    X = set_union(X,singleton);
    if(!P.empty())
      v = P.begin();
  }
}

1. Copie el código a un editor de texto y guárdelo como main.cpp

2. Compile en la línea de comando g++ main.cpp -std=c++11 -o Bronker.exe

3. Luego ejecute el código desde el comando línea ./Bronker.exe .

Después de compilar y ejecutar el código fuente, ¿el programa "hace una fiesta"? y proporcionará una lista de todos los grupos máximos.

Fuente:

https://elsolitario.org/post/algoritmo-de-bron-kerbosch/