Ordinamento topologico in OCaml

Question

Sto cercando di scrivere l'ordinamento topologico in ocaml, ma sono un principiante (negli algoritmi di OCaml &) e non posso farlo da solo.

È più facile per me pensare all'ordinamento topologico, ad esempio in C++ (e ci sono molti esempi di ordinamento topologico in C++ su Internet), ma voglio imparare qualcosa di nuovo. Inoltre, ho trovato alcuni esempi di ordinamento topologico scritti in OCaml, ma non li capisco, per essere sinceri.

Diciamo che ho una lista (int * int list) list, ad esempio:

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

e questo significa, che ho bisogno di "fare" compito 1 prima operazione 2, compito 4 prima attività 3 e 1 etc.

penso, che l'uscita di questo elenco dovrebbe essere:

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

(tuttavia non sono sicuro, perché ho appena fatto questo esempio, quindi se mi sbaglio, correggetemi per favore)

Inoltre, ho letto, quel tipo topologico non funziona per cicli in grafici, quindi ci deve essere un qualche tipo di condizione per i cicli - quando un dato grafico ha ciclo (s) solleviamo eccezione (penso che sia una buona idea).

AFAIK, ho bisogno di utilizzare DFS in un algoritmo per l'ordinamento topologico, che (DFS) non so come implementare in OCaml (capisco idea principale, ma non mi sento , come funziona in OCaml/programmazione funzionale).

Apprezzerei molto il tuo aiuto per capirmi questi concetti (intendo ordinamento topologico, DFS in OCaml/programmazione funzionale). Se puoi, sarebbe bello, se mi mostri codici di esempio, perché il codice di lettura è (per me) il metodo migliore per comprendere il concetto dell'algoritmo.

So che per la maggior parte di voi questa è una domanda semplice, ma spero che non ti impedirà di aiutarmi.

PS: Sto imparando OCaml da solo (sono in una scuola superiore), quindi non ho una solida teoria di base (in OCaml o algoritmi). Avevo iniziato ad imparare OCaml, perché volevo capire il concetto di ricorsione, e ora questo linguaggio sembra essere interessante, perché è molto diverso dal C++, quindi sto ancora cercando di imparare qualcosa di nuovo in OCaml.

Answer 1

[Nel caso in cui non si conosce il termine, dove scrivo DAG sotto intendo "diretto grafo aciclico", o un insieme di da/per archi che connettono vertici tale che non vi sono cicli.]

Un modo per farlo è estendere il tuo ordine parziale (la tua struttura DAG) in un ordine totale (quindi per ogni coppia di vertici distinti u e v, o è un successore di v o viceversa). Quindi puoi ordinare i tuoi vertici in ordine: u viene prima di v se v è un successore di u.

È possibile costruire l'ordine totale iniziando dal grafico vuoto e aggiungendo un bordo alla volta dal DAG originale. Cioè, un item (u, [v1; v2; ...; vn]) nel tuo DAG originale corrisponde ai bordi (u, v1), (u, v2), ..., (u, vn). Per ciascuno di questi lati (u, v), trova i predecessori P di te i successori S di v dal tuo ordine totale. Quindi aggiungi (p, s) al tuo ordine totale per tutti i p in P U {u} e s in S U {v}.

ORA! Un modo più veloce per farlo è trovare una radice nel DAG originale (cioè un vertice senza predecessori) e fare una prima ricerca approfondita da quella radice, assicurando di non visitare mai lo stesso vertice due volte. Ogni volta che ritorni nella tua traversata, "fai uscire" il vertice che stai lasciando. In questo modo costruisci il tipo topologico del tuo DAG. Se sono rimasti dei vertici, sciacquare la schiuma e ripetere finché non sono tutti fatti.

Answer 2

Non conosco OCaml, ma c'è un semplice algoritmo in Wikipedia accreditato a Kahn che ho usato con successo (trascrivendo in Python). È abbastanza semplice, quindi forse potresti tradurlo in OCaml. Eccolo:

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

Si dovrebbe provare DFS prima, è più facile e gratificante.

Answer 4

In primo luogo, essere consapevoli del fatto che Objective Caml supporta uno stile di programmazione che, nonostante le differenze sintattiche, è abbastanza simile al C++, mediante strutture dati mutevoli (riferimenti, array, tabelle hash) e costrutti imperativi (per e while loop , assegnazione variabile). Suppongo di seguito che in realtà stai cercando di scrivere il tuo tipo topologico in puro stile funzionale idiomatico.

Programmazione funzionale pura per lo più dichiarativa: questa funzione applicata a tale valore è questo altro valore. Questo è il motivo per cui il lato destro di let x = è un'espressione (restituisce un valore) anziché una sequenza di azioni che utilizza return. Ovviamente, compare un problema quando si adatta un algoritmo che viene comunemente descritto come una serie di passaggi.

Fortunatamente, esiste un modello (in realtà una famiglia di modelli) che consente di rappresentare algoritmi imperativi in ​​stile funzionale trasformando "modifica il valore di X" in "restituisce un nuovo oggetto identico a quello vecchio" , ad eccezione del valore di X ".

Un algoritmo DFS tradizionale prevede di passare attraverso il grafico ricordando quali elementi sono già stati visitati - in generale (in modo che non li visiti più di una volta) e per raggiungere la posizione corrente (in modo da poter rilevare cicli). Quindi, lo stato imperativo di un algoritmo DFS è costituito dal nodo corrente, dall'insieme di nodi visitati e dall'insieme di nodi nel percorso corrente. Tutti questi dati dovranno essere forniti alle chiamate ricorsive e tutte le modifiche permanenti dovranno essere restituite da quelle stesse chiamate ricorsive.

Utilizzando la struttura del grafico dall'alto, combinata con una rappresentazione lista per i due set (non è certo ottimale - Set sarebbe una scelta migliore qui), l'algoritmo apparirebbe un po 'come questo:

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 

Tre dettagli importanti sopra: in primo luogo, DFS dice che hai finito di esplorare tutti i figli di un dato nodo, dovresti rimuovere quel nodo dall'elenco "percorso corrente" e inserirlo nell'elenco "visitato". Poiché utilizziamo strutture di dati immutabili, il primo passaggio non è necessario: il suo unico scopo era quello di annullare l'inserimento del nodo all'avvio dell'esplorazione e nella nostra versione l'elenco new_path non viene modificato dalla chiamata ricorsiva a explore. Questo è un esempio di caso in cui le strutture dati funzionali sono più comode da gestire rispetto alle strutture imperative.

Un altro dettaglio importante è l'uso di List.fold_left. Quando abbiamo iniziato a rendere esplicito lo stato, abbiamo sostituito funzioni imperative implicite di tipo -> unit con funzioni esplicite di tipo -> state -> .. -> state (accetta lo stato come parametro, restituisce nuovo stato).Quindi, l'elenco di esplorazione imperativo, che si presentava così:

f edge_1 ; f edge_2 ; f edge_3 

Ora si presenta così:

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

che è esattamente ciò List.fold_left f state [edge_1 ; edge_2 ; edge_3] fa. Tooting my horn personale, ma ho a nice article about this here.

Il terzo punto è che l'operazione "aggiungi elemento da impostare", quando si usano gli elenchi per rappresentare gli insiemi, viene scritta semplicemente come element :: set, perché questa è un'operazione che restituisce un nuovo set (elenco) che contiene tutti gli elementi di il set originale insieme al nuovo elemento. Questo lascia intatto il set originale (che è buono per le ragioni descritte nel primo passaggio) mentre si utilizza una quantità costante di memoria (crea una cella contro - una semplice coppia testa-coda contenente un riferimento all'elemento e un riferimento al set): non solo ottieni funzionalità di annullamento, ma lo fai senza costi aggiuntivi.

L'algoritmo di cui sopra "inserisce" i nodi in visited a partire dalle foglie dell'esplorazione DFS, che nel tuo caso rappresentano quei nodi che devono essere eseguiti per ultimi. In breve, la lista restituita è ordinata topologicamente, ma potrebbe non contenere tutti gli elementi perché il punto di partenza potrebbe non essere l'unico elemento radice (o addirittura essere un elemento radice). Quindi, qui c'è un ulteriore passaggio di elaborazione che consiste nel prendere un altro nodo dal grafico fino a quando tutto il grafico è stato esplorato.

O, in altre parole, a partire un'esplorazione nuova DFS da ogni nodo del grafo, ma ignorando tutti i nodi in precedenza esplorati - che equivale a tenere aggiornato l'elenco degli elementi visitati da un'esplorazione DFS per la prossima .

Con un piccolo tweak per il nostro algoritmo precedente, questo richiede solo due righe:

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 

Il tweak consiste nel permettere al chiamante di dfs per specificare l'elenco dei nodi già visitati. Portare l'elenco dei nodi visitati mentre si avvia un DFS da ogni nodo viene eseguito utilizzando List.fold_left esattamente come prima.

EDIT: a parte il tipo di eccezione, non c'è nulla qui che limiti il ​​tipo di elementi nel grafico. Tuttavia, un'eccezione non può essere polimorfica, quindi hai due possibili soluzioni. Il primo è quello di rinunciare effettivamente restituzione qualsiasi dato insieme con l'eccezione:

exception CycleFound 

... raise CycleFound ... 

Verrà ripristinata il tipo di toposort nuovo ad un più generico ('a * ('a list)) list -> 'a list.

L'altra soluzione è piuttosto avanzata OCaml: è necessario effettuare il moduloche contiene l'eccezione e l'ordinamento topologico polimorfica in quel tipo specifico, come segue:

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 

Ciò renderebbe il tipo di Topo(Node).sort essere (Node.t * (Node.t list)) list -> Node.t list, il che significa che è possibile ordinare qualsiasi tipo che si desidera definendo un modulo nodo con quel tipo:

y

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