Include functional because of std::less.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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
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>
31 /// \brief Strongly connected orientation
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.
39 /// \include strongly_connected_orientation.cc
41 using namespace lemon;
44 typedef SmartUGraph UGraph;
45 UGRAPH_TYPEDEFS(UGraph);
48 return c ? BLACK : RED;
51 template <typename DirMap>
52 class OrientVisitor : public DfsVisitor<UGraph> {
55 OrientVisitor(const UGraph& ugraph, DirMap& dirMap)
56 : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}
58 void discover(const Edge& edge) {
59 _processed.set(edge, true);
60 _dirMap.set(edge, _ugraph.direction(edge));
63 void examine(const Edge& edge) {
64 if (_processed[edge]) return;
65 _processed.set(edge, true);
66 _dirMap.set(edge, _ugraph.direction(edge));
70 const UGraph& _ugraph;
72 UGraph::UEdgeMap<bool> _processed;
77 cout << "Orientation of the strongly_connected_orientation.lgf "
78 << "to be strongly connected" << endl;
81 UGraph::NodeMap<dim2::Point<double> > coords(ugraph);
82 UGraphReader<UGraph>("strongly_connected_orientation.lgf", ugraph).
83 readNodeMap("coords", coords).run();
85 UGraph::UEdgeMap<bool> dmap(ugraph);
87 typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
88 Visitor visitor(ugraph, dmap);
90 DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
94 typedef DirUGraphAdaptor<UGraph> DGraph;
95 DGraph dgraph(ugraph, dmap);
97 cout << "The result written into the "
98 << "strongly_connected_orientation.eps file" << endl;
100 graphToEps(dgraph, "strongly_connected_orientation.eps").
101 drawArrows().coords(coords).scaleToA4().enableParallel().
102 autoNodeScale().autoEdgeWidthScale().run();
104 int num_scc = countStronglyConnectedComponents(dgraph);
105 int num_becc = countBiEdgeConnectedComponents(ugraph);
107 if (num_scc != num_becc) {
108 std::cerr << "Wrong Orientation" << std::endl;