COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/topology_demo.cc @ 2207:75a29ac69c19

Last change on this file since 2207:75a29ac69c19 was 2207:75a29ac69c19, checked in by Alpar Juttner, 13 years ago

xy -> dim2::Point

File size: 5.4 KB
Line 
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/dim2.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
38using namespace lemon;
39using namespace std;
40
41
42Color color(bool val) {
43  return val ? RED : BLUE;
44}
45
46
47void drawConnectedComponents() {
48  typedef ListUGraph Graph;
49  typedef Graph::Node Node;
50
51  Graph graph;
52  Graph::NodeMap<dim2::Point<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  Palette palette;
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(palette, compMap)).run();
68
69  std::cout << "Result: connected_components.eps" << std::endl;
70}
71
72void drawStronglyConnectedComponents() {
73  typedef ListGraph Graph;
74  typedef Graph::Node Node;
75
76  Graph graph;
77  Graph::NodeMap<dim2::Point<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  Palette palette;
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(palette, compMap)).
96    edgeColors(composeMap(functorMap(&color), cutMap)).run();
97
98  std::cout << "Result: strongly_connected_components.eps" << std::endl;
99}
100
101void drawNodeBiconnectedComponents() {
102  typedef ListUGraph Graph;
103  typedef Graph::Node Node;
104  typedef Graph::UEdge UEdge;
105
106  Graph graph;
107  Graph::NodeMap<dim2::Point<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  Palette palette;
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(palette, compMap)).
125    nodeColors(composeMap(functorMap(&color), cutMap)).
126    run();
127
128  std::cout << "Result: bi_node_connected_components.eps" << std::endl;
129}
130
131void drawEdgeBiconnectedComponents() {
132  typedef ListUGraph Graph;
133  typedef Graph::Node Node;
134  typedef Graph::UEdge UEdge;
135
136  Graph graph;
137  Graph::NodeMap<dim2::Point<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  Palette palette;
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(palette, compMap)).
155    edgeColors(composeMap(functorMap(&color), cutMap)).run();
156 
157  std::cout << "Result: bi_edge_connected_components.eps" << std::endl;
158}
159
160void drawBipartitePartitions() {
161  typedef ListUGraph Graph;
162  typedef Graph::Node Node;
163  typedef Graph::UEdge UEdge;
164
165  Graph graph;
166  Graph::NodeMap<dim2::Point<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  Palette palette;
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
186int main() {
187  srand(time(0));
188
189  drawConnectedComponents();
190  drawStronglyConnectedComponents();
191  drawNodeBiconnectedComponents();
192  drawEdgeBiconnectedComponents();
193  drawBipartitePartitions();
194  return 0;
195}
Note: See TracBrowser for help on using the repository browser.