GraphType.h

Go to the documentation of this file.
00001 // Copyright (C) 2005 Alexander Ushakov
00002 // Contents: Definition of the GraphVertex and GraphEdge
00003 //
00004 // Principal Authors: Alexander Ushakov
00005 //
00006 // Revision History:
00007 //
00008 
00009 
00010 #ifndef _GraphType_H_
00011 #define _GraphType_H_
00012 
00013 
00014 #include "set"
00015 #include "vector"
00016 #include "iostream"
00017 #include "string"
00018 using namespace std;
00019 
00020 #include "GraphConcept.h"
00021 #include "GraphConceptAlgorithms.h"
00022 #include "GraphDrawingAttributes.h"
00023 using namespace Graphs;
00024 
00025 #include "RanlibCPP.h"
00026 
00027 
00032 //---------------------------------------------------------------------------//
00033 //------------------------------- GraphEdge ---------------------------------//
00034 //---------------------------------------------------------------------------//
00035 
00036 
00038 struct GraphEdge
00039 {
00041   GraphEdge( int t ) : theTarget(t) { }
00042 
00044   GraphEdge( ) : theTarget(-1) { }
00045 
00046 
00047  
00049   GraphEdge inverse( int origin ) { return GraphEdge( origin ); }
00050 
00051 
00053   bool operator < ( const GraphEdge& e ) const { return theTarget< e.theTarget; }
00054 
00055 
00057   bool operator ==( const GraphEdge& e ) const { return theTarget==e.theTarget; }
00058 
00059 
00061   bool operator!= ( const GraphEdge& e ) const { return theTarget!=e.theTarget; }
00062 
00063   
00065   int theTarget;
00066 };
00067 
00068 ostream& operator << ( ostream& os , const GraphEdge& e );
00069 
00070 
00071 //---------------------------------------------------------------------------//
00072 //------------------------------- GraphVertex -------------------------------//
00073 //---------------------------------------------------------------------------//
00074 
00075 
00077 template< class EdgeType >
00078 struct GraphVertex
00079 {
00081   typedef EdgeType edge_type;
00082   
00083   
00085   GraphVertex( ) { }
00086 
00087   
00089   set< edge_type > in;
00090 
00091   
00093   set< edge_type > out;
00094 };
00095 
00096 
00097 //---------------------------------------------------------------------------//
00098 //----------------------------- IntLabeledEdge ------------------------------//
00099 //---------------------------------------------------------------------------//
00100 
00101 
00103 struct IntLabeledEdge : virtual public GraphEdge
00104 {
00106   IntLabeledEdge( int target , int label ) : GraphEdge(target), theLabel( label ) { }
00107 
00109   IntLabeledEdge( ) : GraphEdge(-1), theLabel( 0 ) { }
00110   
00111   
00113   IntLabeledEdge inverse( int origin ) { return IntLabeledEdge( origin , -theLabel ); }
00114   
00116   bool operator < ( const IntLabeledEdge& e ) const { 
00117     if( theLabel!=e.theLabel )
00118       return theLabel<e.theLabel;
00119     return theTarget<e.theTarget; 
00120   }
00121   
00122   
00124   bool operator ==( const IntLabeledEdge& e ) const { return this->GraphEdge::operator==( e ) && theLabel==e.theLabel; }
00125 
00126 
00128   bool operator!= ( const IntLabeledEdge& e ) const { return this->GraphEdge::operator!=( e ) || theLabel!=e.theLabel; }
00129 
00130 
00132   int theLabel;
00133 };
00134 
00135 
00137 ostream& operator << ( ostream& os , const IntLabeledEdge& e );
00138 
00139 
00141 void prepareToFold( const IntLabeledEdge& e1 , const IntLabeledEdge& e2 );
00142 
00143 
00144 //---------------------------------------------------------------------------//
00145 //----------------------------- PlanarGraphEdge -----------------------------//
00146 //---------------------------------------------------------------------------//
00147 
00148 
00150 struct PlanarGraphEdge : virtual public GraphEdge
00151 {
00152   
00154   PlanarGraphEdge( int target , int cell1=-1 , int cell2=-1 ) : GraphEdge(target), theCell1( cell1 ), theCell2( cell2 ) { }
00155   
00156   
00158   PlanarGraphEdge( ) : GraphEdge(-1), theCell1( -1 ), theCell2( -1 ) { }
00159   
00160   
00162   PlanarGraphEdge inverse( int origin ) { return PlanarGraphEdge( origin , theCell2 , theCell1 ); }
00163   
00164   
00166   bool operator < ( const PlanarGraphEdge& e ) const { 
00167     if( theCell1!=e.theCell1 )
00168       return theCell1<e.theCell1;
00169     if( theCell2!=e.theCell2 )
00170       return theCell2<e.theCell2;
00171     return theTarget<e.theTarget;
00172   }
00173   
00174   
00176   bool operator ==( const PlanarGraphEdge& e ) const { return theTarget==e.theTarget && theCell1==e.theCell1 && theCell2==e.theCell2; }
00177   
00178   
00180   bool operator!= ( const PlanarGraphEdge& e ) const { return theTarget!=e.theTarget || theCell1!=e.theCell1 || theCell2!=e.theCell2; }
00181   
00182   
00184   int theCell1;
00185   
00186   
00188   int theCell2;
00189 };
00190 
00191 
00192 //---------------------------------------------------------------------------//
00193 //------------------------ PlanarGraphIntLabelledEdge -----------------------//
00194 //---------------------------------------------------------------------------//
00195 
00196 
00198 struct PlanarGraphIntLabelledEdge : public PlanarGraphEdge, public IntLabeledEdge
00199 {
00200   
00202   PlanarGraphIntLabelledEdge( int target , int label , int cell1=-1 , int cell2=-1 ) : PlanarGraphEdge(target,cell1,cell2), IntLabeledEdge(target,label) { }
00203   
00204   
00206   PlanarGraphIntLabelledEdge( ) { }
00207   
00208   
00210   PlanarGraphIntLabelledEdge inverse( int origin ) { return PlanarGraphIntLabelledEdge( origin , -theLabel , theCell2 , theCell1 ); }
00211   
00212   
00214   bool operator < ( const PlanarGraphIntLabelledEdge& e ) const { 
00215     if( theLabel!=e.theLabel )
00216       return theLabel<e.theLabel;
00217     if( theCell1!=e.theCell1 )
00218       return theCell1<e.theCell1;
00219     if( theCell2!=e.theCell2 )
00220       return theCell2<e.theCell2;
00221     return theTarget<e.theTarget;
00222   }
00223   
00224   
00226   bool operator ==( const PlanarGraphIntLabelledEdge& e ) const { return theLabel==e.theLabel && theTarget==e.theTarget && theCell1==e.theCell1 && theCell2==e.theCell2; }
00227   
00228   
00230   bool operator!= ( const PlanarGraphIntLabelledEdge& e ) const { return theLabel!=e.theLabel || theTarget!=e.theTarget || theCell1!=e.theCell1 || theCell2!=e.theCell2; }
00231 };
00232 
00233 
00234 //---------------------------------------------------------------------------//
00235 //----------------------------- IntLabeledEdge ------------------------------//
00236 //---------------------------------------------------------------------------//
00237 
00238 
00239 
00241 typedef GraphConcept< GraphVertex< GraphEdge > , GraphEdge > Graph;
00242 
00243 
00244 
00246 typedef GraphConcept< GraphVertex< IntLabeledEdge > , IntLabeledEdge > IntLabeledGraph;
00247 
00248 
00249 
00250 
00251 //---------------------------------------------------------------------------//
00252 //---------------------------- Specific functions ---------------------------//
00253 //---------------------------------------------------------------------------//
00254 
00255 
00257 template< class ConstIntIterator >
00258 int addRay( IntLabeledGraph& G , int v , ConstIntIterator B , ConstIntIterator E , bool direct=false )
00259 {
00260   int cur_v = v;
00261   for( ; B!=E ; ) {
00262     int l = *(B++);
00263     int new_v = G.newVertex( IntLabeledGraph::vertex_type( ) );
00264     G.newEdge( cur_v , IntLabeledGraph::edge_type( new_v ,  l ) );
00265     if( !direct )
00266       G.newEdge( new_v , IntLabeledGraph::edge_type( cur_v , -l ) );
00267     cur_v = new_v;
00268   }
00269   return cur_v;
00270 }
00271 
00272 
00274 template< class ConstIntIterator >
00275 void addLoop( IntLabeledGraph& G , int v , ConstIntIterator B , ConstIntIterator E , bool direct=false )
00276 {
00277   int cur_v = v;
00278   for( ; B!=E ; ) {
00279     int l = *(B++);
00280     if( B!=E ) {
00281       int new_v = G.newVertex( IntLabeledGraph::vertex_type( ) );
00282       G.newEdge( cur_v , IntLabeledGraph::edge_type( new_v ,  l ) );
00283       if( !direct )
00284         G.newEdge( new_v , IntLabeledGraph::edge_type( cur_v , -l ) );
00285       cur_v = new_v;
00286     } else {
00287       G.newEdge( cur_v , IntLabeledGraph::edge_type( v ,  l ) );
00288       if( !direct )
00289         G.newEdge( v , IntLabeledGraph::edge_type( cur_v , -l ) );
00290     }
00291   }
00292 }
00293 
00294 
00296 Graph randomGraph( int N , float edge_param );
00297 
00298 
00300 vector< vector< int > > lengthTable( const Graph& G );
00301 
00302 
00304 vector< vector< int > > innerProductTable( const Graph& G , int origin );
00305 
00306 
00308 float getHyperbolicityConst( const Graph& G );
00309 
00310 
00312 string graphviz_format( const Graph& G , const GraphDrawingAttributes& GDA = GraphDrawingAttributes( ) );
00313 
00314 
00316 string graphviz_format( const IntLabeledGraph& G , const GraphDrawingAttributes& GDA = GraphDrawingAttributes( ) );
00317 
00318 
00319 #endif
00320 
00321 
 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