Adopted contributions by Christian.
[libdai.git] / clustergraph.h
1 /* Copyright (C) 2006-2008 Joris Mooij [j dot mooij at science dot ru dot nl]
2 Radboud University Nijmegen, The Netherlands
3
4 This file is part of libDAI.
5
6 libDAI is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 libDAI is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with libDAI; if not, write to the Free Software
18 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21
22 #ifndef __CLUSTERGRAPH_H__
23 #define __CLUSTERGRAPH_H__
24
25
26 #include <set>
27 #include <vector>
28 #include "varset.h"
29
30
31 namespace dai {
32
33
34 using namespace std;
35
36
37 /// A ClusterGraph is a hypergraph with VarSets as nodes.
38 /// It is implemented as a set<VarSet> in which the adjacency
39 /// relationship is computed realtime. It may be better to
40 /// implement it as a bipartitegraph, though. The additional
41 /// functionality compared to a simple set<VarSet> is
42 /// finding maximal clusters, finding cliques, etc...
43 class ClusterGraph : public set<VarSet> {
44 public:
45 /// Default constructor
46 ClusterGraph() : set<VarSet>() {}
47
48 /// Construct from vector<VarSet>
49 ClusterGraph( const vector<VarSet> & cls ) {
50 insert( cls.begin(), cls.end() );
51 }
52
53 /// Copy constructor
54 ClusterGraph(const ClusterGraph &x) : set<VarSet>(x) {}
55
56 /// Assignment operator
57 ClusterGraph& operator=( const ClusterGraph &x ) {
58 if( this != &x ) {
59 set<VarSet>::operator=( x );
60 }
61 return *this;
62 }
63
64 /// Returns true if ns is a maximal member of *this under inclusion (VarSet::operator<<)
65 bool isMaximal( const VarSet &ns ) const {
66 if( count( ns ) ) {
67 // ns is a member
68 bool maximal = true;
69 for( const_iterator x = begin(); x != end() && maximal; x++ )
70 if( (ns << *x) && (ns != *x) )
71 maximal = false;
72 return maximal;
73 } else
74 return false;
75 }
76
77 /// Erase all VarSets that are not maximal
78 ClusterGraph& eraseNonMaximal() {
79 for( iterator x = begin(); x != end(); )
80 if( !isMaximal(*x) )
81 erase(x++);
82 else
83 x++;
84 return *this;
85 }
86
87 /// Return union of all members
88 VarSet vars() const {
89 VarSet result;
90 for( iterator x = begin(); x != end(); x++ )
91 result |= *x;
92 return result;
93 }
94
95 /// Returns true if n1 and n2 are adjacent, i.e.\ by
96 /// definition, are both contained in some cluster in *this
97 bool adj( const Var& n1, const Var& n2 ) {
98 bool result = false;
99 for( iterator x = begin(); (x != end()) && (!result); x++ )
100 if( (*x && n1) && (*x && n2) )
101 result = true;
102 return result;
103 }
104
105 /// Returns union of clusters that contain n, minus n
106 VarSet Delta( const Var& n ) const {
107 VarSet result;
108 for( iterator x = begin(); x != end(); x++ )
109 if( (*x && n) )
110 result |= *x;
111 return result;
112 }
113
114 /// Returns union of clusters that contain n, minus n
115 VarSet delta( const Var& n ) const {
116 return Delta( n ) / n;
117 }
118
119 /// Erases all members that contain n
120 ClusterGraph& eraseSubsuming( const Var& n ) {
121 for( iterator x = begin(); x != end(); )
122 if( (*x && n) )
123 erase(x++);
124 else
125 x++;
126 return *this;
127 }
128
129 /// Send to output stream
130 friend std::ostream & operator << ( std::ostream & os, const ClusterGraph & cl ) {
131 os << "{";
132 ClusterGraph::const_iterator x = cl.begin();
133 if( x != cl.end() )
134 os << *(x++);
135 for( ; x != cl.end(); x++ )
136 os << ", " << *x;
137 os << "}";
138 return os;
139 }
140
141 /// Convert to vector<VarSet>
142 vector<VarSet> toVector() const {
143 vector<VarSet> result;
144 result.reserve( size() );
145 for( const_iterator x = begin(); x != end(); x++ )
146 result.push_back( *x );
147 return result;
148 }
149
150 /// Calculate cost of eliminating variable n
151 /// using as a measure "number of added edges in the adjacency graph"
152 /// where the adjacency graph has the variables as its nodes and
153 /// connects nodes i1 and i2 iff i1 and i2 occur in some common factor I
154 size_t eliminationCost( const Var& n ) {
155 VarSet d_n = delta( n );
156 size_t cost = 0;
157
158 // for each unordered pair {i1,i2} adjacent to n
159 for( VarSet::const_iterator i1 = d_n.begin(); i1 != d_n.end(); i1++ ) {
160 VarSet d_i1 = delta( *i1 );
161 for( VarSet::const_iterator i2 = i1; (++i2) != d_n.end(); ) {
162 // if i1 and i2 are not adjacent, eliminating n would make them adjacent
163 if( !adj(*i1, *i2) )
164 cost++;
165 }
166 }
167 return cost;
168 }
169
170 /// Perform Variable Elimination without Probs, i.e. only keeping track of
171 /// the interactions that are created along the way.
172 /// Input: a set of outer clusters and an elimination sequence
173 /// Output: a set of elimination "cliques"
174 ClusterGraph VarElim( const vector<Var> &ElimSeq ) const;
175
176 /// As Taylan does it
177 ClusterGraph VarElim_MinFill() const;
178 };
179
180
181 }
182
183
184 #endif