source: lemon-0.x/demo/topological_ordering.cc @ 2263:9273fe7d850c

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * 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;
}