Clasificación Topológica con Agrupación

Question

Bien, entonces en la clasificación topológica dependiendo de los datos de entrada, generalmente hay múltiples soluciones correctas para qué orden el gráfico puede ser "procesado" para que todas las dependencias entren antes que los nodos que son "dependientes" de ellas. Sin embargo, estoy buscando una respuesta ligeramente diferente:

Supongamos los siguientes datos: a -> b y c -> d (a debe venir antes y bc debe venir antes d).
Con solo estas dos limitaciones, tenemos múltiples soluciones candidatas: (a b c d, a c d b, c a b d, etc.). Sin embargo, estoy buscando crear un método para "agrupar" estos nodos de modo que después del procesamiento de un grupo, todas las entradas en el siguiente grupo tengan sus dependencias atendidas. Para los supuestos datos anteriores, estaría buscando una agrupación como (a, c) (b, d). Dentro de cada grupo, no importa qué orden se procesen los nodos (a antes del c o b antes del d, etc. y viceversa) siempre que el grupo 1 (a, c) finalice antes de que se procese alguno del grupo 2 (b, d).

El único inconveniente adicional sería que cada nodo debería estar en el primer grupo posible. Considerar los siguientes:
a -> b -> c
d -> e -> f
x -> y

Un esquema de agrupación de (a, d) (b, e, x) (c, f, y) sería técnicamente correcto porque x es antes y, una solución más óptima sería (a, d, x) (b, e, y) (c, f) porque tener x en el grupo 2 implica que x era dependiente en algún nodo del grupo 1.

¿Alguna idea sobre cómo hacer esto?

---

EDIT: Creo que logré unir algunos códigos de solución. ¡Gracias a todos los que ayudaron!

// Topological sort 
// Accepts: 2d graph where a [0 = no edge; non-0 = edge] 
// Returns: 1d array where each index is that node's group_id 
vector<int> top_sort(vector< vector<int> > graph) 
{ 
    int size = graph.size(); 
    vector<int> group_ids = vector<int>(size, 0); 
    vector<int> node_queue; 

    // Find the root nodes, add them to the queue. 
    for (int i = 0; i < size; i++) 
    { 
     bool is_root = true; 

     for (int j = 0; j < size; j++) 
     { 
      if (graph[j][i] != 0) { is_root = false; break; } 
     } 

     if (is_root) { node_queue.push_back(i); } 
    } 

    // Detect error case and handle if needed. 
    if (node_queue.size() == 0) 
    { 
     cerr << "ERROR: No root nodes found in graph." << endl; 
     return vector<int>(size, -1); 
    } 


    // Depth first search, updating each node with it's new depth. 
    while (node_queue.size() > 0) 
    { 
     int cur_node = node_queue.back(); 
     node_queue.pop_back(); 

     // For each node connected to the current node... 
     for (int i = 0; i < size; i++) 
     { 
      if (graph[cur_node][i] == 0) { continue; } 

      // See if dependent node needs to be updated with a later group_id 
      if (group_ids[cur_node] + 1 > group_ids[i]) 
      { 
       group_ids[i] = group_ids[cur_node] + 1; 
       node_queue.push_back(i); 
      } 
     } 
    } 

    return group_ids; 
} 

Answer 1

Etiquete todos los nodos de raíz con un valor de nivel 0. Etiquete todos los elementos secundarios con el valor de nivel primario + 1. Si, un nodo se está revisando, es decir, si ya tiene un valor de nivel asignado, verifique si el valor asignado anteriormente es menor que el nuevo. Si es así, actualícelo con el valor más alto y propagalo a los descendientes.

Ahora, usted tiene tantos grupos como hay etiquetas únicas nivel 0 ... K

Answer 2

Recientemente he implementado este algoritmo. Empecé con el enfoque que ha mostrado, pero no se ha ampliado a gráficos de más de 20 millones de nodos. La solución con la que terminé se basa en the approach detailed here.

Puede pensar que se trata de calcular la altura de cada nodo, y luego el resultado es un grupo de cada nodo a una altura determinada.

Considere el gráfico:

A -> X

B -> X

X -> Y

X -> Z

Así la salida deseada es (A, B), (X), (Y, Z)

El enfoque básico es encontrar todo sin nada usándolo (A, B en este ejemplo). Todos estos están en la altura 0.

Ahora elimine A y B del gráfico, encuentre algo que ahora no tenga nada usándolo (ahora X en este ejemplo). Entonces X está en la altura 1.

Quite X del gráfico, encuentre algo que ahora no tenga nada usándolo (ahora Y, Z en este ejemplo). entonces Y, Z están en la altura 2.

Puede realizar una optimización al darse cuenta del hecho de que no necesita almacenar bordes bidireccionales para todo o eliminar realmente nada de su gráfico, solo necesita saber el número de cosas que apuntan a un nodo y los nodos que usted conoce están en la siguiente altura.

Así que para este ejemplo, al inicio:

• 0 cosas utilizan 1
• 0 uso de las cosas 2
• 2 cosas utilizar X (1 y 2)
• 1 cosas use Y, Z (X)

Cuando visita un nodo, disminuya el número de cada uno de los nodos a los que apunta, si ese número es cero, usted sabe que ese nodo está en la siguiente altura.