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