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

 }