00001
00002
00003
00004
00005
00006
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
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
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
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
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
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