94bb8c1f3a85893e4c8a66e2b56dd54b5fae2113
[libdai.git] / 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 <dai/weightedgraph.h>
14 #include <dai/util.h>
15 #include <dai/exceptions.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 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 }
58
59 return result;
60 }
61 }
62
63
64 UEdgeVec RandomDRegularGraph( size_t N, size_t d ) {
65 DAI_ASSERT( (N * d) % 2 == 0 );
66
67 bool ready = false;
68 UEdgeVec G;
69
70 size_t tries = 0;
71 while( !ready ) {
72 tries++;
73
74 // Start with N*d points {0,1,...,N*d-1} (N*d even) in N groups.
75 // Put U = {0,1,...,N*d-1}. (U denotes the set of unpaired points.)
76 vector<size_t> U;
77 U.reserve( N * d );
78 for( size_t i = 0; i < N * d; i++ )
79 U.push_back( i );
80
81 // Repeat the following until no suitable pair can be found: Choose
82 // two random points i and j in U, and if they are suitable, pair
83 // i with j and delete i and j from U.
84 G.clear();
85 bool finished = false;
86 while( !finished ) {
87 random_shuffle( U.begin(), U.end() );
88 size_t i1, i2;
89 bool suit_pair_found = false;
90 for( i1 = 0; i1 < U.size()-1 && !suit_pair_found; i1++ )
91 for( i2 = i1+1; i2 < U.size() && !suit_pair_found; i2++ )
92 if( (U[i1] / d) != (U[i2] / d) ) {
93 // they are suitable
94 suit_pair_found = true;
95 G.push_back( UEdge( U[i1] / d, U[i2] / d ) );
96 U.erase( U.begin() + i2 ); // first remove largest
97 U.erase( U.begin() + i1 ); // remove smallest
98 }
99 if( !suit_pair_found || U.empty() )
100 finished = true;
101 }
102
103 if( U.empty() ) {
104 // G is a graph with edge from vertex r to vertex s if and only if
105 // there is a pair containing points in the r'th and s'th groups.
106 // If G is d-regular, output, otherwise return to Step 1.
107
108 vector<size_t> degrees;
109 degrees.resize( N, 0 );
110 for( UEdgeVec::const_iterator e = G.begin(); e != G.end(); e++ ) {
111 degrees[e->n1]++;
112 degrees[e->n2]++;
113 }
114 ready = true;
115 for( size_t n = 0; n < N; n++ )
116 if( degrees[n] != d ) {
117 ready = false;
118 break;
119 }
120 } else
121 ready = false;
122 }
123
124 return G;
125 }
126
127
128 } // end of namespace dai