Graph
Definitions
def
boundedDistances
[mt]
(
g :
m[(t, Int32, t)]
)
: Map[(t, t), Int32]
\ Pure
with
Foldable[m]
Order[t]
Returns the shortest distance between all pairs of nodes in the
weighted directed graph g.
OBS: No negative cycles must be present.
def
closure
[mt]
(
g :
m[(t, t)]
)
: Set[(t, t)]
\ Pure
with
Foldable[m]
Order[t]
Returns the pairs (a, b) where a can reach b through a number of
edges in the directed graph g, including zero.
def
cutPoints
[mt]
(
g :
m[(t, t)]
)
: Set[(t, t, t)]
\ Pure
with
Foldable[m]
Order[t]
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
[mt]
(
g :
m[(t, t)]
)
: Map[t, Int32]
\ Pure
with
Foldable[m]
Order[t]
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
[tm]
(
src :
{ src = t }
dst :
{ dst = t }
g :
m[(t, Int32, t)]
)
: Option[Int32]
\ Pure
with
Foldable[m]
Order[t]
Returns the shortest distance from src to dst in the weighted
directed graph g.
def
distances
[mt]
(
g :
m[(t, Int32, t)]
)
: Option[Map[(t, t), Int32]]
\ Pure
with
Foldable[m]
Order[t]
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
[tm]
(
src :
t
g :
m[(t, Int32, t)]
)
: Map[t, Int32]
\ Pure
with
Foldable[m]
Order[t]
Returns the shortest distance from src to every other node in the
weighted directed graph g.
def
flipEdges
[mt]
(
g :
m[(t, t)]
)
: Set[(t, t)]
\ Pure
with
Foldable[m]
Order[t]
Returns the graph where all edges in the directed graph g have their
nodes flipped.
def
frontiersFrom
[tm]
(
src :
t
g :
m[(t, t)]
)
: Map[Int32, Set[t]]
\ Pure
with
Foldable[m]
Order[t]
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
[mt]
(
g :
m[(t, t)]
)
: Map[t, Int32]
\ Pure
with
Foldable[m]
Order[t]
Returns the in-degree (how many edges end in a given node)
of each node in the directed graph g.
def
invert
[mt]
(
g :
m[(t, t)]
)
: Set[(t, t)]
\ Pure
with
Foldable[m]
Order[t]
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
[mt]
(
g :
m[(t, t)]
)
: Bool
\ Pure
with
Foldable[m]
Order[t]
Returns true if the directed graph g contains at least one cycle.
def
outDegrees
[mt]
(
g :
m[(t, t)]
)
: Map[t, Int32]
\ Pure
with
Foldable[m]
Order[t]
Returns the out-degree (how many edges start in a given node)
of each node in the directed graph g.
def
reachable
[tm]
(
src :
{ src = t }
dst :
{ dst = t }
g :
m[(t, t)]
)
: Bool
\ Pure
with
Foldable[m]
Order[t]
Returns true if there is a path from src to dst in the directed
graph g.
def
reachableFrom
[tm]
(
src :
t
g :
m[(t, t)]
)
: Set[t]
\ Pure
with
Foldable[m]
Order[t]
Returns the nodes that are reachable from src in the directed
graph g.
def
stronglyConnectedComponents
[mt]
(
g :
m[(t, t)]
)
: Set[Set[t]]
\ Pure
with
Foldable[m]
Order[t]
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
[mt]
(
g :
m[(t, t)]
)
: String
\ Pure
with
Foldable[m]
Order[t]
ToString[t]
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
[mt]
(
g :
m[(t, Int32, t)]
)
: String
\ Pure
with
Foldable[m]
Order[t]
ToString[t]
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
[mt]
(
g :
m[(t, t)]
)
: Set[(t, t)]
\ Pure
with
Foldable[m]
Order[t]
Returns a copy of the directed graph g where all flipped edges are
added. An undirected graph in directed representation.
def
toUndirectedWeighted
[mt]
(
g :
m[(t, Int32, t)]
)
: Set[(t, Int32, t)]
\ Pure
with
Foldable[m]
Order[t]
Returns a copy of the weighted directed graph g where all flipped
edges are added. An undirected graph in directed representation.
def
topologicalSort
[mt]
(
g :
m[(t, t)]
)
: List[t]
\ Pure
with
Foldable[m]
Order[t]
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
[tm]
(
src :
t
g :
m[(t, t)]
)
: Set[t]
\ Pure
with
Foldable[m]
Order[t]
Returns the nodes that are unreachable from src in the directed
graph g.
def
withinDistanceOf
[tm]
(
src :
t
limit :
Int32
g :
m[(t, Int32, t)]
)
: Set[t]
\ Pure
with
Foldable[m]
Order[t]
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
[tm]
(
src :
t
limit :
Int32
g :
m[(t, t)]
)
: Set[t]
\ Pure
with
Foldable[m]
Order[t]
Returns the nodes that are at most limit (inclusive) edges away
from src in the directed graph g.