source: lemon-0.x/demo/strongly_connected_orientation.cc @ 2189:de2b77e3868c

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * 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<xy<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;
}