loom.alg — aysylu/loom 1.0.2

Graph algorithms. Any graph record/type that satisfies the Graph, Digraph, or WeightedGraph protocols (as appropriate per algorithm) can use these functions.

all-pairs-shortest-paths clj/s

(all-pairs-shortest-paths g)

Finds all-pairs shortest paths in a graph. Uses Johnson's algorithm for weighted graphs which is efficient for sparse graphs. Breadth-first spans are used for unweighted graphs.

astar-dist clj/s

(astar-dist g src target heur)

Returns the length of the shortest path between src and target using the A* algorithm

astar-path clj/s

(astar-path g src target heur)

(astar-path g src target heur q explored)

Returns the shortest path using A* algorithm. Returns a map of predecessors.

bellman-ford clj/s

(bellman-ford g start)

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/s

(bf-all-pairs-shortest-paths g)

Uses bf-span on each node in the graph.

bf-path clj/s

(bf-path g start end & opts)

Returns a path from start to end with the fewest hops (i.e. irrespective of edge weights)

bf-path-bi clj/s

(bf-path-bi g start end)

Using a bidirectional breadth-first search, finds a path from start to end with the fewest hops (i.e. irrespective of edge weights). Can be much faster than a unidirectional search on certain types of graphs

bf-span clj/s

(bf-span g)

(bf-span g start)

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

bf-traverse clj/s

(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/s

(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/s

(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/s

(bipartite? g)

Returns true if g is bipartite

coloring? clj/s

(coloring? g coloring)

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

connect clj/s

(connect g)

Returns graph g with all connected components connected to each other

connected-components clj/s

(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/s

(connected? g)

Returns true if g is connected

dag? clj/s

(dag? g)

Returns true if g is a directed acyclic graph

degeneracy-ordering clj/s

(degeneracy-ordering g)

Returns sequence of vertices in degeneracy order.

density clj/s

(density g & {:keys [loops] :or {loops false}})

Return the density of graph g

dijkstra-path clj/s

(dijkstra-path g start end)

Finds the shortest path from start to end

dijkstra-path-dist clj/s

(dijkstra-path-dist g start end)

Finds the shortest path from start to end. Returns a vector: [path distance]

dijkstra-span clj/s

(dijkstra-span g)

(dijkstra-span g start)

Finds all shortest distances from start. Returns a map in the format {node {successor distance}}

dijkstra-traverse clj/s

(dijkstra-traverse g)

(dijkstra-traverse g start)

(dijkstra-traverse g start f)

Returns a lazy-seq of [current-node state] where state is a map in the format {node [distance predecessor]}. When f is provided, returns a lazy-seq of (f node state) for each node

distinct-edges clj/s

(distinct-edges g)

Returns the distinct edges of g. Only useful for undirected graphs

eql? clj/s

(eql? g1 g2)

Returns true iff g1 is a subgraph of g2 and g2 is a subgraph of g1

greedy-coloring clj/s

(greedy-coloring g)

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

isomorphism? clj/s

(isomorphism? g1 g2 phi)

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/s

(johnson g)

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. This algorithm is efficient for sparse graphs.

If the graph is unweighted, a default weight of 1 will be used. Note that it is more efficient to use breadth-first spans for a graph with a uniform edge weight rather than Dijkstra's algorithm. Most callers should use shortest-paths and allow the most efficient implementation be selected for the graph.

loners clj/s

(loners g)

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

longest-shortest-path clj/s

(longest-shortest-path g start)

Finds the longest shortest path beginning at start, using Dijkstra's algorithm if the graph is weighted, breadth-first search otherwise.

max-flow clj/s

(max-flow g source sink & {:keys [method] :or {method :edmonds-karp}})

Returns [flow-map flow-value], where flow-map is a weighted adjacency map representing the maximum flow. The argument should be a weighted digraph, where the edge weights are flow capacities. Source and sink are the vertices representing the flow source and sink vertices. Optionally, pass in :method :algorithm to use. Currently, the only option is :edmonds-karp .

maximal-cliques clj/s

(maximal-cliques g)

Enumerate the maximal cliques using Bron-Kerbosch.

post-traverse clj/s

(post-traverse g)

(post-traverse g start & opts)

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

pre-span clj/s

(pre-span g)

(pre-span g start)

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

pre-traverse clj/s

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

prim-mst clj/s

(prim-mst wg)

Minimum spanning tree of given graph. If the graph contains more than one component then returns a spanning forest of minimum spanning trees.

prim-mst-edges clj/s

(prim-mst-edges wg)

(prim-mst-edges wg n h visited acc)

An edge-list of an minimum spanning tree along with weights that represents an MST of the given graph. Returns the MST edge-list for un-weighted graphs.

scc clj/s

(scc g)

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

shortest-path clj/s

(shortest-path g start end)

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/s

(strongly-connected? g)

subgraph? clj/s

(subgraph? g1 g2)

Returns true iff g1 is a subgraph of g2. An undirected graph is never considered as a subgraph of a directed graph and vice versa.

topsort clj/s

(topsort g)

(topsort g start)

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