Example Transitive Closure and Transitive ReductionThe 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 Then After some output operations #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 Manual Entries: |