___NTP, --_Node_type
___WT<$NUMBER{WT}, --_Weight_type

Flattened version is here



Readonly Shareds
shared debug: BOOL := false;

Writable Shareds
shared debug: BOOL := false;

bellman_ford(g:GTP,s:NTP,out d:MAP{NTP,WT},out p:MAP{NTP,NTP}): BOOL
**** Computes the source shortest paths from "s" using a queue and breadth first search. On return, "d" holds a mapping from nodes to their distances for "src" and "pred" holds a mapping from each node to its parent node in the shortest paths tree. Returns true if no negative cycle was found
Implementation: Note that bellman_ford works even in cyclic graphs, provided there is no cycle with negative weight (in which case the min weight to any of the nodes in the cycle can be arbitrarily decreased) If such a negative weight cycle is found, the routine quits and returns false - it can therefore also be used as a reliable detector of negative cycles.
dijkstra(g:GTP,s:NTP,out dist:MAP{NTP,WT},out
**** Please see the comment at WTD_DIGRAPH_ALG{_,_,_,_}::dijkstra Computes single source shortest paths from "src" for a non-negative graph i.e. one without negative cycles. Returns the distance from "src" to all other nodes in "dist" and the predecessor of each node of "g" in the shortest paths tree in "pred"
maxval: WT
zero: WT

max_weight_path_node!(once g: GTP,once src,once sink: NTP): NTP
**** Computes the maximum node-weight path from "src" to "sink" in the graph "g", returning a list of nodes in that maximum weight path that starts with "src" and ends with "sink" Fully considered only for DAGs: May have problems with other types of graphs


deb(s: STR): BOOL
deb2(s: STR)
node_str(n: NTP): STR
str(e: $OB): STR

The Sather Home Page