Estoy buscando un algoritmo simple para 'serializar' un gráfico dirigido. En particular, tengo un conjunto de archivos con interdependencias en su orden de ejecución, y quiero encontrar el orden correcto en tiempo de compilación. Sé que debe ser algo bastante común de hacer, los compiladores lo hacen todo el tiempo, pero mi Google-Fu ha sido débil hoy. ¿Cuál es el algoritmo 'go-to' para esto?serialización de gráficos
Topological Sort (de Wikipedia):
En la teoría de grafos, una especie topológica o ordenamiento topológico de un dirigida gráfico acíclico (DAG) es un ordenación lineal de sus nodos en la que viene cada nodo antes de todos los nodos a los que tiene bordes de salida. Cada DAG tiene uno o más géneros topológicos. código
Pseudo:
L ← Empty list where we put the sorted elements
Q ← Set of all nodes with no incoming edges
while Q is non-empty do
remove a node n from Q
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into Q
if graph has edges then
output error message (graph has a cycle)
else
output message (proposed topologically sorted order: L)
Esperaría que las herramientas que lo necesitan simplemente caminen por el árbol en profundidad y cuando toquen una hoja, simplemente procese (por ejemplo, compile) y quítelo del gráfico (o márquelo como procesado, y trate nodos con todas las hojas procesadas como hojas).
Siempre que se trate de un DAG, esta simple caminata basada en la pila debería ser trivial.
Sí, así es como lo haces. Se llama búsqueda en profundidad (DFS). Y a menos que esté seguro de que tiene un DAG, debe verificar los bordes posteriores, de lo contrario, un ciclo lo enviará a un bucle infinito. – sleske
Yo he llegado con un algoritmo recursivo bastante ingenua (pseudocódigo):
Map<Object, List<Object>> source; // map of each object to its dependency list
List<Object> dest; // destination list
function resolve(a):
if (dest.contains(a)) return;
foreach (b in source[a]):
resolve(b);
dest.add(a);
foreach (a in source):
resolve(a);
El mayor problema con esto es que no tiene capacidad para detectar dependencias cíclicas - que pueda entrar en la repetición infinita (es decir, desbordamiento de pila ;-p). La única forma de evitarlo que veo es voltear el algoritmo recursivo en uno interactivo con una pila manual y verificar manualmente la pila para ver si hay elementos repetidos.
¿Alguien tiene algo mejor?
en lugar de utilizar foreach por un tiempo, mantenga dos punteros que atraviesen los datos a, uno principal que doble pasos y uno posterior que solo pasos. El puntero principal maneja las resoluciones reales y, si alguna vez toca el puntero, hay un ciclo. – Tenderdude
Si el gráfico contiene ciclos, órdenes de ejecución cómo puede existir permitidos para sus archivos? Me parece que si el gráfico contiene ciclos, entonces no tiene solución, y este se informa correctamente mediante el algoritmo anterior.
Sí, un tipo topológico no es posible si un gráfico contiene ciclos. Esto corresponde al mundo real: si te pido que hagas A antes de B, * y * B antes que A, no hay forma de que me vayas a satisfacer ;-). – sleske
Eh ... copiado directamente de wikipedia? – Benjol
sí, por favor cite fuentes –
Gracias. Me ayudó a mapear el hecho de que el árbol de dependencias se puede ordenar usando este método. :-) –