Ranking
A graph g ranked in direction d has a ranking function r: Vertex b NAT, such that
r(v) e 0 ' w: edge v d w Ò r(v) ý r(w) ' r(v) is no larger than it has to be.
Rankings are only meaningul for acyclic graphs.
RankGraph:
PROC [g: Graph, d: DirectedDirection];
GraphRanked:
PROC [g: Graph, d: DirectedDirection]
RETURNS [
BOOL];
VertexRank: PROC [v: Vertex, d: DirectedDirection] RETURNS [rank: INT];
Connected Components
EdgePredicate:
TYPE =
PROC [v, w: Vertex]
RETURNS [
BOOL];
Decide whether a particular edge is to be noticed in a connected components computation. It is assumed that there actually is a (possibly directed) edge from v to w in the graph.
DetermineComponents:
PROC [g: Graph, d: Direction, predicate: EdgePredicate ←
NIL]
RETURNS[numComponents:
CARDINAL ← 0];
Compute connected components of g, under the conditions that only edges which do not have direction d are ignored, and an edge having direction d is only noticed if it satisfies predicate.
ComponentsDetermined:
PROC [g: Graph, d: Direction]
RETURNS [
BOOL];
VertexComponent: PROC [v: Vertex, d: Direction] RETURNS [component: CARDINAL];