ubergraph.alg — ubergraph 0.7.1

Contains algorithms that operate on Ubergraphs, and all the functions associated with paths

*auto-bellman-ford* clj

Bind this dynamic variable to false if you prefer for shortest-path to throw an error, if negative cost edge is found.

bellman-ford clj

(bellman-ford g search-specification)

(bellman-ford g start-node cost-attr)

Given an ubergraph g, and one or more start nodes, the Bellman-Ford algorithm produces an implementation of the IAllPathsFromSource protocol if no negative-weight cycle that is reachable from the source exits, and false otherwise, indicating that no solution exists.

bellman-ford is very similar to shortest-path. It is less efficient, but it correctly handles graphs with negative edges. If you know you have edges with negative costs, use bellman-ford. If you are unsure whether your graph has negative costs, or don't understand when and why you'd want to use bellman-ford, just use shortest-path and it will make the decision for you, calling this function if necessary.

Takes a search-specification map which must contain: Either :start-node (single node) or :start-nodes (collection)

Map may contain the following entries: Either :end-node (single node) or :end-nodes (collection) or :end-node? (predicate function) :cost-fn - A function that takes an edge as an input and returns a cost (defaults to weight, or 1 if no weight is present) :cost-attr - Alternatively, can specify an edge attribute to use as the cost :node-filter - A predicate function that takes a node and returns true or false. If specified, only nodes that pass this node-filter test will be considered in the search. :edge-filter - A predicate function that takes an edge and returns true or false. If specified, only edges that pass this edge-filter test will be considered in the search.

Map may contain the following additional entries if a traversal sequence is desired: :traverse true - Changes output to be a sequence of paths in order encountered. :min-cost - Filters traversal sequence, only applies if :traverse is set to true :max-cost - Filters traversal sequence, only applies if :traverse is set to true

bellman-ford has specific arity for the most common combination: (bellman-ford g start-node cost-attr)

bf-span clj

(bf-span g)

(bf-span g start)

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

bf-traverse clj

(bf-traverse g)

(bf-traverse g start)

(bf-traverse g start & opts)

Traverses graph g breadth-first from start. When option :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 option :when is provided, filters successors with (f neighbor predecessor depth).

bipartite-color clj

(bipartite-color g)

Attempts a two-coloring of graph g. When successful, returns a map of nodes to colors (1 or 0). Otherwise, returns nil.

bipartite-sets clj

(bipartite-sets g)

Returns two sets of nodes, one for each color of the bipartite coloring, or nil if g is not bipartite

bipartite? clj

(bipartite? g)

Returns true if g is bipartite

coloring? clj

(coloring? g coloring)

Returns true if a map of nodes to colors is a proper coloring of a graph.

connect clj

(connect g)

Returns graph g with all connected components connected to each other

connected-components clj

(connected-components g)

Returns the connected components of graph g as a vector of vectors. If g is directed, returns the weakly-connected components.

connected? clj

(connected? g)

Returns true if g is connected

cost-of-path clj

(cost-of-path path)

Returns the cost of the path with respect to the property that was minimized in the search that produced this path.

dag? clj

(dag? g)

Returns true if g is a directed acyclic graph

degeneracy-ordering clj

(degeneracy-ordering g)

Returns sequence of vertices in degeneracy order.

distinct-edges clj

(distinct-edges g)

Distinct edges of g.

edges-in-path clj

(edges-in-path path)

A list of edges comprising the path

end-of-path clj

(end-of-path path)

Returns the last node in the path

greedy-coloring clj

(greedy-coloring g)

Greedily color the vertices of a graph using the first-fit heuristic. Returns a map of nodes to colors (0, 1, ...).

loners clj

(loners g)

Return nodes with no connections to other nodes (i.e., isolated nodes)

longest-shortest-path clj

(longest-shortest-path g start)

The longest shortest-path starting from start

maximal-cliques clj

(maximal-cliques g)

Enumerate the maximal cliques using Bron-Kerbosch.

nodes-in-path clj

(nodes-in-path path)

A list of nodes comprising the path

path-to clj

(path-to paths dest)

The shortest path to dest

post-traverse clj

(post-traverse g)

(post-traverse g start & opts)

Traverses graph g depth-first, post-order from start. Returns a vector of the nodes.

pprint-path clj

(pprint-path p)

(pprint-path g p)

Prints a path's edges along with the edges' attribute maps. (pprint-path g p) will print the attribute maps currently stored in graph g for each edge in p. (pprint-path p) will print the attribute maps associated with each edge in p at the time the path was generated.

pre-span clj

(pre-span g)

(pre-span g start)

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

pre-traverse clj

(pre-traverse g)

(pre-traverse g start)

Traverses graph g depth-first from start. Returns a lazy seq of nodes. When no starting node is provided, traverses the entire graph, connected or not.

scc clj

(scc g)

Returns the strongly-connected components of directed graph g as a vector of vectors. Uses Kosaraju's algorithm.

shortest-path clj

(shortest-path g search-specification)

(shortest-path g start-node end-node)

(shortest-path g start-node end-node cost-attr)

Finds the shortest path in graph g. You must specify a start node or a collection of start nodes from which to begin the search, however specifying an end node is optional. If an end node condition is specified, this function will return an implementation of the IPath protocol, representing the shortest path. Otherwise, it will search out as far as it can go, and return an implementation of the IAllPathsFromSource protocol, which contains all the data needed to quickly find the shortest path to a given destination (using IAllPathsFromSource's path-to protocol function).

If :traverse is set to true, then the function will instead return a lazy sequence of the shortest paths from the start node(s) to each node in the graph in the order the nodes are encountered by the search process.

Takes a search-specification map which must contain: Either :start-node (single node) or :start-nodes (collection)

Map may contain the following entries: Either :end-node (single node) or :end-nodes (collection) or :end-node? (predicate function) :cost-fn - A function that takes an edge as an input and returns a cost (defaults to every edge having a cost of 1, i.e., breadth-first search if no cost-fn given) :cost-attr - Alternatively, can specify an edge attribute to use as the cost :heuristic-fn - A function that takes a node as an input and returns a lower-bound on the distance to a goal node, used to guide the search and make it more efficient. :node-filter - A predicate function that takes a node and returns true or false. If specified, only nodes that pass this node-filter test will be considered in the search. :edge-filter - A predicate function that takes an edge and returns true or false. If specified, only edges that pass this edge-filter test will be considered in the search.

Map may contain the following additional entries if a traversal sequence is desired: :traverse true - Changes output to be a sequence of paths in order encountered. :min-cost - Filters traversal sequence, only applies if :traverse is set to true :max-cost - Filters traversal sequence, only applies if :traverse is set to true

shortest-path has specific arities for the two most common combinations: (shortest-path g start-node end-node) (shortest-path g start-node end-node cost-attr)

start-of-path clj

(start-of-path path)

Returns the first node in the path

strongly-connected? clj

(strongly-connected? g)

topsort clj

(topsort g)

(topsort g start)

Topological sort of a directed acyclic graph (DAG). Returns nil if g contains any cycles.