# Graph

## Definitions

`def boundedDistances(g: m[(t, Int32, t)]): Map[(t, t), Int32] \ Aef[m] with Foldable[m], Order[t]`

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

.

OBS: No negative cycles must be present.

Returns the pairs `(a, b)`

where `a`

can reach `b`

through a number of
edges in the directed graph `g`

, including zero.

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

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] \ Aef[m] with Foldable[m], Order[t]`

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]] \ Aef[m] with Foldable[m], Order[t]`

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] \ Aef[m] with Foldable[m], Order[t]`

SourceReturns the shortest distance from `src`

to every other reachable vertex in the
weighted directed graph `g`

.

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]] \ Aef[m] with Foldable[m], Order[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.

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

.

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.

Returns `true`

if the directed graph `g`

contains at least one cycle.

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 \ Aef[m] with Foldable[m], Order[t]`

SourceReturns `true`

if there is a path from `src`

to `dst`

in the directed
graph `g`

.

Returns the nodes that are reachable from `src`

in the directed
graph `g`

.

`def stronglyConnectedComponents(g: m[(t, t)]): Set[Set[t]] \ Aef[m] with Foldable[m], Order[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.

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 toGraphvizLabeled(g: m[(t, l, t)]): String \ Aef[m] with Foldable[m], ToString[t], ToString[l]`

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.

Returns a copy of the directed graph `g`

where all flipped edges are
added. An undirected graph in directed representation.

`def toUndirectedLabeled(g: m[(t, Int32, t)]): Set[(t, Int32, t)] \ Aef[m] with Foldable[m], Order[t]`

SourceReturns a copy of the weighted directed graph `g`

where all flipped
edges are added. An undirected graph in directed representation.

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.

Returns the nodes that are unreachable from `src`

in the directed
graph `g`

.