Example of How to Use CHECK_SP_T()
The following program shows how the function CHECK_SP_T()
can be used to check the result of a single source shortest paths computation
in a directed graph.
Remark: The graph algorithms in LEDA are generic, that is, they
accept graphs as well as parameterized
graphs.
In order to use the template functions CHECK_SP_T() we need
to include <LEDA/templates/shortest_path.t>. We use the
LEDA number type integer
as the number type NT for
the edge costs. In constrast to the C++ number type int,
LEDA's integer does not overflow.
#include <LEDA/graph/graph.h>
#include <LEDA/graph/templates/shortest_path.h>
#include <LEDA/numbers/integer.h>
using namespace leda;
In main() we first create a simple graph G
with six nodes and six edges. We use an edge_array<integer>
cost to store the costs of the edges of G.
int main()
{
graph G;
node n0=G.new_node(); node n1=G.new_node();
node n2=G.new_node(); node n3=G.new_node();
node n4=G.new_node(); node n5=G.new_node();
edge e0=G.new_edge(n0,n1); edge e1=G.new_edge(n0,n2);
edge e2=G.new_edge(n2,n3); edge e3=G.new_edge(n3,n4);
edge e4=G.new_edge(n4,n2); edge e5=G.new_edge(n3,n5);
edge_array<integer> cost(G);
cost[e0]=1; cost[e1]=1; cost[e2]=-1;
cost[e3]=1; cost[e4]=-1; cost[e5]=1;
In our example SHORTEST_PATH_T()
is used for the SSSP computation. The node_array<edge>
pred and the node_array<integer> dist are used
for the result of SHORTEST_PATH_T(). The result of the function
CHECK_SP_T() is the node_array<int> label.
For a node v, label[v]==-2 if v is on a negative
cost cycle, label[v]==-1 if v is reachable from
a negative cost cycle, label[v]>0 if v is
not reachable from s, and label[v]==0 otherwise.
CHECK_SP_T() aborts with an error message if the check fails.
node_array<edge> pred(G);
node_array<integer> dist(G);
SHORTEST_PATH_T(G,n0,cost,dist,pred);
node_array<int> label(G);
label=CHECK_SP_T(G,n0,cost,dist,pred);
node v;
forall_nodes(v,G) {
G.print_node(v);
if (label[v]==-2)
std::cout << " is on a negative cycle." << std::endl;
else if (label[v]==-1)
std::cout << " is reachable from a negative cycle." << std::endl;
else if (label[v]>0)
std::cout << " is not reachable from n0." << std::endl;
else
std::cout << " has finite distance from n0." << std::endl;
}
return 0;
}
|