hara.sort micellaneous sorting functions

Author: Chris Zheng  (z@caudate.me)
Date: 29 June 2017
Repository: https://github.com/zcaudate/hara
Version: 2.5.10

hara.sort contain functions and utilities for sorting algorithms.

1    sort.hierarchical

Add to project.clj dependencies:

[im.chit/hara.sort.hierarchical "2.5.10"]

hara.sort.hierarchical gives a list of dependents for each key



hierarchical-sort ^

prunes a hierarchy of descendants into a directed graph

v 2.2
(defn hierarchical-sort
  [idx]
  (let [top (top-node idx)]
    (loop [out {}
          candidates (dissoc idx top)
           level #{top}]
      (if (empty? level)
        out
        (let [base  (apply set/union (vals candidates))
              out   (reduce (fn [out i]
                              (assoc out i (set/difference (get idx i) base)))
                            out
                            level)
              nlevel (mapcat #(get out %) level)
              ncandidates (apply dissoc idx (concat (keys out) nlevel))]
          (recur out
                 ncandidates
                 nlevel))))))
link
(hierarchical-sort {1 #{2 3 4 5 6} 2 #{3 5 6} 3 #{5 6} 4 #{} 5 #{6} 6 #{}}) => {1 #{4 2} 2 #{3} 3 #{5} 4 #{} 5 #{6} 6 #{} }

top-node ^

find the top node for the hierarchy of descendants

v 2.2
(defn top-node
  [idx]
  (let [rest (apply set/union (vals idx))]
    (ffirst (filter (fn [[k v]]
                     (not-empty (set/difference (conj v k) rest)))
                    idx))))
link
(top-node {1 #{2 3 4 5 6} 2 #{3 5 6} 3 #{5 6} 4 #{} 5 #{6} 6 #{}}) => 1

2    sort.topological

Add to project.clj dependencies:

[im.chit/hara.sort.topological "2.5.10"]

hara.sort.topological gives an order of preference for a set of hierarchies



top-nodes ^

nodes that have no other nodes that are dependent on them

v 2.1
(defn top-nodes
  [g]
  (let [nodes (set (keys g))
        dependent-nodes (apply union (vals g))]
    (difference nodes dependent-nodes)))
link
(top-nodes {:a #{} :b #{:a}}) => #{:b}

topological-sort ^

sorts a directed graph into its dependency order

v 2.1
(defn topological-sort
  ([g]
     (let [g (let [dependent-nodes (apply union (vals g))]
               (reduce #(if (get % %2) % (assoc % %2 #{})) g dependent-nodes))]
       (topological-sort g () (top-nodes g))))
  ([g l s]
     (cond (empty? s)
           (if (every? empty? (vals g))
             l
             (throw (Exception. (str "Graph Contains Circular Dependency: "
                                     (->> g
                                          (filter (fn [[k v]] (-> v empty? not)))
                                          (into {}))))))

           :else
           (let [[n s*] (if-let [item (first s)]
                          [item (difference s #{item})])
                 m (g n)
                 g* (reduce #(update-in % [n] difference #{%2}) g m)]
             (recur g* (cons n l) (union s* (intersection (top-nodes g*) m)))))))
link
(topological-sort {:a #{:b :c}, :b #{:d :e}, :c #{:e :f}, :d #{}, :e #{:f}, :f nil}) => [:f :d :e :b :c :a] (topological-sort {:a #{:b}, :b #{:a}}) => (throws Exception)