# GraphConceptAlgorithms.h

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

Generated on Mon Sep 26 18:43:45 2011 for CRyptography And Groups (CRAG) by  1.6.1