GraphConcept.h

Go to the documentation of this file.
00001 // Copyright (C) 2005 Alexander Ushakov
00002 // Contents: Definition of the graph concept
00003 //
00004 // Principal Authors: Alexander Ushakov
00005 //
00006 // Revision History:
00007 //
00008 
00009 
00010 #ifndef _GraphConcept_h_
00011 #define _GraphConcept_h_
00012 
00013 
00014 #include "RefCounter.h"
00015 #include "ObjectOf.h"
00016 
00017 
00018 #include "set"
00019 #include "map"
00020 using namespace std;
00021 
00028 //---------------------------------------------------------------------------//
00029 //------------------------------- GraphConcept ------------------------------//
00030 //---------------------------------------------------------------------------//
00031 
00032 
00033 
00034 namespace Graphs
00035 {
00036   
00037   template< class VertexType , class EdgeType > class GraphConcept;
00038   template< class VertexType , class EdgeType > class GraphConceptRep;
00039   
00040   
00041   //---------------------------------------------------------------------------//
00042   //-------------------------------- GraphRep ---------------------------------//
00043   //---------------------------------------------------------------------------//
00044   
00045   
00047   template< class VertexType , class EdgeType > class GraphConceptRep : public RefCounter 
00048   {
00050       //                                                      //
00051       //  Constructors                                       //
00052       //                                                     //
00054       public:
00055     
00056     typedef VertexType vertex_type;
00057     typedef EdgeType   edge_type;
00058 
00059     friend class GraphConcept< vertex_type , edge_type >;
00060 
00062       //                                                     //
00063       //  Constructors                                       //
00064       //                                                     //
00066       private:
00067     
00068     GraphConceptRep( ) : maxVertex( 0 ) { }
00069 
00070 
00072       //                                                     //
00073       //  Accessors                                          //
00074       //                                                     //
00076       public:
00077 
00078     GraphConceptRep* clone( ) const { return new GraphConceptRep( *this ); }
00079   
00081       //                                                     //
00082       //  Internal functions                                 //
00083       //                                                     //
00085       private:
00086     
00088     const map< int, vertex_type >& getVertices( ) const { return theVertices; }
00089     
00091     int newVertex( ) {
00092       theVertices[maxVertex] = vertex_type( );
00093       return maxVertex++;
00094     }
00096     int newVertex( const vertex_type& V ) {
00097       _newVertex( maxVertex , V );
00098       return maxVertex++;
00099     }
00101     void replaceVertex( int v , const vertex_type& V ) {
00102       eraseVertex( v );
00103       _newVertex( v , V );
00104     }
00105 
00107     void eraseVertex( int v ) {
00108       const vertex_type& V = theVertices[v];
00109       set< edge_type >  in = V. in;
00110       set< edge_type > out = V.out;
00111       
00112       typename set< edge_type >::iterator it;
00113       
00114       // state <- (*it).first by (*it).second
00115       for( it=in.begin( ) ; it!=in.end( ) ; ++it ) {
00116         edge_type edge = *it;
00117         int origin = edge.theTarget;
00118         edge.theTarget = v;
00119         theVertices[origin].out.erase( edge );
00120       }
00121       
00122       // state2 -> (*it).first by (*it).second
00123       for( it=out.begin( ) ; it!=out.end( ) ; ++it ) {
00124         edge_type edge = *it;
00125         int target = edge.theTarget;
00126         edge.theTarget = v;
00127         theVertices[target].in.erase( edge );
00128       }
00129       theVertices.erase( v );
00130     }
00131     
00133     void newEdge( int v , const edge_type& E ) {
00134       int t = E.theTarget;
00135       theVertices[v].out.insert( E );
00136       edge_type back = E;
00137       back.theTarget = v;
00138       theVertices[t]. in.insert( back );
00139     }
00140 
00142     void eraseVertex( int v , const edge_type& E ) {
00143       int t = E.theTarget;
00144       theVertices[v].out.erase( E );
00145       edge_type back = E;
00146       back.theTarget = v;
00147       theVertices[t]. in.erase( back );
00148     }
00149     
00150     
00152     void clear( ) {
00153       theVertices.clear( );
00154       maxVertex = 0;
00155     }
00156     
00157     void pinch( int v1 , int v2 ) {
00158       if( v1==v2 ) return;
00159       if( v1>v2 ) swap( v1 , v2 );
00160       const vertex_type& V2 = theVertices[v2];
00161       set< edge_type >  in = V2. in;
00162       set< edge_type > out = V2.out;
00163       
00164       typename set< edge_type >::iterator it;
00165       
00166       // V2 <- *it
00167       for( it=in.begin( ) ; it!=in.end( ) ; ++it ) {
00168         edge_type edge = *it;
00169         int origin = edge.theTarget;
00170         if( origin!=v2 ) {
00171           edge.theTarget = v2;
00172           // cout << "    Erase  from out N " << origin << " : " << edge << endl;
00173           theVertices[origin].out.erase( edge );
00174           edge.theTarget = v1;
00175           // cout << "    Insert to   out N " << origin << " : " << edge << endl;
00176           newEdge( origin , edge );
00177           // theVertices[origin].out.insert( edge );
00178         } else {
00179           edge.theTarget = v1;
00180           theVertices[v1].out.insert( edge );
00181         }
00182       }
00183       
00184       // V2 -> *it
00185       for( it=out.begin( ) ; it!=out.end( ) ; ++it ) {
00186         edge_type edge = *it;
00187         int target = edge.theTarget;
00188         
00189         if( target!=v2 ) {
00190           // add a edge v1 -> target
00191           newEdge( v1 , edge );
00192           // remove old incoming edge v2 -> target
00193           edge.theTarget = v2;
00194           // cout << "    Erase  from in N " << target << " : " << edge << endl;
00195           theVertices[target].in.erase( edge );
00196           // cout << "    Insert to   in N " << target << " : " << edge << endl;
00197         } else {
00198           edge.theTarget = v1;
00199           theVertices[v1].in.insert( edge );
00200         }
00201       }
00202       theVertices.erase( v2 );
00203     }
00204 
00206       //                                                     //
00207       //  Internal Functions:                                //
00208       //                                                     //
00210       private:
00211     
00213     int _newVertex( int v , const vertex_type& V ) {
00214       
00215       // add V into the graph
00216       theVertices[v] = V;
00217       
00218       // link new edges incoming to V and leaving V
00219       set< edge_type >  in = V. in;
00220       set< edge_type > out = V.out;
00221       typename set< edge_type >::iterator it;
00222 
00223       // V <- *it
00224       for( it=in.begin( ) ; it!=in.end( ) ; ++it ) {
00225         edge_type edge = *it;
00226         int origin = edge.theTarget;
00227         if( origin!=v ) {
00228           edge.theTarget = v;
00229           theVertices[origin].out.insert( edge );
00230         }
00231       }
00232 
00233       // V -> *it
00234       for( it=out.begin( ) ; it!=out.end( ) ; ++it ) {
00235         edge_type edge = *it;
00236         int target = edge.theTarget;
00237         if( target!=v ) {
00238           edge.theTarget = v;
00239           theVertices[target].in.insert( edge );
00240         }
00241       }
00242     }
00243 
00244     
00246       //                                                     //
00247       //  Data members                                       //
00248       //                                                     //
00250       private:
00251 
00252     // the set of vertices in the graph
00253     map< int, vertex_type > theVertices;
00254     
00256     int maxVertex;
00257     
00258     
00259   };
00260 
00261 
00262   //---------------------------------------------------------------------------//
00263   //---------------------------------- Graph ----------------------------------//
00264   //---------------------------------------------------------------------------//
00265   
00266 
00268   /* Graph concept provides main functions and data structures for directed graph types.
00269      Examples of directed graph types are: directed graph, directed graph with labelled vertices and edges
00270      and different combinations. By definition Graph = (Vertices,Edges). Changing types of template parameters
00271      VertexType and EdgeType will give different types of graphs.
00272    */
00273 
00274   template< class VertexType , class EdgeType > class GraphConcept : public ObjectOf< GraphConceptRep< VertexType , EdgeType > >
00275   {
00276     
00277     
00278   public:
00280     typedef VertexType                               vertex_type;
00282     typedef EdgeType                                 edge_type;
00283     
00284     
00285   private:
00286     typedef GraphConceptRep< VertexType , EdgeType > presentation_type;
00287 
00289       //                                                     //
00290       //  Constructors                                       //
00291       //                                                     //
00293       public:
00294     
00296     GraphConcept( ) : ObjectOf< presentation_type >( new presentation_type( ) ) { }
00297 
00299       //                                                     //
00300       //  Accessors                                          //
00301       //                                                     //
00303       public:
00304 
00305 
00307     const map< int, vertex_type >& getVertices( ) const { return look( )->getVertices( ); }
00308 
00309 
00311     int  newVertex( ) { return change( ) -> newVertex( ); }
00312     
00313     
00315     int  newVertex( const vertex_type& V ) { return change( ) -> newVertex( V ); }
00316 
00317     
00319     void eraseVertex( int v ) { return change( ) -> eraseVertex( v ); }
00320     
00321     
00323     void replaceVertex( int v , const vertex_type& V ) { return change( ) -> replaceVertex( v , V ); }
00324 
00325 
00327     void newEdge( int v1 , const EdgeType& E ) { change( ) -> newEdge( v1 , E ); }
00328 
00329 
00331     void clear( ) { change( ) -> clear( ); }
00332 
00333 
00335     void pinch( int v1 , int v2 ) { change( ) -> pinch( v1 , v2 ); }
00336       
00337   };
00338 
00339 
00341 
00345   template< class VertexType , class EdgeType > 
00346     ostream& operator << ( ostream& os , const GraphConcept< VertexType , EdgeType >& G ) {
00347 
00348     typedef VertexType                               vertex_type;
00349     typedef EdgeType                                 edge_type;
00350     const map< int, vertex_type >& theVertices = G.getVertices( );
00351     typename map< int, vertex_type >::const_iterator v_it = theVertices.begin( );
00352     for( ; v_it!=theVertices.end( ) ; ++v_it ) {
00353 
00354       int v = (*v_it).first;
00355       const vertex_type& V = (*v_it).second;
00356       const set< edge_type >& out = V.out;
00357       os << v << ":";
00358       typename set< edge_type >::const_iterator out_it = out.begin( );
00359       for( ; out_it!=out.end( ) ; ++out_it )
00360         os << *out_it << " ";
00361       os << endl;
00362     }
00363 
00364     return os;
00365   }
00366 
00367 }
00368 
00369 
00370 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

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