LEDA Guide: Example CHECK

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

Example of How to Use `CHECK_SP()`

The following program shows how the function CHECK_SP() 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 main() we first create a simple graph G with six nodes and six edges. The costs of the edges are stored in the edge_array<int> cost.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/shortest_path.h>

using namespace leda;

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<int> cost(G);
  cost[e0]=1; cost[e1]=1;  cost[e2]=-1;
  cost[e3]=1; cost[e4]=-1; cost[e5]=1;

In our example we use SHORTEST_PATH() for the SSSP computation. The node_array<edge> pred and the node_array<integer> dist are used for the result of SHORTEST_PATH(). The result of the function CHECK_SP() 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() aborts with an error message if the check fails..

  node_array<edge> pred(G);  
  node_array<int> dist(G);
  SHORTEST_PATH(G,n0,cost,dist,pred);
 
  node_array<int> label(G);
  label=CHECK_SP(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()

See also:

Example of How to Use `CHECK_SP()`