digraph

Directed graph library written in pure Clojure. Many algorithms have yet to be written, but it's polished enough to publish and open to the community. Pull requests encouraged!

Features so far:

• Full clojure.spec coverage, ready to be extended
• Topological sort via Kahn's algorithm
• Cycle detection
• Indegree and outdegree
• Sink/source/internal/stranded node operations

The use of specs does indeed require Clojure version >= 1.9.0.

Usage

Require the namespace:

(require '[digraph.core :as d])

Define a graph:

(def g (make-digraph #{1 2 3} [1 2] [1 3] [1 4]))

; Check that the graph conforms to the spec
(s/valid? ::d/digraph g)
=> true

; Acyclic?
(s/valid? ::d/dag g)
=> true

Examples:

; Find all the sink nodes
(filter #(d/sink? g %) (:nodes g))
=> (3)

; Sort nodes topologically
(d/topological-sort g)
=> [1 2 3]

; Detect cycles
(d/cyclic? g)
=> false

Check the core namespace for other possible operations, as well as the clojure.spec definitions. These can be very helpful for extending directed graphs into, say, a network. For an example, check out kranium.

Development

Refresh all namespaces in dependency order:

; At the REPL
(refresh)

All digraph namespaces are available from the user namespace by their short names:

; digraph.core/some-fn would be
(core/some-fn)

Auto run the tests upon file change:

lein auto test

The user namespace automatically calls (st/instrument). Any defined specs will be instrumented while working at the REPL. Note that the user namespace is not loaded in production builds; it is a development dependency only.

License

Copyright © 2017 Calvin Sauer

Distributed under the Eclipse Public License version 1.0