claw 1.9.0
 
Loading...
Searching...
No Matches
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
35namespace 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> >
66 class breadth_scan
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;
142 typedef topological_sort<Graph> self_type;
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__
std::map< vertex_type, int, typename Graph::vertex_compare > coloration
Colors are :
std::map< vertex_type, int, typename Graph::vertex_compare > coloration
Colors are :
Different stages of graph scanning.
Pass this class as the "Envents" template parameter of the depth scan class to sort the vertices of a...
This is the main namespace.