00001
00009 #include<istream>
00010 #include<vector>
00011
00012 #include<cassert>
00013
00014 #include"util.hpp"
00015
00016
00017 #ifndef __graph_hpp
00018 #define __graph_hpp
00019
00020
00021 namespace graphgen{
00023
00024
00028 typedef unsigned int vertex_type;
00029
00033 typedef int link_type;
00034
00035
00055 class undirected_graph
00056 {
00057
00058 public:
00059 static const link_type null_link=-1;
00060
00061
00062 class isequence;
00063 class ineighbors;
00064 class ibreadth;
00065 class idepth;
00066 class ilinks;
00067
00069 undirected_graph();
00070
00072 undirected_graph( unsigned int n_v );
00073
00075 undirected_graph( unsigned int n_v, unsigned int n_l );
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00087 qint degree( vertex_type v ) const{ return deg_[v]; }
00088
00089
00097 link_type link( vertex_type v1, vertex_type v2 ) const{
00098 if( degree(v1) > degree(v2) )
00099 return inverse_link( link( v2, v1 ) );
00100
00101 link_type link=null_link;
00102 for( link=out_link(v1) ; ((link!=null_link)&&(target(link)!=v2)) ; link=next_out_link(link) ) ;
00103
00104 return link;
00105 }
00106
00112 bool are_linked( vertex_type v1, vertex_type v2 ) const{
00113 return link( v1,v2 ) != null_link;
00114 }
00115
00120 bool same_link( link_type l1, link_type l2 ) const{
00121 return (l1==l2) || (l1==inverse_link(l2));
00122 }
00123
00131 qint no_of_links( vertex_type v1, vertex_type v2 ) const{
00132 int count=0;
00133 if( degree(v1) > degree(v2) ) return no_of_links(v2,v1);
00134 link_type l = link( v1, v2 );
00135
00136 while( l!=null_link ){
00137 count++;
00138 l=link_to(l,v2);
00139 }
00140 return count;
00141 }
00142
00144 unsigned int nv() const{ return nv_; };
00146 unsigned int n_vertices() const;
00147
00149 unsigned int nl() const{ return nl_; };
00151 unsigned int n_links() const;
00152
00154 link_type linkpool( unsigned int i ) const { return 2*links_[i/2] + (i%2); }
00155
00160 vertex_type add_vertex();
00161
00166 void remove_vertex( vertex_type vertex );
00167
00169 link_type add_link( vertex_type, vertex_type );
00170
00172 void remove_link( link_type l ) {
00173 link_type l_inv = inverse_link(l);
00174
00175 vertex_type t = target(l);
00176 vertex_type s = target(l_inv);
00177
00178 remove_link_from_vertex( s,l );
00179 remove_link_from_vertex( t,l_inv );
00180 nl_--;
00181
00182 links_.put( l/2 );
00183 }
00184
00189 void remove_link( vertex_type v1, vertex_type v2 ){
00190 remove_link( link( v1, v2 ) );
00191 };
00192
00193
00201 void switch_link( link_type link, vertex_type to )
00202 {
00203 link_type l_inv=inverse_link(link);
00204 switch_link( link, l_inv, to );
00205 }
00206
00214 void switch_link( link_type link, link_type link_inverse, vertex_type to )
00215 {
00216 remove_link_from_vertex(target(link), link_inverse);
00217
00218 target_[link] = to;
00219
00220 add_link_to_vertex(to, link_inverse);
00221 }
00222
00227 void cross_links( link_type link1, link_type link2 ){
00228
00229
00230 vertex_type target1 = target(link1);
00231 switch_link( link1, target( link2 ) );
00232 switch_link( link2, target1 );
00233 }
00234
00235
00236
00237
00238
00239
00240
00242 vertex_type target(link_type link) const {
00243 return target_[link];
00244 }
00245
00247 vertex_type source(int link) const {
00248 return target(inverse_link(link));
00249 }
00250
00255 link_type out_link(vertex_type v) const {return l_out_[v];}
00256
00261 link_type next_out_link(link_type l) const {return l_next_[l];}
00262
00263 friend std::istream& operator>>( std::istream&is, undirected_graph& graph);
00268
00272 void clear();
00273
00281 void gen_BarabasiAlbert( qint m, vertex_type N0=2 );
00282
00289 void gen_ErdosRenyi( double p );
00290
00295 void gen_ErdosRenyi_N( unsigned int L );
00296
00305 void gen_DMS( qint m, double alpha );
00306
00311 void gen_CompleteGraph( vertex_type N );
00312
00316 void gen_CompleteGraph();
00317
00323 void gen_InitialLinks( link_type );
00324
00328 void gen_RegularLattice( qint d, int L );
00329
00330 protected:
00331
00332
00333 void resize_link_tables( unsigned int n );
00334 void resize_site_tables( unsigned int n );
00335
00337 link_type link_to( link_type l, vertex_type v ) const{
00338 link_type next = next_out_link(l);
00339 while( (next != null_link)&&(target(next)!=v) ) next = next_out_link(next);
00340 return next;
00341 }
00342
00343
00344 private:
00345 unsigned int nv_;
00346 unsigned int nl_;
00347
00349 std::vector<qint> deg_;
00350
00352 std::vector<vertex_type> target_;
00353
00355 std::vector<link_type> l_out_;
00356
00358 std::vector<link_type> l_next_;
00359
00365 integer_pool<link_type> links_;
00366
00373
00374
00379 link_type inverse_link(link_type link) const {
00380 if(link!=null_link) return link^1;
00381 else return null_link;
00382 }
00383
00390 void add_link_to_vertex( vertex_type v, link_type l )
00391 {
00392 link_type l_out=l_out_[v];
00393 l_out_[v]=l;
00394 l_next_[l]=l_out;
00395 deg_[v]++;
00396 }
00397
00404 void remove_link_from_vertex( vertex_type v, link_type l )
00405 {
00406 link_type l_tmp=out_link(v);
00407 link_type prev=null_link;
00408
00409 while(l_tmp!=l && l_tmp != null_link) {
00410 prev=l_tmp;
00411 l_tmp=next_out_link(l_tmp);
00412
00413 }
00414
00415 assert( l_tmp != null_link );
00416
00417 if(prev==null_link) {
00418 l_out_[v]=l_next_[l];
00419 }
00420 else {
00421 l_next_[prev]=l_next_[l];
00422 }
00423
00424 deg_[v]--;
00425 }
00426
00427
00432 void move_link( link_type link, vertex_type source, vertex_type target ){
00433 remove_link_from_vertex( source, link );
00434 add_link_to_vertex( target, link );
00435 }
00436
00437 public:
00438
00442 std::istream&load_adjacencylist( std::istream& );
00446 std::istream&load_adjacencymatrix( std::istream& );
00450 std::istream&load_linklist( std::istream& );
00451
00452 };
00453
00454 std::istream& operator>>( std::ostream&is, const undirected_graph& graph);
00455
00456
00457
00458 }
00459
00460
00461 #include"inout.hpp"
00462 #include"iterator.hpp"
00463
00464 #endif