3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
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>
33 /// \brief Demo what shows the result of some topology functions.
35 /// Demo what shows the result of some topology functions.
37 /// \include topology_demo.cc
39 using namespace lemon;
43 Color color(bool val) {
44 return val ? Color(1.0, 0.0, 0.0) : Color(0.0, 0.0, 1.0);
48 void drawConnectedComponents() {
49 typedef ListUGraph Graph;
50 typedef Graph::Node Node;
53 Graph::NodeMap<xy<double> > coords(graph);
55 UGraphReader<Graph>("u_components.lgf", graph).
56 readNodeMap("coordinates_x", xMap(coords)).
57 readNodeMap("coordinates_y", yMap(coords)).
62 Graph::NodeMap<int> compMap(graph);
63 connectedComponents(graph, compMap);
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();
70 std::cout << "Result: connected_components.eps" << std::endl;
73 void drawStronglyConnectedComponents() {
74 typedef ListGraph Graph;
75 typedef Graph::Node Node;
78 Graph::NodeMap<xy<double> > coords(graph);
80 GraphReader<Graph>("dir_components.lgf", graph).
81 readNodeMap("coordinates_x", xMap(coords)).
82 readNodeMap("coordinates_y", yMap(coords)).
87 Graph::NodeMap<int> compMap(graph);
88 Graph::EdgeMap<bool> cutMap(graph);
89 stronglyConnectedComponents(graph, compMap);
90 stronglyConnectedCutEdges(graph, cutMap);
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();
99 std::cout << "Result: strongly_connected_components.eps" << std::endl;
102 void drawNodeBiconnectedComponents() {
103 typedef ListUGraph Graph;
104 typedef Graph::Node Node;
105 typedef Graph::UEdge UEdge;
108 Graph::NodeMap<xy<double> > coords(graph);
110 UGraphReader<Graph>("u_components.lgf", graph).
111 readNodeMap("coordinates_x", xMap(coords)).
112 readNodeMap("coordinates_y", yMap(coords)).
117 Graph::UEdgeMap<int> compMap(graph);
118 Graph::NodeMap<bool> cutMap(graph);
119 biNodeConnectedComponents(graph, compMap);
120 biNodeConnectedCutNodes(graph, cutMap);
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)).
129 std::cout << "Result: bi_node_connected_components.eps" << std::endl;
132 void drawEdgeBiconnectedComponents() {
133 typedef ListUGraph Graph;
134 typedef Graph::Node Node;
135 typedef Graph::UEdge UEdge;
138 Graph::NodeMap<xy<double> > coords(graph);
140 UGraphReader<Graph>("u_components.lgf", graph).
141 readNodeMap("coordinates_x", xMap(coords)).
142 readNodeMap("coordinates_y", yMap(coords)).
147 Graph::NodeMap<int> compMap(graph);
148 Graph::UEdgeMap<bool> cutMap(graph);
149 biEdgeConnectedComponents(graph, compMap);
150 biEdgeConnectedCutEdges(graph, cutMap);
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();
158 std::cout << "Result: bi_edge_connected_components.eps" << std::endl;
161 void drawBipartitePartitions() {
162 typedef ListUGraph Graph;
163 typedef Graph::Node Node;
164 typedef Graph::UEdge UEdge;
167 Graph::NodeMap<xy<double> > coords(graph);
169 UGraphReader<Graph>("partitions.lgf", graph).
170 readNodeMap("coordinates_x", xMap(coords)).
171 readNodeMap("coordinates_y", yMap(coords)).
176 Graph::NodeMap<bool> partMap(graph);
177 bipartitePartitions(graph, partMap);
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();
184 std::cout << "Result: bipartite_partitions.eps" << std::endl;
190 drawConnectedComponents();
191 drawStronglyConnectedComponents();
192 drawNodeBiconnectedComponents();
193 drawEdgeBiconnectedComponents();
194 drawBipartitePartitions();