00001 #ifndef __ensemble_hpp
00002 #define __ensemble_hpp
00003
00020 #include<cmath>
00021 #include<cassert>
00022
00023 #include"weight.hpp"
00024 #include"graph.hpp"
00025 #include"util.hpp"
00026 #include"iterator.hpp"
00027 #include<cmath>
00028
00029
00030 #ifdef DEBUG_VERBOSE
00031 #include<iostream>
00032 #endif
00033
00034
00035 namespace graphgen{
00036
00043
00044 template<template<class W> class R> struct Ratio;
00045
00050 template<class W, template<class W> class S>
00051 class ensemble_base{
00052 public:
00053 typedef W Weight;
00054 typedef S<W> Shape;
00055 typedef undirected_graph Graph;
00056
00057 private:
00058 RNG rand;
00059 };
00060
00073 template<class W, template<class W> class R>
00074 class canonical
00075 {
00077 typedef canonical<W,R> E;
00078
00080 friend class R<W>;
00082 friend class Ratio<R>;
00083
00084
00085
00091 RNG rand;
00092
00093
00095 Ratio<R> ratio;
00096
00101 R<W> propose;
00102
00104 undirected_graph& graph;
00105
00107 W& weight;
00108
00110 link_type link;
00112 vertex_type target;
00113
00114 #ifdef DEBUG_VERBOSE
00115
00119 void dump( std::ostream& os ){
00120 vertex_type s = graph.source(link);
00121 link_type l = graph.link(target,s);
00122
00123 os <<target<<"["<<graph.degree(target)<<"]";
00124 if(l>-1) os<<" <-("<<l<<")-- "; else os<<", ";
00125 os<<s<<"["<<graph.degree(s)<<"]";
00126 if(link!=l){
00127 os<<" --("<<link<<")-> "
00128 <<graph.target(link)<<"["<<graph.degree(graph.target(link))<<"])";
00129 }
00130 }
00131 #endif
00132
00137 void perform(){
00138 graph.switch_link( link, target );
00139 }
00140
00141 public:
00142
00143 typedef W weight_type;
00144 typedef R<W> restriction_set;
00145
00146 canonical( undirected_graph& g, W& w ): graph(g), weight(w), link(0), target(0)
00147 { weight.resize(2*graph.nl()+1); };
00148
00150 const undirected_graph& get_graph() const { return graph; }
00151 const weight_type& get_weight() const { return weight; }
00152
00154 const W& set_weight( W& w ){ return weight = W(w); }
00155
00159 double update(){
00160 if(propose( *this )){
00161
00162 double rate = ratio( *this );
00163
00164 #ifdef DEBUG_VERBOSE
00165 dump(std::cerr); std::cerr<< " =="<<rate<<"=> ";
00166 #endif
00167
00168 if( rand() < rate){
00169 perform();
00170
00171 #ifdef DEBUG_VERBOSE
00172 dump(std::cerr); std::cerr<<std::endl<<std::flush;
00173 #endif
00174
00175 return rate;
00176 }
00177 }
00178 return 1;
00179 }
00180
00184 void sweep( int n=0 ){
00185 if(n==0) n=graph.nl();
00186 while(n--) update();
00187 }
00188 };
00189
00190
00191
00204 template<class W, template<class W> class R>
00205 class microcanonical
00206 {
00208 typedef microcanonical<W,R> E;
00209
00210 friend class R<W>;
00211 friend class Ratio<R>;
00212
00213
00214
00220 RNG rand;
00221
00222
00224 Ratio<R> ratio;
00225
00229 R<W> propose;
00230
00232 undirected_graph&graph;
00233
00235 W& weight;
00236
00238 link_type link1;
00240 link_type link2;
00241
00242 #ifdef DEBUG_VERBOSE
00243
00247 void dump( std::ostream& os ){
00248 os <<graph.source(link1)<<"["<<graph.degree(graph.source(link1))
00249 <<"]--("<<link1<<")--> "
00250 <<graph.target(link1)<<"["<<graph.degree(graph.target(link1))
00251 << "], "
00252 <<graph.source(link2)<<"["<<graph.degree(graph.source(link2))
00253 <<"]--("<<link2<<")--> "
00254 <<graph.target(link2)<<"["<<graph.degree(graph.target(link2)) <<"]";
00255 }
00256 #endif
00257
00262 void perform(){
00263 graph.cross_links( link1, link2 );
00264 }
00265
00266 public:
00267
00268 microcanonical( undirected_graph& g ): graph(g), weight(uniform_weight) {};
00269 microcanonical( undirected_graph& g , W& w): graph(g), weight(w) { weight.resize(graph.nl()); };
00270
00271
00273 const undirected_graph& get_graph() const { return graph; }
00275 const W& set_weight( const W& w ){ return weight = W(w); }
00276
00280 double update(){
00281 if( propose( *this ) ){
00282 double rate=ratio(*this);
00283
00284 #ifdef DEBUG_VERBOSE
00285 dump(std::cerr); std::cerr<<" =="<<rate<<"=> ";
00286 #endif
00287 if( (rate==1) || (rand() < rate) ){
00288 perform();
00289
00290 #ifdef DEBUG_VERBOSE
00291 dump(std::cerr); std::cerr<<std::endl;
00292 #endif
00293 return rate;
00294 }
00295 }
00296
00297 return 1;
00298 }
00299
00303 void sweep( int n=0 ){
00304 if(n==0) n=graph.nl();
00305 for( int i=0; i<n; i++ ) update();
00306 }
00307 };
00308
00309
00310
00322 template<class W, template<class W> class R>
00323 class grandcanonical
00324 {
00326 typedef grandcanonical<W,R> E;
00327
00328 friend class R<W>;
00329 friend class Ratio<R>;
00330
00331
00332
00338 RNG rand;
00339
00340
00342 Ratio<R> ratio;
00343
00347 R<W> propose;
00348
00350 undirected_graph& graph;
00351
00353 W& weight;
00354
00356 static const double padd = 0.5;
00357
00359 link_type link;
00361 vertex_type v1;
00363 vertex_type v2;
00364
00365 #ifdef DEBUG_VERBOSE
00366
00370 void dump( std::ostream& os ){
00371 if(link>-1){
00372 v1 = graph.source(link);
00373 v2 = graph.target(link);
00374 }
00375
00376 os <<v1<<"["<<graph.degree(v1)<<"]";
00377 if(link>-1) os<<"--("<<link<<")->"; else os<<" , ";
00378 os<<v2<<"["<<v2<<"]";
00379 }
00380 #endif
00381
00382 public:
00383 grandcanonical( const undirected_graph& g, const W& w ): graph(g), weight(w), mu(0.5)
00384 { weight.resize(graph.nl()); };
00385
00387 double mu;
00388
00390 const undirected_graph& get_graph() const { return graph; }
00392 W& set_weight( const W& w ){ return weight = W(w); }
00393
00394
00398 double update(){
00399 if(propose( *this )){
00400
00401 if(link>-1){
00402 double rate = ratio(*this) * exp(mu)*(2*graph.nl())/(pow(graph.nv(),2)) ;
00403
00404 #ifdef DEBUG_VERBOSE
00405 dump(std::cerr); std::cerr<<" =="<<rate<<"=> ";
00406 #endif
00407
00408 if(rand()<rate){
00409 graph.remove_link(link);
00410 return rate;
00411 #ifdef DEBUG_VERBOSE
00412 dump(std::cerr); std::cerr<<std::endl;
00413 #endif
00414 }
00415 }
00416 else {
00417 double prerate = exp(-mu)*pow(graph.nv(),2)*0.5/((graph.nl()+1)) ;
00418 double rate = ratio( *this );
00419
00420 #ifdef DEBUG_VERBOSE
00421 dump(std::cerr); std::cerr<<" ++"<<prerate<<"*"<<rate<<"+> ";
00422 #endif
00423
00424 rate *= prerate;
00425
00426 if( rand() < rate ){
00427 graph.add_link(v1,v2);
00428 #ifdef DEBUG_VERBOSE
00429 dump(std::cerr); std::cerr<<std::endl;
00430 #endif
00431 return rate;
00432 }
00433 }
00434 }
00435 link=-1;
00436 return 1;
00437 }
00438
00442 void sweep( int n=0 ){
00443 if(n==0) n=graph.nl();
00444 for( int i=0; i<n; i++ ) update();
00445 }
00446
00447 };
00448
00449
00467 template<value_type::weight_value_type WV, template<value_type::weight_value_type WV>class W>
00468 double graph_weight( const undirected_graph&graph, const W<WV>& weight);
00469
00471 template<value_type::weight_value_type WV>
00472 double graph_weight( const undirected_graph& graph, const vertex_weight<WV>& weight )
00473 {
00474 if(vertex_weight<WV>::logarithmic){
00475
00476
00477 double product = 0;
00478 for( undirected_graph::isequence vertex(graph); vertex.valid(); ++vertex )
00479 product += weight.weight( graph.degree( *vertex ) );
00480
00481 return product;
00482
00483 } else {
00484
00485
00486 double product = 1;
00487 for( undirected_graph::isequence vertex(graph); vertex.valid(); ++vertex )
00488 product *= weight.weight( graph.degree( *vertex ) );
00489
00490 return product;
00491 }
00492 }
00493
00495 template<value_type::weight_value_type WV>
00496 double graph_weight( const undirected_graph& graph, const link_weight<WV>& weight)
00497 {
00498 if(vertex_weight<WV>::logarithmic){
00499
00500
00501
00502
00503 double product = 0;
00504
00506 for( undirected_graph::ilinks link(graph); link.valid(); ++link )
00507 product += weight.weight( graph.degree( graph.source( *link ) ),
00508 graph.degree( graph.target( *link ) ) );
00509
00510 return product;
00511
00512 } else {
00513
00514
00515
00516 double product = 1;
00517
00519 for( undirected_graph::ilinks link(graph); link.valid(); ++link )
00520 product *= weight.weight( graph.degree( graph.source( *link ) ),
00521 graph.degree( graph.target( *link ) ) );
00522
00523 return product;
00524
00525 }
00526 }
00527
00528
00551 template<template<class W>class R>
00552 class Ratio{
00553
00554
00555
00556
00557
00558
00559
00560
00561
00562
00563
00564
00565
00566
00567
00568
00569
00570
00571 public:
00572
00574 template<value_type::weight_value_type WV>
00575 double operator()( const canonical<vertex_weight<WV>,R>& ensemble )
00576 {
00577 if( ensemble.target == ensemble.graph.target(ensemble.link) ) return 0;
00578
00579 if( vertex_weight<WV>::logarithmic ){
00580
00581 return exp( ensemble.weight.r(ensemble.graph.degree( ensemble.target )) -
00582 ensemble.weight.r(ensemble.graph.degree( ensemble.graph.target(ensemble.link) )-1 ) );
00583
00584 }
00585 else {
00586 return ( ensemble.weight.r(ensemble.graph.degree( ensemble.target )) /
00587 ensemble.weight.r(ensemble.graph.degree( ensemble.graph.target(ensemble.link) )-1 ) );
00588 }
00589 }
00590
00592 template<value_type::weight_value_type WV>
00593 double operator()( const canonical<link_weight<WV>,R>& ensemble )
00594 {
00595
00596 const undirected_graph& g = ensemble.graph;
00597
00598 vertex_type h = g.source(ensemble.link);
00599 vertex_type k = g.target( ensemble.link );
00600 vertex_type l = ensemble.target;
00601
00602 qint qh = g.degree(h);
00603 qint qk = g.degree(k);
00604 qint ql = g.degree(l);
00605
00606
00607 double ratio = 1;
00608
00609
00610 for( undirected_graph::ineighbors nn(g,l); nn.valid(); ++nn )
00611 ratio *= ensemble.weight.r(ql,g.degree(*nn));
00612 for( undirected_graph::ineighbors nn(g,k); nn.valid(); ++nn )
00613 ratio /= ensemble.weight.r(qk-1,g.degree(*nn));
00614
00615
00616
00617 qint mkl = g.no_of_links(k,l);
00618 if(mkl) ratio *= pow(ensemble.weight.r(ql,qk-1) / ensemble.weight.r(ql,qk), mkl);
00619
00620
00621 if( R<link_weight<WV> >::allow_self ){
00622
00623 qint mkk = g.no_of_links(k,k);
00624
00625 if(mkk) ratio *= std::pow( ensemble.weight.r(qk-1,qk) / ensemble.weight.r(qk-1,qk-1), mkk/2.0 );
00626
00627
00628 qint mll = g.no_of_links(l,l);
00629
00630 if(mll) ratio *= std::pow( ensemble.weight.r(ql,ql+1) / ensemble.weight.r(ql,ql), mll/2.0 );
00631 }
00632
00633
00634
00635
00636 if( R<link_weight<WV> >::allow_self && h==k ){
00637 ratio *= (ensemble.weight.p(qh-1,ql+1)/ensemble.weight.p(qh-1,qh-1));
00638 }
00639 else if( R<link_weight<WV> >::allow_self && h==l ) {
00640 ratio *= (ensemble.weight.p(qh+1,qh+1)/ensemble.weight.p(qk-1,qh+1));
00641 }
00642 else
00643 ratio *= (ensemble.weight.p(qh,ql+1)/ensemble.weight.p(qh,qk-1));
00644
00645 return ratio;
00646 }
00647
00649 template<value_type::weight_value_type WV>
00650 double operator()( const grandcanonical<vertex_weight<WV>,R>& ensemble )
00651 {
00652 if( ensemble.link != undirected_graph::null_link ){
00653
00654 qint qk = ensemble.graph.degree( ensemble.graph.source(ensemble.link) );
00655 qint ql = ensemble.graph.degree( ensemble.graph.target(ensemble.link) );
00656
00657 if(link_weight<WV>::logarithmic)
00658 return -ensemble.weight.ratio(qk-1)-ensemble.weight.ratio(ql-1);
00659 else
00660 return 1 / ( ensemble.weight.ratio(qk-1) * ensemble.weight.ratio(ql-1) );
00661 } else {
00662
00663
00664 if(link_weight<WV>::logarithmic)
00665 return ( ensemble.weight.ratio(ensemble.graph.degree(ensemble.v1)) +
00666 ensemble.weight.ratio(ensemble.graph.degree(ensemble.v2)) );
00667 else
00668 return ( ensemble.weight.ratio(ensemble.graph.degree(ensemble.v1)) *
00669 ensemble.weight.ratio(ensemble.graph.degree(ensemble.v2)) );
00670 }
00671 }
00672
00674 template<value_type::weight_value_type WV>
00675 double operator()( const grandcanonical<link_weight<WV>,R>& ensemble )
00676 {
00677 const undirected_graph& g=ensemble.graph;
00678
00679 if(link_weight<WV>::logarithmic){
00680
00681 assert(false);
00682
00683 } else {
00684
00685 if( ensemble.link != undirected_graph::null_link ) {
00686
00687 vertex_type k= ensemble.graph.source(ensemble.link);
00688 vertex_type l= ensemble.graph.target(ensemble.link);
00689
00690 qint qk = ensemble.graph.degree(k);
00691 qint ql = ensemble.graph.degree(l);
00692
00693
00694 if( R<link_weight<WV> >::allow_self && ensemble.v1==ensemble.v2 ){
00695 double ratio = 1/ensemble.weight(qk-1,qk);
00696
00697 for( undirected_graph::ineighbors nn(g,ensemble.v1); nn.valid(); ++nn )
00698 ratio /= ( ensemble.weight.ratio(qk-2,g.degree(*nn)) *
00699 ensemble.weight.ratio(qk-1,g.degree(*nn)) );
00700
00701
00702
00703 return ratio;
00704 }
00705
00706 qint mkl=g.no_of_links( ensemble.v1, ensemble.v2 );
00707
00708 double ratio = 1/ensemble.weight(ql-1,qk-1);
00709
00710
00711 for( undirected_graph::ineighbors nn(g,ensemble.v1); nn.valid(); ++nn )
00712 ratio /= ensemble.weight.ratio(qk-1,g.degree(*nn));
00713 for( undirected_graph::ineighbors nn(g,ensemble.v2); nn.valid(); ++nn )
00714 ratio /= ensemble.weight.ratio(ql-1,g.degree(*nn));
00715
00716
00717 ratio *= pow( (ensemble.weight(qk-1,ql-1)*ensemble.weight(qk,ql)) /
00718 (ensemble.weight(qk-1,ql)*ensemble.weight(ql-1,qk)) ,mkl);
00719
00720
00721 if( R<link_weight<WV> >::allow_self ){
00722 qint mkk = g.no_of_links(ensemble.v1,ensemble.v1);
00723 qint mll = g.no_of_links(ensemble.v2,ensemble.v2);
00724
00725 if( mkk ) ratio *= pow( ensemble.weight.ratio(qk-1,qk) ,mkk/2);
00726 if( mll ) ratio *= pow( ensemble.weight.ratio(ql-1,ql) ,mll/2);
00727 }
00728 return ratio;
00729
00730
00731
00732 } else {
00733 vertex_type k = ensemble.v1;
00734 vertex_type l = ensemble.v2;
00735
00736 qint qk = ensemble.graph.degree(k);
00737 qint ql = ensemble.graph.degree(l);
00738
00739
00740 if(R<link_weight<WV> >::allow_self && ensemble.v1==ensemble.v2){
00741 double ratio = 1;
00742
00744
00745 return ratio;
00746 }
00747
00748 double ratio = ensemble.weight(qk+1,ql+1);
00749
00750 for( undirected_graph::ineighbors nn(g,ensemble.v1); nn.valid(); ++nn )
00751 ratio *= ensemble.weight.ratio(qk+1, g.degree(*nn));
00752 for( undirected_graph::ineighbors nn(g,ensemble.v2); nn.valid(); ++nn )
00753 ratio *= ensemble.weight.ratio(ql+1, g.degree(*nn));
00754
00755
00756 if( R<link_weight<WV> >::allow_self ){
00757 qint mkk = g.no_of_links(ensemble.v1,ensemble.v1);
00758 qint mll = g.no_of_links(ensemble.v2,ensemble.v2);
00759
00760 qint m_kk = g.no_of_links(k,k);
00761 qint m_ll = g.no_of_links(l,l);
00762
00763 if( m_kk ) ratio *= pow( ensemble.weight(qk,qk+1) / ensemble.weight(qk,qk), mkk/2 );
00764 if( m_ll ) ratio *= pow( ensemble.weight(ql,ql+1) / ensemble.weight(ql,ql), mll/2 );
00765 }
00766 return ratio;
00767 }
00768 }
00769 };
00770
00776 template<value_type::weight_value_type WV>
00777 double operator()( const microcanonical<vertex_weight<WV>,R>& )
00778 {
00779 return 1;
00780 }
00781
00783 template<value_type::weight_value_type WV>
00784 double operator()( const microcanonical<link_weight<WV>,R>& ensemble )
00785 {
00786 if( ensemble.graph.same_link(ensemble.link1,ensemble.link2) ) return 0;
00787
00788 qint qk=ensemble.graph.degree(ensemble.graph.source(ensemble.link1));
00789 qint ql=ensemble.graph.degree(ensemble.graph.source(ensemble.link2));
00790 qint qm=ensemble.graph.degree(ensemble.graph.target(ensemble.link1));
00791 qint qn=ensemble.graph.degree(ensemble.graph.target(ensemble.link2));
00792
00793 if(link_weight<WV>::logarithmic){
00794
00795 return ( (ensemble.weight.p(qk,qn)+ensemble.weight.p(ql,qm) ) -
00796 (ensemble.weight.p(qk,qm)+ensemble.weight.p(ql,qn) ) );
00797
00798 } else {
00799
00800 return ( (ensemble.weight.p(qk,qn)*ensemble.weight.p(ql,qm) ) /
00801 (ensemble.weight.p(qk,qm)*ensemble.weight.p(ql,qn) ) );
00802 }
00803 }
00804
00805 };
00806
00831 namespace shape{
00832
00844 template<class W>
00845 struct tree{
00847 static const bool restrict_tree = true;
00849 static const bool restrict_simple = true;
00851 static const bool allow_multi = false;
00853 static const bool allow_self = false;
00854
00856 bool operator()( const undirected_graph& G );
00857
00859 bool operator()( canonical<W, shape::tree>& ensemble )
00860 {
00861 vertex_type vertex;
00862
00863 if(ensemble.graph.nl() == 0) return false;
00864
00865
00866 do vertex = ensemble.rand( ensemble.graph.nv() );
00867 while( ensemble.graph.degree(vertex) > 1 );
00868
00869
00870 ensemble.link = ensemble.graph.out_link(vertex);
00871 ensemble.target = ensemble.rand( ensemble.graph.nv() );
00872
00873
00874 if(ensemble.target == vertex) return false;
00875
00876 if(ensemble.target == ensemble.graph.target(ensemble.link)) return false;
00877
00878 return true;
00879 }
00880
00882 bool operator()( microcanonical<W, shape::tree>& ensemble )
00883 {
00884
00885 vertex_type v1, v2;
00886 do v1 = ensemble.rand( ensemble.graph.nv() );
00887 while( ensemble.graph.degree(v1) > 1 );
00888 ensemble.link1 = ensemble.graph.out_link(v1);
00889
00890 do v2 = ensemble.rand( ensemble.graph.nv() );
00891 while( (ensemble.graph.degree(v2) > 1) && (v1==v2) );
00892 ensemble.link2 = ensemble.graph.out_link(v2);
00893
00894 return true;
00895 }
00896
00898 bool operator()( grandcanonical<W, shape::tree>& ensemble );
00899
00900 typedef tree<W> Type;
00901 };
00902
00903
00909 template<class W>
00910 struct simple{
00912 static const bool restrict_tree = false;
00914 static const bool restrict_simple = true;
00916 static const bool allow_multi = false;
00918 static const bool allow_self = false;
00919
00921 bool operator()( const undirected_graph& G );
00922
00924 bool operator()( canonical<W, shape::simple>& ensemble )
00925 {
00928 if( ensemble.graph.nl() == 0 ) return false;
00929
00930 ensemble.link = ensemble.graph.linkpool(ensemble.rand(2*ensemble.graph.nl()));
00931 ensemble.target = ensemble.rand( ensemble.graph.nv() );
00932
00933
00934 if( ensemble.graph.source(ensemble.link) == ensemble.target ) return false;
00935 if( ensemble.graph.target(ensemble.link) == ensemble.target ) return false;
00936
00937 if( ensemble.graph.are_linked(ensemble.graph.source(ensemble.link), ensemble.target) ) return false;
00938
00939 return true;
00940 }
00941
00943 bool operator()( microcanonical<W, shape::simple>& ensemble )
00944 {
00945 link_type l1 = ensemble.rand(2*ensemble.graph.nl());
00946 link_type l2 = ensemble.rand(2*(ensemble.graph.nl()-2));
00947
00948 if(l2 >= l1) l2+=2;
00949
00950 ensemble.link1 = ensemble.graph.linkpool(l1);
00951 ensemble.link2 = ensemble.graph.linkpool(l2);
00952
00953 if( ( ensemble.graph.target(ensemble.link1) == ensemble.graph.source(ensemble.link2) ) ||
00954 ( ensemble.graph.source(ensemble.link1) == ensemble.graph.target(ensemble.link1) ) )
00955 return false;
00956
00957 return true;
00958 }
00959
00961 bool operator()( grandcanonical<W, shape::simple>& ensemble )
00962 {
00963 if(ensemble.rand() < ensemble.padd){
00964 if(ensemble.graph.nv() < 2) return false;
00965
00966 ensemble.v1 = ensemble.rand( ensemble.graph.nv() );
00967 ensemble.v2 = ensemble.rand( ensemble.graph.nv()-1 );
00968
00969 if(ensemble.v2 >= ensemble.v1) ensemble.v2++;
00970
00971
00972 if(ensemble.graph.are_linked(ensemble.v1, ensemble.v2)) return false;
00973 return true;
00974 }
00975 else{
00976 if(ensemble.graph.nl() == 0) return false;
00977
00978 ensemble.link = ensemble.graph.linkpool(ensemble.rand( ensemble.graph.nl() ));
00979
00980 return true;
00981 }
00982 }
00983
00984
00985 typedef tree<W> Type;
00986 };
00987
00988
00989
00995 template<class W>
00996 struct noselflinks{
00998 static const bool restrict_tree = false;
01000 static const bool restrict_simple = false;
01002 static const bool allow_multi = true;
01004 static const bool allow_self = false;
01005
01007 bool operator()( const undirected_graph& G );
01008
01010 bool operator()( canonical<W, shape::noselflinks>& ensemble )
01011 {
01014 if( ensemble.graph.nl() == 0 ) return false;
01015
01016 ensemble.link = ensemble.graph.linkpool(ensemble.rand(2*ensemble.graph.nl()));
01017 ensemble.target = ensemble.rand(ensemble.graph.nv() );
01018
01019
01020 if(ensemble.graph.source(ensemble.link) == ensemble.target) return false;
01021
01022 if(ensemble.target == ensemble.graph.target(ensemble.link)) return false;
01023
01024 return true;
01025 }
01026
01027
01029 bool operator()( microcanonical<W, shape::noselflinks>& ensemble )
01030 {
01031 int l1 = ensemble.rand( 2*ensemble.graph.nl() );
01032 int l2 = ensemble.rand( 2*(ensemble.graph.nl()-2) );
01033
01034 if(l2 >= l1) l2+=2;
01035
01036 ensemble.link1 = ensemble.graph.linkpool(l1);
01037 ensemble.link2 = ensemble.graph.linkpool(l2);
01038
01039
01040 if( ( ensemble.graph.target(ensemble.link1) == ensemble.graph.source(ensemble.link2) ) ||
01041 ( ensemble.graph.source(ensemble.link1) == ensemble.graph.target(ensemble.link1) ) )
01042 return false;
01043
01044 return true;
01045 }
01046
01048 bool operator()( grandcanonical<W, shape::noselflinks>& ensemble )
01049 {
01050 if(ensemble.rand() < ensemble.padd) {
01051 if(ensemble.graph.nv() < 2) return false;
01052
01053 ensemble.v1 = ensemble.rand( ensemble.graph.nv() );
01054 ensemble.v2 = ensemble.rand( ensemble.graph.nv()-1 );
01055
01056 if(ensemble.v2 >= ensemble.v1) ensemble.v2++;
01057
01058 return true;
01059 }
01060 else {
01061 if( ensemble.graph.nl() == 0 ) return false;
01062
01063 ensemble.link = ensemble.graph.linkpool(ensemble.rand( ensemble.graph.nl() ));
01064
01065 return true;
01066 }
01067 }
01068
01069 };
01070
01071
01072
01077 template<class W>
01078 struct multigraph{
01080 static const bool restrict_tree = false;
01082 static const bool restrict_simple = false;
01084 static const bool allow_multi = true;
01086 static const bool allow_self = true;
01087
01089 bool operator()( const undirected_graph& G );
01090
01092 bool operator()( canonical<W, shape::multigraph>& ensemble )
01093 {
01096 if( ensemble.graph.nl() == 0 ) return false;
01097
01098 ensemble.link = ensemble.graph.linkpool( ensemble.rand( 2*ensemble.graph.nl()) );
01099 ensemble.target = ensemble.rand( ensemble.graph.nv() );
01100
01101
01102 if(ensemble.target == ensemble.graph.target(ensemble.link)) return false;
01103
01104 return true;
01105 }
01106
01108 bool operator()( microcanonical<W, shape::multigraph>& ensemble )
01109 {
01110 if(ensemble.graph.nl() < 2) return false;
01111
01112 int l1 = ensemble.rand( 2*ensemble.graph.nl() );
01113 int l2 = ensemble.rand( 2*(ensemble.graph.nl()-2) );
01114
01115 if(l2 >= l1) l2+=2;
01116
01117 ensemble.link1 = ensemble.graph.linkpool(l1);
01118 ensemble.link2 = ensemble.graph.linkpool(l2);
01119
01120 return true;
01121 }
01122
01124 bool operator()( grandcanonical<W, shape::multigraph>& ensemble )
01125 {
01126 if(ensemble.rand() < ensemble.padd){
01127 if(ensemble.graph.nv() == 0) return false;
01128
01129 ensemble.v1 = ensemble.rand( ensemble.graph.nv() );
01130 ensemble.v2 = ensemble.rand( ensemble.graph.nv() );
01131
01132 return true;
01133 }
01134 else {
01135 if(ensemble.graph.nl() == 0) return false;
01136
01137 ensemble.link = ensemble.graph.linkpool(ensemble.rand( ensemble.graph.nl() ));
01138
01139 return true;
01140 }
01141 }
01142 };
01143
01146 }
01147
01148 }
01149
01150 #endif