pattern.nanopass.kahn — com.github.pangloss/pattern 1.0.435

kahn-sort clj

(kahn-sort g)

(kahn-sort g l s)

Proposes a topological sort for directed graph g using Kahn's algorithm, where g is a map of nodes to sets of nodes. If g is cyclic, returns nil.

A graph here is a map of sets representing a directed edge from the key to each element in its associated set.

The following represents a -> b and a -> c:

{:a #{:b :c}, :b #{}}

See also [[fermor.graph.algo/reverse-post-order-numbering]] for an alternate approach to topological sort which can handle cycles.

no-incoming clj

(no-incoming g)

Returns the set of nodes in graph g for which there are no incoming edges, where g is a map of nodes to sets of nodes.

normalize clj

(normalize g)

Returns g with empty outgoing edges added for nodes with incoming edges only. Example: {:a #{:b}} => {:a #{:b}, :b #{}}

take-1 clj

(take-1 s)

Returns the pair [element, s'] where s' is set s with element removed.

without clj

(without s x)

Returns set s with x removed.