00001
00002
00003
00004
00005
00006
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
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
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
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
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
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
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
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