idm.graph.alg
Algorithms for traversing the graph
Algorithms for traversing the graph
all-multipathsclj
(all-multipaths backlinks costs)Prepare an ubergraph-compatible representation of all possible multipaths based on a priority map of visited edges and a map of edge->siblings
Prepare an ubergraph-compatible representation of all possible multipaths based on a priority map of visited edges and a map of edge->siblings
arborescenceclj
(arborescence G r w)Calculate an arborescence in D rooted at r with cost fn w.
Minimum spanning tree algorithm for a directed graph.
See https://en.wikipedia.org/wiki/Edmonds%27_algorithm
w should be a function of the edge attributes map
Calculate an arborescence in `D` rooted at `r` with cost fn `w`. Minimum spanning tree algorithm for a directed graph. See https://en.wikipedia.org/wiki/Edmonds%27_algorithm `w` should be a function of the edge attributes map
edge->vectorclj
(edge->vector edge)Convert an Ubergraph edge to a vector of the form [src dest attrs], using the graph, which is stored on a given edge as metadata (usually) to retrieve the attributes.
Convert an Ubergraph edge to a vector of the form [src dest attrs], using the graph, which is stored on a given edge as metadata (usually) to retrieve the attributes.
find-multipathclj
(find-multipath edge-or-rel backlinks)Given the final relation id in a path, return a sequence of relation ids or sets of relation ids from the initial node(s) to the final relation.
Given the final *relation id* in a path, return a sequence of relation ids or sets of relation ids from the initial node(s) to the final relation.
least-cost-pathclj
(least-cost-path g
starting-nodes
goal?
may-final-edge?
cost-fn
node-filter
edge-filter)Finds the cheapest path satisfying the given constraints. Respects mult-edge relations (idm.graph.relation/[one->one, many->one, one->many])
Arguments:
g: graph
starting-nodes: set of initial, known nodes
goal?: function returning truthy value if a node is the target
may-final-edge?: function indicating whether or not a given edge may be final
cost-fn: function providing cost of a given edge
node-filter: function returning true when a given node is allowed
edge-filter: function returning true when a given edge is allowed
Finds the cheapest path satisfying the given constraints. Respects mult-edge relations (idm.graph.relation/[one->one, many->one, one->many]) Arguments: `g`: graph `starting-nodes`: set of initial, known nodes `goal?`: function returning truthy value if a node is the target `may-final-edge?`: function indicating whether or not a given edge may be final `cost-fn`: function providing cost of a given edge `node-filter`: function returning true when a given node is allowed `edge-filter`: function returning true when a given edge is allowed
least-cost-path-wrapperclj
(least-cost-path-wrapper g opts)(least-cost-path-wrapper g start-node end-node)(least-cost-path-wrapper g start-node end-node cost-attr)Wrapper function for least-cost-path and similar to work with and standardize the many options available.
Wrapper function for least-cost-path and similar to work with and standardize the many options available.
msp-directedclj
(msp-directed graph root cost-fn)multipathclj
(multipath backlinks costs last-edge last-rel)Create an object satisfying Ubergraph's IPath as well as IMultipath to represent a multipath.
Create an object satisfying Ubergraph's IPath as well as IMultipath to represent a multipath.
pprint-multipathclj
(pprint-multipath multipath)Pretty-print a multipath
Pretty-print a multipath
queue-entry->strclj
(queue-entry->str [edge prev-edge cost])Convert an entry in the priority queue into a string
Convert an entry in the priority queue into a string
cljdoc is a website building & hosting documentation for Clojure/Script libraries
× close