Graph algorithms over cljgrapht.core graphs. Every function takes a graph
and returns plain Clojure data (paths as vectors, components as sets, scores as
maps), so results compose with the rest of your Clojure code.
Direction matters: connected-components is for undirected graphs;
strongly-connected-components, topological-sort, and cycle? are for
directed graphs.
Graph algorithms over `cljgrapht.core` graphs. Every function takes a graph and returns plain Clojure data (paths as vectors, components as sets, scores as maps), so results compose with the rest of your Clojure code. Direction matters: `connected-components` is for undirected graphs; `strongly-connected-components`, `topological-sort`, and `cycle?` are for directed graphs.
(all-directed-paths g src dst)(all-directed-paths g src dst {:keys [simple? max-length] :or {simple? true}})All directed paths from src to dst. Options are :simple? (default true)
and :max-length, the maximum number of edges.
All directed paths from `src` to `dst`. Options are `:simple?` (default true) and `:max-length`, the maximum number of edges.
(all-pairs-shortest-path-length g)Nested map {u {v weight}} of cheapest path weights between every reachable ordered pair of distinct vertices (Floyd-Warshall).
Nested map {u {v weight}} of cheapest path weights between every reachable
ordered pair of distinct vertices (Floyd-Warshall).(all-simple-paths g src dst)All simple directed paths from src to dst, as vectors of
{:path [v ...] :weight w} maps.
All simple directed paths from `src` to `dst`, as vectors of
`{:path [v ...] :weight w}` maps.(alpha-centrality g)(alpha-centrality g alpha)Map of vertex -> alpha-attenuated (Katz) centrality score. alpha defaults
to JGraphT's damping factor.
Map of vertex -> alpha-attenuated (Katz) centrality score. `alpha` defaults to JGraphT's damping factor.
(articulation-points g)Set of articulation vertices in an undirected graph.
Set of articulation vertices in an undirected graph.
(assignment g part1 part2)Minimum-weight perfect bipartite matching between part1 and part2.
Minimum-weight perfect bipartite matching between `part1` and `part2`.
(astar g src dst heuristic)Cheapest path from src to dst as {:path [v ...] :weight w}, or nil if
unreachable, using A* with heuristic, a function of [vertex target].
Cheapest path from `src` to `dst` as `{:path [v ...] :weight w}`, or nil if
unreachable, using A* with `heuristic`, a function of `[vertex target]`.(bar-yehuda-even-two-approx-vertex-cover g)(bar-yehuda-even-two-approx-vertex-cover g weights)Bar-Yehuda-Even 2-approximation vertex cover, optionally weighted.
Bar-Yehuda-Even 2-approximation vertex cover, optionally weighted.
(bellman-ford g src dst)Cheapest path from src to dst as {:path [v ...] :weight w}, or nil if
unreachable. Supports negative edge weights but not negative cycles.
Cheapest path from `src` to `dst` as `{:path [v ...] :weight w}`, or nil if
unreachable. Supports negative edge weights but not negative cycles.(bellman-ford-distances g src)Map of every reachable vertex from src to its Bellman-Ford distance.
Includes src with distance 0.0.
Map of every reachable vertex from `src` to its Bellman-Ford distance. Includes `src` with distance 0.0.
(betweenness-centrality g)Map of vertex -> betweenness centrality score.
Map of vertex -> betweenness centrality score.
(bfs g start)Vector of vertices in breadth-first order from start.
Vector of vertices in breadth-first order from `start`.
(biconnected-components g)Seq of vertex sets, one per maximal biconnected block.
Seq of vertex sets, one per maximal biconnected block.
(bidirectional-shortest-path g src dst)Cheapest path from src to dst using bidirectional Dijkstra.
Cheapest path from `src` to `dst` using bidirectional Dijkstra.
(bipartite-matching g part1 part2)Maximum cardinality matching of bipartite graph g with vertex partitions
part1 and part2, as {:edges #{[u v] ...} :size n} (Hopcroft-Karp).
Maximum cardinality matching of bipartite graph `g` with vertex partitions
`part1` and `part2`, as `{:edges #{[u v] ...} :size n}` (Hopcroft-Karp).(bipartite-sets g)Two vertex partition sets when g is bipartite, otherwise nil.
Two vertex partition sets when `g` is bipartite, otherwise nil.
(block-cut-tree g)Block-cut tree as block sets, articulation vertices, and [block cutpoint]
edges.
Block-cut tree as block sets, articulation vertices, and `[block cutpoint]` edges.
(blocks g)Seq of vertex sets, one per block of an undirected graph.
Seq of vertex sets, one per block of an undirected graph.
(boruvka-minimum-spanning-tree g)Minimum spanning tree using Boruvka's algorithm.
Minimum spanning tree using Boruvka's algorithm.
(bridges g)Set of bridge edges as [source target] pairs in an undirected graph.
Set of bridge edges as `[source target]` pairs in an undirected graph.
(bron-kerbosch-maximal-cliques g)Seq of maximal cliques using the basic Bron-Kerbosch algorithm.
Seq of maximal cliques using the basic Bron-Kerbosch algorithm.
(capacitated-spanning-tree g root capacity demands)Esau-Williams capacitated spanning tree rooted at root. demands maps
vertices to nonnegative demand values.
Esau-Williams capacitated spanning tree rooted at `root`. `demands` maps vertices to nonnegative demand values.
(chinese-postman g)Minimum closed walk covering every edge as {:path [v ...] :weight w}.
Minimum closed walk covering every edge as `{:path [v ...] :weight w}`.
(chordal-coloring g)Optimal coloring of a chordal graph.
Optimal coloring of a chordal graph.
(chordal-maximum-clique g)Maximum clique as a vertex set, or nil when the graph is non-chordal.
Maximum clique as a vertex set, or nil when the graph is non-chordal.
(chordal-maximum-independent-set g)Maximum independent vertex set of a chordal graph.
Maximum independent vertex set of a chordal graph.
(chordal-minimum-vertex-cover g)Minimum vertex cover of a chordal graph, derived as the complement of a maximum independent set.
Minimum vertex cover of a chordal graph, derived as the complement of a maximum independent set.
(chordal? g)True if the undirected graph is chordal.
True if the undirected graph is chordal.
(clarkson-two-approx-vertex-cover g)(clarkson-two-approx-vertex-cover g weights)Clarkson 2-approximation vertex cover, optionally weighted.
Clarkson 2-approximation vertex cover, optionally weighted.
(closeness-centrality g)Map of vertex -> closeness centrality score.
Map of vertex -> closeness centrality score.
(clustering g)(clustering g {:keys [method k] :or {method :label-propagation}})Partition vertices into clusters. Methods are :label-propagation (default),
:girvan-newman, and :k-spanning-tree; the latter two require :k.
Partition vertices into clusters. Methods are `:label-propagation` (default), `:girvan-newman`, and `:k-spanning-tree`; the latter two require `:k`.
(clustering-coefficient g)Map of vertex -> local clustering coefficient.
Map of vertex -> local clustering coefficient.
(color-refinement g)Stable equitable vertex coloring produced by color refinement.
Stable equitable vertex coloring produced by color refinement.
(color-refinement-isomorphic? g1 g2)True when color refinement proves g1 and g2 isomorphic.
True when color refinement proves `g1` and `g2` isomorphic.
(coloring g)(coloring g {:keys [algorithm] :or {algorithm :saturation}})Vertex coloring of g as {:colors {vertex color-int, ...} :chromatic n}.
Options may include :algorithm, one of :saturation (default), :greedy,
:largest-degree-first, or :smallest-degree-last.
Vertex coloring of `g` as `{:colors {vertex color-int, ...} :chromatic n}`.
Options may include `:algorithm`, one of `:saturation` (default), `:greedy`,
`:largest-degree-first`, or `:smallest-degree-last`.(condensation g)Condensation DAG of a directed graph as SCC vertex sets and edges between those sets.
Condensation DAG of a directed graph as SCC vertex sets and edges between those sets.
(connected-components g)Seq of vertex sets, one per connected component (undirected; for a directed graph these are the weakly-connected components).
Seq of vertex sets, one per connected component (undirected; for a directed graph these are the weakly-connected components).
(connected? g)True if g is connected. Directed graphs are checked as weakly connected.
True if `g` is connected. Directed graphs are checked as weakly connected.
(contraction-hierarchy-shortest-path g src dst)Cheapest path from src to dst using a contraction hierarchy.
Cheapest path from `src` to `dst` using a contraction hierarchy.
(coreness g)Map of vertex -> core number.
Map of vertex -> core number.
(cycle-basis g)Paton cycle basis as {:cycles [[v ...] ...] :length n :weight w}.
Paton cycle basis as `{:cycles [[v ...] ...] :length n :weight w}`.
(cycle? g)True if the directed graph g contains a cycle.
True if the directed graph `g` contains a cycle.
(dag? g)True if directed graph g is acyclic.
True if directed graph `g` is acyclic.
(degeneracy-maximal-cliques g)Seq of maximal cliques using degeneracy-ordered Bron-Kerbosch.
Seq of maximal cliques using degeneracy-ordered Bron-Kerbosch.
(delta-stepping-shortest-path g src dst)Cheapest path from src to dst using parallel delta-stepping.
Cheapest path from `src` to `dst` using parallel delta-stepping.
(dense-edmonds-maximum-matching g)Maximum-cardinality matching using the dense Edmonds implementation.
Maximum-cardinality matching using the dense Edmonds implementation.
(density g)Graph density as m divided by the number of possible non-loop edges.
Graph density as m divided by the number of possible non-loop edges.
(dfs g start)Vector of vertices in depth-first pre-order from start. Neighbor
visitation follows JGraphT's stack order: most-recently-added first.
Vector of vertices in depth-first pre-order from `start`. Neighbor visitation follows JGraphT's stack order: most-recently-added first.
(diameter g)Maximum shortest-path distance between any two vertices.
Maximum shortest-path distance between any two vertices.
(dinic-max-flow g source sink)Maximum flow using Dinic's algorithm.
Maximum flow using Dinic's algorithm.
(disjoint-shortest-paths g src dst k)Up to k edge-disjoint shortest paths from src to dst using Suurballe.
Up to `k` edge-disjoint shortest paths from `src` to `dst` using Suurballe.
(dsatur-coloring g)Saturation-degree (DSATUR) vertex coloring.
Saturation-degree (DSATUR) vertex coloring.
(dulmage-mendelsohn g part1 part2)(dulmage-mendelsohn g part1 part2 {:keys [fine?] :or {fine? false}})Dulmage-Mendelsohn decomposition of a bipartite graph. Set :fine? for the
fine decomposition of the perfectly matched part.
Dulmage-Mendelsohn decomposition of a bipartite graph. Set `:fine?` for the fine decomposition of the perfectly matched part.
(edge-based-two-approx-vertex-cover g)Edge-based 2-approximation vertex cover.
Edge-based 2-approximation vertex cover.
(edmonds-karp-max-flow g source sink)Maximum flow using Edmonds-Karp.
Maximum flow using Edmonds-Karp.
(eigenvector-centrality g)Map of vertex -> eigenvector centrality score.
Map of vertex -> eigenvector centrality score.
(eulerian-cycle g)Eulerian cycle as {:path [v ...] :weight w}, or nil when none exists.
Eulerian cycle as `{:path [v ...] :weight w}`, or nil when none exists.
(eulerian? g)True when g has an Eulerian cycle.
True when `g` has an Eulerian cycle.
(gabow-strongly-connected-components g)Seq of strongly-connected vertex sets using Gabow's algorithm.
Seq of strongly-connected vertex sets using Gabow's algorithm.
(girth g)Length of the shortest cycle in an undirected graph, or nil when acyclic.
Length of the shortest cycle in an undirected graph, or nil when acyclic.
(global-clustering-coefficient g)Global clustering coefficient of g.
Global clustering coefficient of `g`.
(gomory-hu-tree g)Gomory-Hu cut tree as weighted [u v weight] edges.
Gomory-Hu cut tree as weighted `[u v weight]` edges.
(graph-center g)Set of vertices whose eccentricity equals the graph radius.
Set of vertices whose eccentricity equals the graph radius.
(graph-periphery g)Set of vertices whose eccentricity equals the graph diameter.
Set of vertices whose eccentricity equals the graph diameter.
(greedy-coloring g)Greedy vertex coloring of g as
{:colors {vertex color-int, ...} :chromatic n}.
Greedy vertex coloring of `g` as
`{:colors {vertex color-int, ...} :chromatic n}`.(greedy-maximum-matching g)Greedy maximal cardinality matching.
Greedy maximal cardinality matching.
(greedy-vertex-cover g)(greedy-vertex-cover g weights)Greedy vertex cover, optionally using a vertex-to-weight map.
Greedy vertex cover, optionally using a vertex-to-weight map.
(greedy-weighted-matching g)Greedy approximate maximum-weight matching.
Greedy approximate maximum-weight matching.
(harmonic-centrality g)Map of vertex -> harmonic centrality score.
Map of vertex -> harmonic centrality score.
(hopcroft-karp-matching g part1 part2)Maximum bipartite matching using Hopcroft-Karp.
Maximum bipartite matching using Hopcroft-Karp.
(isolated-vertices g)Set of vertices with degree zero.
Set of vertices with degree zero.
(isomorphic? g1 g2)True if g1 and g2 are graph-isomorphic according to VF2. Rejects mixed
directed/undirected graph pairs.
True if `g1` and `g2` are graph-isomorphic according to VF2. Rejects mixed directed/undirected graph pairs.
(johnson-all-pairs g)Nested map {u {v weight}} of cheapest path weights between every reachable ordered pair of distinct vertices (Johnson). Supports negative edge weights but not negative cycles.
Nested map {u {v weight}} of cheapest path weights between every reachable
ordered pair of distinct vertices (Johnson). Supports negative edge weights
but not negative cycles.(johnson-simple-cycles g)Simple directed cycles using Johnson's algorithm.
Simple directed cycles using Johnson's algorithm.
(k-shortest-paths g src dst k)k shortest simple paths from src to dst, as vectors of
{:path [v ...] :weight w} maps (Yen).
`k` shortest simple paths from `src` to `dst`, as vectors of
`{:path [v ...] :weight w}` maps (Yen).(kosaraju-strongly-connected-components g)Seq of strongly-connected vertex sets using Kosaraju's algorithm.
Seq of strongly-connected vertex sets using Kosaraju's algorithm.
(kruskal-minimum-spanning-tree g)Minimum spanning tree using Kruskal's algorithm.
Minimum spanning tree using Kruskal's algorithm.
(kuratowski-subdivision g)Kuratowski subdivision witness as vertex and edge sets; nil if planar.
Kuratowski subdivision witness as vertex and edge sets; nil if planar.
(largest-degree-first-coloring g)Greedy coloring in descending degree order.
Greedy coloring in descending degree order.
(lca g a b)(lca g a b opts)Lowest common ancestor, or nil when none exists.
Lowest common ancestor, or nil when none exists.
(lca-set g a b)(lca-set g a b opts)Set of lowest common ancestors, possibly empty.
Set of lowest common ancestors, possibly empty.
(line-graph g)(line-graph g weight-fn)Return the line graph of g. With weight-fn, produce weighted line edges.
Return the line graph of `g`. With `weight-fn`, produce weighted line edges.
(link-prediction-score g
u
v
{:keys [algorithm] :or {algorithm :common-neighbors}})Predict a link score between u and v.
Predict a link score between `u` and `v`.
(max-flow g source sink)Maximum source->sink flow in directed graph g as
{:value flow-value :flow {[u v] flow-on-edge, ...}} (Push-Relabel). Edge
weights are capacities; zero-flow edges are omitted from :flow.
Maximum `source`->`sink` flow in directed graph `g` as
`{:value flow-value :flow {[u v] flow-on-edge, ...}}` (Push-Relabel). Edge
weights are capacities; zero-flow edges are omitted from `:flow`.(maximal-cliques g)Seq of maximal cliques of undirected graph g, each as a vertex set
(Bron-Kerbosch).
Seq of maximal cliques of undirected graph `g`, each as a vertex set (Bron-Kerbosch).
(maximum-density-subgraph g s t)(maximum-density-subgraph g s t {:keys [epsilon] :or {epsilon 1.0E-9}})Find a densest subgraph. s and t must be distinct sentinel vertices not in g.
Find a densest subgraph. `s` and `t` must be distinct sentinel vertices not in `g`.
(maximum-matching g)Maximum cardinality matching of undirected graph g as
{:edges #{[u v] ...} :size n} (Edmonds).
Maximum cardinality matching of undirected graph `g` as
`{:edges #{[u v] ...} :size n}` (Edmonds).(maximum-weight-matching g)Maximum weight matching of undirected graph g as
{:edges #{[u v] ...} :weight w} (Kolmogorov blossom).
Maximum weight matching of undirected graph `g` as
`{:edges #{[u v] ...} :weight w}` (Kolmogorov blossom).(min-cost-flow g
{:keys [supplies capacities lower-bounds]
:or {supplies {} capacities {} lower-bounds {}}})Minimum-cost flow for integer :supplies and :capacities maps.
Edge weights are costs. Optional :lower-bounds defaults to zero.
Minimum-cost flow for integer `:supplies` and `:capacities` maps. Edge weights are costs. Optional `:lower-bounds` defaults to zero.
(min-cut g source sink)Minimum source->sink cut in directed graph g as
{:weight w :source-partition #{...} :sink-partition #{...}} (Push-Relabel).
Minimum `source`->`sink` cut in directed graph `g` as
`{:weight w :source-partition #{...} :sink-partition #{...}}` (Push-Relabel).(min-vertex-cover g)(min-vertex-cover g weights)Exact minimum vertex cover, optionally using a vertex-to-weight map.
Exact minimum vertex cover, optionally using a vertex-to-weight map.
(minimal-weight-perfect-matching g part1 part2)Alias for assignment.
Alias for `assignment`.
(minimum-cut g)Global minimum cut of an undirected graph.
Global minimum cut of an undirected graph.
(minimum-spanning-tree g)Minimum spanning tree of weighted graph g as
{:edges #{[u v] ...} :weight w} (Prim).
Minimum spanning tree of weighted graph `g` as
`{:edges #{[u v] ...} :weight w}` (Prim).(minimum-st-cut g source sink)Minimum source-to-sink cut with source and sink partitions.
Minimum source-to-sink cut with source and sink partitions.
(pagerank g)Map of vertex -> PageRank score.
Map of vertex -> PageRank score.
(path-growing-weighted-matching g)Approximate maximum-weight matching using path growing.
Approximate maximum-weight matching using path growing.
(perfect-elimination-order g)Perfect elimination order for a chordal graph, or nil when non-chordal.
Perfect elimination order for a chordal graph, or nil when non-chordal.
(pivot-maximal-cliques g)Seq of maximal cliques using pivoting Bron-Kerbosch.
Seq of maximal cliques using pivoting Bron-Kerbosch.
(planar-embedding g)Planar rotation system as {vertex [neighbor ...]}; nil if nonplanar.
Planar rotation system as `{vertex [neighbor ...]}`; nil if nonplanar.
(planar? g)True if the undirected graph is planar.
True if the undirected graph is planar.
(predict-links g pairs)(predict-links g pairs {:keys [algorithm] :or {algorithm :common-neighbors}})Predict scores for [u v] pairs as a map.
Predict scores for `[u v]` pairs as a map.
(prim-minimum-spanning-tree g)Minimum spanning tree using Prim's algorithm.
Minimum spanning tree using Prim's algorithm.
(pseudo-periphery g)Set of vertices whose neighbors have no greater eccentricity.
Set of vertices whose neighbors have no greater eccentricity.
(push-relabel-max-flow g source sink)Maximum flow using push-relabel.
Maximum flow using push-relabel.
(random-greedy-coloring g)Greedy coloring in randomized vertex order.
Greedy coloring in randomized vertex order.
(shortest-path g src dst)Cheapest path from src to dst as {:path [v ...] :weight w}, or nil if
unreachable. Uses Dijkstra; unweighted graphs use unit edge weights, so
:weight is the hop count.
Cheapest path from `src` to `dst` as `{:path [v ...] :weight w}`, or nil if
unreachable. Uses Dijkstra; unweighted graphs use unit edge weights, so
`:weight` is the hop count.(shortest-path-length g src dst)Weight of the cheapest src->dst path, or nil if unreachable.
Weight of the cheapest `src`->`dst` path, or nil if unreachable.
(simple-cycles g)Vector of simple directed cycles, each as a vector of vertices (JohnsonSimpleCycles).
Vector of simple directed cycles, each as a vector of vertices (JohnsonSimpleCycles).
(smallest-degree-last-coloring g)Greedy coloring in smallest-degree-last order.
Greedy coloring in smallest-degree-last order.
(spanner g k)Greedy multiplicative (2k-1)-spanner as {:edges ... :weight w}.
Greedy multiplicative `(2k-1)`-spanner as `{:edges ... :weight w}`.
(sparse-edmonds-maximum-matching g)Maximum-cardinality matching using the sparse Edmonds implementation.
Maximum-cardinality matching using the sparse Edmonds implementation.
(steiner-tree g terminals)Approximate weighted Steiner tree spanning terminals.
Approximate weighted Steiner tree spanning `terminals`.
(strongly-connected-components g)Seq of vertex sets, one per strongly-connected component (directed).
Seq of vertex sets, one per strongly-connected component (directed).
(strongly-connected? g)True if directed graph g is strongly connected.
True if directed graph `g` is strongly connected.
(subgraph-isomorphic? g subgraph)True if subgraph is isomorphic to a subgraph of g.
True if `subgraph` is isomorphic to a subgraph of `g`.
(szwarcfiter-lauer-simple-cycles g)Simple directed cycles using the Szwarcfiter-Lauer algorithm.
Simple directed cycles using the Szwarcfiter-Lauer algorithm.
(tarjan-simple-cycles g)Simple directed cycles using Tarjan's algorithm.
Simple directed cycles using Tarjan's algorithm.
(topological-sort g)Vector of vertices of directed acyclic graph g in topological order, or nil
if g contains a cycle.
Vector of vertices of directed acyclic graph `g` in topological order, or nil if `g` contains a cycle.
(transitive-closure g)Edges of the transitive closure of directed graph g.
Edges of the transitive closure of directed graph `g`.
(transitive-reduction g)Edges of the transitive reduction of directed acyclic graph g.
Edges of the transitive reduction of directed acyclic graph `g`.
(tree-edit-distance tree1 root1 tree2 root2)Zhang-Shasha edit distance between two rooted ordered trees.
Zhang-Shasha edit distance between two rooted ordered trees.
(tree-isomorphic? tree1 tree2)(tree-isomorphic? tree1 root1 tree2 root2)AHU tree-isomorphism predicate. The four-argument form fixes both roots.
AHU tree-isomorphism predicate. The four-argument form fixes both roots.
(tsp-tour g)(tsp-tour g {:keys [method] :or {method :nearest-neighbor}})Hamiltonian tour as {:tour [v ... v] :weight w}. Methods are
:nearest-neighbor (default), :held-karp, :christofides, :greedy,
:nearest-insertion, :random, :two-opt, and :palmer.
Hamiltonian tour as `{:tour [v ... v] :weight w}`. Methods are
`:nearest-neighbor` (default), `:held-karp`, `:christofides`, `:greedy`,
`:nearest-insertion`, `:random`, `:two-opt`, and `:palmer`.(vertex-eccentricities g)Map of vertex -> maximum shortest-path distance to another vertex.
Map of vertex -> maximum shortest-path distance to another vertex.
(vertices-on-cycles g)Set of vertices that participate in at least one cycle of directed graph g.
Set of vertices that participate in at least one cycle of directed graph `g`.
(yen-k-shortest-paths g src dst k)The k shortest loopless paths from src to dst using Yen's algorithm.
The `k` shortest loopless paths from `src` to `dst` using Yen's algorithm.
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |