从 Parent/Child 关系创建嵌套映射

Question

给定一组 parent/child 关系，我该如何构建嵌套地图来显示此结构？

比如我要怎么转这个数据：

({"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" {}}}}

从 Parent/Child 关系创建嵌套映射

Create Nested Map From Parent/Child Relationships

clojure