COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/topology_demo.cc @ 1913:49fe71fce7fb

Last change on this file since 1913:49fe71fce7fb was 1910:f95eea8c34b0, checked in by Balazs Dezso, 18 years ago

Bipartite => Bp
Upper => A
Lower => B

+ some bug fix

File size: 5.4 KB
RevLine 
[1802]1/* -*- C++ -*-
2 * demo/min_route.cc - Part of LEMON, a generic C++ optimization library
3 *
[1875]4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1802]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() {
[1909]46  typedef ListUGraph Graph;
[1802]47  typedef Graph::Node Node;
48
49  Graph graph;
50  Graph::NodeMap<xy<double> > coords(graph);
51
[1909]52  UGraphReader<Graph>("u_components.lgf", graph).
[1802]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
[1910]62  graphToEps(graph, "connected_components.eps").undirected().
[1802]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() {
[1909]100  typedef ListUGraph Graph;
[1802]101  typedef Graph::Node Node;
[1909]102  typedef Graph::UEdge UEdge;
[1802]103
104  Graph graph;
105  Graph::NodeMap<xy<double> > coords(graph);
106
[1909]107  UGraphReader<Graph>("u_components.lgf", graph).
[1802]108    readNodeMap("coordinates_x", xMap(coords)).
109    readNodeMap("coordinates_y", yMap(coords)).
110    run();
111
112  ColorSet colorSet;
113
[1909]114  Graph::UEdgeMap<int> compMap(graph);
[1802]115  Graph::NodeMap<bool> cutMap(graph);
116  biNodeConnectedComponents(graph, compMap);
117  biNodeConnectedCutNodes(graph, cutMap);
[1910]118
119  graphToEps(graph, "bi_node_connected_components.eps").undirected().
[1802]120    coords(coords).scaleToA4().enableParallel().
121    parEdgeDist(20.0).edgeWidthScale(5.0).nodeScale(20.0).
122    edgeColors(composeMap(colorSet, compMap)).
123    nodeColors(composeMap(functorMap(&color), cutMap)).
124    run();
125
126  std::cout << "Result: bi_node_connected_components.eps" << std::endl;
127}
128
129void drawEdgeBiconnectedComponents() {
[1909]130  typedef ListUGraph Graph;
[1802]131  typedef Graph::Node Node;
[1909]132  typedef Graph::UEdge UEdge;
[1802]133
134  Graph graph;
135  Graph::NodeMap<xy<double> > coords(graph);
136
[1909]137  UGraphReader<Graph>("u_components.lgf", graph).
[1802]138    readNodeMap("coordinates_x", xMap(coords)).
139    readNodeMap("coordinates_y", yMap(coords)).
140    run();
141 
142  ColorSet colorSet;
143
144  Graph::NodeMap<int> compMap(graph);
[1909]145  Graph::UEdgeMap<bool> cutMap(graph);
[1802]146  biEdgeConnectedComponents(graph, compMap);
147  biEdgeConnectedCutEdges(graph, cutMap);
148
[1910]149  graphToEps(graph, "bi_edge_connected_components.eps").undirected().
[1802]150    coords(coords).scaleToA4().enableParallel().
151    parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
152    nodeColors(composeMap(colorSet, compMap)).
153    edgeColors(composeMap(functorMap(&color), cutMap)).run();
154 
155  std::cout << "Result: bi_edge_connected_components.eps" << std::endl;
156}
157
158void drawBipartitePartitions() {
[1909]159  typedef ListUGraph Graph;
[1802]160  typedef Graph::Node Node;
[1909]161  typedef Graph::UEdge UEdge;
[1802]162
163  Graph graph;
164  Graph::NodeMap<xy<double> > coords(graph);
165
[1909]166  UGraphReader<Graph>("partitions.lgf", graph).
[1802]167    readNodeMap("coordinates_x", xMap(coords)).
168    readNodeMap("coordinates_y", yMap(coords)).
169    run();
170 
171  ColorSet colorSet;
172
173  Graph::NodeMap<bool> partMap(graph);
174  bipartitePartitions(graph, partMap);
175
[1910]176  graphToEps(graph, "bipartite_partitions.eps").undirected().
[1802]177    coords(coords).scaleToA4().enableParallel().
178    parEdgeDist(20.0).edgeWidthScale(2.0).nodeScale(20.0).
179    nodeColors(composeMap(functorMap(&color), partMap)).run();
180 
181  std::cout << "Result: bipartite_partitions.eps" << std::endl;
182}
183
184int main() {
185  srand(time(0));
186
187  drawConnectedComponents();
188  drawStronglyConnectedComponents();
189  drawNodeBiconnectedComponents();
190  drawEdgeBiconnectedComponents();
191  drawBipartitePartitions();
192  return 0;
193}
Note: See TracBrowser for help on using the repository browser.