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-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.(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]`.(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`.
(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.
(closeness-centrality g)Map of vertex -> closeness centrality score.
Map of vertex -> closeness centrality score.
(clustering-coefficient g)Map of vertex -> local clustering coefficient.
Map of vertex -> local clustering coefficient.
(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`.(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.
(coreness g)Map of vertex -> core number.
Map of vertex -> core number.
(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.
(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.
(global-clustering-coefficient g)Global clustering coefficient of g.
Global clustering coefficient of `g`.
(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}`.(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.(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).(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-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-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).(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).(pagerank g)Map of vertex -> PageRank score.
Map of vertex -> PageRank score.
(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).
(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.
(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.
(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`.
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 |