Updated copyrights
[libdai.git] / include / dai / clustergraph.h
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 #ifndef __defined_libdai_clustergraph_h
24 #define __defined_libdai_clustergraph_h
25
26
27 #include <set>
28 #include <vector>
29 #include <dai/varset.h>
30 #include <dai/bipgraph.h>
31
32
33 namespace dai {
34
35
36 /// A ClusterGraph is a hypergraph with VarSets as nodes.
37 /// It is implemented as bipartite graph with variable nodes
38 /// and cluster (VarSet) nodes. The additional
39 /// functionality compared to a simple set<VarSet> is
40 /// finding maximal clusters, finding cliques, etc...
41 class ClusterGraph {
42 public:
43 BipartiteGraph G;
44 std::vector<Var> vars;
45 std::vector<VarSet> clusters;
46
47 typedef BipartiteGraph::Neighbor Neighbor;
48 typedef BipartiteGraph::Edge Edge;
49
50 public:
51 /// Default constructor
52 ClusterGraph() : G(), vars(), clusters() {}
53
54 /// Construct from vector<VarSet>
55 ClusterGraph( const std::vector<VarSet> & cls );
56
57 /// Copy constructor
58 ClusterGraph( const ClusterGraph &x ) : G(x.G), vars(x.vars), clusters(x.clusters) {}
59
60 /// Assignment operator
61 ClusterGraph& operator=( const ClusterGraph &x ) {
62 if( this != &x ) {
63 G = x.G;
64 vars = x.vars;
65 clusters = x.clusters;
66 }
67 return *this;
68 }
69
70 /// Returns true if cluster I is not contained in a larger cluster
71 bool isMaximal( size_t I ) const {
72 #ifdef DAI_DEBUG
73 assert( I < G.nr2() );
74 #endif
75 const VarSet & clI = clusters[I];
76 bool maximal = true;
77 // The following may not be optimal, since it may repeatedly test the same cluster *J
78 foreach( const Neighbor &i, G.nb2(I) ) {
79 foreach( const Neighbor &J, G.nb1(i) )
80 if( (J != I) && (clI << clusters[J]) ) {
81 maximal = false;
82 break;
83 }
84 if( !maximal )
85 break;
86 }
87 return maximal;
88 }
89
90 /// Erase all VarSets that are not maximal
91 ClusterGraph& eraseNonMaximal() {
92 for( size_t I = 0; I < G.nr2(); ) {
93 if( !isMaximal(I) ) {
94 clusters.erase( clusters.begin() + I );
95 G.erase2(I);
96 } else
97 I++;
98 }
99 return *this;
100 }
101
102 /// Return number of clusters
103 size_t size() const {
104 return G.nr2();
105 }
106
107 /// Return index of variable n
108 size_t findVar( const Var &n ) const {
109 return find( vars.begin(), vars.end(), n ) - vars.begin();
110 }
111
112 /// Returns true if vars with indices i1 and i2 are adjacent, i.e., both contained in the same cluster
113 bool adj( size_t i1, size_t i2 ) {
114 bool result = false;
115 foreach( const Neighbor &I, G.nb1(i1) )
116 if( find( G.nb2(I).begin(), G.nb2(I).end(), i2 ) != G.nb2(I).end() ) {
117 result = true;
118 break;
119 }
120 return result;
121 }
122
123 /// Returns union of clusters that contain the variable with index i
124 VarSet Delta( size_t i ) const {
125 VarSet result;
126 foreach( const Neighbor &I, G.nb1(i) )
127 result |= clusters[I];
128 return result;
129 }
130
131 /// Inserts a cluster (if it does not already exist)
132 void insert( const VarSet &cl ) {
133 if( find( clusters.begin(), clusters.end(), cl ) == clusters.end() ) {
134 clusters.push_back( cl );
135 // add variables (if necessary) and calculate neighborhood of new cluster
136 std::vector<size_t> nbs;
137 for( VarSet::const_iterator n = cl.begin(); n != cl.end(); n++ ) {
138 size_t iter = find( vars.begin(), vars.end(), *n ) - vars.begin();
139 nbs.push_back( iter );
140 if( iter == vars.size() ) {
141 G.add1();
142 vars.push_back( *n );
143 }
144 }
145 G.add2( nbs.begin(), nbs.end(), nbs.size() );
146 }
147 }
148
149 /// Returns union of clusters that contain variable with index i, minus this variable
150 VarSet delta( size_t i ) const {
151 return Delta( i ) / vars[i];
152 }
153
154 /// Erases all clusters that contain n where n is the variable with index i
155 ClusterGraph& eraseSubsuming( size_t i ) {
156 while( G.nb1(i).size() ) {
157 clusters.erase( clusters.begin() + G.nb1(i)[0] );
158 G.erase2( G.nb1(i)[0] );
159 }
160 return *this;
161 }
162
163 /// Provide read access to clusters
164 const std::vector<VarSet> & toVector() const { return clusters; }
165
166 /// Calculate cost of eliminating the variable with index i,
167 /// using as a measure "number of added edges in the adjacency graph"
168 /// where the adjacency graph has the variables as its nodes and
169 /// connects nodes i1 and i2 iff i1 and i2 occur in some common cluster
170 size_t eliminationCost( size_t i ) {
171 std::vector<size_t> id_n = G.delta1( i );
172
173 size_t cost = 0;
174
175 // for each unordered pair {i1,i2} adjacent to n
176 for( size_t _i1 = 0; _i1 < id_n.size(); _i1++ )
177 for( size_t _i2 = _i1 + 1; _i2 < id_n.size(); _i2++ ) {
178 // if i1 and i2 are not adjacent, eliminating n would make them adjacent
179 if( !adj(id_n[_i1], id_n[_i2]) )
180 cost++;
181 }
182
183 return cost;
184 }
185
186 /// Perform Variable Elimination without Probs, i.e. only keeping track of
187 /// the interactions that are created along the way.
188 /// Input: a set of outer clusters and an elimination sequence
189 /// Output: a set of elimination "cliques"
190 ClusterGraph VarElim( const std::vector<Var> &ElimSeq ) const;
191
192 /// Perform Variable Eliminiation using the MinFill heuristic
193 ClusterGraph VarElim_MinFill() const;
194
195 /// Send to output stream
196 friend std::ostream & operator << ( std::ostream & os, const ClusterGraph & cl ) {
197 os << cl.toVector();
198 return os;
199 }
200 };
201
202
203 } // end of namespace dai
204
205
206 #endif