algorithm - Ordenamiento topológico en OCaml

topological-sort

Question

Estoy tratando de escribir la clasificación topológica en ocaml, pero soy un principiante (en algoritmos OCaml y gráficos) y no puedo hacerlo solo.

Es más fácil para mí pensar en la clasificación topológica, por ejemplo, en C ++ (y hay muchos ejemplos de clasificación topológica en C ++ en Internet), pero quiero aprender algo nuevo. Además, he encontrado algunos ejemplos de ordenación topológica escritos en OCaml, pero no los entiendo, para ser sinceros.

Digamos que tengo una lista (int * int list) list , por ejemplo:

myList = [(1, [2]); (5, [6; 7]); (3, [2]); (6, [3; 7]); (8, [7]); (4, [3; 1])];;

y eso significa que necesito "hacer" la tarea 1 antes de la tarea 2 , la tarea 4 antes de las tareas 3 y 1 etc.

Creo que esa salida para esta lista debería ser:

[8; 5; 6; 7; 4; 3; 1; 2]

(Sin embargo, no estoy seguro, porque acabo de hacer este ejemplo, así que si me equivoco, corrígeme por favor)

Además, he leído que el ordenamiento topológico no funciona para los ciclos en los gráficos, por lo que debe haber algún tipo de condición para los ciclos: cuando un gráfico dado tiene ciclo (s), generamos una excepción (creo que es una buena idea) .

AFAIK, necesito usar DFS en el algoritmo para la ordenación topológica, que (DFS) no sé cómo implementar en OCaml (entiendo la idea principal, pero no siento cómo funciona en la programación funcional / OCaml).

Realmente agradecería su ayuda para entenderme estos conceptos (me refiero a ordenamiento topológico, DFS en programación de OCaml / funcional). Si puede, sería genial, si me muestra códigos de ejemplo, porque leer código es (para mí) el mejor método para entender el concepto de algoritmo.

Sé que para la mayoría de ustedes, esta es una pregunta simple, pero espero que no le impida ayudarme.

PD: Estoy aprendiendo OCaml por mi cuenta (estoy en una escuela secundaria), así que no tengo una sólida formación teórica (ni en OCaml ni en algoritmos). Comencé a aprender OCaml porque quería entender el concepto de recursión, y ahora este lenguaje parece interesante, porque es muy diferente de C ++, por lo que todavía estoy intentando aprender algo nuevo en OCaml.

Answer 1

Debes probar DFS primero, es más fácil y gratificante.

Answer 2

No sé OCaml, pero hay un algoritmo simple en Wikipedia acreditado para Kahn que he usado con éxito (transcribiendo a Python). Es bastante simple, así que quizás puedas traducirlo a OCaml. Aquí está:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    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 S
if graph has edges then
    output error message (graph has at least one cycle)
else 
    output message (proposed topologically sorted order: L)

Answer 3

Primero, tenga en cuenta que Objective Caml admite un estilo de programación que, a pesar de las diferencias sintácticas, es bastante similar a C ++, por medio de estructuras de datos mutables (referencias, matrices, tablas hash) y construcciones imperativas (bucles para y while, asignación de variables) . Supongo que a continuación está intentando escribir su ordenamiento topológico en un estilo idiomático y funcional puro.

La programación funcional pura es en su mayoría declarativa: esta función aplicada a ese valor es este otro valor. Esta es la razón por la que el lado derecho de let x = es una expresión (se evalúa como un valor) en lugar de una secuencia de acciones que usa return . Por supuesto, los problemas aparecen cuando se adapta un algoritmo que normalmente se describe como una serie de pasos.

Afortunadamente, hay un patrón (en realidad, una familia de patrones) que le permite representar algoritmos imperativos en estilo funcional al convertir "cambiar el valor de X" en "devolver un nuevo objeto que es idéntico al anterior, excepto el valor de X ".

Un algoritmo tradicional de DFS implica recorrer el gráfico mientras recuerda los elementos que ya se han visitado, en general (para que no los visite más de una vez) y para llegar a su posición actual (para que pueda detectar ciclos). Por lo tanto, el estado imperativo de un algoritmo DFS se compone del nodo actual, el conjunto de nodos visitados y el conjunto de nodos en la ruta actual. Todos estos datos deberán proporcionarse a las llamadas recursivas, y cualquier cambio permanente tendrá que ser devuelto por esas mismas llamadas recursivas.

Usando la estructura de su gráfica desde arriba, combinada con una representación de lista para los dos conjuntos (es difícilmente óptima, aquí el Set sería una mejor opción), el algoritmo se parecería a esto:

let dfs graph start_node = 
  let rec explore path visited node = 
    if List.mem node path    then raise (CycleFound path) else
    if List.mem node visited then visited else     
      let new_path = node :: path in 
      let edges    = List.assoc node graph in
      let visited  = List.fold_left (explore new_path) visited edges in
      node :: visited
  in explore [] [] start_node

Tres detalles importantes mencionados anteriormente: primero, DFS dice que cuando haya terminado de explorar todos los hijos de un nodo determinado, debe eliminar ese nodo de la lista de "ruta de acceso actual" y colocarlo en la lista de "visitados". Ya que estamos usando estructuras de datos inmutables, el primer paso es innecesario: su único propósito fue deshacer la inserción del nodo cuando comenzó la exploración, y en nuestra versión la llamada recursiva no modifica la lista new_path . Este es un ejemplo de un caso en el que las estructuras de datos funcionales son más cómodas para trabajar que las estructuras imperativas.

Otro detalle importante es el uso de List.fold_left . Cuando comenzamos a hacer explícito el estado, reemplazamos funciones imperativas implícitas de tipo -> unit con funciones explícitas de tipo -> state -> .. -> state (aceptar el estado como parámetro, devolver un nuevo estado). Entonces, la exploración de la lista imperativa, que se veía así:

f edge_1 ; f edge_2 ; f edge_3

Ahora se ve así:

let state = f (f (f state edge_1) edge_2) edge_3)

Que es exactamente lo que List.fold_left f state [edge_1 ; edge_2 ; edge_3] List.fold_left f state [edge_1 ; edge_2 ; edge_3] List.fold_left f state [edge_1 ; edge_2 ; edge_3] hace. Tooting mi propio cuerno, pero tengo un buen artículo sobre esto aquí .

El tercer punto es que la operación "agregar elemento al conjunto", cuando se usan listas para representar conjuntos, se escribe simplemente como element :: set , porque esta es una operación que devuelve un nuevo conjunto (lista) que contiene todos los elementos del Conjunto original junto con el nuevo elemento. Esto deja el conjunto original intacto (lo cual es bueno por las razones descritas en el paso uno) mientras se usa una cantidad constante de memoria (crea una celda de contras: un simple par cabeza-cola que contiene una referencia al elemento y una referencia al conjunto ): no solo obtiene capacidades de deshacer, sino que lo hace sin costo adicional.

El algoritmo anterior "inserta" los nodos en las visited comenzando con las hojas de la exploración DFS, que en su caso representan aquellos nodos que deben hacerse en último lugar. En resumen, la lista devuelta está ordenada topológicamente, pero puede que no contenga todos los elementos porque el punto de partida podría no ser el único elemento raíz (o incluso ser un elemento raíz). Por lo tanto, hay un paso de procesamiento adicional involucrado aquí que consiste en tomar otro nodo del gráfico hasta que se haya explorado todo el gráfico.

O, en otras palabras, comenzar una nueva exploración DFS desde cada nodo en el gráfico , pero ignorando cualquier nodo previamente explorado , lo que equivale a mantener la lista de elementos visitados de una exploración DFS a la siguiente.

Usando un pequeño ajuste a nuestro algoritmo anterior, esto toma solo dos líneas:

let dfs graph visited start_node = 
  let rec explore path visited node = 
    if List.mem node path    then raise (CycleFound path) else
    if List.mem node visited then visited else     
      let new_path = node :: path in 
      let edges    = List.assoc node graph in
      let visited  = List.fold_left (explore new_path) visited edges in
      node :: visited
  in explore [] visited start_node

let toposort graph = 
  List.fold_left (fun visited (node,_) -> dfs graph visited node) [] graph

El ajuste consiste en permitir que la persona que llama a dfs especifique la lista de nodos ya visitados. El traslado de la lista de nodos visitados al iniciar un DFS desde cada nodo se realiza utilizando List.fold_left exactamente como antes.

EDITAR : aparte del tipo de excepción, no hay nada aquí que limite el tipo de los elementos en el gráfico. Sin embargo, una excepción no puede ser polimórfica, por lo que tiene dos soluciones posibles. La primera es renunciar a devolver cualquier dato junto con la excepción:

exception CycleFound

... raise CycleFound ...

Esto revertirá el tipo de toposort nuevo a una lista más genérica (''a * (''a list)) list -> ''a list .

La otra solución es bastante avanzada OCaml: debe hacer que el módulo que contiene la excepción y el ordenamiento topológico sea polimórfico en ese tipo específico, de la siguiente manera:

module type NODE = sig
  type t 
end

module type Topo = functor (Node:NODE) -> struct 
  exception CycleFound of Node.t list      
  let dfs ...
  let sort ...  
end

Esto haría que el tipo de Topo(Node).sort sea (Node.t * (Node.t list)) list -> Node.t list , lo que significa que puede ordenar cualquier tipo que desee definiendo un módulo de nodo con ese tipo :

type recipe = Eggs | Milk | Wheat | Mix | Cook | Serve

module Node = struct 
  type t = recipe 
end

let graph = [ Wheat, [Eggs,Milk,Mix] ;
              Milk,  [Mix] ;
              Eggs,  [Mix] ;
              Mix,   [Cook] ;
              Cook,  [Serve] ;
              Serve, [] ]

module RecipeTopo = Topo(Node)

let sorted = RecipeTopo.sort graph

Answer 4

[En caso de que no conozca el término, donde escribo DAG a continuación, me refiero a "gráfico acíclico dirigido", o una colección de desde / hacia bordes que conectan vértices de modo que no haya ciclos.]

Una forma de hacerlo es extender su orden parcial (su estructura DAG) en un orden total (por lo tanto, para cada par de vértices distintos u y v, u es un sucesor de v o viceversa). Luego puede ordenar sus vértices en orden: u aparece antes de v si v es un sucesor de u.

Puede construir su orden total comenzando con el gráfico vacío y agregando un borde a la vez desde su DAG original. Es decir, un elemento (u, [v1; v2; ...; vn]) en su DAG original corresponde a los bordes (u, v1), (u, v2), ..., (u, vn). Para cada una de esas ventajas (u, v), encuentre los predecesores P de u y los sucesores S de v de su orden total. Luego agregue (p, s) a su orden total para todos los p en PU {u} ys en SU ​​{v}.

¡AHORA! Una forma más rápida de hacerlo es encontrar una raíz en su DAG original (es decir, un vértice sin predecesores) y realizar una búsqueda en profundidad desde esa raíz, asegurándose de que nunca visite el mismo vértice dos veces. Cada vez que retrocedes en tu recorrido, "sacas" el vértice que estás dejando. De esta manera usted construye el tipo topológico de su DAG. Si quedan vértices, enjuague con espuma y repita hasta que estén listos.