1 /* This file is part of libDAI - http://www.libdai.org/
2 *
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]
9 */
12 #include <algorithm>
13 #include <dai/weightedgraph.h>
14 #include <dai/util.h>
15 #include <dai/exceptions.h>
18 namespace dai {
21 using namespace std;
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;
32 // Nodes in the tree
33 set<size_t> treeV;
36 treeV.insert( Root );
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 DAI_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 }
59 return result;
60 }
61 }
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).
73 DAI_ASSERT( (N * d) % 2 == 0 );
76 UEdgeVec G;
78 size_t tries = 0;
80 tries++;
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 );
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 }
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.
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 }