LEDA Guide: Example CHECK_SP

Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Shortest Path Algorithms > Checking the Results of an SSSP Algorithm > Example CHECK_SP_T()

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;
}

Example of How to Use CHECK_SP_T()

See also:

Example of How to Use `CHECK_SP_T()`