Graph

Definitions

def boundedDistances(g: m[(t, Int32, t)]): Map[(t, t), Int32] \ Aef[m] with Foldable[m], Order[t] 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)] \ Aef[m] with Foldable[m], Order[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)] \ Aef[m] with Foldable[m], Order[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] \ Aef[m] with Foldable[m], Order[t] 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] \ Aef[m] with Foldable[m], Order[t] 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]] \ Aef[m] with Foldable[m], Order[t] 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] \ Aef[m] with Foldable[m], Order[t] Source

Returns the shortest distance from src to every other reachable vertex in the weighted directed graph g.

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

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

def outDegrees(g: m[(t, t)]): Map[t, Int32] \ Aef[m] with Foldable[m], Order[t] 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 \ Aef[m] with Foldable[m], Order[t] 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] \ Aef[m] with Foldable[m], Order[t] Source

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

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

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