Algoritmo para calcular ordenamientos parciales de gráficos de dependencia

Question

Estoy tratando de calcular un "tipo topológico" parcial de un gráfico de dependencia, que en realidad es un DAG (Gráfico acíclico dirigido) para ser preciso; para ejecutar tareas sin dependencias conflictivas en paralelo.

Se me ocurrió este algoritmo simple porque lo que encontré en Google no fue del todo útil (sigo buscando solo algoritmos que se ejecuten en paralelo para calcular un tipo topológico normal).

visit(node) 
{ 
    maxdist = 0; 
    foreach (e : in_edge(node)) 
    { 
     maxdist = max(maxdist, 1 + visit(source(e))) 
    } 
    distance[node] = maxdist; 
    return distance[node]; 
} 

make_partial_ordering(node) 
{ 
    set all node distances to +infinite; 
    num_levels = visit(node, 0); 
    return sort(nodes, by increasing distance) where distances < +infinite; 
} 

(Tenga en cuenta que esto sólo es pseudocódigo y sin duda habría un par de optimizaciones posibles pequeños)

En cuanto a la exactitud, parece bastante obvio: Para las hojas (: = nodos que no tienen más dependencia) la distancia máxima a la hoja siempre es 0 (correcta porque se omite el ciclo debido a 0 aristas). Para cualquier nodo conectado a los nodos n1, .., nk la distancia máxima a la hoja es 1 + max {distancia [n1], .., distancia [nk]}.

he encontrado este artículo después de haber escrito el algoritmo: http://msdn.microsoft.com/en-us/magazine/dd569760.aspx Pero honestamente, ¿por qué hacen todo eso lista de copia y así sucesivamente, apenas se parece de manera muy ineficiente ..?

De todos modos, me preguntaba si mi algoritmo es correcto, y si es así, cómo se llama para que pueda leer algunas cosas al respecto.

Actualización: Implementé el algoritmo en mi programa y parece funcionar muy bien para todo lo que probé. Código en cuanto se parece a esto:

typedef boost::graph_traits<my_graph> my_graph_traits; 
    typedef my_graph_traits::vertices_size_type vertices_size_type; 
    typedef my_graph_traits::vertex_descriptor vertex; 
    typedef my_graph_traits::edge_descriptor edge; 

    vertices_size_type find_partial_ordering(vertex v, 
     std::map<vertices_size_type, std::set<vertex> >& distance_map) 
    { 
     vertices_size_type d = 0; 

     BOOST_FOREACH(edge e, in_edges(v)) 
     { 
      d = std::max(d, 1 + find_partial_ordering(source(e), distance_map)); 
     } 

     distance_map[d].insert(v); 

     return d; 
    } 

Answer 1

Su algoritmo (C++) funciona, pero tiene muy mala en el peor caso de tiempo. Calcula find_partial_ordering en un nodo para tantas rutas como hay para ese nodo. En el caso de un árbol, el número de caminos es 1, pero en un gráfico acíclico dirigido general el número de caminos puede ser exponencial.

Puede corregir esto por memoizing sus resultados y volver sin recurrir cuando ya haya calculado el valor para un nodo determinado. Sin embargo, esto aún te deja con una solución recursiva que rompe la pila.

An efficient (linear) algorithm for topological sorting is given on Wikipedia. ¿Esto no se ajusta a tus necesidades?

Editar: ah, ya veo, quieres saber dónde están los límites de profundidad para que puedas paralelizar todo a una profundidad determinada. Todavía puede usar el algoritmo en Wikipedia para esto (y así evitar la recursión).

Primero, haga un tipo topológico con el algoritmo en Wikipedia. Ahora profundidades de cómputo visitando nodos en orden topológico:

depths : array 1..n 
for i in 1..n 
    depths[i] = 0 
    for j in children of i 
     depths[i] = max(depths[i], depths[j] + 1) 
return depths 

en cuenta que no hay recursividad arriba, solo un O(|V| + |E|) algoritmo simple. Esto tiene la misma complejidad que el algoritmo en Wikipedia.