demo/topology_demo.cc
author deba
Wed, 16 Nov 2005 09:15:41 +0000
changeset 1802 fdfa3aa18607
child 1875 98698b69a902
permissions -rw-r--r--
Demo for topology
     1 /* -*- C++ -*-
     2  * demo/min_route.cc - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #include <lemon/list_graph.h>
    18 #include <lemon/topology.h>
    19 #include <lemon/graph_to_eps.h>
    20 #include <lemon/graph_reader.h>
    21 #include <lemon/xy.h>
    22 
    23 #include <iostream>
    24 
    25 #include <cstdlib>
    26 #include <ctime>
    27 
    28 /// \ingroup demos
    29 /// \file
    30 /// \brief Demo what shows the result of some topology functions.
    31 ///
    32 ///  Demo what shows the result of some topology functions.
    33 ///
    34 /// \include topology_demo.cc
    35 
    36 using namespace lemon;
    37 using namespace std;
    38 
    39 
    40 Color color(bool val) {
    41   return val ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 1.0);
    42 }
    43 
    44 
    45 void drawConnectedComponents() {
    46   typedef UndirListGraph Graph;
    47   typedef Graph::Node Node;
    48 
    49   Graph graph;
    50   Graph::NodeMap<xy<double> > coords(graph);
    51 
    52   UndirGraphReader<Graph>("undir_components.lgf", graph).
    53     readNodeMap("coordinates_x", xMap(coords)).
    54     readNodeMap("coordinates_y", yMap(coords)).
    55     run();
    56   
    57   ColorSet colorSet;
    58 
    59   Graph::NodeMap<int> compMap(graph);
    60   connectedComponents(graph, compMap);
    61 
    62   graphToEps(graph, "connected_components.eps").undir().
    63     coords(coords).scaleToA4().enableParallel().
    64     parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
    65     nodeColors(composeMap(colorSet, compMap)).run();
    66 
    67   std::cout << "Result: connected_components.eps" << std::endl;
    68 }
    69 
    70 void drawStronglyConnectedComponents() {
    71   typedef ListGraph Graph;
    72   typedef Graph::Node Node;
    73 
    74   Graph graph;
    75   Graph::NodeMap<xy<double> > coords(graph);
    76 
    77   GraphReader<Graph>("dir_components.lgf", graph).
    78     readNodeMap("coordinates_x", xMap(coords)).
    79     readNodeMap("coordinates_y", yMap(coords)).
    80     run();
    81   
    82   ColorSet colorSet;
    83 
    84   Graph::NodeMap<int> compMap(graph);
    85   Graph::EdgeMap<bool> cutMap(graph);
    86   stronglyConnectedComponents(graph, compMap);
    87   stronglyConnectedCutEdges(graph, cutMap);
    88 
    89   graphToEps(graph, "strongly_connected_components.eps").
    90     coords(coords).scaleToA4().enableParallel().
    91     drawArrows().arrowWidth(10.0).arrowLength(10.0).
    92     parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
    93     nodeColors(composeMap(colorSet, compMap)).
    94     edgeColors(composeMap(functorMap(&color), cutMap)).run();
    95 
    96   std::cout << "Result: strongly_connected_components.eps" << std::endl;
    97 }
    98 
    99 void drawNodeBiconnectedComponents() {
   100   typedef UndirListGraph Graph;
   101   typedef Graph::Node Node;
   102   typedef Graph::UndirEdge UndirEdge;
   103 
   104   Graph graph;
   105   Graph::NodeMap<xy<double> > coords(graph);
   106 
   107   UndirGraphReader<Graph>("undir_components.lgf", graph).
   108     readNodeMap("coordinates_x", xMap(coords)).
   109     readNodeMap("coordinates_y", yMap(coords)).
   110     run();
   111 
   112   ColorSet colorSet;
   113 
   114   Graph::UndirEdgeMap<int> compMap(graph);
   115   Graph::NodeMap<bool> cutMap(graph);
   116   biNodeConnectedComponents(graph, compMap);
   117   biNodeConnectedCutNodes(graph, cutMap);
   118   graphToEps(graph, "bi_node_connected_components.eps").undir().
   119     coords(coords).scaleToA4().enableParallel().
   120     parEdgeDist(20.0).edgeWidthScale(5.0).nodeScale(20.0).
   121     edgeColors(composeMap(colorSet, compMap)).
   122     nodeColors(composeMap(functorMap(&color), cutMap)).
   123     run();
   124 
   125   std::cout << "Result: bi_node_connected_components.eps" << std::endl;
   126 }
   127 
   128 void drawEdgeBiconnectedComponents() {
   129   typedef UndirListGraph Graph;
   130   typedef Graph::Node Node;
   131   typedef Graph::UndirEdge UndirEdge;
   132 
   133   Graph graph;
   134   Graph::NodeMap<xy<double> > coords(graph);
   135 
   136   UndirGraphReader<Graph>("undir_components.lgf", graph).
   137     readNodeMap("coordinates_x", xMap(coords)).
   138     readNodeMap("coordinates_y", yMap(coords)).
   139     run();
   140   
   141   ColorSet colorSet;
   142 
   143   Graph::NodeMap<int> compMap(graph);
   144   Graph::UndirEdgeMap<bool> cutMap(graph);
   145   biEdgeConnectedComponents(graph, compMap);
   146   biEdgeConnectedCutEdges(graph, cutMap);
   147 
   148   graphToEps(graph, "bi_edge_connected_components.eps").undir().
   149     coords(coords).scaleToA4().enableParallel().
   150     parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
   151     nodeColors(composeMap(colorSet, compMap)).
   152     edgeColors(composeMap(functorMap(&color), cutMap)).run();
   153   
   154   std::cout << "Result: bi_edge_connected_components.eps" << std::endl;
   155 }
   156 
   157 void drawBipartitePartitions() {
   158   typedef UndirListGraph Graph;
   159   typedef Graph::Node Node;
   160   typedef Graph::UndirEdge UndirEdge;
   161 
   162   Graph graph;
   163   Graph::NodeMap<xy<double> > coords(graph);
   164 
   165   UndirGraphReader<Graph>("partitions.lgf", graph).
   166     readNodeMap("coordinates_x", xMap(coords)).
   167     readNodeMap("coordinates_y", yMap(coords)).
   168     run();
   169   
   170   ColorSet colorSet;
   171 
   172   Graph::NodeMap<bool> partMap(graph);
   173   bipartitePartitions(graph, partMap);
   174 
   175   graphToEps(graph, "bipartite_partitions.eps").undir().
   176     coords(coords).scaleToA4().enableParallel().
   177     parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
   178     nodeColors(composeMap(functorMap(&color), partMap)).run();
   179   
   180   std::cout << "Result: bipartite_partitions.eps" << std::endl;
   181 } 
   182 
   183 int main() {
   184   srand(time(0));
   185 
   186   drawConnectedComponents();
   187   drawStronglyConnectedComponents();
   188   drawNodeBiconnectedComponents();
   189   drawEdgeBiconnectedComponents();
   190   drawBipartitePartitions();
   191   return 0;
   192 }