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