algorithm - grafo - ¿Algoritmo para encontrar el ancestro común más bajo en el gráfico acíclico dirigido?

grafico aciclico directo

Question

Imagine un gráfico acíclico dirigido de la siguiente manera, donde:

• "A" es la raíz (siempre hay exactamente una raíz)
• cada nodo conoce su padre (s)
• los nombres de los nodos son arbitrarios, no se puede inferir nada de ellos
• sabemos por otra fuente que los nodos se agregaron al árbol en el orden de A a G (p. ej., se confirman en un sistema de control de versiones)

¿Qué algoritmo podría usar para determinar el antecesor común más bajo (LCA) de dos nodos arbitrarios, por ejemplo, el ancestro común de:

• B y E son B
• D y F es B

Nota:

• No hay necesariamente una sola ruta a un nodo dado desde la raíz (por ejemplo, "G" tiene dos rutas), por lo que no puede simplemente recorrer rutas desde la raíz a los dos nodos y buscar el último elemento igual
• He encontrado algoritmos LCA para árboles, especialmente árboles binarios, pero no se aplican aquí porque un nodo puede tener múltiples padres (es decir, este no es un árbol)

Answer 1

Estaba buscando una solución para el mismo problema y encontré una solución en el siguiente documento:

http://dx.doi.org/10.1016/j.ipl.2010.02.014

En resumen, no está buscando el ancestro común más bajo, sino el ancestro común SIMPLE más bajo, que definen en este documento.

Answer 2

Estoy proponiendo una solución de complejidad de tiempo O (| V | + | E |), y creo que este enfoque es correcto; de lo contrario, corrígeme.

Dado un gráfico acíclico dirigido, necesitamos encontrar LCA de dos vértices v y w.

Paso 1: Encuentre la distancia más corta de todos los vértices desde el vértice raíz usando bfs http://en.wikipedia.org/wiki/Breadth-first_search con la complejidad temporal O (| V | + | E |) y también encuentre el padre de cada vértice.

Paso 2: Encuentre los ancestros comunes de ambos vértices usando parent hasta llegar al vértice raíz. Complejidad del tiempo- 2 | v |

Paso 3: LCA será ese ancestro común que tenga la distancia máxima más corta.

Entonces, este es el algoritmo de complejidad de tiempo O (| V | + | E |).

Por favor, corríjame si estoy equivocado o cualquier otra sugerencia es bienvenida.

Answer 3

Sé que es una vieja pregunta y una discusión bastante buena, pero como tenía un problema similar para resolver, me encontré con los algoritmos del Ancestro Común Más JGraphT de JGraphT , pensé que esto podría ser de ayuda:

• NativeLcaFinder
• TarjanLowestCommonAncestor

Answer 4

Si el gráfico tiene ciclos, ''ancestro'' está definido de manera vaga. ¿Quizás te refieres al ancestro en la salida de árbol de un DFS o BFS? ¿O quizás por ''ancestro'' te refieres al nodo en el dígrafo que minimiza el número de saltos de E y B ?

Si no te preocupa la complejidad, puedes calcular un A * (o el camino más corto de Dijkstra) desde cada nodo hasta E y B Para los nodos que pueden alcanzar E y B , puede encontrar el nodo que minimiza PathLengthToE + PathLengthToB .

EDITAR: Ahora que ha aclarado algunas cosas, creo que entiendo lo que está buscando.

Si solo puede ir "arriba" del árbol, le sugiero que realice un BFS desde E y también un BFS desde B Cada nodo en su gráfica tendrá dos variables asociadas: saltos desde B y saltos desde E Deje que tanto B como E tengan copias de la lista de nodos de gráficos. La lista de B está ordenada por saltos desde B mientras que la lista de E está ordenada por saltos desde E

Para cada elemento en la lista de B , intente encontrarlo en la lista de E Coloca los partidos en una tercera lista, ordenados por saltos desde B + saltos desde E Después de haber agotado la lista de B , su tercera lista ordenada debe contener el LCA a la cabeza. Esto permite una solución, soluciones múltiples (elegidas arbitrariamente entre su orden BFS para B ), o ninguna solución.

Answer 5

Solo un pensamiento salvaje. ¿Qué hay del uso de ambos nodos de entrada como raíces, y hacer dos BFS simultáneamente paso a paso. En un cierto paso, cuando hay superposición en sus conjuntos NEGROS (grabación de nodos visitados), el algoritmo se detiene y los nodos superpuestos son sus LCA (s). De esta manera, cualquier otro antepasado común tendrá distancias más largas que las que hemos descubierto.

Answer 6

Suponga que desea encontrar los antepasados ​​de xey en un gráfico.

Mantenga una matriz de vectores- padres (que almacenen los padres de cada nodo).

1. Primero haz un bfs (sigue almacenando los padres de cada vértice) y encuentra todos los antepasados ​​de x (busca padres de xy usa padres , encuentra todos los antepasados ​​de x) y guárdalos en un vector. Además, almacene la profundidad de cada padre en el vector.

2. Encuentre los antepasados ​​de y usando el mismo método y guárdelos en otro vector. Ahora, tienes dos vectores que almacenan los antecesores de xey respectivamente, junto con su profundidad.

3. LCA sería un ancestro común con la mayor profundidad. La profundidad se define como la distancia más larga desde la raíz (vértice con in_degree = 0). Ahora, podemos ordenar los vectores en orden decreciente de sus profundidades y descubrir el LCA. Usando este método, incluso podemos encontrar múltiples LCA (si existen).

Answer 7

También necesito exactamente lo mismo, para encontrar LCA en un DAG (gráfico acíclico dirigido). El problema de LCA está relacionado con RMQ (Problema mínimo de consulta de rango).

Es posible reducir el LCA a RMQ y encontrar el LCA deseado de dos nodos arbitrarios a partir de un gráfico acíclico dirigido.

Encontré ESTE TUTORIAL detallado y bueno. También estoy planeando implementar esto.

Answer 8

Todo el mundo. Pruebe por favor en Java.

static String recentCommonAncestor(String[] commitHashes, String[][] ancestors, String strID, String strID1)
{
HashSet<String> setOfAncestorsLower = new HashSet<String>();
HashSet<String> setOfAncestorsUpper = new HashSet<String>();
String[] arrPair= {strID, strID1};
Arrays.sort(arrPair);
Comparator<String> comp = new Comparator<String>(){
@Override
public int compare(String s1, String s2) {
return s2.compareTo(s1);
}};
int indexUpper = Arrays.binarySearch(commitHashes, arrPair[0], comp);
int indexLower = Arrays.binarySearch(commitHashes, arrPair[1], comp);
setOfAncestorsLower.addAll(Arrays.asList(ancestors[indexLower]));
setOfAncestorsUpper.addAll(Arrays.asList(ancestors[indexUpper]));
HashSet<String>[] sets = new HashSet[] {setOfAncestorsLower, setOfAncestorsUpper};
for (int i = indexLower + 1; i < commitHashes.length; i++)
{
for (int j = 0; j < 2; j++)
{
if (sets[j].contains(commitHashes[i]))
{
if (i > indexUpper)
if(sets[1 - j].contains(commitHashes[i]))
return commitHashes[i];
sets[j].addAll(Arrays.asList(ancestors[i]));
}
}
}
return null;
}

La idea es muy simple. Suponemos que commitHashes está ordenado en una secuencia de degradación. Encontramos los índices más bajos y más altos de cadenas (hashes, no significa). Es claro que (considerando orden descendiente) el ancestro común puede ser solo después del índice superior (valor más bajo entre hashes). Luego comenzamos a enumerar los valores hash de la cadena de compilación y compilación de las cadenas padre descendentes. Para este propósito, tenemos dos hashsets inicializados por los padres del hash de confirmación más bajo y más alto. setOfAncestorsLower, setOfAncestorsUpper. Si el siguiente cometido hash pertenece a cualquiera de las cadenas (hashsets), entonces si el índice actual es superior al índice del hash más bajo, entonces si está contenido en otro conjunto (cadena) devolveremos el hash actual como resultado. Si no, agregamos sus padres (ancestros [i]) a hashset, que rastrea el conjunto de antepasados ​​del conjunto ,, donde se encuentra el elemento actual. Eso es todo, básicamente

Answer 9

http://www.gghh.name/dibtp/2014/02/25/how-does-mercurial-select-the-greatest-common-ancestor.html

Este enlace describe cómo se hace en Mercurial: la idea básica es encontrar todos los padres para los nodos especificados, agruparlos por distancia desde la raíz y luego hacer una búsqueda en esos grupos.

Answer 10

El enlace de Den Roman parece prometedor, pero me pareció un poco complicado, así que probé con otro enfoque. Aquí hay un algoritmo simple que utilicé:

Supongamos que quiere calcular LCA (x, y) con x y y dos nodos. Cada nodo debe tener un valor de color y count , resp. inicializado a blanco y 0 .

1. Colorea todos los antepasados ​​de x como azul (se puede hacer usando BFS )
2. Colorea todos los antepasados azules de y como rojo (BFS otra vez)
3. Para cada nodo rojo en el gráfico, incremente el count sus padres en uno

Cada nodo rojo que tiene un valor de count establecido en 0 es una solución.

Puede haber más de una solución, dependiendo de su gráfico. Por ejemplo, considere este gráfico:

Las soluciones posibles de LCA (4,5) son 1 y 2.

Tenga en cuenta que aún funciona si desea encontrar el LCA de 3 nodos o más, solo necesita agregar un color diferente para cada uno de ellos.