COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/topology_demo.cc @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 11 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 5.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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 lemon::dim2;
40using namespace std;
41
42
43Color color(bool val) {
44  return val ? RED : BLUE;
45}
46
47
48void drawConnectedComponents() {
49  typedef ListUGraph Graph;
50  typedef Graph::Node Node;
51
52  Graph graph;
53  Graph::NodeMap<Point<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  Palette palette;
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    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<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().drawArrows().
93    nodeColors(composeMap(palette, 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 ListUGraph Graph;
101  typedef Graph::Node Node;
102  typedef Graph::UEdge UEdge;
103
104  Graph graph;
105  Graph::NodeMap<Point<double> > coords(graph);
106
107  UGraphReader<Graph>("u_components.lgf", graph).
108    readNodeMap("coordinates_x", xMap(coords)).
109    readNodeMap("coordinates_y", yMap(coords)).
110    run();
111
112  Palette palette;
113
114  Graph::UEdgeMap<int> compMap(graph);
115  Graph::NodeMap<bool> cutMap(graph);
116  biNodeConnectedComponents(graph, compMap);
117  biNodeConnectedCutNodes(graph, cutMap);
118
119  graphToEps(graph, "bi_node_connected_components.eps").undirected().
120    coords(coords).scaleToA4().enableParallel().
121    edgeColors(composeMap(palette, 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 ListUGraph Graph;
130  typedef Graph::Node Node;
131  typedef Graph::UEdge UEdge;
132
133  Graph graph;
134  Graph::NodeMap<Point<double> > coords(graph);
135
136  UGraphReader<Graph>("u_components.lgf", graph).
137    readNodeMap("coordinates_x", xMap(coords)).
138    readNodeMap("coordinates_y", yMap(coords)).
139    run();
140 
141  Palette palette;
142
143  Graph::NodeMap<int> compMap(graph);
144  Graph::UEdgeMap<bool> cutMap(graph);
145  biEdgeConnectedComponents(graph, compMap);
146  biEdgeConnectedCutEdges(graph, cutMap);
147
148  graphToEps(graph, "bi_edge_connected_components.eps").undirected().
149    coords(coords).scaleToA4().enableParallel().
150    nodeColors(composeMap(palette, compMap)).
151    edgeColors(composeMap(functorMap(&color), cutMap)).run();
152 
153  std::cout << "Result: bi_edge_connected_components.eps" << std::endl;
154}
155
156void drawBipartitePartitions() {
157  typedef ListUGraph Graph;
158  typedef Graph::Node Node;
159  typedef Graph::UEdge UEdge;
160
161  Graph graph;
162  Graph::NodeMap<Point<double> > coords(graph);
163
164  UGraphReader<Graph>("partitions.lgf", graph).
165    readNodeMap("coordinates_x", xMap(coords)).
166    readNodeMap("coordinates_y", yMap(coords)).
167    run();
168 
169  Palette palette;
170
171  Graph::NodeMap<bool> partMap(graph);
172  bipartitePartitions(graph, partMap);
173
174  graphToEps(graph, "bipartite_partitions.eps").undirected().
175    coords(coords).scaleToA4().enableParallel().
176    nodeColors(composeMap(functorMap(&color), partMap)).run();
177 
178  std::cout << "Result: bipartite_partitions.eps" << std::endl;
179}
180
181int main() {
182  drawConnectedComponents();
183  drawStronglyConnectedComponents();
184  drawNodeBiconnectedComponents();
185  drawEdgeBiconnectedComponents();
186  drawBipartitePartitions();
187  return 0;
188}
Note: See TracBrowser for help on using the repository browser.