COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/strongly_connected_orientation.cc @ 2390:8450951a8e2d

Last change on this file since 2390:8450951a8e2d was 2207:75a29ac69c19, checked in by Alpar Juttner, 13 years ago

xy -> dim2::Point

File size: 3.0 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 <iostream>
20
21#include <lemon/smart_graph.h>
22#include <lemon/graph_reader.h>
23#include <lemon/ugraph_adaptor.h>
24#include <lemon/graph_to_eps.h>
25#include <lemon/dfs.h>
26#include <lemon/topology.h>
27
28
29/// \ingroup demos
30/// \file
31/// \brief Strongly connected orientation
32///
33/// This example demonstrates the usage of the DirUGraphAdaptor,
34/// the DfsVisitor and some topology functions. The program reads
35/// an input undirected graph and with a DfsVisit it orients each edge
36/// to minimize the strongly connected components in the graph. At least
37/// it checks the result of the orientation with to topology functions.
38///
39/// \include strongly_connected_orientation.cc
40
41using namespace lemon;
42using namespace std;
43
44typedef SmartUGraph UGraph;
45UGRAPH_TYPEDEFS(UGraph)
46
47Color color(bool c) {
48  return c ? BLACK : RED;
49}
50
51template <typename DirMap>
52class OrientVisitor : public DfsVisitor<UGraph> {
53public:
54
55  OrientVisitor(const UGraph& ugraph, DirMap& dirMap)
56    : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}
57
58  void discover(const Edge& edge) {
59    _processed.set(edge, true);
60    _dirMap.set(edge, _ugraph.direction(edge));
61  }
62
63  void examine(const Edge& edge) {
64    if (_processed[edge]) return;
65    _processed.set(edge, true);
66    _dirMap.set(edge, _ugraph.direction(edge));
67  } 
68
69private:
70  const UGraph& _ugraph; 
71  DirMap& _dirMap;
72  UGraph::UEdgeMap<bool> _processed;
73};
74
75
76int main() {
77  cout << "Orientation of the strongly_connected_orientation.lgf "
78       << "to be strongly connected" << endl;
79
80  UGraph ugraph;
81  UGraph::NodeMap<dim2::Point<double> > coords(ugraph);
82  UGraphReader<UGraph>("strongly_connected_orientation.lgf", ugraph).
83    readNodeMap("coords", coords).run();
84
85  UGraph::UEdgeMap<bool> dmap(ugraph);
86
87  typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
88  Visitor visitor(ugraph, dmap);
89
90  DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
91
92  dfs.run();
93
94  typedef DirUGraphAdaptor<UGraph> DGraph;
95  DGraph dgraph(ugraph, dmap);
96
97  cout << "The result written into the "
98       << "strongly_connected_orientation.eps file" << endl;
99
100  graphToEps(dgraph, "strongly_connected_orientation.eps").
101    drawArrows().coords(coords).scaleToA4().enableParallel().
102    autoNodeScale().autoEdgeWidthScale().run();
103
104  int num_scc = countStronglyConnectedComponents(dgraph);
105  int num_becc = countBiEdgeConnectedComponents(ugraph);
106
107  if (num_scc != num_becc) {
108    std::cerr << "Wrong Orientation" << std::endl;
109  }
110 
111  return 0;
112}
Note: See TracBrowser for help on using the repository browser.