VARS

->DirectedGraph

add-loops

component-graph

dependency-list

fixed-point

fold-into-sets

get-neighbors

lazy-walk

map->DirectedGraph

post-ordered-nodes

post-ordered-visit

recursive-component?

remove-loops

reverse-graph

scc

self-recursive-sets

stratification-list

transitive-closure

->DirectedGraph

add-loops

component-graph

dependency-list

fixed-point

fold-into-sets

get-neighbors

lazy-walk

map->DirectedGraph

post-ordered-nodes

post-ordered-visit

recursive-component?

remove-loops

reverse-graph

scc

self-recursive-sets

stratification-list

transitive-closure

« Index of all namespaces of this project

Basic graph theory algorithms

`(component-graph g)`

`(component-graph g sccs)`

Given a graph, perhaps with cycles, return a reduced graph that is acyclic. Each node in the new graph will be a set of nodes from the old. These sets are the strongly connected components. Each edge will be the union of the corresponding edges of the prior graph.

`(dependency-list g)`

Similar to a topological sort, this returns a vector of sets. The set of nodes at index 0 are independent. The set at index 1 depend on index 0; those at 2 depend on 0 and 1, and so on. Those withing a set have no mutual dependencies. Assume the input graph (which much be acyclic) has an edge a->b when a depends on b.

`(fixed-point data fun max equal)`

Repeatedly apply fun to data until (equal old-data new-data) returns true. If max iterations occur, it will throw an exception. Set max to nil for unlimited iterations.

`(lazy-walk g n)`

`(lazy-walk g ns v)`

Return a lazy sequence of the nodes of a graph starting a node n. Optionally, provide a set of visited notes (v) and a collection of nodes to visit (ns).

`(map->DirectedGraph m__7585__auto__)`

Factory function for class datalog.graph.DirectedGraph, taking a map of keywords to field values.

Private

`(post-ordered-visit g n [visited acc :as state])`

Starting at node n, perform a post-ordered walk.

`(reverse-graph g)`

Given a directed graph, return another directed graph with the order of the edges reversed.

`(self-recursive-sets g)`

Returns, as a sequence of sets, the components of a graph that are self-recursive.

`(stratification-list g1 g2)`

Similar to dependency-list (see doc), except two graphs are provided. The first is as dependency-list. The second (which may have cycles) provides a partial-dependency relation. If node a depends on node b (meaning an edge a->b exists) in the second graph, node a must be equal or later in the sequence.

`(transitive-closure g)`

Returns the transitive closure of a graph. The neighbors are lazily computed. Note: some version of this algorithm return all edges a->a regardless of whether such loops exist in the original graph. This version does not. Loops will be included only if produced by cycles in the graph. If you have code that depends on such behavior, call (-> g transitive-closure add-loops)