Example Transitive Closure and Transitive Reduction

The following example shows how to use the LEDA functions for transitive closure and transitive reduction.

Remark: The graph algorithms in LEDA are generic, that is, they accept graphs as well as parameterized graphs.

The program creates a graph G with four nodes and four edges.

Then TRANSITIVE_CLOSURE() is called for G. The result is stored in the parameterized graph H. The nodes of H correspond uniquely to the nodes of G and there is a path between two nodes in G if and only if there is an edge between the corresponding nodes in H.

After some output operations TRANSITIVE_REDUCTION() is called for H. Notice that the resulting graph G2 is not equivalent to G, i.e., TRANSITIVE_CLOSURE() and TRANSITIVE_REDUTION() are not inverse to each other.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/basic_graph_alg.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();

  G.new_edge(n0,n1); G.new_edge(n1,n2);
  G.new_edge(n2,n3); G.new_edge(n1,n3);
 
  GRAPH<node,edge> H=TRANSITIVE_CLOSURE(G);

  std::cout << "Graph G:" << std::endl;
  G.print();
  std::cout << "Graph H:" << std::endl;
  H.print();

  node v;
  forall_nodes(v,H) {
    std::cout << "Node ";
    H.print_node(v);
    std::cout << " in H corresponds to node ";
    G.print_node(H[v]);
    std::cout << " in G" << std::endl;
  }
  std::cout << std::endl;

  edge e;
  forall_edges(e,H) {
    std::cout << "There is a path in G from ";
    G.print_node(H[H.source(e)]);
    std::cout << " to ";
    G.print_node(H[H.target(e)]);
    std::cout << std::endl;
  }
 
  GRAPH<node,edge> G2=TRANSITIVE_REDUCTION(H);
  
  std::cout << "\nGraph G2:" << std::endl;
  G2.print();

  forall_nodes(v,G2) {
    std::cout << "Node ";
    G2.print_node(v);
    std::cout << " in G2 corresponds to node ";
    H.print_node(G2[v]);
    std::cout << " in H" << std::endl;
  }

  return 0;
}

See also:

Transitive Closure and Transitive Reduction

Graphs

Parameterized Graphs

Basic Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Manual Page Basic Graph Algorithms