# Graph

## Definitions

`def boundedDistances(g: m[(t, Int32, t)]): Map[(t, t), Int32]`Source

Returns the shortest distance between all pairs of nodes in the weighted directed graph `g`.

OBS: No negative cycles must be present.

`def closure(g: m[(t, t)]): Set[(t, t)]`Source

Returns the pairs `(a, b)` where `a` can reach `b` through a number of edges in the directed graph `g`, including zero.

`def cutPoints(g: m[(t, t)]): Set[(t, t, t)]`Source

Returns triples `(x, cut, y)` such that `x` cannot reach `y` without using `cut` (where `x`, `cut` and `y` are all distinct) in the directed graph `g`.

There will at most be one triple for each pair of nodes (which will be the maximum `cut` of the possible choices).

`def degrees(g: m[(t, t)]): Map[t, Int32]`Source

Returns the degree of each node in the directed graph `g` (the number of times a node exists as an endpoint of an edge).

`def distance(src: { src = t }, dst: { dst = t }, g: m[(t, Int32, t)]): Option[Int32]`Source

Returns the shortest distance from `src` to `dst` in the weighted directed graph `g`.

`def distances(g: m[(t, Int32, t)]): Option[Map[(t, t), Int32]]`Source

Returns the shortest distance between all pairs of nodes in the weighted directed graph `g`. Returns `None` if `g` contains a negative cycle.

`def distancesFrom(src: t, g: m[(t, Int32, t)]): Map[t, Int32]`Source

Returns the shortest distance from `src` to every other node in the weighted directed graph `g`.

`def flipEdges(g: m[(t, t)]): Set[(t, t)]`Source

Returns the graph where all edges in the directed graph `g` have their nodes flipped.

`def frontiersFrom(src: t, g: m[(t, t)]): Map[Int32, Set[t]]`Source

Returns a mapping from distances to the set of nodes for which the shortest path from `src` in the directed graph `g` is of a given length.

`def inDegrees(g: m[(t, t)]): Map[t, Int32]`Source

Returns the in-degree (how many edges end in a given node) of each node in the directed graph `g`.

`def invert(g: m[(t, t)]): Set[(t, t)]`Source

Returns the inverse graph of the directed graph `g`. For all nodes in `g`. The new graph contains exactly those edges that are not in `g`.

OBS: No self-edges are returned no matter the input.

`def isCyclic(g: m[(t, t)]): Bool`Source

Returns `true` if the directed graph `g` contains at least one cycle.

`def outDegrees(g: m[(t, t)]): Map[t, Int32]`Source

Returns the out-degree (how many edges start in a given node) of each node in the directed graph `g`.

`def reachable(src: { src = t }, dst: { dst = t }, g: m[(t, t)]): Bool`Source

Returns `true` if there is a path from `src` to `dst` in the directed graph `g`.

`def reachableFrom(src: t, g: m[(t, t)]): Set[t]`Source

Returns the nodes that are reachable from `src` in the directed graph `g`.

`def stronglyConnectedComponents(g: m[(t, t)]): Set[Set[t]]`Source

Returns the strongly connected components of the directed graph `g`. Two nodes are in the same component if and only if they can both reach each other.

`def toGraphviz(g: m[(t, t)]): String`Source

Returns a Graphviz (DOT) string of the directed graph `g`. The strings of nodes are put in quotes but DOT identifier validity is up to the caller.

`def toGraphvizWeighted(g: m[(t, Int32, t)]): String`Source

Returns a Graphviz (DOT) string of the directed graph `g`. The strings of nodes are put in quotes and existing quotes are escaped. Other than that, DOT identifier validity is up to the caller.

`def toUndirected(g: m[(t, t)]): Set[(t, t)]`Source

Returns a copy of the directed graph `g` where all flipped edges are added. An undirected graph in directed representation.

`def toUndirectedWeighted(g: m[(t, Int32, t)]): Set[(t, Int32, t)]`Source

Returns a copy of the weighted directed graph `g` where all flipped edges are added. An undirected graph in directed representation.

`def topologicalSort(g: m[(t, t)]): List[t]`Source

Returns the topologically sorted nodes (all edges go from lower indices to higher indices of the list) in the directed graph `g`. Unordered nodes are consistently (although not intuitively) ordered.

OBS: No cycles must be present.

`def unreachableFrom(src: t, g: m[(t, t)]): Set[t]`Source

Returns the nodes that are unreachable from `src` in the directed graph `g`.

`def withinDistanceOf(src: t, limit: Int32, g: m[(t, Int32, t)]): Set[t]`Source

Returns the nodes that are at most `limit` (inclusive) distance away from `src` in the weighted directed graph `g`.

OBS: No negative cycles must be present.

`def withinEdgesOf(src: t, limit: Int32, g: m[(t, t)]): Set[t]`Source

Returns the nodes that are at most `limit` (inclusive) edges away from `src` in the directed graph `g`.