/* -*- 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;

}