Claw  1.7.3
graph_algorithm.tpp
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@gamned.org
24 */
30 #include <queue>
31 #include <stack>
32 
33 /*---------------------------------------------------------------------------*/
40 template<class Graph, class Events>
42  const vertex_type& source,
43  Events& events )
44  : m_g(g), m_source(source), m_events(events)
45 {
46 
47 } // breadth_scan::breadth_scan() [constructor]
48 
49 /*---------------------------------------------------------------------------*/
53 template<class Graph, class Events>
55 {
56  coloration seen_vertices;
57  std::queue<vertex_type> pending_vertices;
58  vertex_type current_vertex;
59  std::vector<vertex_type> neighbourhood;
60  typename std::vector<vertex_type>::const_iterator it;
61 
62  m_events.init(m_g);
63 
64  for (vertex_iterator it_v=m_g.vertex_begin(); it_v!=m_g.vertex_end(); ++it_v)
65  seen_vertices[*it_v] = 0;
66 
67  seen_vertices[m_source] = 1;
68  pending_vertices.push( m_source );
69 
70  while ( !pending_vertices.empty() )
71  {
72  current_vertex = pending_vertices.front();
73  m_events.start_vertex(current_vertex);
74 
75  m_g.neighbours( current_vertex, neighbourhood );
76 
77  for( it = neighbourhood.begin(); it != neighbourhood.end(); ++it )
78  {
79  if ( seen_vertices[*it] == 0 )
80  {
81  m_events.visit_edge(current_vertex, *it);
82  seen_vertices[*it] = 1;
83  }
84  }
85 
86  pending_vertices.pop();
87  m_events.end_vertex( current_vertex );
88  seen_vertices[current_vertex] = 2;
89  }
90 } // breadth_scan::operator()
91 
92 
93 
94 //****************************** depth_scan ***********************************
95 
96 
97 
98  /*---------------------------------------------------------------------------*/
104 template<class Graph, class Events>
105 claw::depth_scan<Graph, Events>::depth_scan( const Graph& g, Events& events )
106  : m_g(g), m_events(events)
107 {
108 
109 } // depth_scan::depth_scan() [constructor]
110 
111 /*---------------------------------------------------------------------------*/
115 template<class Graph, class Events>
117 {
118  coloration seen_vertices;
119  vertex_iterator it;
120 
121  m_events.init(m_g);
122 
123  for (it=m_g.vertex_begin(); it!=m_g.vertex_end(); ++it)
124  seen_vertices[*it] = 0;
125 
126  for (it = m_g.vertex_begin(); it!=m_g.vertex_end(); ++it)
127  if ( seen_vertices[*it] == 0 )
128  recursive_scan( *it, seen_vertices );
129 } // depth_scan::operator()()
130 
131 /*---------------------------------------------------------------------------*/
135 template<class Graph, class Events>
137 ( const vertex_type& s, coloration& seen_vertices )
138 {
139  std::vector<vertex_type> neighbourhood;
140  typename std::vector<vertex_type>::const_iterator it;
141 
142  m_events.start_vertex(s);
143  seen_vertices[s] = 1;
144 
145  m_g.neighbours( s, neighbourhood );
146 
147  for( it = neighbourhood.begin(); it != neighbourhood.end(); ++it )
148  if ( seen_vertices[*it] == 0 )
149  {
150  m_events.visit_edge(s, *it);
151  recursive_scan( *it, seen_vertices );
152  }
153 
154  m_events.end_vertex(s);
155  seen_vertices[s] = 2;
156 } // depth_scan::operator()
157 
158 
159 
160 
161 
162 
163 //********************** topological_sort ***********************************
164 
165 
166 
167 
168 
169 
170 
171 
172 
173  /*---------------------------------------------------------------------------*/
178 template<class Graph>
180 {
181  m_result.resize( g.vertices_count() );
182  m_next_index = (int)g.vertices_count()-1;
183 } // topological_sort::init()
184 
185 #include <iostream>
186 /*---------------------------------------------------------------------------*/
187 template<class Graph>
188 void claw::topological_sort<Graph>::end_vertex( const vertex_type& s )
189 {
190  m_result[m_next_index] = s;
191  --m_next_index;
192 } // topological_sort::end()
193 
194 /*---------------------------------------------------------------------------*/
195 template<class Graph>
196 void claw::topological_sort<Graph>::operator()( const Graph& g )
197 {
198  claw::depth_scan< Graph, self_type > scan( g, *this );
199  scan();
200 } // topological_sort::operator()()
201 
202 /*---------------------------------------------------------------------------*/
203 template<class Graph>
204 const typename claw::topological_sort<Graph>::vertex_type &
205 claw::topological_sort<Graph>::operator[](unsigned int index) const
206 {
207  return m_result[index];
208 } // topological_sort::operator[]()
209 
210 /*---------------------------------------------------------------------------*/
211 template<class Graph>
212 typename claw::topological_sort<Graph>::const_iterator
214 {
215  return m_result.begin();
216 } // topological_sort::begin()
217 
218 /*---------------------------------------------------------------------------*/
219 template<class Graph>
220 typename claw::topological_sort<Graph>::const_iterator
222 {
223  return m_result.end();
224 } // topological_sort::end()