Wiselib: wiselib.testing/algorithms/graph/ddfs/ddfs

Wiselib
00001 /***************************************************************************
00002  ** This file is part of the generic algorithm library Wiselib.           **
00003  ** Copyright (C) 2008,2009 by the Wisebed (www.wisebed.eu) project.      **
00004  **                                                                       **
00005  ** The Wiselib is free software: you can redistribute it and/or modify   **
00006  ** it under the terms of the GNU Lesser General Public License as        **
00007  ** published by the Free Software Foundation, either version 3 of the    **
00008  ** License, or (at your option) any later version.                       **
00009  **                                                                       **
00010  ** The Wiselib is distributed in the hope that it will be useful,        **
00011  ** but WITHOUT ANY WARRANTY; without even the implied warranty of        **
00012  ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         **
00013  ** GNU Lesser General Public License for more details.                   **
00014  **                                                                       **
00015  ** You should have received a copy of the GNU Lesser General Public      **
00016  ** License along with the Wiselib.                                       **
00017  ** If not, see <http://www.gnu.org/licenses/>.                           **
00018  **                                                                       **
00019  ** Author: Víctor López Ferrando, victorlopez90@gmail.com                **
00020  ***************************************************************************/
00021 #ifndef __ALGORITHMS_GRAPH_DDFS_GRAPH_H__
00022 #define __ALGORITHMS_GRAPH_DDFS_GRAPH_H__
00023 
00024 #include "util/delegates/delegate.hpp"
00025 #include "util/pstl/vector_static.h"
00026 
00027 #define DEBUG_DDFS_GRAPH
00028 
00029 namespace wiselib
00030 {
00031 
00039    template<typename OsModel_P,
00040             typename Radio_P = typename OsModel_P::Radio,
00041             typename Debug_P = typename OsModel_P::Debug,
00042             uint16_t MAX_NODES = 32>
00043    class DdfsGraph
00044    {
00045    public:
00046       typedef OsModel_P OsModel;
00047       typedef Radio_P Radio;
00048       typedef Debug_P Debug;
00049 
00050       typedef typename OsModel_P::Timer Timer;
00051 
00052       typedef DdfsGraph<OsModel, Radio, Debug, MAX_NODES> self_type;
00053 
00054       typedef typename Radio::node_id_t node_id_t;
00055       typedef typename Radio::size_t size_t;
00056       typedef typename Radio::block_data_t block_data_t;
00057 
00058       typedef typename Timer::millis_t millis_t;
00059 
00060       typedef delegate0<void> ddfs_delegate_t;
00061 
00064       node_id_t parent_;
00065       vector_static<OsModel, node_id_t, MAX_NODES> children_;
00067 
00070       DdfsGraph();
00071       ~DdfsGraph();
00073 
00076       void enable( void );
00077       void disable( void );
00078       inline void set_root( void )
00079       { root_ = true; }
00081 
00084       void timer0( void *userdata );
00085       void timer1( void *userdata );
00087 
00090       void receive( node_id_t from, size_t len, block_data_t *data );
00092 
00093       inline void set_startup_time( millis_t startup_time )
00094       { startup_time_ = startup_time; };
00095 
00096       inline void set_neighbourhood_construction_time( millis_t neighbourhood_construction_time )
00097       { neighbourhood_construction_time_ = neighbourhood_construction_time; };
00098 
00099       template<class T, void (T::*TMethod)()>
00100       inline void reg_finish_callback( T *obj_pnt )
00101       {
00102          ddfs_delegate_ = ddfs_delegate_t::from_method<T, TMethod>( obj_pnt );
00103          set_ddfs_delegate_ = true;
00104       };
00105 
00106       void init( Radio& radio, Timer& timer, Debug& debug ) {
00107          radio_ = &radio;
00108          timer_ = &timer;
00109          debug_ = &debug;
00110       }
00111       
00112       void destruct() {
00113       }
00114       
00115    private:
00116       Radio& radio()
00117       { return *radio_; }
00118       
00119       Timer& timer()
00120       { return *timer_; }
00121       
00122       Debug& debug()
00123       { return *debug_; }
00124      
00125       Radio * radio_;
00126       Timer * timer_;
00127       Debug * debug_;
00128 
00131       enum DdfsGraphMsgIds {
00132          DdfsMsgIdDiscover = 130, 
00133          DdfsMsgIdReturn = 131, 
00134          DdfsMsgIdVisited = 132, 
00135          DdfsMsgIdAck = 133, 
00136          DdfsMsgIdNeighbourhood = 134, 
00137       };
00138 
00139       uint8_t message_;
00140 
00141       bool root_;
00142       millis_t startup_time_, neighbourhood_construction_time_;
00143 
00144       bool set_ddfs_delegate_;
00145       ddfs_delegate_t ddfs_delegate_;
00146 
00147       vector_static<OsModel, node_id_t, MAX_NODES> neighbours_;
00148       vector_static<OsModel, node_id_t, MAX_NODES> unvisited_;
00149       vector_static<OsModel, bool, MAX_NODES> flag_;
00150 
00151    };
00152    // -----------------------------------------------------------------------
00153    // -----------------------------------------------------------------------
00154    // -----------------------------------------------------------------------
00155    template<typename OsModel_P,
00156             typename Radio_P,
00157             typename Debug_P,
00158             uint16_t MAX_NODES>
00159    DdfsGraph<OsModel_P, Radio_P, Debug_P, MAX_NODES>::
00160    DdfsGraph()
00161       : root_ ( false ),
00162       startup_time_ ( 2000 ),
00163       neighbourhood_construction_time_ ( 3000 ),
00164       set_ddfs_delegate_ ( false )
00165    {};
00166    // -----------------------------------------------------------------------
00167    template<typename OsModel_P,
00168             typename Radio_P,
00169             typename Debug_P,
00170             uint16_t MAX_NODES>
00171    DdfsGraph<OsModel_P, Radio_P, Debug_P, MAX_NODES>::
00172    ~DdfsGraph()
00173    {
00174 #ifdef DEBUG_DDFS_GRAPH
00175 //       debug().debug( "%i: DdfsGraph Destroyed\n", radio().id() );
00176 #endif
00177    };
00178    // -----------------------------------------------------------------------
00179    template<typename OsModel_P,
00180             typename Radio_P,
00181             typename Debug_P,
00182             uint16_t MAX_NODES>
00183    void
00184    DdfsGraph<OsModel_P, Radio_P, Debug_P, MAX_NODES>::
00185    enable( void )
00186    {
00187       radio().enable_radio();
00188       radio().template reg_recv_callback<self_type, &self_type::receive>(
00189                                  this );
00190       parent_ = -1; // TODO NOTE
00191       timer().template set_timer<self_type, &self_type::timer0>(
00192                            startup_time_, this, 0 );
00193    }
00194    // -----------------------------------------------------------------------
00195    template<typename OsModel_P,
00196             typename Radio_P,
00197             typename Debug_P,
00198             uint16_t MAX_NODES>
00199    void
00200    DdfsGraph<OsModel_P, Radio_P, Debug_P, MAX_NODES>::
00201    disable( void )
00202    {
00203 #ifdef DEBUG_DDFS_GRAPH
00204       debug().debug( "%i: Called DdfsGraph::disable\n", radio().id() );
00205 #endif
00206    }
00207    // -----------------------------------------------------------------------
00208    template<typename OsModel_P,
00209             typename Radio_P,
00210             typename Debug_P,
00211             uint16_t MAX_NODES>
00212    void
00213    DdfsGraph<OsModel_P, Radio_P, Debug_P, MAX_NODES>::
00214    timer0( void* userdata )
00215    {
00216 #ifdef DEBUG_DDFS_GRAPH
00217       debug().debug( "%i: Executing TimerElapsed 'DdfsGraph'\n", radio().id()  );
00218 #endif
00219       message_ = DdfsMsgIdNeighbourhood;
00220       radio().send( radio().BROADCAST_ADDRESS, 1, (uint8_t*)&message_ );
00221       if ( root_ )
00222          timer().template set_timer<self_type, &self_type::timer1>(
00223                                     neighbourhood_construction_time_, this, 0 );
00224    }
00225    // -----------------------------------------------------------------------
00226    template<typename OsModel_P,
00227             typename Radio_P,
00228             typename Debug_P,
00229             uint16_t MAX_NODES>
00230    void
00231    DdfsGraph<OsModel_P, Radio_P, Debug_P, MAX_NODES>::
00232    timer1( void* userdata )
00233    {
00234 #ifdef DEBUG_DDFS_GRAPH
00235       debug().debug( "%i: Executing TimerElapsed 'DdfsGraph'\n", radio().id()  );
00236 #endif
00237       message_ = DdfsMsgIdDiscover;
00238       receive( radio().id(), 1, (uint8_t*)&message_ );
00239    }
00240    // -----------------------------------------------------------------------
00241    template<typename OsModel_P,
00242             typename Radio_P,
00243             typename Debug_P,
00244             uint16_t MAX_NODES>
00245    void
00246    DdfsGraph<OsModel_P, Radio_P, Debug_P, MAX_NODES>::
00247    receive( node_id_t from, size_t len, block_data_t *data )
00248    {
00249 #ifdef DEBUG_DDFS_GRAPH
00250    debug().debug( "%i: Received message from %i\n", radio().id(), from  );
00251 #endif
00252       uint8_t msg_id = *data;
00253       if ( msg_id == DdfsMsgIdNeighbourhood and from != radio().id() )
00254       {
00255 #ifdef DEBUG_DDFS_GRAPH
00256    debug().debug( "%i: It's a DdfsMsgIdNeighbourhood message from %i\n", radio().id(), from );
00257 #endif
00258          neighbours_.push_back( from );
00259          unvisited_.push_back( from );
00260          flag_.push_back( false );
00261       }
00262       else if ( msg_id == DdfsMsgIdDiscover ) // I'm visited for the first time
00263       {
00264 #ifdef DEBUG_DDFS_GRAPH
00265    debug().debug( "%i: It's a DdfsMsgIdDiscover message from %i\n", radio().id(), from );
00266 #endif
00267          parent_ = from;
00268          for ( int i = 0; i < (int)neighbours_.size(); ++i )
00269          {
00270             message_ = DdfsMsgIdVisited;
00271             radio().send( neighbours_[i], 1, (uint8_t*)&message_ );
00272             flag_[i] = true;
00273          }
00274          if ( neighbours_.size() == 1 and neighbours_[0] == from ) // from is my only neighbour
00275          {
00276             message_ = DdfsMsgIdReturn;
00277             if ( parent_ == radio().id() )
00278                receive( radio().id(), 1, (uint8_t*)&message_ );
00279             else
00280                radio().send( parent_, 1, (uint8_t*)&message_ );
00281          }
00282       }
00283       else if ( msg_id == DdfsMsgIdReturn ) // the search is resumed from me, wich I've already been visited
00284       {
00285 #ifdef DEBUG_DDFS_GRAPH
00286    debug().debug( "%i: It's a DdfsMsgIdReturn message from %i\n", radio().id(), from );
00287 #endif
00288          if ( from != radio().id() )
00289             children_.push_back( from );
00290          if ( not unvisited_.empty() )
00291          {
00292             message_ = DdfsMsgIdDiscover;
00293             radio().send( unvisited_[unvisited_.size() - 1], 1, (uint8_t*)&message_ );
00294             unvisited_.pop_back();
00295          }
00296          else // all neighbours are visited
00297          {
00298             if ( parent_ != radio().id() )
00299             {
00300                message_ = DdfsMsgIdReturn;
00301                if ( parent_ == radio().id() )
00302                   receive( radio().id(), 1, (uint8_t*)&message_ );
00303                else
00304                   radio().send( parent_, 1, (uint8_t*)&message_ );
00305             }
00306             else
00307             {
00308 #ifdef DEBUG_DDFS_GRAPH
00309    debug().debug( "%i: Stop of the algorithm\n", radio().id(), from );
00310 #endif
00311                if ( set_ddfs_delegate_ )
00312                   ddfs_delegate_();
00313             }
00314          }
00315       }
00316       else if ( msg_id == DdfsMsgIdVisited )
00317       {
00318 #ifdef DEBUG_DDFS_GRAPH
00319    debug().debug( "%i: It's a DdfsMsgIdVisited message from %i\n", radio().id(), from );
00320 #endif
00321          int erase_position = -1;
00322          for ( int i = 0; i < (int)unvisited_.size(); ++i )
00323             if ( unvisited_[i] == from )
00324                erase_position = i;
00325          if ( erase_position != -1 )
00326             unvisited_.erase(unvisited_.begin() + erase_position);
00327          message_ = DdfsMsgIdAck;
00328          radio().send( from, 1, (uint8_t*)&message_ );
00329       }
00330       else if ( msg_id == DdfsMsgIdAck )
00331       {
00332 #ifdef DEBUG_DDFS_GRAPH
00333    debug().debug( "%i: It's a DdfsMsgIdAck message from %i\n", radio().id(), from );
00334 #endif
00335          for ( int i = 0; i < (int)neighbours_.size(); ++i )
00336             if ( neighbours_[i] == from )
00337                flag_[i] = false;
00338          bool all_false = true;
00339          for ( int i = 0; all_false and i < (int)neighbours_.size(); ++i )
00340          {
00341             if ( flag_[i] == true )
00342                all_false = false;
00343          }
00344          if ( all_false )
00345          {
00346             message_ = DdfsMsgIdReturn;
00347             receive( radio().id(), 1, (uint8_t*)&message_ );
00348          }
00349       }
00350    }
00351 }
00352 #endif