[Patrick Pletscher] Fixed performance issue in FactorGraph::clamp and FactorGraph...
[libdai.git] / src / clustergraph.cpp
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 #include <set>
24 #include <vector>
25 #include <iostream>
26 #include <dai/varset.h>
27 #include <dai/clustergraph.h>
28
29
30 namespace dai {
31
32
33 using namespace std;
34
35
36 ClusterGraph::ClusterGraph( const std::vector<VarSet> & cls ) : G(), vars(), clusters() {
37 // construct vars, clusters and edge list
38 vector<Edge> edges;
39 foreach( const VarSet &cl, cls ) {
40 if( find( clusters.begin(), clusters.end(), cl ) == clusters.end() ) {
41 // add cluster
42 size_t n2 = clusters.size();
43 clusters.push_back( cl );
44 for( VarSet::const_iterator n = cl.begin(); n != cl.end(); n++ ) {
45 size_t n1 = find( vars.begin(), vars.end(), *n ) - vars.begin();
46 if( n1 == vars.size() )
47 // add variable
48 vars.push_back( *n );
49 edges.push_back( Edge( n1, n2 ) );
50 }
51 } // disregard duplicate clusters
52 }
53
54 // Create bipartite graph
55 G.construct( vars.size(), clusters.size(), edges.begin(), edges.end() );
56 }
57
58
59 ClusterGraph ClusterGraph::VarElim_MinFill() const {
60 // Make a copy
61 ClusterGraph cl(*this);
62 cl.eraseNonMaximal();
63
64 ClusterGraph result;
65
66 // Construct set of variable indices
67 set<size_t> varindices;
68 for( size_t i = 0; i < vars.size(); ++i )
69 varindices.insert( i );
70
71 // Do variable elimination
72 while( !varindices.empty() ) {
73 set<size_t>::const_iterator lowest = varindices.end();
74 size_t lowest_cost = -1UL;
75 for( set<size_t>::const_iterator i = varindices.begin(); i != varindices.end(); i++ ) {
76 size_t cost = cl.eliminationCost( *i );
77 if( lowest == varindices.end() || lowest_cost > cost ) {
78 lowest = i;
79 lowest_cost = cost;
80 }
81 }
82 size_t i = *lowest;
83
84 result.insert( cl.Delta( i ) );
85
86 cl.insert( cl.delta( i ) );
87 cl.eraseSubsuming( i );
88 cl.eraseNonMaximal();
89 varindices.erase( i );
90 }
91
92 return result;
93 }
94
95
96
97 ClusterGraph ClusterGraph::VarElim( const std::vector<Var> & ElimSeq ) const {
98 // Make a copy
99 ClusterGraph cl(*this);
100 cl.eraseNonMaximal();
101
102 ClusterGraph result;
103
104 // Do variable elimination
105 for( vector<Var>::const_iterator n = ElimSeq.begin(); n != ElimSeq.end(); n++ ) {
106 size_t i = cl.findVar( *n );
107 assert( i != cl.vars.size() );
108
109 result.insert( cl.Delta(i) );
110
111 cl.insert( cl.delta(i) );
112 cl.eraseSubsuming( i );
113 cl.eraseNonMaximal();
114 }
115
116 return result;
117 }
118
119
120 } // end of namespace dai