COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/topology_demo.cc @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 12 years ago

Happy New Year to all source files!

File size: 5.0 KB
RevLine 
[1802]1/* -*- C++ -*-
2 *
[1956]3 * This file is a part of LEMON, a generic C++ optimization library
4 *
[2391]5 * Copyright (C) 2003-2007
[1956]6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1802]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>
[2207]23#include <lemon/dim2.h>
[1802]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;
[2306]39using namespace lemon::dim2;
[1802]40using namespace std;
41
42
43Color color(bool val) {
[2174]44  return val ? RED : BLUE;
[1802]45}
46
47
48void drawConnectedComponents() {
[1909]49  typedef ListUGraph Graph;
[1802]50  typedef Graph::Node Node;
51
52  Graph graph;
[2306]53  Graph::NodeMap<Point<double> > coords(graph);
[1802]54
[1909]55  UGraphReader<Graph>("u_components.lgf", graph).
[1802]56    readNodeMap("coordinates_x", xMap(coords)).
57    readNodeMap("coordinates_y", yMap(coords)).
58    run();
59 
[2172]60  Palette palette;
[1802]61
62  Graph::NodeMap<int> compMap(graph);
63  connectedComponents(graph, compMap);
64
[1910]65  graphToEps(graph, "connected_components.eps").undirected().
[1802]66    coords(coords).scaleToA4().enableParallel().
[2172]67    nodeColors(composeMap(palette, compMap)).run();
[1802]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;
[2306]77  Graph::NodeMap<Point<double> > coords(graph);
[1802]78
79  GraphReader<Graph>("dir_components.lgf", graph).
80    readNodeMap("coordinates_x", xMap(coords)).
81    readNodeMap("coordinates_y", yMap(coords)).
82    run();
83 
[2172]84  Palette palette;
[1802]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").
[2306]92    coords(coords).scaleToA4().enableParallel().drawArrows().
[2172]93    nodeColors(composeMap(palette, compMap)).
[1802]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;
[2306]105  Graph::NodeMap<Point<double> > coords(graph);
[1802]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
[2172]112  Palette palette;
[1802]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().
[2172]121    edgeColors(composeMap(palette, compMap)).
[1802]122    nodeColors(composeMap(functorMap(&color), cutMap)).
123    run();
124
125  std::cout << "Result: bi_node_connected_components.eps" << std::endl;
126}
127
128void drawEdgeBiconnectedComponents() {
[1909]129  typedef ListUGraph Graph;
[1802]130  typedef Graph::Node Node;
[1909]131  typedef Graph::UEdge UEdge;
[1802]132
133  Graph graph;
[2306]134  Graph::NodeMap<Point<double> > coords(graph);
[1802]135
[1909]136  UGraphReader<Graph>("u_components.lgf", graph).
[1802]137    readNodeMap("coordinates_x", xMap(coords)).
138    readNodeMap("coordinates_y", yMap(coords)).
139    run();
140 
[2172]141  Palette palette;
[1802]142
143  Graph::NodeMap<int> compMap(graph);
[1909]144  Graph::UEdgeMap<bool> cutMap(graph);
[1802]145  biEdgeConnectedComponents(graph, compMap);
146  biEdgeConnectedCutEdges(graph, cutMap);
147
[1910]148  graphToEps(graph, "bi_edge_connected_components.eps").undirected().
[1802]149    coords(coords).scaleToA4().enableParallel().
[2172]150    nodeColors(composeMap(palette, compMap)).
[1802]151    edgeColors(composeMap(functorMap(&color), cutMap)).run();
152 
153  std::cout << "Result: bi_edge_connected_components.eps" << std::endl;
154}
155
156void drawBipartitePartitions() {
[1909]157  typedef ListUGraph Graph;
[1802]158  typedef Graph::Node Node;
[1909]159  typedef Graph::UEdge UEdge;
[1802]160
161  Graph graph;
[2306]162  Graph::NodeMap<Point<double> > coords(graph);
[1802]163
[1909]164  UGraphReader<Graph>("partitions.lgf", graph).
[1802]165    readNodeMap("coordinates_x", xMap(coords)).
166    readNodeMap("coordinates_y", yMap(coords)).
167    run();
168 
[2172]169  Palette palette;
[1802]170
171  Graph::NodeMap<bool> partMap(graph);
172  bipartitePartitions(graph, partMap);
173
[1910]174  graphToEps(graph, "bipartite_partitions.eps").undirected().
[1802]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.