lemon-0.x: demo/topology_demo.cc@52f5a7f9fb48

     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  */

    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>

    23 #include <iostream>

    25 #include <cstdlib>

    26 #include <ctime>

    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

    36 using namespace lemon;

    37 using namespace std;

    40 Color color(bool val) {

    41   return val ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 1.0);

    42 }

    45 void drawConnectedComponents() {

    46   typedef UndirListGraph Graph;

    47   typedef Graph::Node Node;

    49   Graph graph;

    50   Graph::NodeMap<xy<double> > coords(graph);

    52   UndirGraphReader<Graph>("undir_components.lgf", graph).

    53     readNodeMap("coordinates_x", xMap(coords)).

    54     readNodeMap("coordinates_y", yMap(coords)).

    55     run();

    57   ColorSet colorSet;

    59   Graph::NodeMap<int> compMap(graph);

    60   connectedComponents(graph, compMap);

    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();

    67   std::cout << "Result: connected_components.eps" << std::endl;

    68 }

    70 void drawStronglyConnectedComponents() {

    71   typedef ListGraph Graph;

    72   typedef Graph::Node Node;

    74   Graph graph;

    75   Graph::NodeMap<xy<double> > coords(graph);

    77   GraphReader<Graph>("dir_components.lgf", graph).

    78     readNodeMap("coordinates_x", xMap(coords)).

    79     readNodeMap("coordinates_y", yMap(coords)).

    80     run();

    82   ColorSet colorSet;

    84   Graph::NodeMap<int> compMap(graph);

    85   Graph::EdgeMap<bool> cutMap(graph);

    86   stronglyConnectedComponents(graph, compMap);

    87   stronglyConnectedCutEdges(graph, cutMap);

    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();

    96   std::cout << "Result: strongly_connected_components.eps" << std::endl;

    97 }

    99 void drawNodeBiconnectedComponents() {

   100   typedef UndirListGraph Graph;

   101   typedef Graph::Node Node;

   102   typedef Graph::UndirEdge UndirEdge;

   104   Graph graph;

   105   Graph::NodeMap<xy<double> > coords(graph);

   107   UndirGraphReader<Graph>("undir_components.lgf", graph).

   108     readNodeMap("coordinates_x", xMap(coords)).

   109     readNodeMap("coordinates_y", yMap(coords)).

   110     run();

   112   ColorSet colorSet;

   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();

   125   std::cout << "Result: bi_node_connected_components.eps" << std::endl;

   126 }

   128 void drawEdgeBiconnectedComponents() {

   129   typedef UndirListGraph Graph;

   130   typedef Graph::Node Node;

   131   typedef Graph::UndirEdge UndirEdge;

   133   Graph graph;

   134   Graph::NodeMap<xy<double> > coords(graph);

   136   UndirGraphReader<Graph>("undir_components.lgf", graph).

   137     readNodeMap("coordinates_x", xMap(coords)).

   138     readNodeMap("coordinates_y", yMap(coords)).

   139     run();

   141   ColorSet colorSet;

   143   Graph::NodeMap<int> compMap(graph);

   144   Graph::UndirEdgeMap<bool> cutMap(graph);

   145   biEdgeConnectedComponents(graph, compMap);

   146   biEdgeConnectedCutEdges(graph, cutMap);

   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();

   154   std::cout << "Result: bi_edge_connected_components.eps" << std::endl;

   155 }

   157 void drawBipartitePartitions() {

   158   typedef UndirListGraph Graph;

   159   typedef Graph::Node Node;

   160   typedef Graph::UndirEdge UndirEdge;

   162   Graph graph;

   163   Graph::NodeMap<xy<double> > coords(graph);

   165   UndirGraphReader<Graph>("partitions.lgf", graph).

   166     readNodeMap("coordinates_x", xMap(coords)).

   167     readNodeMap("coordinates_y", yMap(coords)).

   168     run();

   170   ColorSet colorSet;

   172   Graph::NodeMap<bool> partMap(graph);

   173   bipartitePartitions(graph, partMap);

   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();

   180   std::cout << "Result: bipartite_partitions.eps" << std::endl;

   181 }

   183 int main() {

   184   srand(time(0));

   186   drawConnectedComponents();

   187   drawStronglyConnectedComponents();

   188   drawNodeBiconnectedComponents();

   189   drawEdgeBiconnectedComponents();

   190   drawBipartitePartitions();

   191   return 0;

   192 }

author	hegyi
	Tue, 03 Jan 2006 14:56:45 +0000
changeset 1869	52f5a7f9fb48
child 1875	98698b69a902
permissions	-rw-r--r--