percorsi trovando in (DAG) indirizzati grafo aciclico determinata destinazione

Question

Diciamo che ho questo array:

let reportStructure = [|(2, 1); (3, 2); (4, 2); (5, 3); (6, 4); (7, 3)|] 

dove il primo int in un report tuple al secondo int.

posso mappare che in realtà facilmente con

let orgMap = Map.ofArray reporting 

Da lì, ho potuto facilmente ottenere un elenco di tutti gli interi che riportano a 2 con

orgMap 
|> Map.filter (fun _ key -> key = 2) 

che restituisce

map [(3, 2); (4, 2)] 

Quello che mi piacerebbe davvero vedere, tuttavia, è l'intera struttura, dal 2 fino in fondo. Ad esempio, mi piacerebbe trovare un modo che mi potesse dare il campione di uscita

map [(3, 2); (4, 2); (5, 3); (6, 4); (7, 3)] 

se sto cercando persona 2 o

map [(5, 3); (7, 3)] 

se sono interessato a persona 3.

Posso fare questo? Se é cosi, come? C'è un'altra struttura oltre a un map che sarebbe un modo migliore per farlo accadere?

Grazie in anticipo per il vostro aiuto.

Answer 1

Dal OCaml è vicino a F # e cercando di trovare sorta topologico in F # non era di alzare qualcosa di utile Ho guardato il codice OCaml.

ho trovato An Introduction to Objective Caml che aveva una soluzione al vostro problema utilizzando ricerca in profondità e lo usò come base per questa risposta. Inoltre, dato che sei nuovo su F # puoi rivedere il documento e vedere come viene derivato il codice. Stranamente ho dato un'occhiata al resto del documento dopo aver postato questo e ha una versione più avanzata di DFS nel documento.

Il tuo input è un array [| |] ma la tua risposta è una lista [] quindi ho fatto la maggior parte del lavoro come lista.

Le risposte non sono nello stesso ordine come si doveva, ma sono nello stesso formato.

let reportStructure = [|(2, 1); (3, 2); (4, 2); (5, 3); (6, 4); (7, 3)|] 

    // 
    // 6 -> 4 -> 2 
    // 5 -> 3 -> 2 -> 1 
    // 7 -> 3 

    // val revStructure : tl:('a * 'b) list -> ('b * 'a) list 
    let revStructure tl = List.map (fun (a,b) -> (b,a)) tl 

    // val mem : item:'a -> list:'a list -> bool when 'a : equality 
    let mem item list = List.exists (fun x -> x = item) list 

    // val successors : n:'a -> edges:('a * 'b) list -> 'b list when 'a : equality 
    let successors n edges = 
     let matching (s,_) = s = n 
     List.map snd (List.filter matching edges) 

    // val dist : pred:'a -> succs:'b list -> ('a * 'b) list 
    let dist pred succs = List.map (fun y -> (pred,y)) succs 

    // val dfsPairs : edges:('a * 'a) list -> start:'a -> ('a * 'a) list when 'a : equality 
    let dfsPairs edges start = 
     let rec dfsPairsInner edges visited start result = 
      match start with 
      | [] -> List.rev (revStructure result) 
      | n::nodes -> 
       if mem n visited then 
        dfsPairsInner edges visited nodes result 
       else 
        let predecessors = dist n (successors n edges) 
        let result = 
         match predecessors with 
         | [] -> result 
         | _ -> predecessors @ result 
        dfsPairsInner edges (n::visited) ((successors n edges) @ nodes) result 
     dfsPairsInner edges [] [start] [] 

    let revEdges = revStructure (List.ofArray reportStructure) 

    let result = dfsPairs revEdges 2 
    // val result : (int * int) list = [(4, 2); (3, 2); (7, 3); (5, 3); (6, 4)] 

    let result = dfsPairs revEdges 3 
    // val result : (int * int) list = [(7, 3); (5, 3)] 

Answer 2

presumo che si desidera ottenere un elenco di coppia di interi con "numeri" che riportano direttamente o indirettamente ad alcuni "root". Qui è una soluzione semplice ma inefficiente:

let reportStructure = [|(2, 1); (3, 2); (4, 2); (5, 3); (6, 4); (7, 3)|] 

let reportStructureSet = 
    reportStructure |> Set.ofArray 

let reportingDirectlyTo root raportsToSet = 
    raportsToSet 
    |> Set.filter(fun (_, key) -> key = root) 

let addNextGeneration previousIteration raportsToSet = 
    let numbersLowerInHierarchy = previousIteration |> Set.map fst 
    raportsToSet |> Set.filter(
     // select only those elements from raportsToSet... 
     fun (num, supervisor) -> 
      // ...which either are already in previousIteration 
      (Set.contains (num, supervisor) previousIteration) || 
      // ...or are "below" someone from previousIteration 
      (Set.contains supervisor numbersLowerInHierarchy)) 

let reportingDirectlyOrIndirectlyTo root raportsToSet = 
    // applies addNextGeneration until is "stabilizes" on some value 
    let rec fixPointHelper previousIteration = 
     let nextIteration = addNextGeneration previousIteration raportsToSet 
     if nextIteration = previousIteration 
      then nextIteration 
      else fixPointHelper nextIteration 

    // set of numbers directly reporting to root 
    let reportsDirectly = reportingDirectlyTo root raportsToSet 
    // start "iteration" using numbers directly reporting to root 
    fixPointHelper reportsDirectly 

let reportingDirectlyOrIndirectlyToList root raportsToSet = 
    reportingDirectlyOrIndirectlyTo root raportsToSet 
    |> Set.toList 

Se si desidera implementare una soluzione efficiente, si dovrebbe interpretare reportStructureSet come un grafico nel seguente modo:

• int s sono vertici
• coppia di int s sono i bordi diretti

Quindi è sufficiente verificare quale e i dges sono raggiungibili da "root" usando un DFS.

Answer 3

Mi piacciono i puzzle f #, quindi ho preso una pugnalata a questo. Spero che ti piaccia.

let orgList = [(2, 1); (3, 2); (4, 2); (5, 3); (6, 4); (7, 3)] 

let orgMap = 
    orgList 
    |> List.fold (fun acc item -> 
     let key = snd item 
     match Map.tryFind key acc with 
     | Some(value) -> 
      let map' = Map.remove key acc 
      Map.add(key) (item::value) map' 
     | None -> 
      Map.add(key) (item::[]) acc 
     ) Map.empty<int, (int*int) list> 

let findReports supervisor = 
    let rec findReports' acc collection = 
     match collection with 
     | head::tail -> 
      (findReports' (head::acc) tail) 
      @ match Map.tryFind (fst head) orgMap with 
       | Some(value) -> (findReports' [] value) 
       | None -> [] 
     | [] -> acc  
    findReports' [] (Map.find supervisor orgMap)  

findReports 2 
|> List.map fst 
|> List.distinct 

rendimenti

val it : int list = [3; 4; 5; 7; 6] 

findReports 2 restituisce

val it : (int * int) list = [(3, 2); (4, 2); (5, 3); (7, 3); (6, 4)] 

---

ti rompo il basso per chiarire.

let orgList = [ (1, 2); (1, 3); (1, 4); (2, 5); (3, 6); (4, 5); (5, 6); (5, 7) ] 

Prendiamo la vostra lista di tuple e creare una mappa funzionale di capo per (elenco (rapporto, capo)). Questo potrebbe essere conosciuto come un elenco di adiacenze, che viene utilizzato per i grafici di attraversamento.

let orgMap = 
    orgList 
    |> List.fold (fun acc item -> 
     let key = snd item 
     match Map.tryFind key acc with 

Se è presente un elenco di rapporti sotto un capo, aggiungere a tale elenco.

 | Some(reports) -> 
      let map' = Map.remove key acc 
      Map.add(key) (item::reports) map' 

In caso contrario, aggiungere a una lista vuota e inserire nel dizionario.

 | None -> 
      Map.add(key) (item::[]) acc 

Iniziare con una mappa vuota come accumulatore.

 ) Map.empty<int, (int*int) list> 

Recurse attraverso gli articoli per trovare tutti i report.

let findReports supervisor = 
    let rec findReports' acc collection = 
     match collection with 

Se è presente un articolo, aggiungerlo all'accumulatore. Questo è BFS. Se si cambia l'espressione prima e dopo l'operatore concatenato (@), diventerà DFS.

Concatena l'elenco corrente all'elenco ricorsivo di rapporti ai rapporti.

  @ match Map.tryFind (fst head) orgMap with 
       | Some(value) -> (findReports' [] value) 
       | None -> [] 

Se alla fine dell'elenco, restituire l'elenco.

 | [] -> acc  

Eseguire la funzione ricorsiva.

findReports' [] (Map.find supervisor orgMap)  

Eseguire la funzione.

findReports 7 

restituire solo i rapporti

|> List.map fst 

non riportano il rapporto due volte.

|> List.distinct