COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/topology_demo.cc @ 2115:4cd528a30ec1

Last change on this file since 2115:4cd528a30ec1 was 2115:4cd528a30ec1, checked in by Balazs Dezso, 13 years ago

Splitted graph files

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/list_ugraph.h>
21#include <lemon/topology.h>
22#include <lemon/graph_to_eps.h>
23#include <lemon/graph_reader.h>
24#include <lemon/xy.h>
25
26#include <iostream>
27
28#include <cstdlib>
29#include <ctime>
30
31/// \ingroup demos
32/// \file
33/// \brief Demo what shows the result of some topology functions.
34///
35///  Demo what shows the result of some topology functions.
36///
37/// \include topology_demo.cc
38
39using namespace lemon;
40using namespace std;
41
42
43Color color(bool val) {
44  return val ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 1.0);
45}
46
47
48void drawConnectedComponents() {
49  typedef ListUGraph Graph;
50  typedef Graph::Node Node;
51
52  Graph graph;
53  Graph::NodeMap<xy<double> > coords(graph);
54
55  UGraphReader<Graph>("u_components.lgf", graph).
56    readNodeMap("coordinates_x", xMap(coords)).
57    readNodeMap("coordinates_y", yMap(coords)).
58    run();
59 
60  ColorSet colorSet;
61
62  Graph::NodeMap<int> compMap(graph);
63  connectedComponents(graph, compMap);
64
65  graphToEps(graph, "connected_components.eps").undirected().
66    coords(coords).scaleToA4().enableParallel().
67    parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
68    nodeColors(composeMap(colorSet, compMap)).run();
69
70  std::cout << "Result: connected_components.eps" << std::endl;
71}
72
73void drawStronglyConnectedComponents() {
74  typedef ListGraph Graph;
75  typedef Graph::Node Node;
76
77  Graph graph;
78  Graph::NodeMap<xy<double> > coords(graph);
79
80  GraphReader<Graph>("dir_components.lgf", graph).
81    readNodeMap("coordinates_x", xMap(coords)).
82    readNodeMap("coordinates_y", yMap(coords)).
83    run();
84 
85  ColorSet colorSet;
86
87  Graph::NodeMap<int> compMap(graph);
88  Graph::EdgeMap<bool> cutMap(graph);
89  stronglyConnectedComponents(graph, compMap);
90  stronglyConnectedCutEdges(graph, cutMap);
91
92  graphToEps(graph, "strongly_connected_components.eps").
93    coords(coords).scaleToA4().enableParallel().
94    drawArrows().arrowWidth(10.0).arrowLength(10.0).
95    parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
96    nodeColors(composeMap(colorSet, compMap)).
97    edgeColors(composeMap(functorMap(&color), cutMap)).run();
98
99  std::cout << "Result: strongly_connected_components.eps" << std::endl;
100}
101
102void drawNodeBiconnectedComponents() {
103  typedef ListUGraph Graph;
104  typedef Graph::Node Node;
105  typedef Graph::UEdge UEdge;
106
107  Graph graph;
108  Graph::NodeMap<xy<double> > coords(graph);
109
110  UGraphReader<Graph>("u_components.lgf", graph).
111    readNodeMap("coordinates_x", xMap(coords)).
112    readNodeMap("coordinates_y", yMap(coords)).
113    run();
114
115  ColorSet colorSet;
116
117  Graph::UEdgeMap<int> compMap(graph);
118  Graph::NodeMap<bool> cutMap(graph);
119  biNodeConnectedComponents(graph, compMap);
120  biNodeConnectedCutNodes(graph, cutMap);
121
122  graphToEps(graph, "bi_node_connected_components.eps").undirected().
123    coords(coords).scaleToA4().enableParallel().
124    parEdgeDist(20.0).edgeWidthScale(5.0).nodeScale(20.0).
125    edgeColors(composeMap(colorSet, compMap)).
126    nodeColors(composeMap(functorMap(&color), cutMap)).
127    run();
128
129  std::cout << "Result: bi_node_connected_components.eps" << std::endl;
130}
131
132void drawEdgeBiconnectedComponents() {
133  typedef ListUGraph Graph;
134  typedef Graph::Node Node;
135  typedef Graph::UEdge UEdge;
136
137  Graph graph;
138  Graph::NodeMap<xy<double> > coords(graph);
139
140  UGraphReader<Graph>("u_components.lgf", graph).
141    readNodeMap("coordinates_x", xMap(coords)).
142    readNodeMap("coordinates_y", yMap(coords)).
143    run();
144 
145  ColorSet colorSet;
146
147  Graph::NodeMap<int> compMap(graph);
148  Graph::UEdgeMap<bool> cutMap(graph);
149  biEdgeConnectedComponents(graph, compMap);
150  biEdgeConnectedCutEdges(graph, cutMap);
151
152  graphToEps(graph, "bi_edge_connected_components.eps").undirected().
153    coords(coords).scaleToA4().enableParallel().
154    parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
155    nodeColors(composeMap(colorSet, compMap)).
156    edgeColors(composeMap(functorMap(&color), cutMap)).run();
157 
158  std::cout << "Result: bi_edge_connected_components.eps" << std::endl;
159}
160
161void drawBipartitePartitions() {
162  typedef ListUGraph Graph;
163  typedef Graph::Node Node;
164  typedef Graph::UEdge UEdge;
165
166  Graph graph;
167  Graph::NodeMap<xy<double> > coords(graph);
168
169  UGraphReader<Graph>("partitions.lgf", graph).
170    readNodeMap("coordinates_x", xMap(coords)).
171    readNodeMap("coordinates_y", yMap(coords)).
172    run();
173 
174  ColorSet colorSet;
175
176  Graph::NodeMap<bool> partMap(graph);
177  bipartitePartitions(graph, partMap);
178
179  graphToEps(graph, "bipartite_partitions.eps").undirected().
180    coords(coords).scaleToA4().enableParallel().
181    parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
182    nodeColors(composeMap(functorMap(&color), partMap)).run();
183 
184  std::cout << "Result: bipartite_partitions.eps" << std::endl;
185}
186
187int main() {
188  srand(time(0));
189
190  drawConnectedComponents();
191  drawStronglyConnectedComponents();
192  drawNodeBiconnectedComponents();
193  drawEdgeBiconnectedComponents();
194  drawBipartitePartitions();
195  return 0;
196}
Note: See TracBrowser for help on using the repository browser.