Fixed regression in scripts/regenerate-properties
[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 RootedTree::RootedTree( const Graph &T, size_t Root ) {
25 if( T.size() != 0 ) {
26 // Make a copy
27 Graph Gr = T;
28
29 // Nodes in the tree
30 set<size_t> nodes;
31
32 // Start with the root
33 nodes.insert( Root );
34
35 // Keep adding edges until done
36 while( !(Gr.empty()) )
37 for( Graph::iterator e = Gr.begin(); e != Gr.end(); ) {
38 bool e1_in_nodes = nodes.count( e->n1 );
39 bool e2_in_nodes = nodes.count( e->n2 );
40 DAI_ASSERT( !(e1_in_nodes && e2_in_nodes) );
41 if( e1_in_nodes ) {
42 // Add directed edge, pointing away from the root
43 push_back( DEdge( e->n1, e->n2 ) );
44 nodes.insert( e->n2 );
45 // Erase the edge
46 Gr.erase( e++ );
47 } else if( e2_in_nodes ) {
48 // Add directed edge, pointing away from the root
49 push_back( DEdge( e->n2, e->n1 ) );
50 nodes.insert( e->n1 );
51 // Erase the edge
52 Gr.erase( e++ );
53 } else
54 e++;
55 }
56
57 }
58 }
59
60
61 Graph RandomDRegularGraph( size_t N, size_t d ) {
62 DAI_ASSERT( (N * d) % 2 == 0 );
63
64 bool ready = false;
65 std::vector<UEdge> G;
66
67 size_t tries = 0;
68 while( !ready ) {
69 tries++;
70
71 // Start with N*d points {0,1,...,N*d-1} (N*d even) in N groups.
72 // Put U = {0,1,...,N*d-1}. (U denotes the set of unpaired points.)
73 vector<size_t> U;
74 U.reserve( N * d );
75 for( size_t i = 0; i < N * d; i++ )
76 U.push_back( i );
77
78 // Repeat the following until no suitable pair can be found: Choose
79 // two random points i and j in U, and if they are suitable, pair
80 // i with j and delete i and j from U.
81 G.clear();
82 bool finished = false;
83 while( !finished ) {
84 random_shuffle( U.begin(), U.end() );
85 size_t i1, i2;
86 bool suit_pair_found = false;
87 for( i1 = 0; i1 < U.size()-1 && !suit_pair_found; i1++ )
88 for( i2 = i1+1; i2 < U.size() && !suit_pair_found; i2++ )
89 if( (U[i1] / d) != (U[i2] / d) ) {
90 // they are suitable
91 suit_pair_found = true;
92 G.push_back( UEdge( U[i1] / d, U[i2] / d ) );
93 U.erase( U.begin() + i2 ); // first remove largest
94 U.erase( U.begin() + i1 ); // remove smallest
95 }
96 if( !suit_pair_found || U.empty() )
97 finished = true;
98 }
99
100 if( U.empty() ) {
101 // G is a graph with edge from vertex r to vertex s if and only if
102 // there is a pair containing points in the r'th and s'th groups.
103 // If G is d-regular, output, otherwise return to Step 1.
104
105 vector<size_t> degrees;
106 degrees.resize( N, 0 );
107 foreach( const UEdge &e, G ) {
108 degrees[e.n1]++;
109 degrees[e.n2]++;
110 }
111 ready = true;
112 for( size_t n = 0; n < N; n++ )
113 if( degrees[n] != d ) {
114 ready = false;
115 break;
116 }
117 } else
118 ready = false;
119 }
120
121 return Graph( G.begin(), G.end() );
122 }
123
124
125 } // end of namespace dai