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