src/weightedgraph.cpp

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