Algoritmo de Árbol Genealógico

Actualización : Esta no es la mejor solución que se me ha ocurrido, pero la he dejado porque hay muchos comentarios relacionados con ella.

Tiene un conjunto de eventos (nacimiento/muerte), estado parental (sin descendientes, padres, abuelos, etc.) y estado de vida (vivo, muerto).

Almacenaría mis datos en estructuras con los siguientes campos:

mother
father
generations
is_alive
may_have_living_ancestor

Ordena tus eventos por fecha, y luego para cada evento toma uno de los siguientes dos cursos de lógica:

Birth:
    Create new person with a mother, father, 0 generations, who is alive and may
        have a living ancestor.
    For each parent:
        If generations increased, then recursively increase generations for
            all living ancestors whose generations increased.  While doing that,
            set the may_have_living_ancestor flag to false for anyone for whom it is
            discovered that they have no living ancestors.  (You only iterate into
            a person's ancestors if you increased their generations, and if they
            still could have living ancestors.)

Death:
    Emit the person's name and generations.
    Set their is_alive flag to false.

El el peor caso es O(n*n) si todo el mundo tiene muchos antepasados vivos. Sin embargo, en general tienes el paso de preprocesamiento de ordenación que es O(n log(n)) y luego eres O(n * avg no of living ancestors) lo que significa que el tiempo total tiende a ser O(n log(n)) en la mayoría de las poblaciones. (No había contado el prestep de clasificación correctamente, gracias a @ Alexey Kukanov por la corrección.)

Mi sugerencia:

• además de los valores descritos en la declaración del problema, cada registro personal tendrá dos campos: contador hijo y un vector de crecimiento dinámico (en el sentido de C++/STL) que mantendrá el cumpleaños más temprano en cada generación de los descendientes de una persona.
• utilice una tabla hash para almacenar los datos, siendo el nombre de la persona la clave. El tiempo para construirlo es lineal (suponiendo una buena función hash, el mapa tiene tiempo constante amortizado para inserciones y encontrar).
• para cada persona, detecte y guarde el número de niños. También se hace en tiempo lineal: para cada registro personal, encuentre el registro para sus padres e incremente sus contadores. Este paso se puede combinar con el anterior: si no se encuentra un registro para un padre, se crea y agrega, mientras que los detalles (fechas, etc.) se agregarán cuando se encuentren en la entrada.
• atraviese el mapa, y ponga las referencias a todos los registros personales sin hijos en una cola. Aun O(N).
• para cada elemento sacado de la cola:
  • agregue el cumpleaños de esta persona en descendant_birthday[0] para ambos padres (crezca ese vector si es necesario). Si este campo ya está establecido, cámbielo solo si la nueva fecha es anterior.
  • Para todas las fechas descendant_birthday[i] disponibles en el vector del registro actual, siga la misma regla que la anterior para actualizar descendant_birthday[i+1] en los registros de los padres.
  • decrementar los contadores de hijos de los padres; si llega a 0, agregue el registro del padre correspondiente en el cola.
  • el costo de este paso es O(C*N), siendo C el mayor valor de "profundidad de familia" para la entrada dada (es decir, el tamaño del vector descendant_birthday más largo). Para datos realistas, puede ser limitado por alguna constante razonable sin pérdida de corrección (como otros ya señalaron), y por lo tanto no depende de N.
• recorrer el mapa una vez más, y "etiquetar a cada persona" con el mayor i para el cual descendant_birthday[i] es todavía anterior a la fecha de muerte; también O(C*N).

Por lo tanto, para datos realistas, la solución para el problema se puede encontrar en tiempo lineal. Aunque para datos artificiales como se sugiere en el comentario de @btilly, C puede ser grande, e incluso del orden de N en casos degenerados. Se puede resolver poniendo un límite al tamaño del vector o extendiendo el algoritmo con el paso 2 de la solución de @btilly.

Una tabla hash es parte clave de la solución en caso de que las relaciones padre-hijo en los datos de entrada se proporcionen a través de nombres (como escrito en la declaración del problema). Sin hashes, se requeriría O(N log N) para construir un gráfico de relaciones. La mayoría de las otras soluciones sugeridas parecen asumir que el gráfico de relaciones ya existe.

Crea una lista de personas, ordenadas por birth_date. Cree otra lista de personas, ordenadas por death_date. Puede viajar lógicamente a través del tiempo, haciendo aparecer a las personas de estas listas, con el fin de obtener una lista de los eventos a medida que sucedieron.

Para cada Persona, defina un campo is_alive. Esto será FALSO para todos al principio. A medida que las personas nacen y mueren, actualice este registro en consecuencia.

Defina otro campo para cada persona, llamado has_a_living_ancestor, inicializado a FALSE para todos al principio. Al nacer, x.has_a_living_ancestor se establecerá en x.mother.is_alive || x.mother.has_a_living_ancestor || x.father.is_alive || x.father.has_a_living_ancestor. Por lo tanto, para la mayoría de las personas (pero no todos), esto se establecerá como VERDADERO al nacer.

El desafío es identificar las ocasiones en que has_a_living_ancestor se puede establecer en FALSO. Cada vez que nace una persona, hacemos un DFS a través de los antepasados, pero solo aquellos antepasados para los que ancestor.has_a_living_ancestor || ancestor.is_alive es cierto.

Durante ese DFS, si encontramos un ancestro que no tiene ancestros vivos, y ahora está muerto, entonces podemos establecer has_a_living_ancestor a FALSE. Esto significa, creo, que a veces has_a_living_ancestor estará fuera de fecha, pero con suerte será capturado rápidamente.

El siguiente es un algoritmo O(n log n) que funciona para gráficos en los que cada hijo tiene como máximo un padre (EDITAR: este algoritmo no se extiende al caso de dos padres con rendimiento O(n log n)). Vale la pena señalar que creo que el rendimiento se puede mejorar a O (n log (etiqueta de nivel máximo)) con trabajo adicional.

Un caso padre:

Para cada nodo x, en orden topológico inverso, cree un árbol de búsqueda binario T_x que esté aumentando estrictamente tanto en fecha de nacimiento como en en número de generaciones removidas de x. (T_x contiene el primer niño nacido c1 en el subgrafo del gráfico de ascendencia arraigado en x, junto con el siguiente niño nacido más temprano c2 en este subgrafo de tal manera que el 'nivel de bisabuelo' de c2 es estrictamente mayor que el de c1, junto con el siguiente niño nacido más temprano c3 en este subgrafo de tal manera que el nivel de c3 es estrictamente mayor que el de c2, etc.) Para crear T_x, fusionamos los árboles previamente construidos T_w donde w es un hijo de x (son construido previamente porque estamos iterando en orden topológico inverso).

Si tenemos cuidado con cómo realizamos las fusiones, podemos mostrar que el costo total de dichas fusiones es O(n log n) para todo el gráfico de ascendencia. La idea clave es tener en cuenta que después de cada fusión, a lo sumo un nodo de cada nivel sobrevive en el árbol fusionado. Asociamos con cada árbol T_w un potencial de h(w) log n, donde h (w) es igual a la longitud del camino más largo de w a una hoja.

Cuando fusionamos el árboles hijos T_w para crear T_x, 'destruimos' todos los árboles T_w, liberando todo el potencial que almacenan para su uso en la construcción del árbol T_x; y creamos un nuevo árbol T_x con (log n)(h(x)) potencial. Por lo tanto, nuestro objetivo es gastar a lo sumo O((log n)(sum_w(h(w)) - h(x) + constante)) tiempo para crear T_x a partir de los árboles T_w para que el costo amortizado de la fusión sea solo O(log n). Esto se puede lograr eligiendo el árbol T_w tal que h (w) sea máximo como punto de partida para T_x y luego modificando T_w para crear T_x. Después de hacer tal elección para T_x, fusionamos cada uno de los otros árboles, uno por uno, en T_x con un algoritmo que es similar al algoritmo estándar para fusionar dos árboles de búsqueda binarios.

Esencialmente, la fusión se logra iterando sobre cada nodo y en T_w, buscando el predecesor de y z por fecha de nacimiento, y luego insertando y en T_x si hay más niveles eliminados de x que z; luego, si z se insertó en T_x, buscamos el nodo en T_x de el nivel más bajo que es estrictamente mayor que el nivel de z, y empalma los nodos intermedios para mantener el invariante que T_x está ordenado estrictamente tanto por fecha de nacimiento como por nivel. Esto cuesta O (log n) para cada nodo en T_w, y hay a lo sumo nodos O(h(w)) en T_w, por lo que el costo total de fusionar todos los árboles es O((log n) (sum_w(h(w))), sumando todos los hijos w excepto el hijo w' tal que h(w') es máximo.

Almacenamos el nivel asociado con cada elemento de T_x en un auxiliar campo de cada nodo en el árbol. Necesitamos este valor para que podamos averiguar el nivel real de x una vez que hemos construido T_x. (Como un detalle técnico, realmente almacenamos la diferencia del nivel de cada nodo con el de su padre en T_x para que podamos incrementar rápidamente los valores para todos los nodos en el árbol. Este es un truco estándar de BST.)

Eso es todo. Simplemente observamos que el potencial inicial es 0 y el potencial final es positivo, por lo que la suma de los límites amortizados es un límite superior en el costo total de todas las fusiones en todo el árbol. Encontramos la etiqueta de cada nodo x una vez que creamos el BST T_x por binario buscando el último elemento en T_x que nació antes de que x muriera al costo O(log n).

Para mejorar el enlace a O(n log(etiqueta de nivel máximo)), puede combinar perezosamente los árboles, solo fusionando los primeros elementos del árbol según sea necesario para proporcionar la solución para el nodo actual. Si utiliza un BST que explota la localidad de referencia, como un árbol de splay, entonces puede lograr el límite anterior.

Con suerte, el algoritmo y el análisis anteriores son al menos lo suficientemente claros como para seguir. Solo comente si necesita alguna aclaración.

Tengo la corazonada de que obtener para cada persona un mapeo (generación -> fecha en que nace el primer descendiente de esa generación) ayudaría.

Dado que las fechas deben ser estrictamente crecientes, podríamos usar el uso de búsqueda binaria (o una estructura de datos ordenada) para encontrar el descendiente vivo más distante en el tiempo O(log n).

El problema es que la fusión de estas listas (al menos ingenuamente) es O (número de generaciones) por lo que esto podría llegar a ser O (n^2) en el peor de los casos (considerar A y B son padres de C y D, que son padres de E y F...).

Todavía tengo que averiguar cómo funciona el mejor caso y tratar de identificar mejor los peores casos (y ver si hay una solución para ellos)

Recientemente implementamos el módulo de relación en uno de nuestros proyectos en el que teníamos todo en la base de datos y sí creo que el algoritmo era el mejor 2nO(m) (m es el factor de rama máximo). Multiplicé las operaciones dos veces a N porque en la primera ronda creamos gráfico de relación y en la segunda ronda visitamos a cada persona. Hemos almacenado la relación bidireccional entre cada dos nodos. Mientras navegamos, solo usamos una dirección para viajar. Pero tenemos dos series de operaciones, una atraviesa solo niños, otro recorrido único padre.

Person{
  String Name;

  // all relations where
  // this is FromPerson
  Relation[] FromRelations; 

  // all relations where
  // this is ToPerson
  Relation[] ToRelations;

  DateTime birthDate;
  DateTime? deathDate;
}

Relation
{
  Person FromPerson;
  Person ToPerson;
  RelationType Type;
}

enum RelationType
{
  Father,
  Son,
  Daughter,
  Mother
}

Este tipo de grafo parece bidireccional. Pero en este caso, primero construyes una lista de todas las personas, y luego puedes construir relaciones de lista y configurar relaciones y torelaciones entre cada nodo. Entonces todo lo que tienes que hacer es, para cada Persona, solo tienes que navegar por las versiones de tipo (Hijo,Hija) solamente. Y como tienes fecha, puedes calcular todo.

No tengo tiempo para comprobar la corrección del código, pero esto le dará idea de cómo hacerlo.

void LabelPerson(Person p){
   int n = GetLevelOfChildren(p, p.birthDate, p.deathDate);
   // label based on n...
}

int GetLevelOfChildren(Person p, DateTime bd, DateTime? ed){
   List<int> depths = new List<int>();
   foreach(Relation r in p.ToRelations.Where(
             x=>x.Type == Son || x.Type == Daughter))
   {
      Person child = r.ToPerson;
      if(ed!=null && child.birthDate <= ed.Value){
         depths.Add( 1 + GetLevelOfChildren( child, bd, ed));
      }else
      {
         depths.Add( 1 + GetLevelOfChildren( child, bd, ed));
      }
   }
   if(depths.Count==0)
      return 0;
   return depths.Max();
}

Aquí está mi puñalada:

class Person
{
    Person [] Parents;
    string Name;
    DateTime DOB;
    DateTime DOD;
    int Generations = 0;

    void Increase(Datetime dob, int generations)
    {
        // current person is alive when caller was born
        if (dob < DOD)
            Generations = Math.Max(Generations, generations)
        foreach (Person p in Parents)
            p.Increase(dob, generations + 1);
    }

    void Calculate()
    {
        foreach (Person p in Parents)
            p.Increase(DOB, 1);
    }
}

// run for everyone
Person [] people = InitializeList(); // create objects from information
foreach (Person p in people)
    p.Calculate();

• Hay un algoritmo O(n log n) relativamente sencillo que barre los eventos cronológicamente con la ayuda de un árbol superior adecuado.

• No deberías asignar tareas que no puedas resolver por ti mismo.