alpar@2216: /* -*- C++ -*- alpar@2216: * alpar@2216: * This file is a part of LEMON, a generic C++ optimization library alpar@2216: * alpar@2216: * Copyright (C) 2003-2006 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 alpar@2216: #include alpar@2216: #include alpar@2216: #include alpar@2216: #include alpar@2216: #include 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 OrderedList; alpar@2216: alpar@2216: OrderedList order; alpar@2216: alpar@2216: SerializingWriteMap( const GR& 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@2216: int main( int argc, char *argv[] ) 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 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::DefProcessedMapTraits > > dfs(gr); alpar@2216: SerializingWriteMap 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::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: }