1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/demo/topological_ordering.cc	Thu Sep 14 19:11:24 2006 +0000
     1.3 @@ -0,0 +1,115 @@
     1.4 +/* -*- C++ -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library
     1.7 + *
     1.8 + * Copyright (C) 2003-2006
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +///\ingroup demos
    1.23 +///\file
    1.24 +///\brief Demonstrating the Dfs class with topological ordering
    1.25 +///
    1.26 +///\include topological_ordering.cc
    1.27 +
    1.28 +#include <iostream>
    1.29 +#include <string>
    1.30 +#include <list>
    1.31 +#include <lemon/list_graph.h>
    1.32 +#include <lemon/maps.h>
    1.33 +#include <lemon/dfs.h>
    1.34 +
    1.35 +using namespace lemon;
    1.36 +
    1.37 +
    1.38 +template< typename GR >
    1.39 +class SerializingWriteMap
    1.40 +{
    1.41 +public:
    1.42 +  typedef typename GR::Node  Key;
    1.43 +  typedef bool  Value;
    1.44 +  typedef std::list<Key>  OrderedList;
    1.45 +
    1.46 +  OrderedList  order;
    1.47 +
    1.48 +  SerializingWriteMap( const GR& gr ) {}
    1.49 +
    1.50 +  void  set( const Key& k, const Value& v ) {
    1.51 +    if( v ) order.push_front(k);
    1.52 +  }
    1.53 +
    1.54 +  Value  operator[] ( const Key& ) {
    1.55 +    return false;
    1.56 +  }
    1.57 +};
    1.58 +
    1.59 +
    1.60 +int  main( int argc, char *argv[] )
    1.61 +{
    1.62 +  std::cout << "Topological Ordering demo" << std::endl;
    1.63 +
    1.64 +  // Create and build the graph
    1.65 +  ListGraph  gr;
    1.66 +  ListGraph::NodeMap<std::string>  label(gr);
    1.67 +  typedef ListGraph::Node  Node;
    1.68 +
    1.69 +  // This DAG example for topological ordering is from the book New Algorithms
    1.70 +  // (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein)
    1.71 +  {
    1.72 +    Node  belt = gr.addNode();
    1.73 +    Node  trousers = gr.addNode();
    1.74 +    Node  necktie = gr.addNode();
    1.75 +    Node  coat = gr.addNode();
    1.76 +    Node  socks = gr.addNode();
    1.77 +    Node  shirt = gr.addNode();
    1.78 +    Node  shoe = gr.addNode();
    1.79 +    Node  watch = gr.addNode();
    1.80 +    Node  pants = gr.addNode();
    1.81 +
    1.82 +    label[belt] = "Belt";
    1.83 +    label[trousers] = "Trousers";
    1.84 +    label[necktie] = "Necktie";
    1.85 +    label[coat] = "Coat";
    1.86 +    label[socks] = "Socks";
    1.87 +    label[shirt] = "Shirt";
    1.88 +    label[shoe] = "Shoe";
    1.89 +    label[watch] = "Watch";
    1.90 +    label[pants] = "Pants";
    1.91 +
    1.92 +    // Here we use a directed edge to indicate precedenc.
    1.93 +    // The source must precede the target.
    1.94 +    gr.addEdge( socks, shoe );
    1.95 +    gr.addEdge( pants, shoe );
    1.96 +    gr.addEdge( pants, trousers );
    1.97 +    gr.addEdge( trousers, shoe );
    1.98 +    gr.addEdge( trousers, belt );
    1.99 +    gr.addEdge( belt, coat );
   1.100 +    gr.addEdge( shirt, belt );
   1.101 +    gr.addEdge( shirt, necktie );
   1.102 +    gr.addEdge( necktie, coat );
   1.103 +  }
   1.104 +
   1.105 +  // Calculate topological order
   1.106 +  Dfs<ListGraph, Dfs<ListGraph>::DefProcessedMapTraits<SerializingWriteMap<ListGraph> > >  dfs(gr);
   1.107 +  SerializingWriteMap<ListGraph>  list(gr);
   1.108 +  dfs.processedMap(list);
   1.109 +  dfs.run();
   1.110 +
   1.111 +  // Write out the result
   1.112 +  std::cout << "One possible order to dress up:";
   1.113 +  for( SerializingWriteMap<ListGraph>::OrderedList::iterator  it = list.order.begin(); it != list.order.end(); ++it )
   1.114 +    std::cout << "  " << label[*it];
   1.115 +  std::cout << std::endl;
   1.116 +
   1.117 +  return 0;
   1.118 +}