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 <iostream>
deba@2084: 
deba@2116: #include <lemon/smart_graph.h>
deba@2084: #include <lemon/graph_reader.h>
deba@2084: #include <lemon/ugraph_adaptor.h>
deba@2084: #include <lemon/graph_to_eps.h>
deba@2084: #include <lemon/dfs.h>
deba@2084: #include <lemon/topology.h>
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 <typename DirMap>
deba@2084: class OrientVisitor : public DfsVisitor<UGraph> {
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<bool> _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<dim2::Point<double> > coords(ugraph);
deba@2084:   UGraphReader<UGraph>("strongly_connected_orientation.lgf", ugraph).
deba@2084:     readNodeMap("coords", coords).run();
deba@2084: 
deba@2084:   UGraph::UEdgeMap<bool> dmap(ugraph);
deba@2084: 
deba@2084:   typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;
deba@2084:   Visitor visitor(ugraph, dmap);
deba@2084: 
deba@2084:   DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);
deba@2084: 
deba@2084:   dfs.run();
deba@2084: 
deba@2084:   typedef DirUGraphAdaptor<UGraph> 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: }