bayes_counters.c from EmStar at Krugle
Show bayes_counters.c syntax highlighted
/* ex: set tabstop=2 expandtab shiftwidth=2 softtabstop=2: */
/*
*
* Copyright (c) 2003 The Regents of the University of California. All
* rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* - Neither the name of the University nor the names of its
* contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS''
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
* PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
*/
// Questions:
// * When providing probabilities - what should happen if it gets
// data it has never seen. Does it say the probability is 0?
// Currently it reports a probability of 1 (because arrays are updated
// with the value, and then the probability is returned).
// However in non=training mode, the arrays will probably not be updated.
//
// Assumptions:
// * Readings are received all on one line. Useful because we process all
// neighborhood data at once, after the next line is read. so that we can be sure
// that all nodes neighbors have sent in their data. So receive data calls
// process_neighbors() for the previous line once a reading with a new time is
// received.
// * Node ids are contiguous and cannot be 0.
// Used in determining a node's 2 neighbors.
// * If neighbor1 returns X and neighbor2 returns Y, and subsequently, neighbor1
// returns Y and neighbor2 returns X, these are considered to be two different
// situations and handled accordingly.
// * time-stamps are increasing (not necessarily monotonically)
// i.e. no out of order data
//
// Current Hardcoding
// * 2 Neighbors for each node
//
// Missing values
// * If a value is missing, then i will not return a probability
// for that value. Otherwise, even if previous readings or neighbor
// readings are missing, still provide a probability.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MISSING_VAL 989898.0000
#define MAX_NODES 30
#define NUM_MAIN_READINGS 50
#define NUM_READINGS 30
#define INCREMENT_READINGS 10
typedef struct single_ctr {
int capacity;
// These are arrays
double* value;
int* num;
} single_ctr_t;
typedef struct double_ctr {
int capacity;
double* value1;
double* value2;
int* num;
} double_ctr_t;
typedef struct bayes_ctr {
single_ctr_t reading;
single_ctr_t previous_readings;
double_ctr_t neighbor_readings;
} bayes_ctr_t;
typedef struct bayes_node {
int node_id;
double previous_reading; // Most recent previous reading
double previous_previous_reading; // Used in get_probabilities
double neighbor_readings[2]; // Most recent neighbor readings
int previous_time;
int capacity;
int num_readings_received;
bayes_ctr_t* reading;
} bayes_node_t;
int initialization_done = 0;
bayes_node_t nodes[MAX_NODES];
int max_node_id_received = 0;
int min_node_id_received = 10000;
static
void get_probabilities(bayes_node_t* node);
double interval = -1;
double digits = -1;
static
void* init_array(int size_element, int new_capacity,
int old_capacity, void* initialization)
{
char* x = calloc(new_capacity, size_element);
if ((initialization) && (old_capacity > 0)) {
memcpy(x, initialization, old_capacity * size_element);
free(initialization);
}
return x;
}
static
void init_single_ctr(single_ctr_t* ctr, int capacity,
single_ctr_t* init_ctr)
{
int old_capacity = (init_ctr ? init_ctr->capacity : 0);
double* init_vals = (init_ctr ? init_ctr->value : NULL);
int* init_nums = (init_ctr ? init_ctr->num : NULL);
ctr->num = (int *) init_array(sizeof(int), capacity,
old_capacity, init_nums);
ctr->value = (double *) init_array(sizeof(double), capacity,
old_capacity, init_vals);
ctr->capacity = capacity;
}
static
void init_double_ctr(double_ctr_t* ctr, int capacity,
double_ctr_t* init_ctr)
{
int old_capacity = (init_ctr ? init_ctr->capacity : 0);
ctr->num = (int *) init_array(sizeof(int),
capacity, old_capacity,
(init_ctr ? init_ctr->num : NULL));
ctr->value1 = (double *) init_array(sizeof(double),
capacity, old_capacity,
(init_ctr ? init_ctr->value1 : NULL));
ctr->value2 = (double *) init_array(sizeof(double),
capacity, old_capacity,
(init_ctr ? init_ctr->value2 : NULL));
ctr->capacity = capacity;
}
static
void init_bayes_ctr(bayes_node_t* node, int increment_capacity)
{
int i, new_capacity;
if (!node) return;
new_capacity = node->capacity + increment_capacity;
node->reading = init_array(sizeof(bayes_ctr_t),
new_capacity, node->capacity, node->reading);
for (i = node->capacity; i < new_capacity; i++) {
init_single_ctr(&node->reading[i].reading,
1, NULL);
init_single_ctr(&node->reading[i].previous_readings,
NUM_READINGS, NULL);
init_double_ctr(&node->reading[i].neighbor_readings,
NUM_READINGS, NULL);
}
node->capacity = new_capacity;
}
static
void init_counters()
{
int i;
memset(nodes, 0, sizeof(nodes));
for (i = 0; i < MAX_NODES; i++) {
init_bayes_ctr(&nodes[i], NUM_READINGS);
}
}
// If present, increments ctr[X].reading.num
// Else inserts into ctr[X] and increments ctr_size
static
double_ctr_t* get_double_ctr(double_ctr_t* ctr,
double reading1, double reading2, int recursive_call)
{
int i, empty_index = -1;
for (i = 0; i < ctr->capacity; i++) {
if ((ctr->value1[i] == reading1) &&
(ctr->value2[i] == reading2)) {
ctr->num[i]++;
return;
}
if ((empty_index == -1) && (ctr->num[i] == 0)) {
empty_index = i;
}
}
if (empty_index >= 0) {
ctr->num[empty_index] = 1;
ctr->value1[empty_index] = reading1;
ctr->value2[empty_index] = reading2;
return;
}
// Otherwise we couldn't find an empty spot so have to
// add a bunch more spots, copy the array over, and free
// the original array
if (!recursive_call) {
init_double_ctr(ctr, ctr->capacity + INCREMENT_READINGS,
ctr);
get_double_ctr(ctr, reading1, reading2, 1);
}
else {
printf("ERROR: Called get_double_ctr recursively and still unable to insert reading1/reading2: %3.2f/%3.2f\n", reading1,reading2);
exit(1);
}
}
static
void get_single_ctr(single_ctr_t* ctr, double reading,
int recursive_call)
{
int i, empty_index = -1;
for (i = 0; i < ctr->capacity; i++) {
if (ctr->value[i] == reading) {
ctr->num[i]++;
return;
}
if ((empty_index == -1) && (ctr->num[i] == 0)) {
empty_index = i;
}
}
if (empty_index >= 0) {
ctr->num[empty_index] = 1;
ctr->value[empty_index] = reading;
return;
}
// Otherwise we couldn't find an empty spot so have to
// add a bunch more spots, copy the array over, and free
// the original array
if (!recursive_call) {
init_single_ctr(ctr, ctr->capacity
+ INCREMENT_READINGS, ctr);
get_single_ctr(ctr, reading, 1);
}
else {
printf("ERROR: Called get_single_ctr recursively and still unable to insert reading: %3.2f\n", reading);
exit(1);
}
}
static
bayes_ctr_t* get_bayes_ctr(bayes_node_t* node,
double reading, int update, int recursive_call)
{
int i, empty_index = -1;
if (recursive_call) {
printf ("RECURSIVE CALL for node %d\n", node->node_id);
}
for (i = 0; i < node->capacity; i++) {
if ((node->reading[i].reading.value[0] == reading) &&
(node->reading[i].reading.num[0] > 0)) {
if (update) node->reading[i].reading.num[0]++;
return &node->reading[i];
}
if ((empty_index == -1) && (node->reading[i].reading.num[0] == 0)) {
empty_index = i;
}
}
if (!update) {
printf("ERROR did not want to update Node %d reading %3.2f but no ctr available!\n",
node->node_id, reading);
return NULL;
}
if (empty_index >= 0) {
node->reading[empty_index].reading.num[0] = 1;
node->reading[empty_index].reading.value[0] = reading;
return &node->reading[empty_index];
}
// Otherwise we couldn't find an empty spot so have to
// add a bunch more spots, copy the array over, and free
// the original array
if (!recursive_call) {
init_bayes_ctr(node, INCREMENT_READINGS);
return get_bayes_ctr(node, reading, update, 1);
}
else {
printf("ERROR: Called get_bayes_ctr recursively and still unable to insert reading: %3.2f\n", reading);
exit(1);
return NULL;
}
}
static
bayes_node_t* get_node(int node_id)
{
int i, empty_index = -1;
for (i = 0; i < MAX_NODES; i++) {
if (nodes[i].node_id == node_id) {
return &nodes[i];
}
if ((empty_index == -1) && (nodes[i].node_id == 0)) {
empty_index = i;
}
}
if (empty_index > -1) {
nodes[empty_index].node_id = node_id;
return &nodes[empty_index];
}
return NULL;
}
// Fill val[] array with readings from the two nearest neighbors.
// For now do it based on node_id
static
void get_neighbor_readings(bayes_node_t* node)
{
int i, index, node_id1 = 0, node_id2 = 0;
int node1_set = 0, node2_set = 0;
if ((!node) || (node->node_id == 0)) return;
if (node->node_id == min_node_id_received) {
node_id1 = node->node_id+1;
node_id2 = node->node_id+2;
}
else if (node->node_id == max_node_id_received) {
node_id1 = node->node_id-1;
node_id2 = node->node_id-2;
}
else {
node_id1 = node->node_id-1;
node_id2 = node->node_id+1;
}
for (i = 0; i < MAX_NODES; i++) {
if (node1_set && node2_set) return;
if (nodes[i].node_id == node->node_id) continue;
index = -1;
if (nodes[i].node_id == node_id1) {
node1_set = 1;
index = 0;
}
else if (nodes[i].node_id == node_id2) {
node2_set = 1;
index = 1;
}
if (index > -1
&& (nodes[i].previous_time == node->previous_time)) {
node->neighbor_readings[index] = nodes[i].previous_reading;
}
}
if (!node1_set || !node2_set) {
printf("ERROR all neighbor readings should be here. Node %d with reading %3.2f and time %d does not have valid neighbors!\n", node->node_id, node->previous_reading, node->previous_time);
}
}
static
void process_neighbor_readings()
{
int i;
bayes_ctr_t* bctr;
for (i = 0; i < MAX_NODES; i++) {
if (nodes[i].node_id <= 0) continue;
get_neighbor_readings(&nodes[i]);
bctr = get_bayes_ctr(&nodes[i], nodes[i].previous_reading, 0, 0);
if (bctr) {
get_double_ctr(&bctr->neighbor_readings,
nodes[i].neighbor_readings[0],
nodes[i].neighbor_readings[1], 0);
}
get_probabilities(&nodes[i]);
}
}
static
int get_number_times(single_ctr_t* sctr, double value)
{
int i;
if (!sctr) return 0;
for (i = 0; i < sctr->capacity; i++) {
if (sctr->value[i] == value) return sctr->num[i];
}
return 0;
}
static
int get_number_times2(double_ctr_t* dctr, double value[])
{
int i;
if (!dctr) return 0;
for (i = 0; i < dctr->capacity; i++) {
if (dctr->value1[i] == value[0] &&
dctr->value2[i] == value[1]) return dctr->num[i];
}
return 0;
}
static
void get_probabilities(bayes_node_t* node)
{
float P_h; //Probability of previous reading;
float P_ri; // Probability of reading
float P_ri_h; // Probability of reading given the previous reading
float P_ri_n; // Probability of a reading given neighbor readings
float P_n; // Probability of n occurring
bayes_ctr_t* bctr;
int num_readings, x;
double reading = node->previous_reading;
double previous_reading = node->previous_previous_reading;
int i;
if ((!node) || (node->num_readings_received <= 1)) return;
if (reading == MISSING_VAL) {
printf("# Skipping node %d cuz current reading is missing!\n",
node->node_id);
return;
}
if (!(bctr = get_bayes_ctr(node, reading, 0, 0))) {
printf("ERROR Something is very wrong that Reading: %f does not appear for node: %d\n",
reading, node->node_id);
exit(1);
}
// Probability of receiving this reading
num_readings = get_number_times(&bctr->reading, reading);
if (num_readings == 0) return;
P_ri = (float) num_readings/node->num_readings_received;
printf("Node %d P_ri (%3.2f) %1.2f (%d/%d)\n", node->node_id,
reading, P_ri, num_readings, node->num_readings_received);
// Given this reading, probability of receiving the previous
// reading
x = 0;
for (i = 0; i < node->capacity; i++) {
x += get_number_times2(&node->reading[i].neighbor_readings,
node->neighbor_readings);
}
P_n = (float) x/node->num_readings_received;
printf("\tP_n (neighbor %3.2f/%3.2f): %3.2f (%d/%d)\n",
node->neighbor_readings[0], node->neighbor_readings[1],
P_n, x, node->num_readings_received);
x = get_number_times(&bctr->previous_readings,
previous_reading);
P_ri_h = (float) x/num_readings;
printf("\tP_ri_h (previous %3.2f) %3.2f (%d/%d)\n", previous_reading,
P_ri_h, x, num_readings);
// Given this reading, probability of receiving the neighbor readings
x = get_number_times2(&bctr->neighbor_readings,
node->neighbor_readings);
P_ri_n = (float) x/num_readings;
printf("\tP_ri_n (neighbor %3.2f/%3.2f): %3.2f (%d/%d)\n",
node->neighbor_readings[0], node->neighbor_readings[1],
P_ri_n, x, num_readings);
// How many times have we observed the previous reading
if ((bctr = get_bayes_ctr(node, previous_reading, 0, 0))) {
x = get_number_times(&bctr->reading, previous_reading);
P_h = (float) x/node->num_readings_received;
printf("\tP_h (previous %3.2f): %3.2f (%d/%d)\n", previous_reading,
P_h, x, node->num_readings_received);
}
}
double
round_reading(double value)
{
double mult = pow(10,digits);
double valueI = value * mult;
double intervalI = interval * mult;
double rem = remainder(valueI, intervalI);
double reading;
if (rem >= 0) reading = (valueI - rem)/mult;
else reading = (valueI - intervalI - rem)/mult;
return reading;
}
//**** API ****//
extern
void set_interval(double intrval, int digs)
{
interval = intrval;
digits = (double) digs;
}
void
receive_data(int time, int node_id, double reading)
{
bayes_node_t* node;
bayes_ctr_t* bctr;
double dummy_val= 0;
static int last_time = 0;
double test = (double) reading;
printf("Reading: %f => ", test);
reading = round_reading(test);
printf("%f\n", reading);
if (!initialization_done) {
init_counters();
initialization_done = 1;
}
// Don't process neighbor values until all readings from a line
// have been read in.
if ((last_time > 0) && (time > last_time)) {
process_neighbor_readings();
}
if(!(node = get_node(node_id))) {
printf(" ERROR: Unable to find node: %d, Consider increasing MAX_NODES\n",
node_id);
return;
}
if (node_id > max_node_id_received) max_node_id_received = node_id;
if (node_id < min_node_id_received) min_node_id_received = node_id;
bctr = get_bayes_ctr(node, reading, 1, 0);
if ((node->num_readings_received > 0) && bctr) {
get_single_ctr(&bctr->previous_readings,
node->previous_reading, 0);
}
if (reading != MISSING_VAL) {
node->num_readings_received++;
}
// Update last_time even if the last value is missing because
// this variable is just used to track if we are on the next line or not.
last_time = time;
node->previous_previous_reading = node->previous_reading;
node->previous_reading = reading;
node->previous_time = time;
}
See more files for this project here