demo/strongly_connected_orientation.cc
author ladanyi
Wed, 21 Jun 2006 08:39:28 +0000
changeset 2104 8e27998e9b1d
child 2115 4cd528a30ec1
permissions -rw-r--r--
Moved the gui to glemon/trunk.
     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 
    41 using namespace lemon;
    42 using namespace std;
    43 
    44 typedef SmartUGraph UGraph;
    45 UGRAPH_TYPEDEFS(UGraph)
    46 
    47 Color color(bool c) {
    48   return c ? Color(0.0, 0.0, 0.0) : Color(1.0, 0.0, 0.0);
    49 }
    50 
    51 template <typename DirMap>
    52 class OrientVisitor : public DfsVisitor<UGraph> {
    53 public:
    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 
    69 private:
    70   const UGraph& _ugraph;  
    71   DirMap& _dirMap;
    72   UGraph::UEdgeMap<bool> _processed;
    73 };
    74 
    75 
    76 int main(int argc, const char *argv[]) {
    77   cout << "Orientation of the strongly_connected_orientation.lgf "
    78        << "to be strongly connected" << endl;
    79 
    80   UGraph ugraph;
    81   UGraph::NodeMap<xy<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   LEMON_ASSERT(num_scc == num_becc, "Wrong Orientation");
   108   
   109   return 0;
   110 }