deba@1802: /* -*- C++ -*- deba@1802: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2553: * Copyright (C) 2003-2008 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@1802: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@1802: * deba@1802: * Permission to use, modify and distribute this software is granted deba@1802: * provided that this copyright notice appears in all copies. For deba@1802: * precise terms see the accompanying LICENSE file. deba@1802: * deba@1802: * This software is provided "AS IS" with no warranty of any kind, deba@1802: * express or implied, and with no claim as to its suitability for any deba@1802: * purpose. deba@1802: * deba@1802: */ deba@1802: deba@1802: #include deba@1802: #include deba@1802: #include deba@1802: #include alpar@2207: #include deba@1802: deba@1802: #include deba@1802: deba@1802: #include deba@1802: #include deba@1802: deba@1802: /// \ingroup demos deba@1802: /// \file deba@1802: /// \brief Demo what shows the result of some topology functions. deba@1802: /// deba@1802: /// Demo what shows the result of some topology functions. deba@1802: /// deba@1802: /// \include topology_demo.cc deba@1802: deba@1802: using namespace lemon; deba@2306: using namespace lemon::dim2; deba@1802: using namespace std; deba@1802: deba@1802: deba@1802: Color color(bool val) { alpar@2174: return val ? RED : BLUE; deba@1802: } deba@1802: deba@1802: deba@1802: void drawConnectedComponents() { klao@1909: typedef ListUGraph Graph; deba@1802: typedef Graph::Node Node; deba@1802: deba@1802: Graph graph; deba@2306: Graph::NodeMap > coords(graph); deba@1802: klao@1909: UGraphReader("u_components.lgf", graph). deba@1802: readNodeMap("coordinates_x", xMap(coords)). deba@1802: readNodeMap("coordinates_y", yMap(coords)). deba@1802: run(); deba@1802: alpar@2172: Palette palette; deba@1802: deba@1802: Graph::NodeMap compMap(graph); deba@1802: connectedComponents(graph, compMap); deba@1802: deba@1910: graphToEps(graph, "connected_components.eps").undirected(). deba@1802: coords(coords).scaleToA4().enableParallel(). alpar@2172: nodeColors(composeMap(palette, compMap)).run(); deba@1802: deba@1802: std::cout << "Result: connected_components.eps" << std::endl; deba@1802: } deba@1802: deba@1802: void drawStronglyConnectedComponents() { deba@1802: typedef ListGraph Graph; deba@1802: typedef Graph::Node Node; deba@1802: deba@1802: Graph graph; deba@2306: Graph::NodeMap > coords(graph); deba@1802: deba@1802: GraphReader("dir_components.lgf", graph). deba@1802: readNodeMap("coordinates_x", xMap(coords)). deba@1802: readNodeMap("coordinates_y", yMap(coords)). deba@1802: run(); deba@1802: alpar@2172: Palette palette; deba@1802: deba@1802: Graph::NodeMap compMap(graph); deba@1802: Graph::EdgeMap cutMap(graph); deba@1802: stronglyConnectedComponents(graph, compMap); deba@1802: stronglyConnectedCutEdges(graph, cutMap); deba@1802: deba@1802: graphToEps(graph, "strongly_connected_components.eps"). deba@2306: coords(coords).scaleToA4().enableParallel().drawArrows(). alpar@2172: nodeColors(composeMap(palette, compMap)). deba@1802: edgeColors(composeMap(functorMap(&color), cutMap)).run(); deba@1802: deba@1802: std::cout << "Result: strongly_connected_components.eps" << std::endl; deba@1802: } deba@1802: deba@1802: void drawNodeBiconnectedComponents() { klao@1909: typedef ListUGraph Graph; deba@1802: typedef Graph::Node Node; klao@1909: typedef Graph::UEdge UEdge; deba@1802: deba@1802: Graph graph; deba@2306: Graph::NodeMap > coords(graph); deba@1802: klao@1909: UGraphReader("u_components.lgf", graph). deba@1802: readNodeMap("coordinates_x", xMap(coords)). deba@1802: readNodeMap("coordinates_y", yMap(coords)). deba@1802: run(); deba@1802: alpar@2172: Palette palette; deba@1802: klao@1909: Graph::UEdgeMap compMap(graph); deba@1802: Graph::NodeMap cutMap(graph); deba@1802: biNodeConnectedComponents(graph, compMap); deba@1802: biNodeConnectedCutNodes(graph, cutMap); deba@1910: deba@1910: graphToEps(graph, "bi_node_connected_components.eps").undirected(). deba@1802: coords(coords).scaleToA4().enableParallel(). alpar@2172: edgeColors(composeMap(palette, compMap)). deba@1802: nodeColors(composeMap(functorMap(&color), cutMap)). deba@1802: run(); deba@1802: deba@1802: std::cout << "Result: bi_node_connected_components.eps" << std::endl; deba@1802: } deba@1802: deba@1802: void drawEdgeBiconnectedComponents() { klao@1909: typedef ListUGraph Graph; deba@1802: typedef Graph::Node Node; klao@1909: typedef Graph::UEdge UEdge; deba@1802: deba@1802: Graph graph; deba@2306: Graph::NodeMap > coords(graph); deba@1802: klao@1909: UGraphReader("u_components.lgf", graph). deba@1802: readNodeMap("coordinates_x", xMap(coords)). deba@1802: readNodeMap("coordinates_y", yMap(coords)). deba@1802: run(); deba@1802: alpar@2172: Palette palette; deba@1802: deba@1802: Graph::NodeMap compMap(graph); klao@1909: Graph::UEdgeMap cutMap(graph); deba@1802: biEdgeConnectedComponents(graph, compMap); deba@1802: biEdgeConnectedCutEdges(graph, cutMap); deba@1802: deba@1910: graphToEps(graph, "bi_edge_connected_components.eps").undirected(). deba@1802: coords(coords).scaleToA4().enableParallel(). alpar@2172: nodeColors(composeMap(palette, compMap)). deba@1802: edgeColors(composeMap(functorMap(&color), cutMap)).run(); deba@1802: deba@1802: std::cout << "Result: bi_edge_connected_components.eps" << std::endl; deba@1802: } deba@1802: deba@1802: void drawBipartitePartitions() { klao@1909: typedef ListUGraph Graph; deba@1802: typedef Graph::Node Node; klao@1909: typedef Graph::UEdge UEdge; deba@1802: deba@1802: Graph graph; deba@2306: Graph::NodeMap > coords(graph); deba@1802: klao@1909: UGraphReader("partitions.lgf", graph). deba@1802: readNodeMap("coordinates_x", xMap(coords)). deba@1802: readNodeMap("coordinates_y", yMap(coords)). deba@1802: run(); deba@1802: alpar@2172: Palette palette; deba@1802: deba@1802: Graph::NodeMap partMap(graph); deba@1802: bipartitePartitions(graph, partMap); deba@1802: deba@1910: graphToEps(graph, "bipartite_partitions.eps").undirected(). deba@1802: coords(coords).scaleToA4().enableParallel(). deba@1802: nodeColors(composeMap(functorMap(&color), partMap)).run(); deba@1802: deba@1802: std::cout << "Result: bipartite_partitions.eps" << std::endl; deba@1802: } deba@1802: deba@1802: int main() { deba@1802: drawConnectedComponents(); deba@1802: drawStronglyConnectedComponents(); deba@1802: drawNodeBiconnectedComponents(); deba@1802: drawEdgeBiconnectedComponents(); deba@1802: drawBipartitePartitions(); deba@1802: return 0; deba@1802: }