deba@1802: /* -*- C++ -*-
deba@1802:  * demo/min_route.cc - Part of LEMON, a generic C++ optimization library
deba@1802:  *
deba@1802:  * Copyright (C) 2005 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 <lemon/list_graph.h>
deba@1802: #include <lemon/topology.h>
deba@1802: #include <lemon/graph_to_eps.h>
deba@1802: #include <lemon/graph_reader.h>
deba@1802: #include <lemon/xy.h>
deba@1802: 
deba@1802: #include <iostream>
deba@1802: 
deba@1802: #include <cstdlib>
deba@1802: #include <ctime>
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@1802: using namespace std;
deba@1802: 
deba@1802: 
deba@1802: Color color(bool val) {
deba@1802:   return val ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 1.0);
deba@1802: }
deba@1802: 
deba@1802: 
deba@1802: void drawConnectedComponents() {
deba@1802:   typedef UndirListGraph Graph;
deba@1802:   typedef Graph::Node Node;
deba@1802: 
deba@1802:   Graph graph;
deba@1802:   Graph::NodeMap<xy<double> > coords(graph);
deba@1802: 
deba@1802:   UndirGraphReader<Graph>("undir_components.lgf", graph).
deba@1802:     readNodeMap("coordinates_x", xMap(coords)).
deba@1802:     readNodeMap("coordinates_y", yMap(coords)).
deba@1802:     run();
deba@1802:   
deba@1802:   ColorSet colorSet;
deba@1802: 
deba@1802:   Graph::NodeMap<int> compMap(graph);
deba@1802:   connectedComponents(graph, compMap);
deba@1802: 
deba@1802:   graphToEps(graph, "connected_components.eps").undir().
deba@1802:     coords(coords).scaleToA4().enableParallel().
deba@1802:     parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
deba@1802:     nodeColors(composeMap(colorSet, 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@1802:   Graph::NodeMap<xy<double> > coords(graph);
deba@1802: 
deba@1802:   GraphReader<Graph>("dir_components.lgf", graph).
deba@1802:     readNodeMap("coordinates_x", xMap(coords)).
deba@1802:     readNodeMap("coordinates_y", yMap(coords)).
deba@1802:     run();
deba@1802:   
deba@1802:   ColorSet colorSet;
deba@1802: 
deba@1802:   Graph::NodeMap<int> compMap(graph);
deba@1802:   Graph::EdgeMap<bool> cutMap(graph);
deba@1802:   stronglyConnectedComponents(graph, compMap);
deba@1802:   stronglyConnectedCutEdges(graph, cutMap);
deba@1802: 
deba@1802:   graphToEps(graph, "strongly_connected_components.eps").
deba@1802:     coords(coords).scaleToA4().enableParallel().
deba@1802:     drawArrows().arrowWidth(10.0).arrowLength(10.0).
deba@1802:     parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
deba@1802:     nodeColors(composeMap(colorSet, 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() {
deba@1802:   typedef UndirListGraph Graph;
deba@1802:   typedef Graph::Node Node;
deba@1802:   typedef Graph::UndirEdge UndirEdge;
deba@1802: 
deba@1802:   Graph graph;
deba@1802:   Graph::NodeMap<xy<double> > coords(graph);
deba@1802: 
deba@1802:   UndirGraphReader<Graph>("undir_components.lgf", graph).
deba@1802:     readNodeMap("coordinates_x", xMap(coords)).
deba@1802:     readNodeMap("coordinates_y", yMap(coords)).
deba@1802:     run();
deba@1802: 
deba@1802:   ColorSet colorSet;
deba@1802: 
deba@1802:   Graph::UndirEdgeMap<int> compMap(graph);
deba@1802:   Graph::NodeMap<bool> cutMap(graph);
deba@1802:   biNodeConnectedComponents(graph, compMap);
deba@1802:   biNodeConnectedCutNodes(graph, cutMap);
deba@1802:   graphToEps(graph, "bi_node_connected_components.eps").undir().
deba@1802:     coords(coords).scaleToA4().enableParallel().
deba@1802:     parEdgeDist(20.0).edgeWidthScale(5.0).nodeScale(20.0).
deba@1802:     edgeColors(composeMap(colorSet, 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() {
deba@1802:   typedef UndirListGraph Graph;
deba@1802:   typedef Graph::Node Node;
deba@1802:   typedef Graph::UndirEdge UndirEdge;
deba@1802: 
deba@1802:   Graph graph;
deba@1802:   Graph::NodeMap<xy<double> > coords(graph);
deba@1802: 
deba@1802:   UndirGraphReader<Graph>("undir_components.lgf", graph).
deba@1802:     readNodeMap("coordinates_x", xMap(coords)).
deba@1802:     readNodeMap("coordinates_y", yMap(coords)).
deba@1802:     run();
deba@1802:   
deba@1802:   ColorSet colorSet;
deba@1802: 
deba@1802:   Graph::NodeMap<int> compMap(graph);
deba@1802:   Graph::UndirEdgeMap<bool> cutMap(graph);
deba@1802:   biEdgeConnectedComponents(graph, compMap);
deba@1802:   biEdgeConnectedCutEdges(graph, cutMap);
deba@1802: 
deba@1802:   graphToEps(graph, "bi_edge_connected_components.eps").undir().
deba@1802:     coords(coords).scaleToA4().enableParallel().
deba@1802:     parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
deba@1802:     nodeColors(composeMap(colorSet, 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() {
deba@1802:   typedef UndirListGraph Graph;
deba@1802:   typedef Graph::Node Node;
deba@1802:   typedef Graph::UndirEdge UndirEdge;
deba@1802: 
deba@1802:   Graph graph;
deba@1802:   Graph::NodeMap<xy<double> > coords(graph);
deba@1802: 
deba@1802:   UndirGraphReader<Graph>("partitions.lgf", graph).
deba@1802:     readNodeMap("coordinates_x", xMap(coords)).
deba@1802:     readNodeMap("coordinates_y", yMap(coords)).
deba@1802:     run();
deba@1802:   
deba@1802:   ColorSet colorSet;
deba@1802: 
deba@1802:   Graph::NodeMap<bool> partMap(graph);
deba@1802:   bipartitePartitions(graph, partMap);
deba@1802: 
deba@1802:   graphToEps(graph, "bipartite_partitions.eps").undir().
deba@1802:     coords(coords).scaleToA4().enableParallel().
deba@1802:     parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
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:   srand(time(0));
deba@1802: 
deba@1802:   drawConnectedComponents();
deba@1802:   drawStronglyConnectedComponents();
deba@1802:   drawNodeBiconnectedComponents();
deba@1802:   drawEdgeBiconnectedComponents();
deba@1802:   drawBipartitePartitions();
deba@1802:   return 0;
deba@1802: }