# Graph

## Definitions

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

SourceReturns 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)]`

SourceReturns 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)]`

SourceReturns 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]`

SourceReturns 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]`

SourceReturns 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]]`

SourceReturns 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]`

SourceReturns the shortest distance from `src`

to every other node in the
weighted directed graph `g`

.

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

SourceReturns 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]]`

SourceReturns 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]`

SourceReturns 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)]`

SourceReturns 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`

SourceReturns `true`

if the directed graph `g`

contains at least one cycle.

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

SourceReturns 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`

SourceReturns `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]`

SourceReturns the nodes that are reachable from `src`

in the directed
graph `g`

.

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

SourceReturns 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`

SourceReturns 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`

SourceReturns 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)]`

SourceReturns 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)]`

SourceReturns 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]`

SourceReturns 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]`

SourceReturns 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]`

SourceReturns 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]`

SourceReturns the nodes that are at most `limit`

(inclusive) edges away
from `src`

in the directed graph `g`

.