claw  1.9.0
graph_algorithm.hpp
Go to the documentation of this file.
1 /*
2  CLAW - a C++ Library Absolutely Wonderful
3 
4  CLAW is a free library without any particular aim but being useful to
5  anyone.
6 
7  Copyright (C) 2005-2011 Julien Jorge
8 
9  This library is free software; you can redistribute it and/or
10  modify it under the terms of the GNU Lesser General Public
11  License as published by the Free Software Foundation; either
12  version 2.1 of the License, or (at your option) any later version.
13 
14  This library is distributed in the hope that it will be useful,
15  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  Lesser General Public License for more details.
18 
19  You should have received a copy of the GNU Lesser General Public
20  License along with this library; if not, write to the Free Software
21  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 
23  contact: julien.jorge@stuff-o-matic.com
24 */
30 #ifndef __CLAW_GRAPH_ALGORITHM_HPP__
31 #define __CLAW_GRAPH_ALGORITHM_HPP__
32 
33 #include <map>
34 
35 namespace claw
36 {
37  //*************************** graph::scan_events ****************************
38 
42  template <class Graph>
44  {
45  public:
46  typedef typename Graph::vertex_type vertex_type;
47 
48  public:
49  void init(const Graph& g)
50  {}
51  void start_vertex(const vertex_type& v)
52  {}
53  void visit_edge(const vertex_type& v1, const vertex_type& v2)
54  {}
55  void end_vertex(const vertex_type& v)
56  {}
57  }; // class scan_events
58 
59  //************************** breadth_scan ***********************************
60 
65  template <class Graph, class Events = scan_events<Graph> >
67  {
68  public:
69  typedef typename Graph::vertex_type vertex_type;
70  typedef typename Graph::vertex_iterator vertex_iterator;
77  typedef std::map<vertex_type, int, typename Graph::vertex_compare>
79 
80  public:
81  breadth_scan(const Graph& g, const vertex_type& source, Events& events);
82 
83  void operator()();
84 
85  private:
86  const Graph& m_g;
87  const vertex_type& m_source;
88  Events& m_events;
89  }; // class breadth_scan
90 
91  //**************************** depth_scan ***********************************
92 
97  template <class Graph, class Events = typename Graph::scan_events>
98  class depth_scan
99  {
100  public:
101  typedef typename Graph::vertex_type vertex_type;
102  typedef typename Graph::vertex_iterator vertex_iterator;
109  typedef std::map<vertex_type, int, typename Graph::vertex_compare>
111 
112  public:
113  depth_scan(const Graph& g, Events& events);
114 
115  void operator()();
116 
117  private:
118  void recursive_scan(const vertex_type& s, coloration& seen_vertices);
119 
120  private:
121  const Graph& m_g;
122  Events& m_events;
123  }; // class depth_scan
124 
125  //********************** topological_sort ***********************************
126 
135  template <class Graph>
136  class topological_sort : public scan_events<Graph>
137  {
138  public:
139  typedef typename scan_events<Graph>::vertex_type vertex_type;
140  typedef std::vector<vertex_type> result_type;
141  typedef typename result_type::const_iterator const_iterator;
143 
144  public:
145  void init(const Graph& g);
146  void end_vertex(const vertex_type& s);
147 
148  void operator()(const Graph& g);
149  const vertex_type& operator[](unsigned int index) const;
150 
151  const_iterator begin() const;
152  const_iterator end() const;
153 
154  private:
156  result_type m_result;
158  int m_next_index;
159  }; // class topological_sort
160 
161 }
162 
163 #include <claw/graph_algorithm.tpp>
164 
165 #endif // __CLAW_GRAPH_ALGORITHM_HPP__
This class performs a depth scan of a graph. All nodes are proceeded.
std::map< vertex_type, int, typename Graph::vertex_compare > coloration
Colors are :
std::map< vertex_type, int, typename Graph::vertex_compare > coloration
Colors are :
This class performs a depth scan of a graph. Only reachables vertices from a given vertex are proceed...
Pass this class as the "Envents" template parameter of the depth scan class to sort the vertices of a...
This is the main namespace.
Definition: application.hpp:49
Different stages of graph scanning.