从 Clojure 中表示为向量的树中获取边

Question

我有一棵这样的树：

[:root
  [:a [:b [:c [:g]]]]
  [:d [:e [:f [:g]]]]]

如何获取边缘，即：

[[:root :a] [:root :d] [:a :b] [:b :c] [:c :g] [:d :e] [:e :f] [:f :g]]

Answer 1

没有简单的 built-in 方法可以做到这一点。最简单的方法是滚动你自己的递归。

这是一个带有独特打嗝标签（无重复）的解决方案：

(ns tst.demo.core
  (:use tupelo.core tupelo.test)
  (:require
    [schema.core :as s]))

(def result (atom []))

(s/defn walk-with-path-impl
  [path :- [s/Any] ; parent path is a vector
   user-fn
   data :- [s/Any]] ; each data item is a hiccup vector
  (let [tag       (xfirst data)
        path-next (append path tag)]
    (user-fn path data)
    (doseq [item (xrest data)]
      (walk-with-path-impl path-next user-fn item))))

(defn walk-with-path!
  [user-fn data]
  (walk-with-path-impl [] user-fn data))

(s/defn print-edge
  [path :- [s/Any] ; parent path is a vector
   data :- [s/Any]] ; each data item is a hiccup vector
  (when (not-empty? path)
    (let [parent-node (xlast path)
          tag         (xfirst data)
          edge        [parent-node tag]]
      (swap! result append edge))))

单元测试显示输入数据&结果

(dotest
  (let [tree [:root
              [:a
               [:b
                [:c
                 [:z]]]]
              [:d
               [:e
                [:f
                 [:g]]]]]]
    (reset! result [])
    (walk-with-path! print-edge tree)
    (is= @result
      [[:root :a] [:a :b] [:b :c] [:c :z]
       [:root :d] [:d :e] [:e :f] [:f :g]])))

Here are the docs 用于 xfirst、append 等便利函数

Answer 2

我真的很喜欢你 post 你的问题 Scott Klarenbach，它真的是合成的。

我在原始 clojure 中提出了一个解决方案。棘手的部分是递归调用的位置以及如何处理这些递归调用的结果。

(def data
  [:root
   [:a [:b [:c [:g]]]]
   [:d [:e [:f [:g]]]]])

(defn get-edges [collection]
  (let [root (first collection)
        branches (rest collection)]
    (if (empty? branches)
      []
      (let [edges
            (mapv (fn [branch] [root (first branch)]) branches)
            sub-edges
            (->> branches
                 (mapcat (fn [branch] (get-edges branch)))
                 vec)]
        (if (empty? sub-edges)
          edges
          (vec (concat edges sub-edges)))))))

(get-edges data)
;; => [[:root :a] [:root :d] [:a :b] [:b :c] [:c :g] [:d :e] [:e :f] [:f :g]]

Answer 3

这是我在检查您的答案之前想到的。除非我遗漏了什么，否则似乎更惯用。

(defn vec->edges [v-tree]
  (->> v-tree
       (tree-seq vector? next)
       (mapcat (fn [[a & children]]
                 (map (fn [[b]] [a b]) children)))))

Answer 4

此方法使用基本循环（不需要额外的库或递归）：

(defn get-edges [tree]
  (loop [subtrees [tree]
         output []]
    (if (empty? subtrees)
      output
      (let [[[root & first-subtrees] & subtrees] subtrees]
        (recur (into subtrees first-subtrees)
               (into output (map #(-> [root (first %)])) first-subtrees))))))

在示例数据上测试它：

(get-edges [:root
            [:a [:b [:c [:g]]]]
            [:d [:e [:f [:g]]]]])
;; => [[:root :a] [:root :d] [:d :e] [:e :f] [:f :g] [:a :b] [:b :c] [:c :g]]

这是另一种基于惰性序列的方法：

(defn get-edges2 [tree]
  (->> [tree]
       (iterate #(into (rest %) (rest (first %))))
       (take-while seq)
       (mapcat (fn [subtrees]
                 (let [[[root & sub] & _] subtrees]
                   (map #(-> [root (first %)]) sub))))))

从 Clojure 中表示为向量的树中获取边

Get edges from tree represented as vector in Clojure

graph

clojure

tree

edges