00001
00002
00003
00004
00005
00006
00007
00008
00009 #include "iostream"
00010 #include "map"
00011 #include "set"
00012 #include "list"
00013 using namespace std;
00014
00015
00016 #ifndef _GraphConceptAlgorithms_H_
00017 #define _GraphConceptAlgorithms_H_
00018
00019
00020 namespace Graphs
00021 {
00022
00023
00024
00025
00027
00031 template < class Graph > map< int , typename Graph::edge_type > getGeodesicTree_in( const Graph& graph , int init_v )
00032 {
00033 typedef typename Graph::vertex_type vertex_type;
00034 typedef typename Graph::edge_type edge_type;
00035 map< int , edge_type > result;
00036
00037 const map< int , vertex_type >& theVertices = graph.getVertices( );
00038
00039 if( theVertices.find( init_v )==theVertices.end( ) ) {
00040 cout << "Nonexisting initial state. (9482)" << endl;
00041 exit( 1 );
00042 }
00043
00044 set< int > checked_verts;
00045 set< int > cur_verts;
00046 set< int > new_verts;
00047 new_verts.insert( init_v );
00048 result[init_v] = edge_type( );
00049
00050 while( new_verts.size( ) ) {
00051
00052 cur_verts = new_verts;
00053 new_verts.clear( );
00054 while( cur_verts.size( ) ) {
00055
00056 int cur_v = *cur_verts.begin( );
00057 cur_verts.erase( cur_verts.begin( ) );
00058 checked_verts.insert( cur_v );
00059
00060 typename map< int , vertex_type >::const_iterator st_it = theVertices.find( cur_v );
00061 if( st_it==theVertices.end( ) ) {
00062 cout << "Unexpected situation in getGeodesicTree. (0276)" << endl;
00063 exit( 1 );
00064 }
00065 const vertex_type& cur_V = (*st_it).second;
00066 const set< edge_type >& in = cur_V.in;
00067 typename set< edge_type >::const_iterator in_it = in.begin( );
00068 for( ; in_it!=in.end( ) ; ++in_it ) {
00069
00070 int new_v = (*in_it).theTarget;
00071 if( checked_verts.find(new_v)==checked_verts.end() && cur_verts.find(new_v)==cur_verts.end() && new_verts.find(new_v)==new_verts.end() ) {
00072 new_verts.insert( new_v );
00073 edge_type edge = *in_it;
00074 edge.theTarget = cur_v;
00075 result[new_v] = edge;
00076 }
00077 }
00078 }
00079 }
00080
00081 return result;
00082 }
00083
00084
00085
00086
00088
00092 template < class Graph >
00093 map< int , typename Graph::edge_type > getGeodesicTree_out( const Graph& graph , int init_v )
00094 {
00095 typedef typename Graph::vertex_type vertex_type;
00096 typedef typename Graph::edge_type edge_type;
00097 map< int , edge_type > result;
00098
00099 const map< int , vertex_type >& theVertices = graph.getVertices( );
00100
00101 if( theVertices.find( init_v )==theVertices.end( ) ) {
00102 cout << "Nonexisting initial state. (9482)" << endl;
00103 exit( 1 );
00104 }
00105
00106 set< int > checked_verts;
00107 set< int > cur_verts;
00108 set< int > new_verts;
00109 new_verts.insert( init_v );
00110 result[init_v] = edge_type( );
00111
00112 while( new_verts.size( ) ) {
00113
00114 cur_verts = new_verts;
00115 new_verts.clear( );
00116 while( cur_verts.size( ) ) {
00117
00118 int cur_v = *cur_verts.begin( );
00119 cur_verts.erase( cur_verts.begin( ) );
00120 checked_verts.insert( cur_v );
00121
00122 typename map< int , vertex_type >::const_iterator st_it = theVertices.find( cur_v );
00123 if( st_it==theVertices.end( ) ) {
00124 cout << "Unexpected situation in getGeodesicTree. (0276)" << endl;
00125 exit( 1 );
00126 }
00127 const vertex_type& cur_V = (*st_it).second;
00128 const set< edge_type >& out = cur_V.out;
00129 typename set< edge_type >::const_iterator out_it = out.begin( );
00130 for( ; out_it!=out.end( ) ; ++out_it ) {
00131
00132 int new_v = (*out_it).theTarget;
00133 if( checked_verts.find(new_v)==checked_verts.end() && cur_verts.find(new_v)==cur_verts.end() && new_verts.find(new_v)==new_verts.end() ) {
00134 new_verts.insert( new_v );
00135 edge_type edge = *out_it;
00136 edge.theTarget = cur_v;
00137 result[new_v] = edge;
00138 }
00139 }
00140 }
00141 }
00142
00143 return result;
00144 }
00145
00146
00147
00148
00149
00150
00152 template < class Graph >
00153 map< int , int > getDistances_out( const Graph& graph , int init_v )
00154 {
00155 typedef typename Graph::vertex_type vertex_type;
00156 typedef typename Graph::edge_type edge_type;
00157 map< int , int > result;
00158
00159 const map< int , vertex_type >& theVertices = graph.getVertices( );
00160
00161 if( theVertices.find( init_v )==theVertices.end( ) ) {
00162 cout << "Nonexisting initial state. (9432)" << endl;
00163 exit( 1 );
00164 }
00165
00166 set< int > checked_verts;
00167 set< int > cur_verts;
00168 set< int > new_verts;
00169 new_verts.insert( init_v );
00170 result[init_v] = 0;
00171
00172 for( int dist=1 ; new_verts.size( ) ; ++dist ) {
00173 cur_verts = new_verts;
00174 new_verts.clear( );
00175 while( cur_verts.size( ) ) {
00176
00177 int cur_v = *cur_verts.begin( );
00178 cur_verts.erase( cur_verts.begin( ) );
00179 checked_verts.insert( cur_v );
00180
00181 typename map< int , vertex_type >::const_iterator st_it = theVertices.find( cur_v );
00182 if( st_it==theVertices.end( ) ) {
00183 cout << "Unexpected situation in getGeodesicTree. (89766)" << endl;
00184 exit( 1 );
00185 }
00186 const vertex_type& cur_V = (*st_it).second;
00187 const set< edge_type >& out = cur_V.out;
00188 typename set< edge_type >::const_iterator out_it = out.begin( );
00189 for( ; out_it!=out.end( ) ; ++out_it ) {
00190
00191 int new_v = (*out_it).theTarget;
00192 if( checked_verts.find(new_v)==checked_verts.end() && cur_verts.find(new_v)==cur_verts.end() && new_verts.find(new_v)==new_verts.end() ) {
00193 new_verts.insert( new_v );
00194 result[new_v] = dist;
00195 }
00196 }
00197 }
00198 }
00199
00200 return result;
00201 }
00202
00203
00204
00205
00206
00207
00208
00210 template < class Graph >
00211 map< int , int > getDistances_in( const Graph& graph , int init_v )
00212 {
00213 typedef typename Graph::vertex_type vertex_type;
00214 typedef typename Graph::edge_type edge_type;
00215 map< int , int > result;
00216
00217 const map< int , vertex_type >& theVertices = graph.getVertices( );
00218
00219 if( theVertices.find( init_v )==theVertices.end( ) ) {
00220 cout << "Nonexisting initial state. (9432)" << endl;
00221 exit( 1 );
00222 }
00223
00224 set< int > checked_verts;
00225 set< int > cur_verts;
00226 set< int > new_verts;
00227 new_verts.insert( init_v );
00228 result[init_v] = 0;
00229
00230 for( int dist=1 ; new_verts.size( ) ; ++dist ) {
00231 cur_verts = new_verts;
00232 new_verts.clear( );
00233 while( cur_verts.size( ) ) {
00234
00235 int cur_v = *cur_verts.begin( );
00236 cur_verts.erase( cur_verts.begin( ) );
00237 checked_verts.insert( cur_v );
00238
00239 typename map< int , vertex_type >::const_iterator st_it = theVertices.find( cur_v );
00240 if( st_it==theVertices.end( ) ) {
00241 cout << "Unexpected situation in getGeodesicTree. (89766)" << endl;
00242 exit( 1 );
00243 }
00244 const vertex_type& cur_V = (*st_it).second;
00245 const set< edge_type >& in = cur_V.in;
00246 typename set< edge_type >::const_iterator in_it = in.begin( );
00247 for( ; in_it!=in.end( ) ; ++in_it ) {
00248
00249 int new_v = (*in_it).theTarget;
00250 if( checked_verts.find(new_v)==checked_verts.end() && cur_verts.find(new_v)==cur_verts.end() && new_verts.find(new_v)==new_verts.end() ) {
00251 new_verts.insert( new_v );
00252 result[new_v] = dist;
00253 }
00254 }
00255 }
00256 }
00257
00258 return result;
00259 }
00260
00261
00262
00263
00264
00265
00266
00268 template < class edge_type >
00269 pair< bool , list< edge_type > > readoffGeodesicTree( const map< int , edge_type >& tree , int v )
00270 {
00271 list< edge_type > result;
00272
00273 while( 1 ) {
00274 typename map< int , edge_type >::const_iterator t_it = tree.find( v );
00275 if( t_it==tree.end( ) )
00276 return pair< bool , list< edge_type > >( false , list< edge_type >( ) );
00277 if( (*t_it).second.theTarget==-1 )
00278 break;
00279 result.push_back( (*t_it).second );
00280 v = (*t_it).second.theTarget;
00281 }
00282
00283 return pair< bool , list< edge_type > >( true , result );
00284 }
00285
00286
00287
00288
00289
00290
00291 template < class LabelledGraph , class ConstIterator >
00292 int trace( const LabelledGraph& LG , int init_v , ConstIterator B , ConstIterator E )
00293 {
00294 typedef typename LabelledGraph::vertex_type vertex_type;
00295 typedef typename LabelledGraph::edge_type edge_type;
00296 const map< int , vertex_type >& theVertices = LG.getVertices( );
00297
00298 int cur_v = init_v;
00299 for( ; B!=E ; ++B ) {
00300
00301 typename map< int , vertex_type >::const_iterator v_it = theVertices.find( cur_v );
00302 if( v_it==theVertices.end( ) )
00303 return -1;
00304
00305 bool success = false;
00306 int label = *B;
00307 const vertex_type& cur_V = (*v_it).second;
00308 const set< edge_type >& out = cur_V.out;
00309 typename set< edge_type >::const_iterator out_it = out.begin( );
00310 for( ; out_it!=out.end( ) ; ++out_it ) {
00311 if( (*out_it).theLabel == label ) {
00312 cur_v = (*out_it).theTarget;
00313 success = true;
00314 break;
00315 }
00316 }
00317 if( !success )
00318 return -1;
00319 }
00320
00321 return cur_v;
00322 }
00323
00324
00325
00326
00327
00328
00329
00330 template < class LabelledGraph , class ConstIterator >
00331 pair< bool , list< typename LabelledGraph::edge_type > > trace_path( const LabelledGraph& LG , int init_v , ConstIterator B , ConstIterator E )
00332 {
00333 typedef typename LabelledGraph::vertex_type vertex_type;
00334 typedef typename LabelledGraph::edge_type edge_type;
00335 const map< int , vertex_type >& theVertices = LG.getVertices( );
00336
00337 int cur_v = init_v;
00338 pair< bool , list< edge_type > > result;
00339 result.first = true;
00340 for( ; B!=E ; ++B ) {
00341
00342 typename map< int , vertex_type >::const_iterator v_it = theVertices.find( cur_v );
00343 if( v_it==theVertices.end( ) )
00344 return pair< bool , list< edge_type > >( false , list< edge_type >( ) );
00345
00346 bool success = false;
00347 int label = *B;
00348 const vertex_type& cur_V = (*v_it).second;
00349 const set< edge_type >& out = cur_V.out;
00350 typename set< edge_type >::const_iterator out_it = out.begin( );
00351 for( ; out_it!=out.end( ) ; ++out_it ) {
00352 if( (*out_it).theLabel == label ) {
00353 cur_v = (*out_it).theTarget;
00354 success = true;
00355 result.second.push_back( *out_it );
00356 break;
00357 }
00358 }
00359 if( !success )
00360 return pair< bool , list< edge_type > >( false , list< edge_type >( ) );
00361 }
00362
00363 return result;
00364 }
00365
00366
00367
00368
00369
00370
00374 template < class VertexType , class EdgeType >
00375 struct FoldDetails {
00376
00377 FoldDetails( int o , const EdgeType& e1 , const EdgeType& e2 , const VertexType& V1 , const VertexType& V2 ) :
00378 theOrigin(o), theEdge1(e1), theEdge2(e2), theVertex1(V1), theVertex2(V2) { }
00379
00380
00381
00382
00383
00384 int theOrigin;
00385 EdgeType theEdge1;
00386 EdgeType theEdge2;
00387
00388 VertexType theVertex1;
00389 VertexType theVertex2;
00390 };
00391
00392
00393
00394
00395
00397
00401 template < class LabelledGraph >
00402 void fold( LabelledGraph& G , set< int > candidates ,
00403 list< FoldDetails< typename LabelledGraph::vertex_type , typename LabelledGraph::edge_type > >* details = NULL )
00404 {
00405 typedef typename LabelledGraph::vertex_type vertex_type;
00406 typedef typename LabelledGraph::edge_type edge_type;
00407 typedef FoldDetails< vertex_type , edge_type > FD;
00408 const map< int , vertex_type >& theVertices = G.getVertices( );
00409
00410
00411 while( !candidates.empty( ) ) {
00412 int v = *candidates.begin( );
00413 candidates.erase( v );
00414 if( theVertices.find(v)==theVertices.end( ) ) continue;
00415 const vertex_type& V = (*theVertices.find( v )).second;
00416
00417 const set< edge_type >& out = V.out;
00418 typename set< edge_type >::const_iterator e_it = out.begin( );
00419 for( ; e_it!=out.end( ) ; ++e_it ) {
00420 typename set< edge_type >::const_iterator e_it2 = e_it;
00421 ++e_it2;
00422 if( e_it2==out.end( ) )
00423 break;
00424 if( (*e_it).theLabel==(*e_it2).theLabel ) {
00425 int t1 = (*e_it).theTarget;
00426 int t2 = (*e_it2).theTarget;
00427 if( details ) {
00428 const vertex_type& V1 = (*theVertices.find( t1 )).second;
00429 const vertex_type& V2 = (*theVertices.find( t2 )).second;
00430 if( t1<t2 )
00431 details->push_back( FD( v , *e_it , *e_it2 , V1 , V2 ) );
00432 else
00433 details->push_back( FD( v , *e_it2 , *e_it , V2 , V1 ) );
00434 }
00435 G.pinch( t1 , t2 );
00436 candidates.insert( t1<t2 ? t1:t2 );
00437 candidates.insert( v );
00438 break;
00439 }
00440 }
00441 }
00442
00443 }
00444
00445 template < class LabelledGraph >
00446 void fold( const LabelledGraph& G , int candidate ,
00447 list< FoldDetails< typename LabelledGraph::vertex_type , typename LabelledGraph::edge_type > >* details = NULL )
00448 {
00449 set< int > candidates;
00450 candidates.insert( candidate );
00451 fold( G , candidates , details );
00452 }
00453
00454 template < class LabelledGraph >
00455 void fold( const LabelledGraph& G ,
00456 list< FoldDetails< typename LabelledGraph::vertex_type , typename LabelledGraph::edge_type > >* details = NULL )
00457 {
00458 typedef typename LabelledGraph::vertex_type vertex_type;
00459 typedef typename LabelledGraph::edge_type edge_type;
00460
00461 set< int > candidates;
00462 const map< int , vertex_type >& theVertices = G.getVertices( );
00463 typename map< int , vertex_type >::const_iterator v_it = theVertices.begin( );
00464 for( ; v_it!=theVertices.end( ) ; ++v_it )
00465 candidates.insert( *v_it );
00466
00467 fold( G , candidates , details );
00468 }
00469
00470
00471
00472
00473
00474
00475
00477 template < class LabelledGraph , class FoldDetailsConstIterator >
00478 void unfold( LabelledGraph& G , FoldDetailsConstIterator B , FoldDetailsConstIterator E )
00479 {
00480 for( ; B!=E ; ) {
00481 --E;
00482 int oldVertex1 = (*E).theEdge1.theTarget;
00483 int oldVertex2 = (*E).theEdge2.theTarget;
00484 G.eraseVertex( oldVertex1 );
00485 G.replaceVertex( oldVertex1 , (*E).theVertex1 );
00486 G.replaceVertex( oldVertex2 , (*E).theVertex2 );
00487 }
00488 }
00489
00490
00491
00492
00493
00495 template < class LabelledGraph , class FoldDetailsConstIterator >
00496 void liftup( const LabelledGraph& graph , int init_vertex ,
00497 list< typename LabelledGraph::edge_type >& path ,
00498 FoldDetailsConstIterator B , FoldDetailsConstIterator E )
00499 {
00500 LabelledGraph G = graph;
00501 typedef typename LabelledGraph::vertex_type vertex_type;
00502 typedef typename LabelledGraph::edge_type edge_type;
00503
00504 for( ; B!=E ; ) {
00505
00506
00507 --E;
00508 int theOrigin = (*E).theOrigin;
00509 int oldVertex1 = (*E).theEdge1.theTarget;
00510 int oldVertex2 = (*E).theEdge2.theTarget;
00511 G.eraseVertex( oldVertex1 );
00512 G.replaceVertex( oldVertex1 , (*E).theVertex1 );
00513 G.replaceVertex( oldVertex2 , (*E).theVertex2 );
00514
00515 const map< int , vertex_type >& theVertices = G.getVertices( );
00516
00517
00518 int cur_vertex = init_vertex;
00519 typename list< edge_type >::iterator path_it = path.begin( );
00520 for( ; path_it!=path.end( ) ; ++path_it ) {
00521
00522 bool edge_found = false;
00523 edge_type edge = *path_it;
00524 int new_vertex = (*path_it).theTarget;
00525 for( int i=0 ; i<(cur_vertex==oldVertex1?2:1) && !edge_found ; ++i ) {
00526
00527 int v1 = (i==0 ? cur_vertex : oldVertex2);
00528
00529 for( int j=0 ; j<(new_vertex==oldVertex1?2:1) && !edge_found ; ++j ) {
00530
00531 int v2 = (j==0 ? new_vertex : oldVertex2);
00532
00533 edge.theTarget = v2;
00534 const vertex_type& V1 = (*theVertices.find( v1 )).second;
00535 if( V1.out.find( edge )!=V1.out.end( ) ) {
00536
00537 (*path_it).theTarget = v2;
00538 if( i==1 ) {
00539
00540 path.insert( path_it , (*E).theEdge1.inverse( theOrigin ) );
00541 path.insert( path_it , (*E).theEdge2 );
00542 }
00543
00544 if( j==1 ) {
00545
00546 ++path_it;
00547 path.insert( path_it , (*E).theEdge2.inverse( theOrigin ) );
00548 path.insert( path_it , (*E).theEdge1 );
00549 --path_it;
00550 }
00551 edge_found = true;
00552 }
00553 }
00554 }
00555
00556 if( !edge_found ) {
00557 cout << "Big shit" << endl;
00558 exit(1);
00559 }
00560 cur_vertex = new_vertex;
00561 }
00562 reduce_path( init_vertex , path );
00563 }
00564 }
00565
00566
00567
00568
00569
00571 template < class edge_type >
00572 void reduce_path( int init_vertex , list< edge_type >& path )
00573 {
00574 list< int > vertices;
00575 vertices.push_back( init_vertex );
00576 typename list< edge_type >::iterator path_it = path.begin( );
00577 for( ; path_it!=path.end( ) ; ) {
00578
00579 vertices.push_back( (*path_it).theTarget );
00580 if( path_it==path.begin( ) ) {
00581 ++path_it;
00582 continue;
00583 }
00584 int old_vertex = *-- -- --vertices.end( );
00585
00586 typename list< edge_type >::iterator path_it2 = path_it;
00587 --path_it2;
00588 if( *path_it!=(*path_it2).inverse( old_vertex ) ) {
00589 ++path_it;
00590 continue;
00591 }
00592
00593 vertices.pop_back( );
00594 vertices.pop_back( );
00595 path.erase( path_it2 );
00596 path_it = path.erase( path_it );
00597 }
00598 }
00599
00600 }
00601
00602
00603 #endif