부모/자식 관계에서 중첩 된지도 만들기

Question

부모/자식 관계의 모음이 주어지면 중첩 된지도를 작성하여이 구조를 표시하려면 어떻게해야합니까? 이 속으로

({"child" "1.1", 
    "parent" "1"} 
{"child" "1.2", 
    "parent" "1"} 
{"child" "1.3", 
    "parent" "1"} 
{"child" "1.4", 
    "parent" "1"} 
{"child" "1.1.1", 
    "parent" "1.1"} 
{"child" "1.1.2", 
    "parent" "1.1"} 
{"child" "2.1", 
    "parent" "2"} 
{"child" "2.2", 
    "parent" "2"} 
{"child" "2.3", 
    "parent" "2"}) 

:

{"1" {"1.1" {"1.1.1" {} 
      "1.1.2" {}} 
     "1.2" {} 
     "1.3" {} 
     "1.4" {}} 
"2" {"2.1" {} 
     "2.2" {} 
     "2.3" {}}} 

내가 함께 일하고 실제 데이터는 다음과 같습니다

({"child" "94bf72cb-01cd-4430-b669-b2e954b5639b", 
    "parent" "6378daf6-3b7f-4cf4-8156-a50cf5f7b6ef"} 
{"child" "8c9c57a0-d20d-4474-9afb-c9d17df83a91", 
    "parent" "6378daf6-3b7f-4cf4-8156-a50cf5f7b6ef"} 
{"child" "73d2a203-e3c1-4d2f-aaf8-a9f2e870792b", 
    "parent" "6378daf6-3b7f-4cf4-8156-a50cf5f7b6ef"} 
{"child" "669fe949-057f-43c0-af7b-ff39594a183d", 
    "parent" "6378daf6-3b7f-4cf4-8156-a50cf5f7b6ef"} 
{"child" "1ceff8fe-a0a8-46ad-81a8-d13fb837aaf6", 
    "parent" "94bf72cb-01cd-4430-b669-b2e954b5639b"} 
{"child" "ba96a425-a3f0-4ce5-8c19-6ea9add14013", 
    "parent" "94bf72cb-01cd-4430-b669-b2e954b5639b"} 
{"child" "160f34ac-68b9-4c8e-930b-1ab6df895df4", 
    "parent" "1ce9b863-5681-4660-85e7-fbd0cc184aed"} 
{"child" "58825b50-23bc-4204-8f8d-c9a9d3ac8beb", 
    "parent" "1ce9b863-5681-4660-85e7-fbd0cc184aed"} 
{"child" "4b1763f9-8380-4507-9a8f-5c86878e49a9", 
    "parent" "1ce9b863-5681-4660-85e7-fbd0cc184aed"}) 

Answer 1

당신은 변환 할 수 있습니다 내가이 데이터를 설정하는 방법을 예를 들어

, 하위 관계를 인접 목록으로 가져온 다음 비순환 방향 그래프를 탐색하여 중첩 된지도를 만듭니다.

(defn adjacency-list [coll] 
    (reduce (fn [r {p "parent" c "child"}] 
      (-> r 
       (update-in [:counts p] #(or % 0)) 
       (update-in [:counts c] #(if % (inc %) 1)) 
       (update-in [:adjacency p] #(if % (conj % c) [c])))) 
      {} 
      coll)) 

(defn root-nodes [counts] 
    (mapv key 
     (filter (comp zero? val) counts))) 

(defn traverse [m al roots] 
    (reduce (fn [r k] 
      (assoc r k 
        (if-let [v (get al k)] 
        (traverse {} al v) 
        {}))) 
      m 
      roots)) 

(def data '({"child" "1.1", "parent" "1"} {"child" "1.2", "parent" "1"} {"child" "1.3", "parent" "1"} {"child" "1.4", "parent" "1"} {"child" "1.1.1", "parent" "1.1"} {"child" "1.1.2", "parent" "1.1"} {"child" "2.1", "parent" "2"} {"child" "2.2", "parent" "2"} {"child" "2.3", "parent" "2"})) 

(let [{:keys [counts adjacency]} (adjacency-list data)] 
    (clojure.pprint/pprint (traverse {} adjacency (root-nodes counts)))) 

;=> {"2" {"2.3" {}, "2.2" {}, "2.1" {}}, 
; "1" {"1.4" {}, "1.3" {}, "1.2" {}, "1.1" {"1.1.2" {}, "1.1.1" {}}}}