Нахождение путей в (DAG) ориентированный ациклический граф данное назначение

Question

Допустим, у меня есть этот массив:

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

где первая int в кортеж докладов второму int.

я могу карту, что на самом деле легко с

let orgMap = Map.ofArray reporting 

Оттуда, я мог бы легко получить список всех Интс, сообщающих до 2 с

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

который возвращает

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

То, что я действительно хотел бы видеть, однако, это вся структура, от 2 до упора вниз. Например, я хотел бы найти способ, который может дать мне пример вывода

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

если я ищу человека 2 или

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

если я заинтересован лично 3.

Могу ли я это сделать? Если да, то как? Есть ли другая структура, отличная от map, что было бы лучшим способом сделать это?

Заранее за вашу помощь.

Answer 1

Поскольку OCaml близок к F # и пытается найти топологическую сортировку в F #, ничего не помогло, я искал код OCaml.

Я нашел An Introduction to Objective Caml, у которого было решение проблемы с использованием метода Depth First Search и использовалось в качестве основы для этого ответа. Кроме того, поскольку вы новичок в F #, вы можете просмотреть документ и посмотреть, как происходит вывод кода. Как ни странно, я просмотрел оставшуюся часть документа после публикации этого сообщения, и у него есть более продвинутая версия DFS в документе.

Ваш вход представляет собой массив [| |], но ваш ответ - это список [], поэтому я сделал большую часть работы как список.

Ответы не в том порядке, как были у вас, но они в одном формате.

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

Я предполагаю, что вы хотите получить список пара int с «цифрами», которые прямо или косвенно сообщают о некотором «root». Вот простое, но неэффективное решение:

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 

Если вы хотите реализовать эффективное решение, вы должны интерпретировать reportStructureSet в виде графика в следующем виде:

• int s является вершинами
• пара от int s - направленные ребра

Затем просто проверьте, какой e dges достижимы от «root», используя DFS.

Answer 3

Мне нравятся головоломки f #, поэтому я сделал удар в этом месте. Надеюсь, вам понравится.

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 

возвращает

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

findReports 2 возвращает

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

---

я сломаю его вниз, чтобы уточнить.

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

Мы список кортежей и создать функциональную карту босса (список (отчет, босс)). Это может быть известно как список смежности, который используется для перемещения графиков.

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

Если есть список отчетов под боссом, добавьте в этот список.

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

В противном случае добавьте в пустой список и вставьте в словарь.

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

Начните с пустой карты как аккумулятора.

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

Считать предметы, чтобы найти все отчеты.

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

Если есть предмет, добавьте его в аккумулятор. Это BFS. Если вы переключите выражение до и после оператора конкатенации (@), оно станет DFS.

 | 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 7 

Возврат только отчеты

|> List.map fst 

Не передавать отчет дважды.

|> List.distinct