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