loom.alg-generic — johannesloetzsch/loom 1.0.3-SNAPSHOT

Graph algorithms for use on any type of graph

ancestor? clj/s

(ancestor? ancestry childer parenter)

Finds if the 'parenter node is an ancestor of 'childer node for the given 'ancestry cache.

ancestors clj/s

(ancestors ancestry child)

Returns all of the ancestors of 'child node.

ancestry-add clj/s

(ancestry-add ancestry node & parents)

Adds a 'node and its 'parents associations to the 'ancestry cache.

ancestry-contains? clj/s

(ancestry-contains? ancestry node)

Finds if a 'node is contained in the 'ancestry cache.

ancestry-new clj/s

(ancestry-new)

Create a new, empty Ancestry cache.

ancestry-nodes clj/s

(ancestry-nodes ancestry)

Returns all of the nodes in an 'ancestry.

bf-path clj/s

(bf-path successors start end & {:as opts})

Returns a path from start to end with the fewest hops (i.e. irrespective of edge weights), successors being a function that returns adjacent nodes

bf-path-bi clj/s≠

(bf-path-bi outgoing predecessors start end)

clj

Using a bidirectional breadth-first search, finds a path from start to end with the fewest hops (i.e. irrespective of edge weights), outgoing and predecessors being functions which return adjacent nodes. Can be much faster than a unidirectional search on certain types of graphs

bf-paths-bi clj/s

(bf-paths-bi successors predecessors start end)

Using a bidirectional breadth-first search, returns all shortest paths from start to end; predecessors is called on end and each preceding node, successors is called on start, etc.

bf-span clj/s

(bf-span successors start & {:keys [seen]})

Return a breadth-first spanning tree of the form {node [successors]}

bf-traverse clj/s

(bf-traverse successors start & {:keys [f when seen]})

Traverses a graph breadth-first from start, successors being a function that returns adjacent nodes. When :f is provided, returns a lazy seq of (f node predecessor-map depth) for each node traversed. Otherwise, returns a lazy seq of the nodes. When :when is provided, filters successors with (f neighbor predecessor depth).

bits-per-long clj/s

bm-get clj/s

(bm-get bitmap idx)

Get boolean state of bit in 'bitmap at 'idx.

bm-get-indicies clj/s

(bm-get-indicies bitmap)

Get the indicies of set bits in 'bitmap.

bm-longs clj/s

(bm-longs bits)

Returns the number of longs required to store bits count bits in a bitmap.

bm-new clj/s

(bm-new)

Create new empty bitmap.

bm-or clj/s

(bm-or & bitmaps)

Logically OR 'bitmaps together.

bm-set clj/s

(bm-set bitmap idx)

Set boolean state of bit in 'bitmap at 'idx to true.

dijkstra-path clj/s

(dijkstra-path successors dist start end)

Finds the shortest path from start to end, where successors and dist are functions called as (successors node) and (dist node1 node2)

dijkstra-path-dist clj/s

(dijkstra-path-dist successors dist start end)

Finds the shortest path from start to end, where successors and dist are functions called as (successors node) and (dist node1 node2). Returns a vector: [path distance]

dijkstra-span clj/s

(dijkstra-span successors dist start)

Finds all shortest distances from start, where successors and dist are functions called as (successors node) and (dist node1 node2). Returns a map in the format {node {successor distance}}

dijkstra-traverse clj/s

(dijkstra-traverse successors dist start)

(dijkstra-traverse successors dist start f)

Returns a lazy-seq of [current-node state] where state is a map in the format {node [distance predecessor]}. When f is provided, returns a lazy-seq of (f node state) for each node

paths clj/s

(paths preds path)

Returns a lazy seq of all non-looping path vectors starting with [<start-node>]

post-edge-traverse clj/s

(post-edge-traverse successors
                    start
                    &
                    {:keys [seen return-seen] :or {seen #{}}})

Traverses a graph depth-first postorder from start, successors being a function that returns direct successors for the node. Returns a seq of edges, each edge being a vector [source-node dest-node]. Note that for undirected graphs each edge will be returned twice, once for each direction.

post-traverse clj/s

(post-traverse successors start & {:keys [seen return-seen] :or {seen #{}}})

Traverses a graph depth-first postorder from start, successors being a function that returns adjacent nodes. Returns a vector

pre-edge-traverse clj/s

(pre-edge-traverse successors start & {:keys [seen] :or {seen #{}}})

Traverses a graph depth-first preorder from start, successors being a function that returns direct successors for the node. Returns a lazy seq of edges, each edge being a vector [source-node dest-node]. Note that for undirected graphs each edge will be returned twice, once for each direction.

pre-span clj/s

(pre-span successors start & {:keys [seen return-seen] :or {seen #{}}})

Returns a depth-first spanning tree of the form {node [successors]}

pre-traverse clj/s

(pre-traverse successors start & {:keys [seen] :or {seen #{}}})

Traverses a graph depth-first preorder from start, successors being a function that returns direct successors for the node. Returns a lazy seq of nodes.

preds->span clj/s

(preds->span preds)

Converts a map of the form {node predecessor} to a spanning tree of the form {node [successors]}

topsort-component clj/s

(topsort-component successors start)

(topsort-component successors start seen explored)

Topological sort of a component of a (presumably) directed graph. Returns nil if the graph contains any cycles. See loom.alg/topsort for a complete topological sort

trace-path clj/s

(trace-path preds node)

Using a map of nodes-to-preds, traces a node's family tree back to the source. Cycles are not accounted for.

trace-paths clj/s

(trace-paths preds start)

Given a function and a starting node, returns all possible paths back to source. Cycles are not accounted for.