Contains algorithms that operate on Ubergraphs, and all the functions associated with paths
Contains algorithms that operate on Ubergraphs, and all the functions associated with paths
Bind this dynamic variable to false if you prefer for shortest-path to throw an error, if negative cost edge is found.
Bind this dynamic variable to false if you prefer for shortest-path to throw an error, if negative cost edge is found.
(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)
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 g)
(bf-span g start)
Returns a breadth-first spanning tree of the form {node [successors]}
Returns a breadth-first spanning tree of the form {node [successors]}
(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).
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 g)
Attempts a two-coloring of graph g. When successful, returns a map of nodes to colors (1 or 0). Otherwise, returns nil.
Attempts a two-coloring of graph g. When successful, returns a map of nodes to colors (1 or 0). Otherwise, returns nil.
(bipartite-sets g)
Returns two sets of nodes, one for each color of the bipartite coloring, or nil if g is not bipartite
Returns two sets of nodes, one for each color of the bipartite coloring, or nil if g is not bipartite
(bipartite? g)
Returns true if g is bipartite
Returns true if g is bipartite
(coloring? g coloring)
Returns true if a map of nodes to colors is a proper coloring of a graph.
Returns true if a map of nodes to colors is a proper coloring of a graph.
(connect g)
Returns graph g with all connected components connected to each other
Returns graph g with all connected components connected to each other
(connected-components g)
Returns the connected components of graph g as a vector of vectors. If g is directed, returns the weakly-connected components.
Returns the connected components of graph g as a vector of vectors. If g is directed, returns the weakly-connected components.
(connected? g)
Returns true if g is connected
Returns true if g is connected
(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.
Returns the cost of the path with respect to the property that was minimized in the search that produced this path.
(dag? g)
Returns true if g is a directed acyclic graph
Returns true if g is a directed acyclic graph
(degeneracy-ordering g)
Returns sequence of vertices in degeneracy order.
Returns sequence of vertices in degeneracy order.
(edges-in-path path)
A list of edges comprising the path
A list of edges comprising the path
(end-of-path path)
Returns the last node in the path
Returns the last node in the path
(greedy-coloring g)
Greedily color the vertices of a graph using the first-fit heuristic. Returns a map of nodes to colors (0, 1, ...).
Greedily color the vertices of a graph using the first-fit heuristic. Returns a map of nodes to colors (0, 1, ...).
(loners g)
Return nodes with no connections to other nodes (i.e., isolated nodes)
Return nodes with no connections to other nodes (i.e., isolated nodes)
(longest-shortest-path g start)
The longest shortest-path starting from start
The longest shortest-path starting from start
(maximal-cliques g)
Enumerate the maximal cliques using Bron-Kerbosch.
Enumerate the maximal cliques using Bron-Kerbosch.
(nodes-in-path path)
A list of nodes comprising the path
A list of nodes comprising the path
(path-to paths dest)
The shortest path to dest
The shortest path to dest
(post-traverse g)
(post-traverse g start & opts)
Traverses graph g depth-first, post-order from start. Returns a vector of the nodes.
Traverses graph g depth-first, post-order from start. Returns a vector of the nodes.
(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.
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 g)
(pre-span g start)
Returns a depth-first spanning tree of the form {node [successors]}
Returns a depth-first spanning tree of the form {node [successors]}
(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.
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 g)
Returns the strongly-connected components of directed graph g as a vector of vectors. Uses Kosaraju's algorithm.
Returns the strongly-connected components of directed graph g as a vector of vectors. Uses Kosaraju's algorithm.
(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)
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 path)
Returns the first node in the path
Returns the first node in the path
(topsort g)
(topsort g start)
Topological sort of a directed acyclic graph (DAG). Returns nil if g contains any cycles.
Topological sort of a directed acyclic graph (DAG). Returns nil if g contains any cycles.
cljdoc is a website building & hosting documentation for Clojure/Script libraries
× close