graph_algorithm.tpp

Go to the documentation of this file.
00001 /*
00002   CLAW - a C++ Library Absolutely Wonderful
00003 
00004   CLAW is a free library without any particular aim but being useful to 
00005   anyone.
00006 
00007   Copyright (C) 2005-2008 Julien Jorge
00008 
00009   This library is free software; you can redistribute it and/or
00010   modify it under the terms of the GNU Lesser General Public
00011   License as published by the Free Software Foundation; either
00012   version 2.1 of the License, or (at your option) any later version.
00013 
00014   This library is distributed in the hope that it will be useful,
00015   but WITHOUT ANY WARRANTY; without even the implied warranty of
00016   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00017   Lesser General Public License for more details.
00018 
00019   You should have received a copy of the GNU Lesser General Public
00020   License along with this library; if not, write to the Free Software
00021   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00022 
00023   contact: julien_jorge@yahoo.fr
00024 */
00030 #include <queue>
00031 #include <stack>
00032 
00033 /*---------------------------------------------------------------------------*/
00040 template<class Graph, class Events>
00041 claw::breadth_scan<Graph, Events>::breadth_scan( const Graph& g, 
00042                                                  const vertex_type& source,
00043                                                  Events& events )
00044   : m_g(g), m_source(source), m_events(events)
00045 {
00046 
00047 } // breadth_scan::breadth_scan() [constructor]
00048 
00049 /*---------------------------------------------------------------------------*/
00053 template<class Graph, class Events>
00054 void claw::breadth_scan<Graph, Events>::operator()()
00055 {
00056   coloration seen_vertices;
00057   std::queue<vertex_type> pending_vertices;
00058   vertex_type current_vertex;
00059   std::vector<vertex_type> neighbourhood;
00060   typename std::vector<vertex_type>::const_iterator it;
00061 
00062   m_events.init(m_g);
00063 
00064   for (vertex_iterator it_v=m_g.vertex_begin(); it_v!=m_g.vertex_end(); ++it_v)
00065     seen_vertices[*it_v] = 0;
00066   
00067   seen_vertices[m_source] = 1;
00068   pending_vertices.push( m_source );
00069                 
00070   while ( !pending_vertices.empty() )
00071     {
00072       current_vertex = pending_vertices.front();
00073       m_events.start_vertex(current_vertex);
00074 
00075       m_g.neighbours( current_vertex, neighbourhood );
00076 
00077       for( it = neighbourhood.begin(); it != neighbourhood.end(); ++it )
00078         {
00079           if ( seen_vertices[*it] == 0 )
00080             {
00081               m_events.visit_edge(current_vertex, *it);
00082               seen_vertices[*it] = 1;
00083             }
00084         }
00085 
00086       pending_vertices.pop();
00087       m_events.end_vertex( current_vertex );
00088       seen_vertices[current_vertex] = 2;
00089     }
00090 } // breadth_scan::operator()
00091 
00092 
00093 
00094 //****************************** depth_scan ***********************************
00095   
00096 
00097 
00098   /*---------------------------------------------------------------------------*/
00104 template<class Graph, class Events>
00105 claw::depth_scan<Graph, Events>::depth_scan( const Graph& g, Events& events )
00106   : m_g(g), m_events(events)
00107 {
00108 
00109 } // depth_scan::depth_scan() [constructor]
00110 
00111 /*---------------------------------------------------------------------------*/
00115 template<class Graph, class Events>
00116 void claw::depth_scan<Graph, Events>::operator()()
00117 {
00118   coloration seen_vertices;
00119   vertex_iterator it;
00120 
00121   m_events.init(m_g);
00122 
00123   for (it=m_g.vertex_begin(); it!=m_g.vertex_end(); ++it)
00124     seen_vertices[*it] = 0;
00125   
00126   for (it = m_g.vertex_begin(); it!=m_g.vertex_end(); ++it)
00127     if ( seen_vertices[*it] == 0 )
00128       recursive_scan( *it, seen_vertices );
00129 } // depth_scan::operator()()
00130 
00131 /*---------------------------------------------------------------------------*/
00135 template<class Graph, class Events>
00136 void claw::depth_scan<Graph, Events>::recursive_scan
00137 ( const vertex_type& s, coloration& seen_vertices )
00138 {
00139   std::vector<vertex_type> neighbourhood;
00140   typename std::vector<vertex_type>::const_iterator it;
00141   
00142   m_events.start_vertex(s);
00143   seen_vertices[s] = 1;
00144   
00145   m_g.neighbours( s, neighbourhood );
00146 
00147   for( it = neighbourhood.begin(); it != neighbourhood.end(); ++it )
00148     if ( seen_vertices[*it] == 0 )
00149       {
00150         m_events.visit_edge(s, *it);
00151         recursive_scan( *it, seen_vertices );
00152       }
00153 
00154   m_events.end_vertex(s);
00155   seen_vertices[s] = 2;
00156 } // depth_scan::operator()
00157 
00158 
00159 
00160 
00161 
00162 
00163 //********************** topological_sort ***********************************
00164 
00165 
00166 
00167 
00168 
00169 
00170 
00171 
00172 
00173   /*---------------------------------------------------------------------------*/
00178 template<class Graph>
00179 void claw::topological_sort<Graph>::init( const Graph& g )
00180 {
00181   m_result.resize( g.vertices_count() );
00182   m_next_index = (int)g.vertices_count()-1;
00183 } // topological_sort::init()
00184 
00185 #include <iostream>
00186 /*---------------------------------------------------------------------------*/
00187 template<class Graph>
00188 void claw::topological_sort<Graph>::end_vertex( const vertex_type& s )
00189 {
00190   m_result[m_next_index] = s;
00191   --m_next_index;
00192 } // topological_sort::end()
00193 
00194 /*---------------------------------------------------------------------------*/
00195 template<class Graph>
00196 void claw::topological_sort<Graph>::operator()( const Graph& g )
00197 {
00198   claw::depth_scan< Graph, self_type > scan( g, *this );
00199   scan();
00200 } // topological_sort::operator()()
00201 
00202 /*---------------------------------------------------------------------------*/
00203 template<class Graph>
00204 const typename claw::topological_sort<Graph>::vertex_type &
00205 claw::topological_sort<Graph>::operator[](unsigned int index) const
00206 {
00207   return m_result[index];
00208 } // topological_sort::operator[]()
00209 
00210 /*---------------------------------------------------------------------------*/
00211 template<class Graph>
00212 typename claw::topological_sort<Graph>::const_iterator
00213 claw::topological_sort<Graph>::begin() const
00214 {
00215   return m_result.begin();
00216 } // topological_sort::begin()
00217 
00218 /*---------------------------------------------------------------------------*/
00219 template<class Graph>
00220 typename claw::topological_sort<Graph>::const_iterator
00221 claw::topological_sort<Graph>::end() const
00222 {
00223   return m_result.end();
00224 } // topological_sort::end()

Generated on 9 Nov 2009 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.6.1