COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/topological_ordering.cc @ 2231:06faf3f06d67

Last change on this file since 2231:06faf3f06d67 was 2216:1e45cdeea3cc, checked in by Alpar Juttner, 13 years ago

The recent progresses on the tutorial due to Mark.

File size: 3.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19///\ingroup demos
20///\file
21///\brief Demonstrating the Dfs class with topological ordering
22///
23///\include topological_ordering.cc
24
25#include <iostream>
26#include <string>
27#include <list>
28#include <lemon/list_graph.h>
29#include <lemon/maps.h>
30#include <lemon/dfs.h>
31
32using namespace lemon;
33
34
35template< typename GR >
36class SerializingWriteMap
37{
38public:
39  typedef typename GR::Node  Key;
40  typedef bool  Value;
41  typedef std::list<Key>  OrderedList;
42
43  OrderedList  order;
44
45  SerializingWriteMap( const GR& gr ) {}
46
47  void  set( const Key& k, const Value& v ) {
48    if( v ) order.push_front(k);
49  }
50
51  Value  operator[] ( const Key& ) {
52    return false;
53  }
54};
55
56
57int  main( int argc, char *argv[] )
58{
59  std::cout << "Topological Ordering demo" << std::endl;
60
61  // Create and build the graph
62  ListGraph  gr;
63  ListGraph::NodeMap<std::string>  label(gr);
64  typedef ListGraph::Node  Node;
65
66  // This DAG example for topological ordering is from the book New Algorithms
67  // (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein)
68  {
69    Node  belt = gr.addNode();
70    Node  trousers = gr.addNode();
71    Node  necktie = gr.addNode();
72    Node  coat = gr.addNode();
73    Node  socks = gr.addNode();
74    Node  shirt = gr.addNode();
75    Node  shoe = gr.addNode();
76    Node  watch = gr.addNode();
77    Node  pants = gr.addNode();
78
79    label[belt] = "Belt";
80    label[trousers] = "Trousers";
81    label[necktie] = "Necktie";
82    label[coat] = "Coat";
83    label[socks] = "Socks";
84    label[shirt] = "Shirt";
85    label[shoe] = "Shoe";
86    label[watch] = "Watch";
87    label[pants] = "Pants";
88
89    // Here we use a directed edge to indicate precedenc.
90    // The source must precede the target.
91    gr.addEdge( socks, shoe );
92    gr.addEdge( pants, shoe );
93    gr.addEdge( pants, trousers );
94    gr.addEdge( trousers, shoe );
95    gr.addEdge( trousers, belt );
96    gr.addEdge( belt, coat );
97    gr.addEdge( shirt, belt );
98    gr.addEdge( shirt, necktie );
99    gr.addEdge( necktie, coat );
100  }
101
102  // Calculate topological order
103  Dfs<ListGraph, Dfs<ListGraph>::DefProcessedMapTraits<SerializingWriteMap<ListGraph> > >  dfs(gr);
104  SerializingWriteMap<ListGraph>  list(gr);
105  dfs.processedMap(list);
106  dfs.run();
107
108  // Write out the result
109  std::cout << "One possible order to dress up:";
110  for( SerializingWriteMap<ListGraph>::OrderedList::iterator  it = list.order.begin(); it != list.order.end(); ++it )
111    std::cout << "  " << label[*it];
112  std::cout << std::endl;
113
114  return 0;
115}
Note: See TracBrowser for help on using the repository browser.