/* -*- C++ -*-

 *

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

 *

 * Copyright (C) 2003-2008

 * 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.

 *

 */

///\ingroup demos

///\file

///\brief Demonstrating the Dfs class with topological ordering

///

///\include topological_ordering.cc

#include <iostream>

#include <string>

#include <list>

#include <lemon/list_graph.h>

#include <lemon/maps.h>

#include <lemon/dfs.h>

using namespace lemon;

template< typename GR >

class SerializingWriteMap

{

public:

  typedef typename GR::Node  Key;

  typedef bool  Value;

  typedef std::list<Key>  OrderedList;

  OrderedList  order;

  SerializingWriteMap( const GR& ) {}

  void  set( const Key& k, const Value& v ) {

    if( v ) order.push_front(k);

  }

  Value  operator[] ( const Key& ) {

    return false;

  }

};

int main()

{

  std::cout << "Topological Ordering demo" << std::endl;

  // Create and build the graph

  ListGraph  gr;

  ListGraph::NodeMap<std::string>  label(gr);

  typedef ListGraph::Node  Node;

  // This DAG example for topological ordering is from the book New Algorithms

  // (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein)

  {

    Node  belt = gr.addNode();

    Node  trousers = gr.addNode();

    Node  necktie = gr.addNode();

    Node  coat = gr.addNode();

    Node  socks = gr.addNode();

    Node  shirt = gr.addNode();

    Node  shoe = gr.addNode();

    Node  watch = gr.addNode();

    Node  pants = gr.addNode();

    label[belt] = "Belt";

    label[trousers] = "Trousers";

    label[necktie] = "Necktie";

    label[coat] = "Coat";

    label[socks] = "Socks";

    label[shirt] = "Shirt";

    label[shoe] = "Shoe";

    label[watch] = "Watch";

    label[pants] = "Pants";

    // Here we use a directed edge to indicate precedenc.

    // The source must precede the target.

    gr.addEdge( socks, shoe );

    gr.addEdge( pants, shoe );

    gr.addEdge( pants, trousers );

    gr.addEdge( trousers, shoe );

    gr.addEdge( trousers, belt );

    gr.addEdge( belt, coat );

    gr.addEdge( shirt, belt );

    gr.addEdge( shirt, necktie );

    gr.addEdge( necktie, coat );

  }

  // Calculate topological order

  Dfs<ListGraph, Dfs<ListGraph>::DefProcessedMapTraits<SerializingWriteMap<ListGraph> > >  dfs(gr);

  SerializingWriteMap<ListGraph>  list(gr);

  dfs.processedMap(list);

  dfs.run();

  // Write out the result

  std::cout << "One possible order to dress up:";

  for( SerializingWriteMap<ListGraph>::OrderedList::iterator  it = list.order.begin(); it != list.order.end(); ++it )

    std::cout << "  " << label[*it];

  std::cout << std::endl;

  return 0;

}