alpar@2216: /* -*- C++ -*-
alpar@2216:  *
alpar@2216:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2216:  *
alpar@2553:  * Copyright (C) 2003-2008
alpar@2216:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2216:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2216:  *
alpar@2216:  * Permission to use, modify and distribute this software is granted
alpar@2216:  * provided that this copyright notice appears in all copies. For
alpar@2216:  * precise terms see the accompanying LICENSE file.
alpar@2216:  *
alpar@2216:  * This software is provided "AS IS" with no warranty of any kind,
alpar@2216:  * express or implied, and with no claim as to its suitability for any
alpar@2216:  * purpose.
alpar@2216:  *
alpar@2216:  */
alpar@2216: 
alpar@2216: ///\ingroup demos
alpar@2216: ///\file
alpar@2216: ///\brief Demonstrating the Dfs class with topological ordering
alpar@2216: ///
alpar@2216: ///\include topological_ordering.cc
alpar@2216: 
alpar@2216: #include <iostream>
alpar@2216: #include <string>
alpar@2216: #include <list>
alpar@2216: #include <lemon/list_graph.h>
alpar@2216: #include <lemon/maps.h>
alpar@2216: #include <lemon/dfs.h>
alpar@2216: 
alpar@2216: using namespace lemon;
alpar@2216: 
alpar@2216: 
alpar@2216: template< typename GR >
alpar@2216: class SerializingWriteMap
alpar@2216: {
alpar@2216: public:
alpar@2216:   typedef typename GR::Node  Key;
alpar@2216:   typedef bool  Value;
alpar@2216:   typedef std::list<Key>  OrderedList;
alpar@2216: 
alpar@2216:   OrderedList  order;
alpar@2216: 
alpar@2232:   SerializingWriteMap( const GR& ) {}
alpar@2216: 
alpar@2216:   void  set( const Key& k, const Value& v ) {
alpar@2216:     if( v ) order.push_front(k);
alpar@2216:   }
alpar@2216: 
alpar@2216:   Value  operator[] ( const Key& ) {
alpar@2216:     return false;
alpar@2216:   }
alpar@2216: };
alpar@2216: 
alpar@2216: 
alpar@2232: int main()
alpar@2216: {
alpar@2216:   std::cout << "Topological Ordering demo" << std::endl;
alpar@2216: 
alpar@2216:   // Create and build the graph
alpar@2216:   ListGraph  gr;
alpar@2216:   ListGraph::NodeMap<std::string>  label(gr);
alpar@2216:   typedef ListGraph::Node  Node;
alpar@2216: 
alpar@2216:   // This DAG example for topological ordering is from the book New Algorithms
alpar@2216:   // (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein)
alpar@2216:   {
alpar@2216:     Node  belt = gr.addNode();
alpar@2216:     Node  trousers = gr.addNode();
alpar@2216:     Node  necktie = gr.addNode();
alpar@2216:     Node  coat = gr.addNode();
alpar@2216:     Node  socks = gr.addNode();
alpar@2216:     Node  shirt = gr.addNode();
alpar@2216:     Node  shoe = gr.addNode();
alpar@2216:     Node  watch = gr.addNode();
alpar@2216:     Node  pants = gr.addNode();
alpar@2216: 
alpar@2216:     label[belt] = "Belt";
alpar@2216:     label[trousers] = "Trousers";
alpar@2216:     label[necktie] = "Necktie";
alpar@2216:     label[coat] = "Coat";
alpar@2216:     label[socks] = "Socks";
alpar@2216:     label[shirt] = "Shirt";
alpar@2216:     label[shoe] = "Shoe";
alpar@2216:     label[watch] = "Watch";
alpar@2216:     label[pants] = "Pants";
alpar@2216: 
alpar@2216:     // Here we use a directed edge to indicate precedenc.
alpar@2216:     // The source must precede the target.
alpar@2216:     gr.addEdge( socks, shoe );
alpar@2216:     gr.addEdge( pants, shoe );
alpar@2216:     gr.addEdge( pants, trousers );
alpar@2216:     gr.addEdge( trousers, shoe );
alpar@2216:     gr.addEdge( trousers, belt );
alpar@2216:     gr.addEdge( belt, coat );
alpar@2216:     gr.addEdge( shirt, belt );
alpar@2216:     gr.addEdge( shirt, necktie );
alpar@2216:     gr.addEdge( necktie, coat );
alpar@2216:   }
alpar@2216: 
alpar@2216:   // Calculate topological order
alpar@2216:   Dfs<ListGraph, Dfs<ListGraph>::DefProcessedMapTraits<SerializingWriteMap<ListGraph> > >  dfs(gr);
alpar@2216:   SerializingWriteMap<ListGraph>  list(gr);
alpar@2216:   dfs.processedMap(list);
alpar@2216:   dfs.run();
alpar@2216: 
alpar@2216:   // Write out the result
alpar@2216:   std::cout << "One possible order to dress up:";
alpar@2216:   for( SerializingWriteMap<ListGraph>::OrderedList::iterator  it = list.order.begin(); it != list.order.end(); ++it )
alpar@2216:     std::cout << "  " << label[*it];
alpar@2216:   std::cout << std::endl;
alpar@2216: 
alpar@2216:   return 0;
alpar@2216: }