loom.alg
(source)Graph algorithms. Any graph record/type that satisfies the
Graph, Digraph, or WeightedGraph protocols (as appropriate per algorithm)
can use these functions.
For more info about this library see:
https://cljdoc.org/d/aysylu/loom/1.0.2/doc/readme| Public Variable | Short Description |
|---|---|
| all-pairs-shortest-paths (clj) | Finds all-pairs shortest paths in a graph. |
| astar-dist (clj) | Returns the length of the shortest path between src and target using the A* algorithm. |
| astar-path (clj) | Returns the shortest path using A* algorithm. |
| bellman-ford (clj) | Given a weighted, directed graph G = (V, E) with source start, the Bellman-Ford algorithm produces map of single source shortest paths and their costs if no negative-weight cycle that is reachable from the source exists, and false otherwise, indicating that no solution exists. |
| bf-all-pairs-shortest-paths (clj) | Uses bf-span on each node in the graph. |
| bf-path (clj) | Returns a path from start to end with the fewest hops (i.e. |
| bf-path-bi (clj) | Using a bidirectional breadth-first search, finds a path from start to end with the fewest hops (i.e. |
| bf-span (clj) | Returns a breadth-first spanning tree of the form {node [successors]}. |
| bf-traverse (clj) | Traverses graph g breadth-first from start. |
| bipartite-color (clj) | Attempts a two-coloring of graph g. |
| bipartite-sets (clj) | Returns two sets of nodes, one for each color of the bipartite coloring, or nil if g is not bipartite. |
| bipartite? (clj) | Returns true if g is bipartite. |
| coloring? (clj) | Returns true if a map of nodes to colors is a proper coloring of a graph. |
| connect (clj) | Returns graph g with all connected components connected to each other. |
| connected-components (clj) | Returns the connected components of graph g as a vector of vectors. |
| connected? (clj) | Returns true if g is connected. |
| dag? (clj) | Returns true if g is a directed acyclic graph. |
| degeneracy-ordering (clj) | Returns sequence of vertices in degeneracy order. |
| density (clj) | Return the density of graph g. |
| dijkstra-path (clj) | Finds the shortest path from start to end. |
| dijkstra-path-dist (clj) | Finds the shortest path from start to end. |
| dijkstra-span (clj) | Finds all shortest distances from start. |
| dijkstra-traverse (clj) | Returns a lazy-seq of [current-node state] where state is a map in the format {node [distance predecessor]}. |
| distinct-edges (clj) | Returns the distinct edges of g. |
| eql? (clj) | Returns true iff g1 is a subgraph of g2 and g2 is a subgraph of g1. |
| greedy-coloring (clj) | Greedily color the vertices of a graph using the first-fit heuristic. |
| isomorphism? (clj) | Given a mapping phi between the vertices of two graphs, determine if the mapping is an isomorphism, e.g., {(phi x), (phi y)} connected in g2 iff {x, y} are connected in g1. |
| johnson (clj) | Finds all-pairs shortest paths using Bellman-Ford to remove any negative edges before using Dijkstra's algorithm to find the shortest paths from each vertex to every other. |
| loners (clj) | Returns nodes with no connections to other nodes (i.e., isolated nodes). |
| longest-shortest-path (clj) | Finds the longest shortest path beginning at start, using Dijkstra's algorithm if the graph is weighted, breadth-first search otherwise. |
| max-flow (clj) | Returns [flow-map flow-value], where flow-map is a weighted adjacency map representing the maximum flow. |
| maximal-cliques (clj) | Enumerate the maximal cliques using Bron-Kerbosch. |
| post-traverse (clj) | Traverses graph g depth-first, post-order from start. |
| pre-span (clj) | Returns a depth-first spanning tree of the form {node [successors]}. |
| pre-traverse (clj) | Traverses graph g depth-first from start. |
| prim-mst (clj) | Minimum spanning tree of given graph. |
| prim-mst-edges (clj) | An edge-list of an minimum spanning tree along with weights that represents an MST of the given graph. |
| scc (clj) | Returns the strongly-connected components of directed graph g as a vector of vectors. |
| shortest-path (clj) | Finds the shortest path from start to end in graph g, using Dijkstra's algorithm if the graph is weighted, breadth-first search otherwise. |
| strongly-connected? (clj) | |
| subgraph? (clj) | Returns true iff g1 is a subgraph of g2. |
| topsort (clj) | Topological sort of a directed acyclic graph (DAG). |