ubergraph.alg

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

*auto-bellman-ford*

dynamic

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

all-destinations

(all-destinations paths)
All possible destinations we know how to get to

bellman-ford

(bellman-ford g start-node cost-attr)(bellman-ford g search-specification)
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

(bf-span g)(bf-span g start)
Returns a breadth-first spanning tree of the form {node [successors]}

bf-traverse

(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

(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

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

bipartite?

(bipartite? g)
Returns true if g is bipartite

coloring?

(coloring? g coloring)
Returns true if a map of nodes to colors is a proper coloring of a graph.

connect

(connect g)
Returns graph g with all connected components connected to each other

connected-components

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

(connected? g)
Returns true if g is connected

cost-of-path

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

(dag? g)
Returns true if g is a directed acyclic graph

degeneracy-ordering

(degeneracy-ordering g)
Returns sequence of vertices in degeneracy order.

distinct-edges

(distinct-edges g)
Distinct edges of g.

edges-in-path

(edges-in-path path)
A list of edges comprising the path

end-of-path

(end-of-path path)
Returns the last node in the path

greedy-coloring

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

last-edge-of-path

(last-edge-of-path path)
Returns the last edge in the path

loners

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

longest-shortest-path

(longest-shortest-path g start)
The longest shortest-path starting from start

maximal-cliques

(maximal-cliques g)
Enumerate the maximal cliques using Bron-Kerbosch.

nodes-in-path

(nodes-in-path path)
A list of nodes comprising the path

path-to

(path-to paths dest)
The shortest path to dest

paths->graph

(paths->graph paths)
Takes output of shortest-path and returns the graph of directed edges implied by the search process

post-traverse

(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

(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

(pre-span g)(pre-span g start)
Returns a depth-first spanning tree of the form {node [successors]}

pre-traverse

(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

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

shortest-path

(shortest-path g start-node end-node)(shortest-path g start-node end-node cost-attr)(shortest-path g search-specification)
Finds the shortest path in g, where g is either an ubergraph or a
transition function that implies a graph. A transition function 
takes the form: (fn [node] [{:dest successor1, ...} {:dest successor2, ...} ...])

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

(start-of-path path)
Returns the first node in the path

strongly-connected?

(strongly-connected? g)

topsort

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