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 using namespace std;
00018 
00019 #include "GraphConcept.h"
00020 #include "GraphConceptAlgorithms.h"
00021 using namespace Graphs;
00022 
00023 #include "RanlibCPP.h"
00024 
00025 
00030 //---------------------------------------------------------------------------//
00031 //------------------------------- GraphEdge ---------------------------------//
00032 //---------------------------------------------------------------------------//
00033 
00034 
00036 struct GraphEdge
00037 {
00039   GraphEdge( int t ) : theTarget(t) { }
00040 
00042   GraphEdge( ) : theTarget(-1) { }
00043 
00044 
00045  
00047   GraphEdge inverse( int origin ) { return GraphEdge( origin ); }
00048 
00049 
00051   bool operator < ( const GraphEdge& e ) const { return theTarget< e.theTarget; }
00052 
00053 
00055   bool operator ==( const GraphEdge& e ) const { return theTarget==e.theTarget; }
00056 
00057 
00059   bool operator!= ( const GraphEdge& e ) const { return theTarget!=e.theTarget; }
00060 
00061   
00063   int theTarget;
00064 };
00065 
00066 ostream& operator << ( ostream& os , const GraphEdge& e );
00067 
00068 
00069 //---------------------------------------------------------------------------//
00070 //------------------------------- GraphVertex -------------------------------//
00071 //---------------------------------------------------------------------------//
00072 
00073 
00075 template< class EdgeType >
00076 struct GraphVertex
00077 {
00079   typedef EdgeType edge_type;
00080   
00081   
00083   GraphVertex( ) { }
00084 
00085   
00087   set< edge_type > in;
00088 
00089   
00091   set< edge_type > out;
00092 };
00093 
00094 
00095 //---------------------------------------------------------------------------//
00096 //----------------------------- IntLabeledEdge ------------------------------//
00097 //---------------------------------------------------------------------------//
00098 
00099 
00101 struct IntLabeledEdge : public GraphEdge
00102 {
00104   IntLabeledEdge( int target , int label ) : GraphEdge(target), theLabel( label ) { }
00105 
00107   IntLabeledEdge( ) : GraphEdge(-1), theLabel( 0 ) { }
00108   
00109   
00111   IntLabeledEdge inverse( int origin ) { return IntLabeledEdge( origin , -theLabel ); }
00112   
00114   bool operator < ( const IntLabeledEdge& e ) const { 
00115     if( theLabel!=e.theLabel )
00116       return theLabel<e.theLabel;
00117     return theTarget<e.theTarget; 
00118   }
00119   
00120   
00122   bool operator ==( const IntLabeledEdge& e ) const { return this->GraphEdge::operator==( e ) && theLabel==e.theLabel; }
00123 
00124 
00126   bool operator!= ( const IntLabeledEdge& e ) const { return this->GraphEdge::operator!=( e ) || theLabel!=e.theLabel; }
00127 
00128 
00130   int theLabel;
00131 };
00132 
00133 
00135 ostream& operator << ( ostream& os , const IntLabeledEdge& e );
00136 
00137 
00139 void prepareToFold( const IntLabeledEdge& e1 , const IntLabeledEdge& e2 );
00140 
00141 
00142 //---------------------------------------------------------------------------//
00143 //----------------------------- IntLabeledEdge ------------------------------//
00144 //---------------------------------------------------------------------------//
00145 
00146 
00147 
00149 typedef GraphConcept< GraphVertex< GraphEdge > , GraphEdge > Graph;
00150 
00151 
00152 
00154 typedef GraphConcept< GraphVertex< IntLabeledEdge > , IntLabeledEdge > IntLabeledGraph;
00155 
00156 
00157 
00158 
00159 //---------------------------------------------------------------------------//
00160 //---------------------------- Specific functions ---------------------------//
00161 //---------------------------------------------------------------------------//
00162 
00163 
00165 template< class ConstIntIterator >
00166 void addRay( IntLabeledGraph& G , int v , ConstIntIterator B , ConstIntIterator E , bool direct=false )
00167 {
00168   int cur_v = v;
00169   for( ; B!=E ; ) {
00170     int l = *(B++);
00171     int new_v = G.newVertex( IntLabeledGraph::vertex_type( ) );
00172     G.newEdge( cur_v , IntLabeledGraph::edge_type( new_v ,  l ) );
00173     if( !direct )
00174       G.newEdge( new_v , IntLabeledGraph::edge_type( cur_v , -l ) );
00175     cur_v = new_v;
00176   }
00177 }
00178 
00179 
00181 template< class ConstIntIterator >
00182 void addLoop( IntLabeledGraph& G , int v , ConstIntIterator B , ConstIntIterator E , bool direct=false )
00183 {
00184   int cur_v = v;
00185   for( ; B!=E ; ) {
00186     int l = *(B++);
00187     if( B!=E ) {
00188       int new_v = G.newVertex( IntLabeledGraph::vertex_type( ) );
00189       G.newEdge( cur_v , IntLabeledGraph::edge_type( new_v ,  l ) );
00190       if( !direct )
00191         G.newEdge( new_v , IntLabeledGraph::edge_type( cur_v , -l ) );
00192       cur_v = new_v;
00193     } else {
00194       G.newEdge( cur_v , IntLabeledGraph::edge_type( v ,  l ) );
00195       if( !direct )
00196         G.newEdge( v , IntLabeledGraph::edge_type( cur_v , -l ) );
00197     }
00198   }
00199 }
00200 
00201 
00203 Graph randomGraph( int N , float edge_param );
00204 
00205 
00207 vector< vector< int > > lengthTable( const Graph& G );
00208 
00209 
00211 vector< vector< int > > innerProductTable( const Graph& G , int origin );
00212 
00213 
00215 float getHyperbolicityConst( const Graph& G );
00216 
00217 
00218 #endif
00219 
00220 

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