-
Notifications
You must be signed in to change notification settings - Fork 0
/
markpart.cpp
145 lines (118 loc) · 4.24 KB
/
markpart.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
// markpart.cpp - 2016 - Atlee Brink
// Markov network partition-function (Z) computer.
// variable-elimination with min-neighbors heuristic, sort of.
#include "cmark.hpp"
namespace {
typedef double flavor_t;
typedef unsigned int color_t;
typedef unsigned int hue_t;
typedef cmark<flavor_t, color_t, hue_t> mark;
}
int main( int argc, char *argv[] )
{
// consider user interaction
if( argc < 2 ) {
cout << "usage: " << argv[0] << " <infile.uai: markov network file>" << endl;
return 0;
}
// where are the boxen?
string boxenhabitat( argv[1] );
// each color may have a different range of hues
vector< hue_t > bandwidths;
// smarkboxen should only be viewed through a prism
mark::smarkboxprism prism;
// capture boxen
if( !mark::wranglesmarks( bandwidths, prism, boxenhabitat ) ) {
cerr << "main: wranglesmarks failed!\n";
return 1;
}
// list colors to eliminate
unordered_set<color_t> uneliminated( prism.size() );
for( color_t c = 0; c < prism.size(); c++ ) uneliminated.insert( c );
// try to eliminate each color once
while( !uneliminated.empty() ) {
// find loneliest color (crudely)
color_t lonely = 0;
size_t num = 0;
for( auto c : uneliminated ) {
if( prism[c].empty() ) continue;
if( num == 0 ) {
lonely = c;
num = prism[c].size();
}
else if( prism[c].size() < num ) {
lonely = c;
num = prism[c].size();
}
}
if( num == 0 ) {
cerr << "main: unexpected variable shortage during elimination!" << endl;
return 1;
}
uneliminated.erase( lonely );
// only ostracize if not already ostracized
bool hasfriends = false;
for( auto pbox : prism[lonely] ) {
if( pbox->palette.size() > 1 ) {
hasfriends = true;
break;
}
}
// if no friends, can't ostracize
if( !hasfriends ) {
// if more than one with no friends, merge into one
if( prism[lonely].size() > 1 ) {
auto merged = mark::merge( bandwidths, prism[lonely], lonely );
prism[lonely].clear();
prism[lonely].insert( merged );
}
continue;
}
// if has friends, ostracize politely and save essence in new smarkbox
shared_ptr<mark::smarkbox> pnewbox = mark::ostracize( bandwidths, prism[lonely], lonely );
// finish ostracizing
while( !prism[lonely].empty() ) {
auto psmark = *prism[lonely].begin();
for( auto &set : prism ) set.erase( psmark );
}
// cast the new smarkbox into the prism
for( auto pair : pnewbox->palette ) prism[pair.first].insert( pnewbox );
}
// the fast work is done: now remaining colors must be combined slowly
{
// find remaining colors
vector< pair<color_t, hue_t> > pattern;
for( color_t c = 0; c < prism.size(); c++ ) {
if( !prism[c].empty() ) pattern.push_back( { c, 0 } );
}
// prepare to taste
flavor_t mealtaste = (flavor_t)0;
// instructions for tasting
vector< hue_t > spectrum( bandwidths.size(), (hue_t)0 );
for( bool hungry = true; hungry; ) {
// take a bite
flavor_t bitetaste = (flavor_t)1;
for( auto &pair : pattern ) {
bitetaste *= (*prism[pair.first].begin())->taste( spectrum );
}
mealtaste += bitetaste;
// adjust spectrum
for( size_t band = pattern.size() - 1;; ) {
++pattern[band].second;
++spectrum[pattern[band].first];
if( pattern[band].second < bandwidths[pattern[band].first] ) break;
if( !band ) {
hungry = false;
break;
}
pattern[band].second = 0;
spectrum[pattern[band].first] = 0;
band--;
}
}
// output partition function
cout << "Z = " << mealtaste << endl;
}
return 0;
}
// end