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 using namespace std;
00014 
00015 
00016 #ifndef _GraphConceptAlgorithms_H_
00017 #define _GraphConceptAlgorithms_H_
00018 
00019 
00020 namespace Graphs
00021 {
00022 
00023   //---------------------------------------------------------------------------//
00024   //-------------------------- getGeodesicTree_in -----------------------------//
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   //-------------------------- getGeodesicTree_out ----------------------------//
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   //---------------------------- getDistances_out -----------------------------//
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   //----------------------------- getDistances_in -----------------------------//
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   //-------------------------- readoffGeodesicTree ----------------------------//
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   //---------------------------------- trace ----------------------------------//
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   //-------------------------------- trace_path -------------------------------//
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   //-------------------------------- FoldDetails ------------------------------//
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       // int newVertex;  // = min{ theEdge1.theTarget , theEdge2.theTarget }
00381       // int oldVertex1; // = theEdge1.theTarget;
00382       // int oldVertex2; // = theEdge2.theTarget;
00383       
00384       int theOrigin;
00385       EdgeType theEdge1; // edge: theOrigin -> theVertex1 
00386       EdgeType theEdge2; // edge: theOrigin -> theVertex2
00387       
00388       VertexType theVertex1;
00389       VertexType theVertex2;
00390     };
00391   
00392   //---------------------------------------------------------------------------//
00393   //------------------------------------ fold ---------------------------------//
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   //----------------------------------- unfold --------------------------------//
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   //----------------------------------- liftup --------------------------------//
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       // unfold
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       // liftup the current path edge by edge
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           // if the current vertex (origin of the current edge) is the split vertex then we make 2 steps
00527           int v1 = (i==0 ? cur_vertex : oldVertex2);
00528           
00529           for( int j=0 ; j<(new_vertex==oldVertex1?2:1) && !edge_found ; ++j ) { 
00530             // if the new vertex (target of the current edge) is the split vertex then we make 2 steps
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( ) ) { // the edge is found
00536               
00537               (*path_it).theTarget = v2;
00538               if( i==1 ) { // initial vertex has jumped
00539                 // insert a 2-edge path before the current edge connecting cur_vertex=oldVertex1 and oldVertex2
00540                 path.insert( path_it , (*E).theEdge1.inverse( theOrigin ) );
00541                 path.insert( path_it , (*E).theEdge2 );
00542               }
00543               
00544               if( j==1 ) { // terminal vertex has jumped
00545                 // insert a 2-edge path after the current edge connecting cur_vertex and removedVertex
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   //----------------------------------- liftup --------------------------------//
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

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