Miscellaneous changes:
[libdai.git] / include / dai / 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 __defined_libdai_clustergraph_h
23 #define __defined_libdai_clustergraph_h
24
25
26 #include <set>
27 #include <vector>
28 #include <dai/varset.h>
29
30
31 namespace dai {
32
33
34 /// A ClusterGraph is a hypergraph with VarSets as nodes.
35 /// It is implemented as a set<VarSet> in which the adjacency
36 /// relationship is computed realtime. It may be better to
37 /// implement it as a bipartitegraph, though. The additional
38 /// functionality compared to a simple set<VarSet> is
39 /// finding maximal clusters, finding cliques, etc...
40 class ClusterGraph : public std::set<VarSet> {
41 public:
42 /// Default constructor
43 ClusterGraph() : std::set<VarSet>() {}
44
45 /// Construct from vector<VarSet>
46 ClusterGraph( const std::vector<VarSet> & cls ) {
47 insert( cls.begin(), cls.end() );
48 }
49
50 /// Copy constructor
51 ClusterGraph(const ClusterGraph &x) : std::set<VarSet>(x) {}
52
53 /// Assignment operator
54 ClusterGraph& operator=( const ClusterGraph &x ) {
55 if( this != &x ) {
56 std::set<VarSet>::operator=( x );
57 }
58 return *this;
59 }
60
61 /// Returns true if ns is a maximal member of *this under inclusion (VarSet::operator<<)
62 bool isMaximal( const VarSet &ns ) const {
63 if( count( ns ) ) {
64 // ns is a member
65 bool maximal = true;
66 for( const_iterator x = begin(); x != end() && maximal; x++ )
67 if( (ns << *x) && (ns != *x) )
68 maximal = false;
69 return maximal;
70 } else
71 return false;
72 }
73
74 /// Erase all VarSets that are not maximal
75 ClusterGraph& eraseNonMaximal() {
76 for( iterator x = begin(); x != end(); )
77 if( !isMaximal(*x) )
78 erase(x++);
79 else
80 x++;
81 return *this;
82 }
83
84 /// Return union of all members
85 VarSet vars() const {
86 VarSet result;
87 for( const_iterator x = begin(); x != end(); x++ )
88 result |= *x;
89 return result;
90 }
91
92 /// Returns true if n1 and n2 are adjacent, i.e.\ by
93 /// definition, are both contained in some cluster in *this
94 bool adj( const Var& n1, const Var& n2 ) {
95 bool result = false;
96 for( iterator x = begin(); (x != end()) && (!result); x++ )
97 if( (*x && n1) && (*x && n2) )
98 result = true;
99 return result;
100 }
101
102 /// Returns union of clusters that contain n, minus n
103 VarSet Delta( const Var& n ) const {
104 VarSet result;
105 for( const_iterator x = begin(); x != end(); x++ )
106 if( (*x && n) )
107 result |= *x;
108 return result;
109 }
110
111 /// Returns union of clusters that contain n, minus n
112 VarSet delta( const Var& n ) const {
113 return Delta( n ) / n;
114 }
115
116 /// Erases all members that contain n
117 ClusterGraph& eraseSubsuming( const Var& n ) {
118 for( iterator x = begin(); x != end(); )
119 if( (*x && n) )
120 erase(x++);
121 else
122 x++;
123 return *this;
124 }
125
126 /// Send to output stream
127 friend std::ostream & operator << ( std::ostream & os, const ClusterGraph & cl ) {
128 os << "{";
129 ClusterGraph::const_iterator x = cl.begin();
130 if( x != cl.end() )
131 os << *(x++);
132 for( ; x != cl.end(); x++ )
133 os << ", " << *x;
134 os << "}";
135 return os;
136 }
137
138 /// Convert to vector<VarSet>
139 std::vector<VarSet> toVector() const {
140 std::vector<VarSet> result;
141 result.reserve( size() );
142 for( const_iterator x = begin(); x != end(); x++ )
143 result.push_back( *x );
144 return result;
145 }
146
147 /// Calculate cost of eliminating variable n
148 /// using as a measure "number of added edges in the adjacency graph"
149 /// where the adjacency graph has the variables as its nodes and
150 /// connects nodes i1 and i2 iff i1 and i2 occur in some common factor I
151 size_t eliminationCost( const Var& n ) {
152 VarSet d_n = delta( n );
153 size_t cost = 0;
154
155 // for each unordered pair {i1,i2} adjacent to n
156 for( VarSet::const_iterator i1 = d_n.begin(); i1 != d_n.end(); i1++ ) {
157 VarSet d_i1 = delta( *i1 );
158 for( VarSet::const_iterator i2 = i1; (++i2) != d_n.end(); ) {
159 // if i1 and i2 are not adjacent, eliminating n would make them adjacent
160 if( !adj(*i1, *i2) )
161 cost++;
162 }
163 }
164 return cost;
165 }
166
167 /// Perform Variable Elimination without Probs, i.e. only keeping track of
168 /// the interactions that are created along the way.
169 /// Input: a set of outer clusters and an elimination sequence
170 /// Output: a set of elimination "cliques"
171 ClusterGraph VarElim( const std::vector<Var> &ElimSeq ) const;
172
173 /// As Taylan does it
174 ClusterGraph VarElim_MinFill() const;
175 };
176
177
178 } // end of namespace dai
179
180
181 #endif