src/weightedgraph.cpp

   1 /*  This file is part of libDAI - http://www.libdai.org/
   2  *
   3  *  libDAI is licensed under the terms of the GNU General Public License version
   4  *  2, or (at your option) any later version. libDAI is distributed without any
   5  *  warranty. See the file COPYING for more details.
   6  *
   7  *  Copyright (C) 2006-2009  Joris Mooij  [joris dot mooij at libdai dot org]
   8  *  Copyright (C) 2006-2007  Radboud University Nijmegen, The Netherlands
   9  */
  10
  11
  12 #include <algorithm>
  13 #include <cassert>
  14 #include <dai/weightedgraph.h>
  15 #include <dai/util.h>
  16
  17
  18 namespace dai {
  19
  20
  21 using namespace std;
  22
  23
  24 DEdgeVec GrowRootedTree( const Graph & T, size_t Root ) {
  25     DEdgeVec result;
  26     if( T.size() == 0 )
  27         return result;
  28     else {
  29         // Make a copy
  30         Graph Gr = T;
  31
  32         // Nodes in the tree
  33         set<size_t> treeV;
  34
  35         // Start with the root
  36         treeV.insert( Root );
  37
  38         // Keep adding edges until done
  39         while( !(Gr.empty()) )
  40             for( Graph::iterator e = Gr.begin(); e != Gr.end(); ) {
  41                 bool e1_in_treeV = treeV.count( e->n1 );
  42                 bool e2_in_treeV = treeV.count( e->n2 );
  43                 assert( !(e1_in_treeV && e2_in_treeV) );
  44                 if( e1_in_treeV ) {
  45                     // Add directed edge, pointing away from the root
  46                     result.push_back( DEdge( e->n1, e->n2 ) );
  47                     treeV.insert( e->n2 );
  48                     // Erase the edge
  49                     Gr.erase( e++ );
  50                 } else if( e2_in_treeV ) {
  51                     result.push_back( DEdge( e->n2, e->n1 ) );
  52                     treeV.insert( e->n1 );
  53                     // Erase the edge
  54                     Gr.erase( e++ );
  55                 } else
  56                     e++;
  57             }
  58
  59         return result;
  60     }
  61 }
  62
  63
  64 UEdgeVec RandomDRegularGraph( size_t N, size_t d ) {
  65     // Algorithm 1 in "Generating random regular graphs quickly"
  66     // by A. Steger and N.C. Wormald
  67     //
  68     // Draws a random graph with size N and uniform degree d
  69     // from an almost uniform probability distribution over these graphs
  70     // (which becomes uniform in the limit that d is small and N goes
  71     // to infinity).
  72
  73     assert( (N * d) % 2 == 0 );
  74
  75     bool ready = false;
  76     UEdgeVec G;
  77
  78     size_t tries = 0;
  79     while( !ready ) {
  80         tries++;
  81
  82         // Start with N*d points {0,1,...,N*d-1} (N*d even) in N groups.
  83         // Put U = {0,1,...,N*d-1}. (U denotes the set of unpaired points.)
  84         vector<size_t> U;
  85         U.reserve( N * d );
  86         for( size_t i = 0; i < N * d; i++ )
  87             U.push_back( i );
  88
  89         // Repeat the following until no suitable pair can be found: Choose
  90         // two random points i and j in U, and if they are suitable, pair
  91         // i with j and delete i and j from U.
  92         G.clear();
  93         bool finished = false;
  94         while( !finished ) {
  95             random_shuffle( U.begin(), U.end() );
  96             size_t i1, i2;
  97             bool suit_pair_found = false;
  98             for( i1 = 0; i1 < U.size()-1 && !suit_pair_found; i1++ )
  99                 for( i2 = i1+1; i2 < U.size() && !suit_pair_found; i2++ )
 100                     if( (U[i1] / d) != (U[i2] / d) ) {
 101                         // they are suitable
 102                         suit_pair_found = true;
 103                         G.push_back( UEdge( U[i1] / d, U[i2] / d ) );
 104                         U.erase( U.begin() + i2 );  // first remove largest
 105                         U.erase( U.begin() + i1 );  // remove smallest
 106                     }
 107             if( !suit_pair_found || U.empty() )
 108                 finished = true;
 109         }
 110
 111         if( U.empty() ) {
 112             // G is a graph with edge from vertex r to vertex s if and only if
 113             // there is a pair containing points in the r'th and s'th groups.
 114             // If G is d-regular, output, otherwise return to Step 1.
 115
 116             vector<size_t> degrees;
 117             degrees.resize( N, 0 );
 118             for( UEdgeVec::const_iterator e = G.begin(); e != G.end(); e++ ) {
 119                 degrees[e->n1]++;
 120                 degrees[e->n2]++;
 121             }
 122             ready = true;
 123             for( size_t n = 0; n < N; n++ )
 124                 if( degrees[n] != d ) {
 125                     ready = false;
 126                     break;
 127                 }
 128         } else
 129             ready = false;
 130     }
 131
 132     return G;
 133 }
 134
 135
 136 } // end of namespace dai