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)]): BoolSource

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)]): BoolSource

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)]): StringSource

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)]): StringSource

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.