Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Basic Graph Algorithms > Transitive Closure and Transitive Reduction > Example

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

Transitive Closure and Transitive Reduction

Graphs

Parameterized Graphs

Basic Graph Algorithms

Graphs and Related Data Types

Manual Entries:

Manual Page Basic Graph Algorithms