GraphAlgorithms.h

Go to the documentation of this file.
00001 // Copyright (C) 2005 Alexander Ushakov
00002 // Contents: Definitions of Graph algorithms
00003 //
00004 // Principal Authors: Alexander Ushakov
00005 //
00006 // Revision History:
00007 //
00008 
00009 #ifndef _GraphAlgorithms_h_
00010 #define _GraphAlgorithms_h_
00011 
00012 
00013 #include "iostream"
00014 #include "map"
00015 #include "set"
00016 #include "list"
00017 using namespace std;
00018 
00019 
00020 //---------------------------------------------------------------------------//
00021 //-------------------------- getGeodesicTree_in -----------------------------//
00022 //---------------------------------------------------------------------------//
00023 
00024 
00025 template < class Graph >
00026 map< int , typename Graph::edge_type > getGeodesicTree_in( const Graph& graph , int init_st )
00027 {
00028   typedef typename Graph::state_type state_type;
00029   typedef typename Graph::edge_type edge_type;
00030   map< int , edge_type > result;
00031 
00032   const map< int , state_type >& theStates = graph.getStates( );
00033 
00034   if( theStates.find( init_st )==theStates.end( ) ) {
00035    cout << "Nonexisting initial state. (9482)" << endl;
00036    exit( 1 );
00037   }
00038 
00039   set< int > checked_pts;
00040   set< int > cur_pts;
00041   set< int > new_pts;
00042   new_pts.insert( init_st );
00043   result[init_st] = edge_type( );
00044 
00045   while( new_pts.size( ) ) {
00046 
00047     cur_pts = new_pts;
00048     new_pts.clear( );
00049     while( cur_pts.size( ) ) {
00050 
00051       int cur_st = *cur_pts.begin( );
00052       cur_pts.erase( cur_pts.begin( ) );
00053       checked_pts.insert( cur_st );
00054         
00055       typename map< int , state_type >::const_iterator st_it = theStates.find( cur_st );
00056       if( st_it==theStates.end( ) ) {
00057         cout << "Unexpected situation in getGeodesicTree. (0276)" << endl;
00058         exit( 1 );
00059       }
00060       const state_type& cur_state = (*st_it).second;
00061       const set< edge_type >& in = cur_state.in;
00062       typename set< edge_type >::const_iterator in_it = in.begin( );
00063       for( ; in_it!=in.end( ) ; ++in_it ) {
00064 
00065         int new_st = (*in_it).target;
00066         if( checked_pts.find(new_st)==checked_pts.end() && cur_pts.find(new_st)==cur_pts.end() && new_pts.find(new_st)==new_pts.end() ) {
00067           new_pts.insert( new_st );
00068           edge_type edge = *in_it;
00069           edge.target = cur_st;
00070           result[new_st] = edge;
00071         }
00072       }
00073     }
00074   }
00075 
00076   return result;
00077 }
00078 
00079 
00080 //---------------------------------------------------------------------------//
00081 //-------------------------- getGeodesicTree_out ----------------------------//
00082 //---------------------------------------------------------------------------//
00083 
00084 
00085 template < class Graph >
00086 map< int , typename Graph::edge_type > getGeodesicTree_out( const Graph& graph , int init_st )
00087 {
00088   typedef typename Graph::state_type state_type;
00089   typedef typename Graph::edge_type edge_type;
00090   map< int , edge_type > result;
00091 
00092   const map< int , state_type >& theStates = graph.getStates( );
00093 
00094   if( theStates.find( init_st )==theStates.end( ) ) {
00095    cout << "Nonexisting initial state. (9482)" << endl;
00096    exit( 1 );
00097   }
00098 
00099   set< int > checked_pts;
00100   set< int > cur_pts;
00101   set< int > new_pts;
00102   new_pts.insert( init_st );
00103   result[init_st] = edge_type( );
00104 
00105   while( new_pts.size( ) ) {
00106 
00107     cur_pts = new_pts;
00108     new_pts.clear( );
00109     while( cur_pts.size( ) ) {
00110 
00111       int cur_st = *cur_pts.begin( );
00112       cur_pts.erase( cur_pts.begin( ) );
00113       checked_pts.insert( cur_st );
00114 
00115       typename map< int , state_type >::const_iterator st_it = theStates.find( cur_st );
00116       if( st_it==theStates.end( ) ) {
00117         cout << "Unexpected situation in getGeodesicTree. (0276)" << endl;
00118         exit( 1 );
00119       }
00120       const state_type& cur_state = (*st_it).second;
00121       const set< edge_type >& out = cur_state.out;
00122       typename set< edge_type >::const_iterator out_it = out.begin( );
00123       for( ; out_it!=out.end( ) ; ++out_it ) {
00124 
00125         int new_st = (*out_it).target;
00126         if( checked_pts.find(new_st)==checked_pts.end() && cur_pts.find(new_st)==cur_pts.end() && new_pts.find(new_st)==new_pts.end() ) {
00127           new_pts.insert( new_st );
00128           edge_type edge = *out_it;
00129           edge.target = cur_st;
00130           result[new_st] = edge;
00131         }
00132       }
00133     }
00134   }
00135 
00136   return result;
00137 }
00138 
00139 
00140 //---------------------------------------------------------------------------//
00141 //-------------------------- getGeodesicTree_out ----------------------------//
00142 //---------------------------------------------------------------------------//
00143 
00144 
00145 template < class Graph >
00146 map< int , int > getDistances_out( const Graph& graph , int init_st )
00147 {
00148   typedef typename Graph::state_type state_type;
00149   typedef typename Graph::edge_type edge_type;
00150   map< int , int > result;
00151   
00152   const map< int , state_type >& theStates = graph.getStates( );
00153   
00154   if( theStates.find( init_st )==theStates.end( ) ) {
00155    cout << "Nonexisting initial state. (9432)" << endl;
00156    exit( 1 );
00157   }
00158   
00159   set< int > checked_pts;
00160   set< int > cur_pts;
00161   set< int > new_pts;
00162   new_pts.insert( init_st );
00163   result[init_st] = 0;
00164   
00165   for( int dist=1 ; new_pts.size( ) ; ++dist ) {
00166     cur_pts = new_pts;
00167     new_pts.clear( );
00168     while( cur_pts.size( ) ) {
00169 
00170       int cur_st = *cur_pts.begin( );
00171       cur_pts.erase( cur_pts.begin( ) );
00172       checked_pts.insert( cur_st );
00173 
00174       typename map< int , state_type >::const_iterator st_it = theStates.find( cur_st );
00175       if( st_it==theStates.end( ) ) {
00176         cout << "Unexpected situation in getGeodesicTree. (89766)" << endl;
00177         exit( 1 );
00178       }
00179       const state_type& cur_state = (*st_it).second;
00180       const set< edge_type >& out = cur_state.out;
00181       typename set< edge_type >::const_iterator out_it = out.begin( );
00182       for( ; out_it!=out.end( ) ; ++out_it ) {
00183 
00184         int new_st = (*out_it).target;
00185         if( checked_pts.find(new_st)==checked_pts.end() && cur_pts.find(new_st)==cur_pts.end() && new_pts.find(new_st)==new_pts.end() ) {
00186           new_pts.insert( new_st );
00187           result[new_st] = dist;
00188         }
00189       }
00190     }
00191   }
00192 
00193   return result;
00194 }
00195 
00196 
00197 //---------------------------------------------------------------------------//
00198 //-------------------------- readoffGeodesicTree ----------------------------//
00199 //---------------------------------------------------------------------------//
00200 
00201 
00203 template < class edge_type >
00204 list< edge_type > readoffGeodesicTree( const map< int , edge_type >& tree , int st_num )
00205 {
00206   list< edge_type > result;
00207 
00208   while( 1 ) {
00209     // cout << "st_num = " << st_num << endl;
00210     typename map< int , edge_type >::const_iterator t_it = tree.find( st_num );
00211     if( t_it==tree.end( ) ) {
00212       cout << "Error. Unpredicted situation in readoffGeodesicTree( ... )" << endl;
00213       exit( 1 );
00214     }
00215     if( (*t_it).second.target==-1 )
00216       break;
00217     result.push_back( (*t_it).second );
00218     st_num = (*t_it).second.target;
00219   }
00220 
00221   return result;
00222 }
00223 
00224 
00225 //---------------------------------------------------------------------------//
00226 //---------------------------------- trace ----------------------------------//
00227 //---------------------------------------------------------------------------//
00228 
00229 
00230 template < class LabelledGraph , class ConstIterator >
00231 int trace( const LabelledGraph& LG , int init , ConstIterator B , ConstIterator E )
00232 {
00233   typedef typename LabelledGraph::state_type state_type;
00234   typedef typename LabelledGraph::edge_type edge_type;
00235   const map< int , state_type >& theStates = LG.getStates( );
00236 
00237         int cur_st = init;
00238         for( ; B!=E ; ++B ) {
00239 
00240     typename map< int , state_type >::const_iterator st_it = theStates.find( cur_st );
00241                 if( st_it==theStates.end( ) )
00242                         return -1;
00243 
00244                 bool success = false;
00245                 int label = *B;
00246     const state_type& cur_state = (*st_it).second;
00247     const set< edge_type >& out = cur_state.out;
00248                 typename set< edge_type >::const_iterator out_it = out.begin( );
00249     for( ; out_it!=out.end( ) ; ++out_it ) {
00250                         if( (*out_it).label == label ) {
00251                                 cur_st = (*out_it).target;
00252                                 success = true;
00253                                 break;
00254                         }
00255                 }
00256                 if( !success )
00257                         return -1;
00258         }
00259 
00260         return cur_st;
00261 }
00262 
00263 
00264 //---------------------------------------------------------------------------//
00265 //---------------------------------- trace ----------------------------------//
00266 //---------------------------------------------------------------------------//
00267 
00268 
00269 template < class LabelledGraph , class ConstIterator >
00270 pair< bool , list< typename LabelledGraph::edge_type > > trace_path( const LabelledGraph& LG , int init , ConstIterator B , ConstIterator E )
00271 {
00272   typedef typename LabelledGraph::state_type state_type;
00273   typedef typename LabelledGraph::edge_type edge_type;
00274   const map< int , state_type >& theStates = LG.getStates( );
00275 
00276         int cur_st = init;
00277         pair< bool , list< edge_type > > result;
00278         result.first = true;
00279         for( ; B!=E ; ++B ) {
00280 
00281     typename map< int , state_type >::const_iterator st_it = theStates.find( cur_st );
00282                 if( st_it==theStates.end( ) )
00283                         return pair< bool , list< edge_type > >( false , list< edge_type >( ) );
00284 
00285                 bool success = false;
00286                 int label = *B;
00287     const state_type& cur_state = (*st_it).second;
00288     const set< edge_type >& out = cur_state.out;
00289                 typename set< edge_type >::const_iterator out_it = out.begin( );
00290     for( ; out_it!=out.end( ) ; ++out_it ) {
00291                         if( (*out_it).label == label ) {
00292                                 cur_st = (*out_it).target;
00293                                 success = true;
00294                                 result.second.push_back( *out_it );
00295                                 break;
00296                         }
00297                 }
00298                 if( !success )
00299                         return pair< bool , list< edge_type > >( false , list< edge_type >( ) );
00300         }
00301 
00302         return result;
00303 }
00304 
00305 
00306 #endif
00307 

Generated on Mon Feb 27 22:47:04 2006 for CRyptography And Groups (CRAG) by  doxygen 1.4.4