Union-Find en JavaScript

Problema

Un cliente, tres perfiles

La tienda tiene 200 000 perfiles de cliente. La misma clienta se registró tres veces: una con el teléfono, otra con el correo del trabajo y otra desde la app. Recibe tres boletines, sus puntos de fidelidad están repartidos en tres, y el informe dice que tienes más clientes de los que tienes.

La regla es sencilla: dos perfiles con el mismo correo o el mismo teléfono son un solo cliente. Pero es contagiosa. Si el perfil a comparte un teléfono con b, y b comparte un correo con c, entonces a, b y c son un cliente, aunque a y c no tengan nada en común.

¿Cómo encuentras todos los grupos sin comparar cada perfil con todos los demás?

La idea

La primera idea: una etiqueta de grupo

Cada perfil lleva una etiqueta: el número de su grupo. Al principio cada perfil es su propio grupo. Cuando resulta que dos perfiles están vinculados, todo el grupo del segundo recibe la etiqueta del primero.

class Relabel {
  #label;

  constructor(n) {
    this.#label = Array.from({ length: n }, (_, i) => i);
    this.count = n;
  }

  find(x) {
    return this.#label[x];
  }

  union(a, b) {
    const from = this.#label[b];
    const to = this.#label[a];
    if (from === to) return false;
    for (let i = 0; i < this.#label.length; i++) {
      if (this.#label[i] === from) this.#label[i] = to;
    }
    this.count--;
    return true;
  }
}

El programa recorre los perfiles y recuerda, para cada contacto, qué perfil lo tuvo primero. Cuando vuelve a ver el contacto, fusiona los dos perfiles:

const profiles = [
  ["marta@correo.es", "600 100 200"],
  ["600 100 200", "m.vega@empresa.es"],
  ["pedro@correo.es"],
  ["m.vega@empresa.es"],
  ["611 300 400", "pedro@correo.es"],
  ["nico@correo.es"],
  ["611 300 400"],
  ["nico@correo.es", "622 500 600"],
  ["marta@correo.es", "611 300 400"],
];
const accounts = new Relabel(profiles.length);
const owner = new Map();
profiles.forEach((contacts, p) => {
  for (const contact of contacts) {
    if (owner.has(contact)) accounts.union(owner.get(contact), p);
    else owner.set(contact, p);
  }
});
console.log(`Grupos: ${accounts.count}`);
const main = profiles.map((_, p) => accounts.find(p));
console.log(`Principal: ${main.join(" ")}`);

Grupos: 2
Principal: 2 2 2 2 2 5 2 5 2

Funciona, pero cada fusión recorre todos los perfiles para encontrar cuáles hay que renombrar. Con n perfiles y unas n fusiones son unas n² miradas: decenas de miles de millones para 200 000 perfiles.

La idea

Un bosque de padres

En vez de que cada perfil lleve la etiqueta del grupo, cada perfil apunta a un padre: otro perfil del grupo. El grupo es un árbol, y el perfil que apunta a sí mismo es la raíz: el perfil principal del grupo.

find(x) sube por los padres hasta llegar a una raíz. Dos perfiles están en un grupo si find da la misma raíz para ambos.
union(a, b) encuentra las raíces de los dos y cuelga una debajo de la otra. Toca una celda del arreglo, por grande que sea el grupo.

Por sí solo, el bosque puede convertirse en una cadena larga, y entonces find es lento. Por eso hay dos mejoras, y juntas son Union-Find:

Unión por tamaño. Cada raíz sabe cuántos perfiles tiene su árbol. El árbol más pequeño va debajo del más grande, así la profundidad crece despacio.
Compresión de caminos. Cuando find llega a la raíz, recorre el camino otra vez y cuelga cada perfil de él directamente de la raíz. El siguiente find para ellos es un paso.

Míralo

Una fusión por dentro

class UnionFind {
  #parent;
  #size;

  constructor(n) {
    this.#parent = Array.from({ length: n }, (_, i) => i);
    this.#size = new Array(n).fill(1);
    this.count = n;
  }

  find(x) {
    let root = x;
    while (this.#parent[root] !== root) {
      root = this.#parent[root];
    }
    while (this.#parent[x] !== root) {
      const above = this.#parent[x];
      this.#parent[x] = root;
      x = above;
    }
    return root;
  }

  union(a, b) {
    let ra = this.find(a);
    let rb = this.find(b);
    if (ra === rb) return false;
    if (this.#size[ra] < this.#size[rb]) {
      [ra, rb] = [rb, ra];
    }
    this.#parent[rb] = ra;
    this.#size[ra] += this.#size[rb];
    this.count--;
    return true;
  }
}

union devuelve false si los perfiles ya están en un grupo: entonces no cambia nada y count se queda igual.

El mismo programa que arriba, con UnionFind en vez de Relabel:

const profiles = [
  ["marta@correo.es", "600 100 200"],
  ["600 100 200", "m.vega@empresa.es"],
  ["pedro@correo.es"],
  ["m.vega@empresa.es"],
  ["611 300 400", "pedro@correo.es"],
  ["nico@correo.es"],
  ["611 300 400"],
  ["nico@correo.es", "622 500 600"],
  ["marta@correo.es", "611 300 400"],
];
const accounts = new UnionFind(profiles.length);
const owner = new Map();
profiles.forEach((contacts, p) => {
  for (const contact of contacts) {
    if (owner.has(contact)) accounts.union(owner.get(contact), p);
    else owner.set(contact, p);
  }
});
console.log(`Grupos: ${accounts.count}`);
const main = profiles.map((_, p) => accounts.find(p));
console.log(`Principal: ${main.join(" ")}`);

Grupos: 2
Principal: 0 0 0 0 0 5 0 5 0

class UnionFind {
  #parent;
  #size;

  constructor(n) {
    this.#parent = Array.from({ length: n }, (_, i) => i);
    this.#size = new Array(n).fill(1);
    this.count = n;
  }

  find(x) {
    let root = x;
    while (this.#parent[root] !== root) {
      root = this.#parent[root];
    }
    while (this.#parent[x] !== root) {
      const above = this.#parent[x];
      this.#parent[x] = root;
      x = above;
    }
    return root;
  }

  union(a, b) {
    let ra = this.find(a);
    let rb = this.find(b);
    if (ra === rb) return false;
    if (this.#size[ra] < this.#size[rb]) {
      [ra, rb] = [rb, ra];
    }
    this.#parent[rb] = ra;
    this.#size[ra] += this.#size[rb];
    this.count--;
    return true;
  }
}

Paso a paso, en palabras

Nueve perfiles de cliente, cada uno es su propio grupo: #parent[i] = i, cada perfil es una raíz. Grupos: 9.
El perfil 1 tiene el teléfono de 0: union(0, 1). Las raíces son distintas, así que 1 se cuelga de 0. Luego 3 tiene el correo de 1: find(1) sube hasta 0, y 3 también va debajo de 0.
Igual con los demás: 4 debajo de 2 (correo compartido), 6 debajo de 2 (teléfono compartido), 7 debajo de 5. Una unión cambia una celda del arreglo: el padre de una raíz.
El perfil 8 tiene el correo de 0: 8 va debajo de 0. El grupo de 0 ya tiene cuatro perfiles.
8 también tiene el teléfono de 4. find(4) llega a 2, find(8) llega a 0. El árbol de 2 es más pequeño (3 contra 4), por eso su raíz va debajo de 0: cambia una celda, tres perfiles cambian de grupo.
Al final el programa llama a find para cada perfil. find(4) sube 4 → 2 → 0 y luego cuelga 4 directamente de 0: compresión de caminos. Igual con 6.
Dos grupos, los perfiles principales son 0 y 5. El árbol es plano: el siguiente find(4) es un paso.

Los dos grupos son los mismos que con etiquetas, solo cambian los números: aquí el perfil principal es la raíz, con etiquetas es la etiqueta que sobrevivió.

Pruébalo

Predice la salida

Seis perfiles y seis vínculos. Después de cada unión el programa anota el número de grupos:

const uf = new UnionFind(6);
const links = [[0, 1], [1, 2], [0, 2], [3, 4], [4, 5], [2, 3]];
const counts = [];
for (const [a, b] of links) {
  uf.union(a, b);
  counts.push(uf.count);
}
console.log(`[${counts.join(", ")}]`);

Respuesta

[5, 4, 3, 2, 1, 0]

[1, 1, 1, 1, 1, 1]

[5, 4, 4, 3, 2, 1]

La idea

El find recursivo

La compresión suele escribirse con recursión: find sobre el padre da la raíz, y el perfil se cuelga de ella. Cada perfil del camino hace lo mismo al volver.

find(x) {
  if (this.#parent[x] !== x) {
    this.#parent[x] = this.find(this.#parent[x]);
  }
  return this.#parent[x];
}

Pruébalo tú:

find(x) {
  if (this.#parent[x] !== x) {
    this.#parent[x] = ;
  }
  return this.#parent[x];
}

Con la unión por tamaño los árboles son bajos: como mucho 17 niveles para 200 000 perfiles (log₂ 200 000 ≈ 17,6). Así que la recursión es segura.

Más precisamente, para curiosos

Sin la unión por tamaño un árbol puede convertirse en una cadena de n perfiles, y el find recursivo hace n llamadas anidadas, apiladas una sobre otra, como en la lección «Recursión». JavaScript lanza RangeError: Maximum call stack size exceeded, normalmente después de unas 10 000 llamadas. El bucle de la lección no tiene este problema con ninguna forma de árbol.

La idea

Cuánto cuesta

Ejecuta las tres maneras. Hay n perfiles y n vínculos al azar «estos dos comparten un contacto». Se cuenta:

con etiquetas: cada mirada a la etiqueta de un perfil al renombrar;
con el bosque simple y con Union-Find: cada paso de find, incluida la mirada a la propia raíz.

Reetiquetar todo el grupo O(n²)
Bosque de padres, sin mejoras O(n²)
Union-find: compresión y tamaño O(n)

Algoritmo	n = 10	n = 1000	n = 10.000	n = 100.000
Reetiquetar todo el grupo	90	843.000	≈ 84.300.000	≈ 8.430.000.000
Bosque de padres, sin mejoras	30	25.641	2.102.613	≈ 210.261.300
Union-find: compresión y tamaño	30	3295	33.355	334.195

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

class UnionFind {
  #parent;
  #size;

  constructor(n) {
    this.#parent = Array.from({ length: n }, (_, i) => i);
    this.#size = new Array(n).fill(1);
    this.count = n;
  }

  find(x) {
    let root = x;
    while (this.#parent[root] !== root) {
      root = this.#parent[root];
    }
    while (this.#parent[x] !== root) {
      const above = this.#parent[x];
      this.#parent[x] = root;
      x = above;
    }
    return root;
  }

  union(a, b) {
    let ra = this.find(a);
    let rb = this.find(b);
    if (ra === rb) return false;
    if (this.#size[ra] < this.#size[rb]) {
      [ra, rb] = [rb, ra];
    }
    this.#parent[rb] = ra;
    this.#size[ra] += this.#size[rb];
    this.count--;
    return true;
  }
}

Con 1000 perfiles las etiquetas necesitan 843 000 miradas, el bosque simple 25 641 pasos y Union-Find 3295. Con 10 000 el bosque simple ya necesita 2 102 613 pasos: sus árboles se vuelven cadenas largas. Union-Find necesita 33 355, unos 3,3 pasos por vínculo, y con 100 000 perfiles 334 195: lo mismo por vínculo.

Es un coste amortizado (mira la complejidad amortizada): un find puede ser largo, pero después el camino queda plano y los siguientes son cortos. En conjunto cada operación cuesta casi O(1).

Más precisamente, para curiosos

Con más precisión: con unión por tamaño (o por rango, mira abajo) y compresión de caminos, m operaciones sobre n elementos cuestan O(m · α(n)). α es la inversa de la función de Ackermann. Crece tan despacio que para cualquier n que quepa en el universo vale 4 como mucho. Por eso en la práctica se dice «casi constante». La demostración es de Tarjan (1975) y no es corta.

En vez del tamaño puedes llevar un rango: una cota superior de la altura del árbol. La raíz con el rango menor va debajo de la otra, y un rango solo crece cuando los rangos son iguales. El coste es el mismo. El tamaño es más cómodo porque también responde a «cuántos perfiles hay en el grupo».

Pruébalo

Encuentra el error

Un compañero escribió la unión. El número de grupos sale 2, pero hay tres perfiles principales distintos:

union(a, b) {
  let ra = this.find(a);
  let rb = this.find(b);
  if (ra === rb) return false;
  if (this.#size[ra] < this.#size[rb]) {
    [ra, rb] = [rb, ra];
  }
  this.#parent[b] = ra;
  this.#size[ra] += this.#size[rb];
  this.count--;
  return true;
}

const profiles = [
  ["marta@correo.es", "600 100 200"],
  ["600 100 200", "m.vega@empresa.es"],
  ["pedro@correo.es"],
  ["m.vega@empresa.es"],
  ["611 300 400", "pedro@correo.es"],
  ["nico@correo.es"],
  ["611 300 400"],
  ["nico@correo.es", "622 500 600"],
  ["marta@correo.es", "611 300 400"],
];
const accounts = new UnionFind(profiles.length);
const owner = new Map();
profiles.forEach((contacts, p) => {
  for (const contact of contacts) {
    if (owner.has(contact)) accounts.union(owner.get(contact), p);
    else owner.set(contact, p);
  }
});
console.log(`Grupos: ${accounts.count}`);
const main = profiles.map((_, p) => accounts.find(p));
console.log(`Principal: ${main.join(" ")}`);

Grupos: 2
Principal: 0 0 2 0 2 5 2 5 0

¿En qué línea está el error?

Elige la línea con el error.

La idea

Dónde más

Union-Find responde a una pregunta: ¿están estos dos en un grupo?, cuando los grupos solo crecen. Lo mismo vale para:

zonas de reparto: almacenes y calles entre ellos. Dos almacenes están en una zona si hay una ruta, quizá pasando por otros almacenes;
una red de computadoras: qué máquinas se alcanzan entre sí después de cada cable nuevo;
el algoritmo de Kruskal para la red de calles más barata, que verás en el módulo Grafos (algo-graphs). Allí Union-Find dice si una calle nueva cierra un ciclo.

Un límite: Union-Find no separa. Si un teléfono compartido resulta ser de oficina y ha fusionado a dos clientes distintos, la unión no se puede deshacer. Por eso los vínculos se guardan aparte, y los grupos se reconstruyen cuando se quita un vínculo. Por eso también un teléfono que aparece en cientos de perfiles normalmente no se usa para fusionar.

Ejercicio

Zonas de reparto

Resuélvelo en tu editor.

Zonas. Hay 10 almacenes (0 … 9) y calles entre ellos: 0-1, 1-2, 3-4, 5-6, 6-7, 7-5, 8-9. Añade dos métodos a la clase: connected(a, b), que dice si dos almacenes están en una zona, y sizeOf(x), que devuelve cuántos almacenes hay en la zona de x. Imprime el número de zonas, si 0 y 2 y si 2 y 3 están en una zona, y cuántos almacenes hay en la zona de 5. Luego abre una calle nueva 2-3 e imprime otra vez el número de zonas y si 0 y 4 están en una zona:

Zonas: 4
0 y 2: sí
2 y 3: no
Zona de 5: 3 almacenes
Nueva calle 2-3. Zonas: 3
0 y 4: sí

Más tareas

Grupos por nombre. Imprime cada grupo de perfiles como una lista: el perfil principal y todos los perfiles debajo de él.
El grupo más grande. Lleva el tamaño del grupo más grande mientras fusionas, sin recorrer todas las raíces al final.
Unión por rango. Cambia el tamaño por el rango y compara el número de pasos de find con los de Bench.

Test

Ponte a prueba

1. Los perfiles a y b comparten un correo, b y c comparten un teléfono, y d no comparte nada con nadie. ¿Cuántos clientes son?3: a y c no comparten ningún contacto4: cada perfil es distinto2: a, b y c son un cliente, d es otro

2. ¿Qué hace union cuando los dos perfiles ya están en un grupo?Nada: find da la misma raíz y el número de grupos se queda igualBaja el número de grupos en unoCuelga la raíz de sí misma

3. ¿Por qué la raíz del árbol más pequeño va debajo de la raíz del más grande y no al revés?Da igual, solo queda más bonitoPara que el perfil más antiguo siga siendo el principalPara que la profundidad solo crezca cuando los tamaños son iguales y nunca pase de log₂ n

4. Dos perfiles se fusionaron por un teléfono compartido, y resulta que es un teléfono de oficina. ¿Cómo los separas?Vuelves a construir los grupos a partir de los vínculos, sin el equivocadoQuitas el móvil del arreglo de padresCon una unión inversa

Union-Find

Cookies