/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2007

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #include <iostream>

 #include <lemon/smart_graph.h>

 #include <lemon/graph_reader.h>

 #include <lemon/ugraph_adaptor.h>

 #include <lemon/graph_to_eps.h>

 #include <lemon/dfs.h>

 #include <lemon/topology.h>

 /// \ingroup demos

 /// \file

 /// \brief Strongly connected orientation

 ///

 /// This example demonstrates the usage of the DirUGraphAdaptor,

 /// the DfsVisitor and some topology functions. The program reads

 /// an input undirected graph and with a DfsVisit it orients each edge

 /// to minimize the strongly connected components in the graph. At least

 /// it checks the result of the orientation with to topology functions.

 ///

 /// \include strongly_connected_orientation.cc

 using namespace lemon;

 using namespace std;

 typedef SmartUGraph UGraph;

 UGRAPH_TYPEDEFS(UGraph);

 Color color(bool c) {

   return c ? BLACK : RED;

 }

 template <typename DirMap>

 class OrientVisitor : public DfsVisitor<UGraph> {

 public:

   OrientVisitor(const UGraph& ugraph, DirMap& dirMap)

     : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}

   void discover(const Edge& edge) {

     _processed.set(edge, true);

     _dirMap.set(edge, _ugraph.direction(edge));

   }

   void examine(const Edge& edge) {

     if (_processed[edge]) return;

     _processed.set(edge, true);

     _dirMap.set(edge, _ugraph.direction(edge));

   }  

 private:

   const UGraph& _ugraph;  

   DirMap& _dirMap;

   UGraph::UEdgeMap<bool> _processed;

 };

 int main() {

   cout << "Orientation of the strongly_connected_orientation.lgf "

        << "to be strongly connected" << endl;

   UGraph ugraph;

   UGraph::NodeMap<dim2::Point<double> > coords(ugraph);

   UGraphReader<UGraph>("strongly_connected_orientation.lgf", ugraph).

     readNodeMap("coords", coords).run();

   UGraph::UEdgeMap<bool> dmap(ugraph);

   typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;

   Visitor visitor(ugraph, dmap);

   DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);

   dfs.run();

   typedef DirUGraphAdaptor<UGraph> DGraph;

   DGraph dgraph(ugraph, dmap);

   cout << "The result written into the " 

        << "strongly_connected_orientation.eps file" << endl;

   graphToEps(dgraph, "strongly_connected_orientation.eps").

     drawArrows().coords(coords).scaleToA4().enableParallel().

     autoNodeScale().autoEdgeWidthScale().run();

   int num_scc = countStronglyConnectedComponents(dgraph);

   int num_becc = countBiEdgeConnectedComponents(ugraph);

   if (num_scc != num_becc) {

     std::cerr << "Wrong Orientation" << std::endl;

   }

   return 0;

 }