1    Introduction

1.1    Overview

std.lib.sort provides graph and hierarchy sorting utilities beyond clojure.core.

2    Walkthrough

2.1    Hierarchical sorting

A hierarchy maps each node to the set of all its descendants. hierarchical-top finds the root node, and hierarchical-sort prunes redundant edges so that only direct children remain.

find the top of a hierarchy

(hierarchical-top
 {1 #{2 3 4 5 6}
  2 #{3 5 6}
  3 #{5 6}
  4 #{}
  5 #{6}
  6 #{}})
=> 1

prune a hierarchy to direct children only

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

2.2    Topological sorting

topological-sort orders nodes so that every dependency appears before the node that depends on it. Use topological-top to find nodes with no dependents, and find-cycle to diagnose cyclic graphs.

find nodes with no dependents

(topological-top {:a #{} :b #{:a}})
=> #{:b}

sort a dependency graph

(topological-sort {:a #{:b :c},
                   :b #{:d :e},
                   :c #{:e :f},
                   :d #{},
                   :e #{:f},
                   :f nil})
=> [:f :d :e :b :c :a]

detect a cycle in a graph

(find-cycle {:a #{:b}, :b #{:a}})
=> (fn [c] (and (= (count c) 3)
                (= (first c) (last c))
                (= (set c) #{:a :b})))

(find-cycle {:a #{:b}, :b #{}})
=> nil

topological sort throws on cycles

(topological-sort {:a #{:b}, :b #{:a}})
=> (throws)

2.3    Stable ordering by dependency count

topological-sort-order-by-deps takes an already topologically sorted list and reorders nodes at each level by how many dependencies they have, producing a stable, predictable ordering.

order nodes at each level by dependency count

(let [g {:a #{:b :c}
         :b #{:d :e}
         :c #{:e :f}
         :d #{}
         :e #{:f}
         :f nil}
      sorted (topological-sort g)]
  (topological-sort-order-by-deps g sorted))
=> [:d :f :e :b :c :a]

2.4    End-to-end: build and validate a task pipeline

Combining the functions above lets you validate and order a task graph. First check for cycles, then topologically sort, and finally refine the order by dependency count.

validate, sort, and refine a task graph

(let [tasks {:compile #{:lint :test}
             :lint    #{}
             :test    #{:lint}
             :deploy  #{:compile}}]
  (find-cycle tasks)
  => nil

  (topological-sort tasks)
  => [:lint :test :compile :deploy]

  (topological-sort-order-by-deps tasks (topological-sort tasks))
  => [:lint :test :compile :deploy])

3    API

find-cycle ^

[g]
Added 4.0

finds a cycle path in a directed graph

v 4.0
(defn find-cycle
  ([g]
   (letfn [(dfs [node visited path]
             (cond (visited node)
                   (let [idx (.indexOf path node)]
                     (conj (subvec path idx) node))

                   (seq (get g node))
                   (let [visited (conj visited node)]
                     (first (keep #(dfs % visited (conj path node))
                                  (get g node))))

                   :else nil))]
     (first (keep #(dfs % #{} []) (keys g))))))
link
(find-cycle {:a #{:b}, :b #{:a}})
=> (fn [c] (and (= (count c) 3)
                (= (first c) (last c))
                (= (set c) #{:a :b})))

(find-cycle {:a #{:b}, :b #{:c}, :c #{:b}})
=> (fn [c] (and (= (count c) 3)
                (= (first c) (last c))
                (= (set c) #{:b :c})
                (every? (fn [[a b]] (get-in {:a #{:b} :b #{:c} :c #{:b}} [a b]))
                        (partition 2 1 c))))

(find-cycle {:a #{:b}, :b #{}})
=> nil

hierarchical-sort ^

[idx]
Added 3.0

prunes a hierarchy of descendants into a directed graph

v 3.0
(defn hierarchical-sort
  ([idx]
   (let [top (hierarchical-top 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 #{}}

hierarchical-top ^

[idx]
Added 3.0

find the top node for the hierarchy of descendants

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

topological-sort ^

[g] [g l s]
Added 3.0

sorts a directed graph into its dependency order

v 3.0
(defn topological-sort
  ([g]
   (let [g (c/map-entries (fn [[k v]]
                            [k (disj v k)])
                          g)
         g (let [dependent-nodes (apply set/union (vals g))]
             (reduce #(if (get % %2) % (assoc % %2 #{})) g dependent-nodes))]
     (topological-sort g () (topological-top g))))
  ([g l s]
   (cond (empty? s)
         (if (every? empty? (vals g))
           l
           (let [remaining (->> g
                                (filter (fn [[k v]] (-> v empty? not)))
                                (into {}))
                 cycle     (find-cycle remaining)]
             (throw (ex-info (str "Graph Contains Circular Dependency: " (pr-str cycle))
                             {:data remaining
                              :list l
                              :cycle cycle}))))

         :else
         (let [[n s*] (if-let [item (first s)]
                        [item (set/difference s #{item})])
               m (g n)
               g* (reduce #(update-in % [n] set/difference #{%2}) g m)]
           (recur g* (cons n l) (set/union s* (set/intersection (topological-top 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)

(try (topological-sort {:a #{:b}, :b #{:a}})
     (catch clojure.lang.ExceptionInfo e
       (:cycle (ex-data e))))
=> (fn [c] (and (= (count c) 3)
                (= (first c) (last c))
                (= (set c) #{:a :b})))

topological-sort-order-by-deps ^

[g sorted-list]
Added 4.0

sorts topological sort by dependency size

v 4.0
(defn topological-sort-order-by-deps
  [g sorted-list]
  (loop [processed-nodes #{}
         result-list []
         remaining-list sorted-list]
    (if (empty? remaining-list)
      result-list
      (let [level-nodes (take-while #(every? processed-nodes (get g %))
                                  remaining-list)
            level-count (count level-nodes)
            sorted-level (sort-by (juxt (fn [n] (count (get g n))) identity) level-nodes)]
        (recur (apply conj processed-nodes sorted-level)
               (apply conj result-list sorted-level)
               (drop level-count remaining-list))))))
link
(let [g {:a #{:b :c}
         :b #{:d :e}
         :c #{:e :f}
         :d #{}
         :e #{:f}
         :f nil}
      sorted (topological-sort g)]
  (topological-sort-order-by-deps g sorted))
=> [:d :f :e :b :c :a]

(let [g {:a #{:c}
         :b #{:c}
         :c #{}}
      sorted (topological-sort g)]
  (topological-sort-order-by-deps g sorted))
=> [:c :a :b]

topological-top ^

[g]
Added 3.0

nodes that have no other nodes that are dependent on them

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

4    std.lib.sort: A Comprehensive Summary

The std.lib.sort namespace provides specialized sorting algorithms for hierarchical and directed graph structures. It offers functions to identify top-level nodes in a hierarchy, prune hierarchies into directed graphs, and perform topological sorting to determine dependency order. This module is crucial for managing complex relationships and dependencies within the foundation-base project, such as module loading, build processes, or data flow analysis.

Key Features and Concepts:

  1. Hierarchical Sorting:n hierarchical-top [idx]: Identifies the top-most node in a hierarchy represented by a map idx where keys are nodes and values are sets of their direct or indirect descendants. The top node is one that is not a descendant of any other node.n hierarchical-sort [idx]: Transforms a hierarchy of descendants into a directed graph where edges represent direct dependencies. It prunes indirect dependencies, resulting in a cleaner representation of immediate relationships.nn2. Topological Sorting:n topological-top [g]: Identifies nodes in a directed graph g that have no incoming dependencies (i.e., no other nodes depend on them). These are the starting points for a topological sort.n topological-sort [g & [l s]]: Sorts a directed graph g into a linear ordering of its nodes such that for every directed edge from node A to node B, A comes before B in the ordering.n It uses Kahn's algorithm (or a similar iterative approach).n It detects and throws an exception if the graph contains a circular dependency.n * The l (sorted list) and s (set of nodes with no incoming edges) arguments are used for the recursive/iterative process.

Usage and Importance:

The std.lib.sort module is essential for managing complex dependencies and ordering tasks within the foundation-base project. Its applications include:

  • Module Loading and Initialization: Determining the correct order in which modules or components should be loaded to satisfy their dependencies.n Build System Dependencies: Ordering compilation or build steps based on file or project dependencies.n Task Scheduling: Sequencing tasks in a workflow where some tasks must complete before others can start.n Data Flow Analysis: Understanding the flow of data through a system by ordering processing steps.n Graph Algorithms: Providing foundational algorithms for working with directed acyclic graphs (DAGs).

By offering robust algorithms for hierarchical and topological sorting, std.lib.sort significantly enhances the foundation-base project's ability to manage complex interdependencies, ensuring correct execution order and detecting circular dependencies, which is vital for its multi-language development ecosystem.

Related

jvm.artifactdocs

artifact coordinates and paths

jvm.classloaderdocs

classpath and classloaders

jvm.depsdocs

JVM dependency resolution

jvm.monitordocs

JVM metrics

jvm.namespacedocs

namespace management

jvm.protocoldocs

JVM extension protocols

jvm.reflectdocs

Java reflection

jvm.requiredocs

dependency-aware requiring