COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/topology_demo.cc @ 1852:ffa7c6e96330

Last change on this file since 1852:ffa7c6e96330 was 1802:fdfa3aa18607, checked in by Balazs Dezso, 18 years ago

Demo for topology

File size: 5.4 KB
Line 
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 */
16
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>
22
23#include <iostream>
24
25#include <cstdlib>
26#include <ctime>
27
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
35
36using namespace lemon;
37using namespace std;
38
39
40Color color(bool val) {
41  return val ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 1.0);
42}
43
44
45void drawConnectedComponents() {
46  typedef UndirListGraph Graph;
47  typedef Graph::Node Node;
48
49  Graph graph;
50  Graph::NodeMap<xy<double> > coords(graph);
51
52  UndirGraphReader<Graph>("undir_components.lgf", graph).
53    readNodeMap("coordinates_x", xMap(coords)).
54    readNodeMap("coordinates_y", yMap(coords)).
55    run();
56 
57  ColorSet colorSet;
58
59  Graph::NodeMap<int> compMap(graph);
60  connectedComponents(graph, compMap);
61
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();
66
67  std::cout << "Result: connected_components.eps" << std::endl;
68}
69
70void drawStronglyConnectedComponents() {
71  typedef ListGraph Graph;
72  typedef Graph::Node Node;
73
74  Graph graph;
75  Graph::NodeMap<xy<double> > coords(graph);
76
77  GraphReader<Graph>("dir_components.lgf", graph).
78    readNodeMap("coordinates_x", xMap(coords)).
79    readNodeMap("coordinates_y", yMap(coords)).
80    run();
81 
82  ColorSet colorSet;
83
84  Graph::NodeMap<int> compMap(graph);
85  Graph::EdgeMap<bool> cutMap(graph);
86  stronglyConnectedComponents(graph, compMap);
87  stronglyConnectedCutEdges(graph, cutMap);
88
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();
95
96  std::cout << "Result: strongly_connected_components.eps" << std::endl;
97}
98
99void drawNodeBiconnectedComponents() {
100  typedef UndirListGraph Graph;
101  typedef Graph::Node Node;
102  typedef Graph::UndirEdge UndirEdge;
103
104  Graph graph;
105  Graph::NodeMap<xy<double> > coords(graph);
106
107  UndirGraphReader<Graph>("undir_components.lgf", graph).
108    readNodeMap("coordinates_x", xMap(coords)).
109    readNodeMap("coordinates_y", yMap(coords)).
110    run();
111
112  ColorSet colorSet;
113
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();
124
125  std::cout << "Result: bi_node_connected_components.eps" << std::endl;
126}
127
128void drawEdgeBiconnectedComponents() {
129  typedef UndirListGraph Graph;
130  typedef Graph::Node Node;
131  typedef Graph::UndirEdge UndirEdge;
132
133  Graph graph;
134  Graph::NodeMap<xy<double> > coords(graph);
135
136  UndirGraphReader<Graph>("undir_components.lgf", graph).
137    readNodeMap("coordinates_x", xMap(coords)).
138    readNodeMap("coordinates_y", yMap(coords)).
139    run();
140 
141  ColorSet colorSet;
142
143  Graph::NodeMap<int> compMap(graph);
144  Graph::UndirEdgeMap<bool> cutMap(graph);
145  biEdgeConnectedComponents(graph, compMap);
146  biEdgeConnectedCutEdges(graph, cutMap);
147
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();
153 
154  std::cout << "Result: bi_edge_connected_components.eps" << std::endl;
155}
156
157void drawBipartitePartitions() {
158  typedef UndirListGraph Graph;
159  typedef Graph::Node Node;
160  typedef Graph::UndirEdge UndirEdge;
161
162  Graph graph;
163  Graph::NodeMap<xy<double> > coords(graph);
164
165  UndirGraphReader<Graph>("partitions.lgf", graph).
166    readNodeMap("coordinates_x", xMap(coords)).
167    readNodeMap("coordinates_y", yMap(coords)).
168    run();
169 
170  ColorSet colorSet;
171
172  Graph::NodeMap<bool> partMap(graph);
173  bipartitePartitions(graph, partMap);
174
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();
179 
180  std::cout << "Result: bipartite_partitions.eps" << std::endl;
181}
182
183int main() {
184  srand(time(0));
185
186  drawConnectedComponents();
187  drawStronglyConnectedComponents();
188  drawNodeBiconnectedComponents();
189  drawEdgeBiconnectedComponents();
190  drawBipartitePartitions();
191  return 0;
192}
Note: See TracBrowser for help on using the repository browser.