Moved platform independent build options into Makefile.ALL and documented tests/testdai
[libdai.git] / src / clustergraph.cpp
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-2010 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
9 */
10
11
12 #include <set>
13 #include <vector>
14 #include <iostream>
15 #include <dai/varset.h>
16 #include <dai/clustergraph.h>
17
18
19 namespace dai {
20
21
22 using namespace std;
23
24
25 ClusterGraph::ClusterGraph( const std::vector<VarSet> & cls ) : G(), vars(), clusters() {
26 // construct vars, clusters and edge list
27 vector<Edge> edges;
28 foreach( const VarSet &cl, cls ) {
29 if( find( clusters.begin(), clusters.end(), cl ) == clusters.end() ) {
30 // add cluster
31 size_t n2 = clusters.size();
32 clusters.push_back( cl );
33 for( VarSet::const_iterator n = cl.begin(); n != cl.end(); n++ ) {
34 size_t n1 = find( vars.begin(), vars.end(), *n ) - vars.begin();
35 if( n1 == vars.size() )
36 // add variable
37 vars.push_back( *n );
38 edges.push_back( Edge( n1, n2 ) );
39 }
40 } // disregard duplicate clusters
41 }
42
43 // Create bipartite graph
44 G.construct( vars.size(), clusters.size(), edges.begin(), edges.end() );
45 }
46
47
48 size_t ClusterGraph::eliminationCost( size_t i ) const {
49 return eliminationCost_MinFill( *this, i );
50 }
51
52
53 ClusterGraph ClusterGraph::VarElim( const std::vector<Var> &ElimSeq ) const {
54 return VarElim( sequentialVariableElimination( ElimSeq ) );
55 }
56
57
58 ClusterGraph ClusterGraph::VarElim_MinFill() const {
59 return VarElim( greedyVariableElimination( &eliminationCost_MinFill ) );
60 }
61
62
63 size_t sequentialVariableElimination::operator()( const ClusterGraph &cl, const std::set<size_t> &/*remainingVars*/ ) {
64 return cl.findVar( seq.at(i++) );
65 }
66
67
68 size_t greedyVariableElimination::operator()( const ClusterGraph &cl, const std::set<size_t> &remainingVars ) {
69 set<size_t>::const_iterator lowest = remainingVars.end();
70 size_t lowest_cost = -1UL;
71 for( set<size_t>::const_iterator i = remainingVars.begin(); i != remainingVars.end(); i++ ) {
72 size_t cost = heuristic( cl, *i );
73 if( lowest == remainingVars.end() || lowest_cost > cost ) {
74 lowest = i;
75 lowest_cost = cost;
76 }
77 }
78 return *lowest;
79 }
80
81
82 size_t eliminationCost_MinNeighbors( const ClusterGraph &cl, size_t i ) {
83 std::vector<size_t> id_n = cl.G.delta1( i );
84 return id_n.size();
85 }
86
87
88 size_t eliminationCost_MinWeight( const ClusterGraph &cl, size_t i ) {
89 std::vector<size_t> id_n = cl.G.delta1( i );
90
91 size_t cost = 1;
92 for( size_t _i = 0; _i < id_n.size(); _i++ )
93 cost *= cl.vars[id_n[_i]].states();
94
95 return cost;
96 }
97
98
99 size_t eliminationCost_MinFill( const ClusterGraph &cl, size_t i ) {
100 std::vector<size_t> id_n = cl.G.delta1( i );
101
102 size_t cost = 0;
103 // for each unordered pair {i1,i2} adjacent to n
104 for( size_t _i1 = 0; _i1 < id_n.size(); _i1++ )
105 for( size_t _i2 = _i1 + 1; _i2 < id_n.size(); _i2++ ) {
106 // if i1 and i2 are not adjacent, eliminating n would make them adjacent
107 if( !cl.adj(id_n[_i1], id_n[_i2]) )
108 cost++;
109 }
110
111 return cost;
112 }
113
114
115 size_t eliminationCost_WeightedMinFill( const ClusterGraph &cl, size_t i ) {
116 std::vector<size_t> id_n = cl.G.delta1( i );
117
118 size_t cost = 0;
119 // for each unordered pair {i1,i2} adjacent to n
120 for( size_t _i1 = 0; _i1 < id_n.size(); _i1++ )
121 for( size_t _i2 = _i1 + 1; _i2 < id_n.size(); _i2++ ) {
122 // if i1 and i2 are not adjacent, eliminating n would make them adjacent
123 if( !cl.adj(id_n[_i1], id_n[_i2]) )
124 cost += cl.vars[id_n[_i1]].states() * cl.vars[id_n[_i2]].states();
125 }
126
127 return cost;
128 }
129
130
131 } // end of namespace dai