demo/topology_demo.cc
author deba
Fri, 03 Nov 2006 14:24:44 +0000
changeset 2291 fbc4af1f9378
parent 2207 75a29ac69c19
child 2306 42cce226b87b
permissions -rw-r--r--
Spellchecking
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@1956
     5
 * Copyright (C) 2003-2006
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@1802
    39
using namespace std;
deba@1802
    40
deba@1802
    41
deba@1802
    42
Color color(bool val) {
alpar@2174
    43
  return val ? RED : BLUE;
deba@1802
    44
}
deba@1802
    45
deba@1802
    46
deba@1802
    47
void drawConnectedComponents() {
klao@1909
    48
  typedef ListUGraph Graph;
deba@1802
    49
  typedef Graph::Node Node;
deba@1802
    50
deba@1802
    51
  Graph graph;
alpar@2207
    52
  Graph::NodeMap<dim2::Point<double> > coords(graph);
deba@1802
    53
klao@1909
    54
  UGraphReader<Graph>("u_components.lgf", graph).
deba@1802
    55
    readNodeMap("coordinates_x", xMap(coords)).
deba@1802
    56
    readNodeMap("coordinates_y", yMap(coords)).
deba@1802
    57
    run();
deba@1802
    58
  
alpar@2172
    59
  Palette palette;
deba@1802
    60
deba@1802
    61
  Graph::NodeMap<int> compMap(graph);
deba@1802
    62
  connectedComponents(graph, compMap);
deba@1802
    63
deba@1910
    64
  graphToEps(graph, "connected_components.eps").undirected().
deba@1802
    65
    coords(coords).scaleToA4().enableParallel().
deba@1802
    66
    parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
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;
alpar@2207
    77
  Graph::NodeMap<dim2::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@1802
    92
    coords(coords).scaleToA4().enableParallel().
deba@1802
    93
    drawArrows().arrowWidth(10.0).arrowLength(10.0).
deba@1802
    94
    parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
alpar@2172
    95
    nodeColors(composeMap(palette, compMap)).
deba@1802
    96
    edgeColors(composeMap(functorMap(&color), cutMap)).run();
deba@1802
    97
deba@1802
    98
  std::cout << "Result: strongly_connected_components.eps" << std::endl;
deba@1802
    99
}
deba@1802
   100
deba@1802
   101
void drawNodeBiconnectedComponents() {
klao@1909
   102
  typedef ListUGraph Graph;
deba@1802
   103
  typedef Graph::Node Node;
klao@1909
   104
  typedef Graph::UEdge UEdge;
deba@1802
   105
deba@1802
   106
  Graph graph;
alpar@2207
   107
  Graph::NodeMap<dim2::Point<double> > coords(graph);
deba@1802
   108
klao@1909
   109
  UGraphReader<Graph>("u_components.lgf", graph).
deba@1802
   110
    readNodeMap("coordinates_x", xMap(coords)).
deba@1802
   111
    readNodeMap("coordinates_y", yMap(coords)).
deba@1802
   112
    run();
deba@1802
   113
alpar@2172
   114
  Palette palette;
deba@1802
   115
klao@1909
   116
  Graph::UEdgeMap<int> compMap(graph);
deba@1802
   117
  Graph::NodeMap<bool> cutMap(graph);
deba@1802
   118
  biNodeConnectedComponents(graph, compMap);
deba@1802
   119
  biNodeConnectedCutNodes(graph, cutMap);
deba@1910
   120
deba@1910
   121
  graphToEps(graph, "bi_node_connected_components.eps").undirected().
deba@1802
   122
    coords(coords).scaleToA4().enableParallel().
deba@1802
   123
    parEdgeDist(20.0).edgeWidthScale(5.0).nodeScale(20.0).
alpar@2172
   124
    edgeColors(composeMap(palette, compMap)).
deba@1802
   125
    nodeColors(composeMap(functorMap(&color), cutMap)).
deba@1802
   126
    run();
deba@1802
   127
deba@1802
   128
  std::cout << "Result: bi_node_connected_components.eps" << std::endl;
deba@1802
   129
}
deba@1802
   130
deba@1802
   131
void drawEdgeBiconnectedComponents() {
klao@1909
   132
  typedef ListUGraph Graph;
deba@1802
   133
  typedef Graph::Node Node;
klao@1909
   134
  typedef Graph::UEdge UEdge;
deba@1802
   135
deba@1802
   136
  Graph graph;
alpar@2207
   137
  Graph::NodeMap<dim2::Point<double> > coords(graph);
deba@1802
   138
klao@1909
   139
  UGraphReader<Graph>("u_components.lgf", graph).
deba@1802
   140
    readNodeMap("coordinates_x", xMap(coords)).
deba@1802
   141
    readNodeMap("coordinates_y", yMap(coords)).
deba@1802
   142
    run();
deba@1802
   143
  
alpar@2172
   144
  Palette palette;
deba@1802
   145
deba@1802
   146
  Graph::NodeMap<int> compMap(graph);
klao@1909
   147
  Graph::UEdgeMap<bool> cutMap(graph);
deba@1802
   148
  biEdgeConnectedComponents(graph, compMap);
deba@1802
   149
  biEdgeConnectedCutEdges(graph, cutMap);
deba@1802
   150
deba@1910
   151
  graphToEps(graph, "bi_edge_connected_components.eps").undirected().
deba@1802
   152
    coords(coords).scaleToA4().enableParallel().
deba@1802
   153
    parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
alpar@2172
   154
    nodeColors(composeMap(palette, compMap)).
deba@1802
   155
    edgeColors(composeMap(functorMap(&color), cutMap)).run();
deba@1802
   156
  
deba@1802
   157
  std::cout << "Result: bi_edge_connected_components.eps" << std::endl;
deba@1802
   158
}
deba@1802
   159
deba@1802
   160
void drawBipartitePartitions() {
klao@1909
   161
  typedef ListUGraph Graph;
deba@1802
   162
  typedef Graph::Node Node;
klao@1909
   163
  typedef Graph::UEdge UEdge;
deba@1802
   164
deba@1802
   165
  Graph graph;
alpar@2207
   166
  Graph::NodeMap<dim2::Point<double> > coords(graph);
deba@1802
   167
klao@1909
   168
  UGraphReader<Graph>("partitions.lgf", graph).
deba@1802
   169
    readNodeMap("coordinates_x", xMap(coords)).
deba@1802
   170
    readNodeMap("coordinates_y", yMap(coords)).
deba@1802
   171
    run();
deba@1802
   172
  
alpar@2172
   173
  Palette palette;
deba@1802
   174
deba@1802
   175
  Graph::NodeMap<bool> partMap(graph);
deba@1802
   176
  bipartitePartitions(graph, partMap);
deba@1802
   177
deba@1910
   178
  graphToEps(graph, "bipartite_partitions.eps").undirected().
deba@1802
   179
    coords(coords).scaleToA4().enableParallel().
deba@1802
   180
    parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
deba@1802
   181
    nodeColors(composeMap(functorMap(&color), partMap)).run();
deba@1802
   182
  
deba@1802
   183
  std::cout << "Result: bipartite_partitions.eps" << std::endl;
deba@1802
   184
} 
deba@1802
   185
deba@1802
   186
int main() {
deba@1802
   187
  drawConnectedComponents();
deba@1802
   188
  drawStronglyConnectedComponents();
deba@1802
   189
  drawNodeBiconnectedComponents();
deba@1802
   190
  drawEdgeBiconnectedComponents();
deba@1802
   191
  drawBipartitePartitions();
deba@1802
   192
  return 0;
deba@1802
   193
}