deba@2084: /* -*- C++ -*- deba@2084: * deba@2084: * This file is a part of LEMON, a generic C++ optimization library deba@2084: * alpar@2553: * Copyright (C) 2003-2008 deba@2084: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@2084: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@2084: * deba@2084: * Permission to use, modify and distribute this software is granted deba@2084: * provided that this copyright notice appears in all copies. For deba@2084: * precise terms see the accompanying LICENSE file. deba@2084: * deba@2084: * This software is provided "AS IS" with no warranty of any kind, deba@2084: * express or implied, and with no claim as to its suitability for any deba@2084: * purpose. deba@2084: * deba@2084: */ deba@2084: deba@2084: #include deba@2084: deba@2116: #include deba@2084: #include deba@2084: #include deba@2084: #include deba@2084: #include deba@2084: #include deba@2084: deba@2084: deba@2084: /// \ingroup demos deba@2084: /// \file deba@2084: /// \brief Strongly connected orientation deba@2084: /// deba@2084: /// This example demonstrates the usage of the DirUGraphAdaptor, deba@2084: /// the DfsVisitor and some topology functions. The program reads deba@2084: /// an input undirected graph and with a DfsVisit it orients each edge deba@2084: /// to minimize the strongly connected components in the graph. At least deba@2084: /// it checks the result of the orientation with to topology functions. deba@2084: /// deba@2084: /// \include strongly_connected_orientation.cc deba@2084: deba@2084: using namespace lemon; deba@2084: using namespace std; deba@2084: deba@2084: typedef SmartUGraph UGraph; deba@2510: UGRAPH_TYPEDEFS(UGraph); deba@2084: deba@2084: Color color(bool c) { alpar@2174: return c ? BLACK : RED; deba@2084: } deba@2084: deba@2084: template deba@2084: class OrientVisitor : public DfsVisitor { deba@2084: public: deba@2084: deba@2084: OrientVisitor(const UGraph& ugraph, DirMap& dirMap) deba@2084: : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {} deba@2084: deba@2084: void discover(const Edge& edge) { deba@2084: _processed.set(edge, true); deba@2084: _dirMap.set(edge, _ugraph.direction(edge)); deba@2084: } deba@2084: deba@2084: void examine(const Edge& edge) { deba@2084: if (_processed[edge]) return; deba@2084: _processed.set(edge, true); deba@2084: _dirMap.set(edge, _ugraph.direction(edge)); deba@2084: } deba@2084: deba@2084: private: deba@2084: const UGraph& _ugraph; deba@2084: DirMap& _dirMap; deba@2084: UGraph::UEdgeMap _processed; deba@2084: }; deba@2084: deba@2084: alpar@2173: int main() { deba@2084: cout << "Orientation of the strongly_connected_orientation.lgf " deba@2084: << "to be strongly connected" << endl; deba@2084: deba@2084: UGraph ugraph; alpar@2207: UGraph::NodeMap > coords(ugraph); deba@2084: UGraphReader("strongly_connected_orientation.lgf", ugraph). deba@2084: readNodeMap("coords", coords).run(); deba@2084: deba@2084: UGraph::UEdgeMap dmap(ugraph); deba@2084: deba@2084: typedef OrientVisitor > Visitor; deba@2084: Visitor visitor(ugraph, dmap); deba@2084: deba@2084: DfsVisit dfs(ugraph, visitor); deba@2084: deba@2084: dfs.run(); deba@2084: deba@2084: typedef DirUGraphAdaptor DGraph; deba@2084: DGraph dgraph(ugraph, dmap); deba@2084: deba@2084: cout << "The result written into the " deba@2084: << "strongly_connected_orientation.eps file" << endl; deba@2084: deba@2084: graphToEps(dgraph, "strongly_connected_orientation.eps"). deba@2084: drawArrows().coords(coords).scaleToA4().enableParallel(). deba@2084: autoNodeScale().autoEdgeWidthScale().run(); deba@2084: deba@2084: int num_scc = countStronglyConnectedComponents(dgraph); deba@2084: int num_becc = countBiEdgeConnectedComponents(ugraph); deba@2084: deba@2161: if (num_scc != num_becc) { deba@2161: std::cerr << "Wrong Orientation" << std::endl; deba@2161: } deba@2084: deba@2084: return 0; deba@2084: }