idm.graph.alg — edu.bard/idm.graph 0.1.0

Algorithms for traversing the graph

all-multipaths clj

(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

arborescence clj

(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

e->str clj

(e->str e)

Debug representation of an edge. Ignores attributes.

edge->vector clj

(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.

find-multipath clj

(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.

least-cost-path clj

(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

least-cost-path-wrapper clj

(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.

msp-directed clj

(msp-directed graph root cost-fn)

multipath clj

(multipath backlinks costs last-edge last-rel)

Create an object satisfying Ubergraph's IPath as well as IMultipath to represent a multipath.

Multipath clj protocol

Functions going beyond the Ubergraph IPath protocol to deal with extended requirements, such as retrieving lists of relations etc.

edge-sets clj

(edge-sets path)

A list of edge sets comprising a full traversal of this multipath. Even single edges will be wrapped in a set.

path clj

(path path)

Get a vector of edges and relations in this multipath. For a path with only one->one edges, equivalent to [[alg/edges-in-path]]

relations clj

(relations path)

A list of relations in this path

no-goal clj

Value indicating no actual goal

pprint-multipath clj

(pprint-multipath multipath)

Pretty-print a multipath

queue-entry->str clj

(queue-entry->str [edge prev-edge cost])

Convert an entry in the priority queue into a string

relation-for clj

(relation-for edge)

(relation-for graph edge)

Get the relation an edge belongs to. Relation will include type, id, and member edges.

When graph is not provided, assumes you know this is a one->one edge and completes as such.