From 5c9ff68089bc20a3d5fb271877ef371b31e21a1f Mon Sep 17 00:00:00 2001 From: adash Date: Mon, 15 Jun 2009 20:59:12 +0000 Subject: [PATCH] add new benchmark : Bayes Will clean up files later, at least have a good copy that compiles --- .../src/Benchmarks/SingleTM/Bayes/Adtree.java | 700 +++++++ .../Benchmarks/SingleTM/Bayes/AdtreeNode.java | 37 + .../Benchmarks/SingleTM/Bayes/AdtreeVary.java | 32 + .../src/Benchmarks/SingleTM/Bayes/Bayes.java | 419 +++++ .../src/Benchmarks/SingleTM/Bayes/Data.java | 463 +++++ .../SingleTM/Bayes/FindBestTaskArg.java | 17 + .../Benchmarks/SingleTM/Bayes/IntList.java | 329 ++++ .../SingleTM/Bayes/IntListNode.java | 8 + .../Benchmarks/SingleTM/Bayes/IntVector.java | 155 ++ .../Benchmarks/SingleTM/Bayes/Learner.java | 1666 +++++++++++++++++ .../SingleTM/Bayes/LearnerTask.java | 10 + Robust/src/Benchmarks/SingleTM/Bayes/Net.java | 1143 +++++++++++ .../Benchmarks/SingleTM/Bayes/NetNode.java | 26 + .../Benchmarks/SingleTM/Bayes/Operation.java | 72 + .../src/Benchmarks/SingleTM/Bayes/Query.java | 66 + .../src/Benchmarks/SingleTM/Bayes/Queue.java | 489 +++++ Robust/src/Benchmarks/SingleTM/Bayes/README | 87 + .../src/Benchmarks/SingleTM/Bayes/Sort.java | 282 +++ Robust/src/Benchmarks/SingleTM/Bayes/makefile | 58 + 19 files changed, 6059 insertions(+) create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/Adtree.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/AdtreeNode.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/AdtreeVary.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/Bayes.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/Data.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/FindBestTaskArg.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/IntList.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/IntListNode.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/IntVector.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/Learner.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/LearnerTask.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/Net.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/NetNode.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/Operation.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/Query.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/Queue.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/README create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/Sort.java create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/makefile diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Adtree.java b/Robust/src/Benchmarks/SingleTM/Bayes/Adtree.java new file mode 100644 index 00000000..220f18fb --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Adtree.java @@ -0,0 +1,700 @@ +/* ============================================================================= + * + * adtree.java + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * + * ============================================================================= + * + * Reference: + * + * A. Moore and M.-S. Lee. Cached sufficient statistics for efficient machine + * learning with large datasets. Journal of Artificial Intelligence Research 8 + * (1998), pp 67-91. + * + * ============================================================================= + * + * For the license of bayes/sort.h and bayes/sort.c, please see the header + * of the files. + * + * ------------------------------------------------------------------------ + * + * For the license of kmeans, please see kmeans/LICENSE.kmeans + * + * ------------------------------------------------------------------------ + * + * For the license of ssca2, please see ssca2/COPYRIGHT + * + * ------------------------------------------------------------------------ + * + * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the + * header of the files. + * + * ------------------------------------------------------------------------ + * + * For the license of lib/rbtree.h and lib/rbtree.c, please see + * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree + * + * ------------------------------------------------------------------------ + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * 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. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * * Neither the name of Stanford 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 STANFORD UNIVERSITY ``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 STANFORD UNIVERSITY 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. + * + * ============================================================================= + */ + /* +#include +#include +#include "adtree.h" +#include "data.h" +#include "query.h" +#include "utility.h" +#include "vector.h" +*/ + +public class Adtree { + int numVar; + int numRecord; + AdtreeNode rootNodePtr; + + public Adtree() { + + } + + /* ============================================================================= + * freeNode + * ============================================================================= + */ + public void + freeNode (AdtreeNode nodePtr) + { + nodePtr.varyVectorPtr.vector_free(); + nodePtr = null; + //free(nodePtr); + } + + + + /* ============================================================================= + * freeVary + * ============================================================================= + */ + public void + freeVary (AdtreeVary varyPtr) + { + varyPtr = null; + //free(varyPtr); + } + + + /* ============================================================================= + * adtree_alloc + * ============================================================================= + */ + public static Adtree adtree_alloc () + { + Adtree adtreePtr = new Adtree(); + //adtree_t* adtreePtr; + //adtreePtr = (adtree_t*)malloc(sizeof(adtree_t)); + if (adtreePtr != null) { + adtreePtr.numVar = -1; + adtreePtr.numRecord = -1; + adtreePtr.rootNodePtr = null; + } + + return adtreePtr; + } + + + /* ============================================================================= + * freeNodes + * ============================================================================= + */ + public void + freeNodes (AdtreeNode nodePtr) + { + if (nodePtr != null) { + Vector_t varyVectorPtr = nodePtr.varyVectorPtr; + //vector_t* varyVectorPtr = nodePtr.varyVectorPtr; + //int v; + int numVary = varyVectorPtr.vector_getSize(); + for (int v = 0; v < numVary; v++) { + AdtreeVary varyPtr = (AdtreeVary)(varyVectorPtr.vector_at(v)); + //adtree_vary_t* varyPtr = (adtree_vary_t*)vector_at(varyVectorPtr, v); + freeNodes(varyPtr.zeroNodePtr); + freeNodes(varyPtr.oneNodePtr); + freeVary(varyPtr); + } + freeNode(nodePtr); + } + } + + + /* ============================================================================= + * adtree_free + * ============================================================================= + */ + public void + adtree_free () + { + freeNodes(rootNodePtr); + this = null; + //free(adtreePtr); + } + + + /* + static adtree_vary_t* + makeVary (int parentIndex, + int index, + int start, + int numRecord, + Data* dataPtr); + + static adtree_node_t* + makeNode (int parentIndex, + int index, + int start, + int numRecord, + Data* dataPtr); + */ + + + /* ============================================================================= + * makeVary + * ============================================================================= + */ + public AdtreeVary + makeVary (int parentIndex, + int index, + int start, + int numRecord, + Data dataPtr) + { + AdtreeVary varyPtr = AdtreeVary.allocVary(index); + //assert(varyPtr); + + if ((parentIndex + 1 != index) && (numRecord > 1)) { + dataPtr.data_sort(start, numRecord, index); + } + + int num0 = dataPtr.data_findSplit(start, numRecord, index); + int num1 = numRecord - num0; + + int mostCommonValue = ((num0 >= num1) ? 0 : 1); + varyPtr.mostCommonValue = mostCommonValue; + + if (num0 == 0 || mostCommonValue == 0) { + varyPtr.zeroNodePtr = null; + } else { + varyPtr.zeroNodePtr = + makeNode(index, index, start, num0, dataPtr); + varyPtr.zeroNodePtr.value = 0; + } + + if (num1 == 0 || mostCommonValue == 1) { + varyPtr.oneNodePtr = null; + } else { + varyPtr.oneNodePtr = + makeNode(index, index, (start + num0), num1, dataPtr); + varyPtr.oneNodePtr.value = 1; + } + + return varyPtr; + } + + + /* ============================================================================= + * makeNode + * ============================================================================= + */ + public AdtreeNode + makeNode (int parentIndex, + int index, + int start, + int numRecord, + Data dataPtr) + { + AdtreeNode nodePtr = AdtreeNode.allocNode(index); + //adtree_node_t* nodePtr = allocNode(index); + //assert(nodePtr); + + nodePtr.count = numRecord; + + Vector_t varyVectorPtr = nodePtr.varyVectorPtr; + + //vector_t* varyVectorPtr = nodePtr.varyVectorPtr; + + //int v; + int numVar = dataPtr.numVar; + for (int v = (index + 1); v < numVar; v++) { + AdtreeVary varyPtr = + //adtree_vary_t* varyPtr = + makeVary(parentIndex, v, start, numRecord, dataPtr); + //assert(varyPtr); + boolean status; + if((status = varyVectorPtr.vector_pushBack(varyPtr)) != true) { + System.out.println("varyVectorPtr.vector_pushBack != true"); + System.exit(0); + } + //assert(status); + } + + return nodePtr; + } + + + /* ============================================================================= + * adtree_make + * -- Records in dataPtr will get rearranged + * ============================================================================= + */ + public void + adtree_make (Data dataPtr) + { + int numRecord = dataPtr.numRecord; + numVar = dataPtr.numVar; + numRecord = dataPtr.numRecord; + dataPtr.data_sort(0, numRecord, 0); + rootNodePtr = makeNode(-1, -1, 0, numRecord, dataPtr); + } + + + /* ============================================================================= + * getCount + * ============================================================================= + */ + public int + getCount (AdtreeNode nodePtr, + int i, + int q, + Vector_t queryVectorPtr, + int lastQueryIndex) + { + if (nodePtr == null) { + return 0; + } + + int nodeIndex = nodePtr.index; + if (nodeIndex >= lastQueryIndex) { + return nodePtr.count; + } + + int count = 0; + + Query queryPtr = (Query)(queryVectorPtr.vector_at(q)); + + //query_t* queryPtr = (query_t*)vector_at(queryVectorPtr, q); + if (queryPtr != null) { + return nodePtr.count; + } + int queryIndex = queryPtr.index; + if(queryIndex > lastQueryIndex) { + System.out.println("Assert failed"); + System.exit(0); + } + //assert(queryIndex <= lastQueryIndex); + Vector_t varyVectorPtr = nodePtr.varyVectorPtr; + //vector_t* varyVectorPtr = nodePtr.varyVectorPtr; + AdtreeVary varyPtr = (AdtreeVary)(varyVectorPtr.vector_at((queryIndex - nodeIndex - 1))); + //adtree_vary_t* varyPtr = + // (adtree_vary_t*)vector_at(varyVectorPtr, + // (queryIndex - nodeIndex - 1)); + //assert(varyPtr); + + int queryValue = queryPtr.value; + + if (queryValue == varyPtr.mostCommonValue) { + + /* + * We do not explicitly store the counts for the most common value. + * We can calculate it by finding the count of the query without + * the current (superCount) and subtracting the count for the + * query with the current toggled (invertCount). + */ + int numQuery = queryVectorPtr.vector_getSize(); + Vector_t superQueryVectorPtr = Vector_t.vector_alloc(numQuery - 1); + //vector_t* superQueryVectorPtr = PVECTOR_ALLOC(numQuery - 1); //MEMORY ALLOACATED FROM THREAD POOL + //assert(superQueryVectorPtr); + + //int qq; + for (int qq = 0; qq < numQuery; qq++) { + if (qq != q) { + boolean status = superQueryVectorPtr.vector_pushBack( + queryVectorPtr.vector_at(qq)); + //assert(status); + } + } + int superCount = adtree_getCount(superQueryVectorPtr); + + superQueryVectorPtr.vector_free(); + //PVECTOR_FREE(superQueryVectorPtr); + + int invertCount; + if (queryValue == 0) { + queryPtr.value = 1; + invertCount = getCount(nodePtr, + i, + q, + queryVectorPtr, + lastQueryIndex); + queryPtr.value = 0; + } else { + queryPtr.value = 0; + invertCount = getCount(nodePtr, + i, + q, + queryVectorPtr, + lastQueryIndex); + queryPtr.value = 1; + } + count += superCount - invertCount; + + } else { + + if (queryValue == 0) { + count += getCount(varyPtr.zeroNodePtr, + (i + 1), + (q + 1), + queryVectorPtr, + lastQueryIndex); + } else if (queryValue == 1) { + count += getCount(varyPtr.oneNodePtr, + (i + 1), + (q + 1), + queryVectorPtr, + lastQueryIndex); + } else { /* QUERY_VALUE_WILDCARD */ + /* +#if 0 + count += getCount(varyPtr.zeroNodePtr, + (i + 1), + (q + 1), + queryVectorPtr, + lastQueryIndex); + count += getCount(varyPtr.oneNodePtr, + (i + 1), + (q + 1), + queryVectorPtr, + lastQueryIndex, + adtreePtr); +#else + assert(0); // catch bugs in learner +#endif + */ + } + + } + + return count; + } + + + /* ============================================================================= + * adtree_getCount + * -- queryVector must consist of queries sorted by id + * ============================================================================= + */ + public int + adtree_getCount (Vector_t queryVectorPtr) + { + //AdtreeNode rootNodePtr = adtreePtr.rootNodePtr; + if (rootNodePtr == null) { + return 0; + } + + int lastQueryIndex = -1; + int numQuery = queryVectorPtr.vector_getSize(); + if (numQuery > 0) { + Query lastQueryPtr = (Query)(queryVectorPtr.vector_at(numQuery - 1)); + //query_t* lastQueryPtr = (query_t*)vector_at(queryVectorPtr, (numQuery - 1)); + lastQueryIndex = lastQueryPtr.index; + } + + return getCount(rootNodePtr, + -1, + 0, + queryVectorPtr, + lastQueryIndex); + } + + + /* ############################################################################# + * TEST_ADTREE + * ############################################################################# + */ + /* +#ifdef TEST_ADTREE + +#include +#include "timer.h" + + static void printNode (adtree_node_t* nodePtr); + static void printVary (adtree_vary_t* varyPtr); + + boolean global_doPrint = FALSE; + + + static void + printData (Data* dataPtr) + { + int numVar = dataPtr.numVar; + int numRecord = dataPtr.numRecord; + + int r; + for (r = 0; r < numRecord; r++) { + printf("%4li: ", r); + char* record = data_getRecord(dataPtr, r); + assert(record); + int v; + for (v = 0; v < numVar; v++) { + printf("%li", (int)record[v]); + } + puts(""); + } + } + + + static void + printNode (adtree_node_t* nodePtr) + { + if (nodePtr) { + printf("[node] index=%li value=%li count=%li\n", + nodePtr.index, nodePtr.value, nodePtr.count); + vector_t* varyVectorPtr = nodePtr.varyVectorPtr; + int v; + int numVary = vector_getSize(varyVectorPtr); + for (v = 0; v < numVary; v++) { + adtree_vary_t* varyPtr = (adtree_vary_t*)vector_at(varyVectorPtr, v); + printVary(varyPtr); + } + } + puts("[up]"); + } + + + static void + printVary (adtree_vary_t* varyPtr) + { + if (varyPtr) { + printf("[vary] index=%li\n", varyPtr.index); + printNode(varyPtr.zeroNodePtr); + printNode(varyPtr.oneNodePtr); + } + puts("[up]"); + } + + + static void + printAdtree (adtree_t* adtreePtr) + { + printNode(adtreePtr.rootNodePtr); + } + + + static void + printQuery (vector_t* queryVectorPtr) + { + printf("["); + int q; + int numQuery = vector_getSize(queryVectorPtr); + for (q = 0; q < numQuery; q++) { + query_t* queryPtr = (query_t*)vector_at(queryVectorPtr, q); + printf("%li:%li ", queryPtr.index, queryPtr.value); + } + printf("]"); + } + + + static int + countData (Data* dataPtr, vector_t* queryVectorPtr) + { + int count = 0; + int numQuery = vector_getSize(queryVectorPtr); + + int r; + int numRecord = dataPtr.numRecord; + for (r = 0; r < numRecord; r++) { + char* record = data_getRecord(dataPtr, r); + boolean isMatch = TRUE; + int q; + for (q = 0; q < numQuery; q++) { + query_t* queryPtr = (query_t*)vector_at(queryVectorPtr, q); + int queryValue = queryPtr.value; + if ((queryValue != QUERY_VALUE_WILDCARD) && + ((char)queryValue) != record[queryPtr.index]) + { + isMatch = FALSE; + break; + } + } + if (isMatch) { + count++; + } + } + + return count; + } + + + static void + testCount (adtree_t* adtreePtr, + Data* dataPtr, + vector_t* queryVectorPtr, + int index, + int numVar) + { + if (index >= numVar) { + return; + } + + int count1 = adtree_getCount(adtreePtr, queryVectorPtr); + int count2 = countData(dataPtr, queryVectorPtr); + if (global_doPrint) { + printQuery(queryVectorPtr); + printf(" count1=%li count2=%li\n", count1, count2); + fflush(stdout); + } + assert(count1 == count2); + + query_t query; + + int i; + for (i = 1; i < numVar; i++) { + query.index = index + i; + boolean status = vector_pushBack(queryVectorPtr, (void*)&query); + assert(status); + + query.value = 0; + testCount(adtreePtr, dataPtr, queryVectorPtr, query.index, numVar); + + query.value = 1; + testCount(adtreePtr, dataPtr, queryVectorPtr, query.index, numVar); + + vector_popBack(queryVectorPtr); + } + } + + + static void + testCounts (adtree_t* adtreePtr, Data* dataPtr) + { + int numVar = dataPtr.numVar; + vector_t* queryVectorPtr = vector_alloc(numVar); + int v; + for (v = -1; v < numVar; v++) { + testCount(adtreePtr, dataPtr, queryVectorPtr, v, dataPtr.numVar); + } + vector_free(queryVectorPtr); + } + + + static void + test (int numVar, int numRecord) + { + random_t* randomPtr = random_alloc(); + Data* dataPtr = data_alloc(numVar, numRecord, randomPtr); + assert(dataPtr); + data_generate(dataPtr, 0, 10, 10); + if (global_doPrint) { + printData(dataPtr); + } + + Data* copyDataPtr = data_alloc(numVar, numRecord, randomPtr); + assert(copyDataPtr); + data_copy(copyDataPtr, dataPtr); + + adtree_t* adtreePtr = adtree_alloc(); + assert(adtreePtr); + + TIMER_T start; + TIMER_READ(start); + + adtree_make(adtreePtr, copyDataPtr); + + TIMER_T stop; + TIMER_READ(stop); + + printf("%lf\n", TIMER_DIFF_SECONDS(start, stop)); + + if (global_doPrint) { + printAdtree(adtreePtr); + } + + testCounts(adtreePtr, dataPtr); + + adtree_free(adtreePtr); + random_free(randomPtr); + data_free(dataPtr); + } + + + int + main () + { + puts("Starting..."); + + puts("Test 1:"); + test(3, 8); + + puts("Test 2:"); + test(4, 64); + + puts("Test 3:"); + test(8, 256); + + puts("Test 4:"); + test(12, 256); + + puts("Test 5:"); + test(48, 1024); + + puts("All tests passed."); + + return 0; + } + + +#endif // TEST_ADTREE + */ + +} +/* ============================================================================= + * + * End of adtree.c + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/AdtreeNode.java b/Robust/src/Benchmarks/SingleTM/Bayes/AdtreeNode.java new file mode 100644 index 00000000..3092fc14 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/AdtreeNode.java @@ -0,0 +1,37 @@ +public class AdtreeNode { + int index; + int value; + int count; + Vector_t varyVectorPtr; + + public AdtreeNode() { + + } + + /* ============================================================================= + * allocNode + * ============================================================================= + */ + public static AdtreeNode + allocNode (int index) + { + AdtreeNode nodePtr = new AdtreeNode(); + //adtree_node_t* nodePtr; + + //nodePtr = (adtree_node_t*)malloc(sizeof(adtree_node_t)); + if (nodePtr != null) { + //nodePtr.varyVectorPtr = vector_alloc(1); + nodePtr.varyVectorPtr = Vector_t.vector_alloc(1); + if (nodePtr.varyVectorPtr == null) { + nodePtr = null; + //free(nodePtr); + return null; + } + nodePtr.index = index; + nodePtr.value = -1; + nodePtr.count = -1; + } + + return nodePtr; + } +} diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/AdtreeVary.java b/Robust/src/Benchmarks/SingleTM/Bayes/AdtreeVary.java new file mode 100644 index 00000000..f4bbfe46 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/AdtreeVary.java @@ -0,0 +1,32 @@ +public class AdtreeVary { + int index; + int mostCommonValue; + AdtreeNode zeroNodePtr; + AdtreeNode oneNodePtr; + + public AdtreeVary() { + + } + + /* ============================================================================= + * allocVary + * ============================================================================= + */ + public AdtreeVary + allocVary (int index) + { + AdtreeVary varyPtr= new AdtreeVary(); + //adtree_vary_t* varyPtr; + + //varyPtr = (adtree_vary_t*)malloc(sizeof(adtree_vary_t)); + if (varyPtr != null) { + varyPtr.index = index; + varyPtr.mostCommonValue = -1; + varyPtr.zeroNodePtr = null; + varyPtr.oneNodePtr = null; + } + + return varyPtr; + } + +} diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Bayes.java b/Robust/src/Benchmarks/SingleTM/Bayes/Bayes.java new file mode 100644 index 00000000..713b310c --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Bayes.java @@ -0,0 +1,419 @@ +/* ============================================================================= + * + * bayes.java + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * Ported to Java + * Author: Alokika Dash + * + * ============================================================================= + * + * For the license of bayes/sort.h and bayes/sort.c, please see the header + * of the files. + * + * ------------------------------------------------------------------------ + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * 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. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * * Neither the name of Stanford 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 STANFORD UNIVERSITY ``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 STANFORD UNIVERSITY 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. + * + * ============================================================================= + */ + +#define PARAM_DEFAULT_QUALITY 1.0f +#define PARAM_EDGE 101 +#define PARAM_INSERT 105 +#define PARAM_NUMBER 110 +#define PARAM_PERCENT 112 +#define PARAM_RECORD 114 +#define PARAM_SEED 115 +#define PARAM_THREAD 116 +#define PARAM_VAR 118 + +#define PARAM_DEFAULT_EDGE -1 +#define PARAM_DEFAULT_INSERT 1 +#define PARAM_DEFAULT_NUMBER 4 +#define PARAM_DEFAULT_PERCENT 10 +#define PARAM_DEFAULT_RECORD 4096 +#define PARAM_DEFAULT_SEED 1 +#define PARAM_DEFAULT_THREAD 1 +#define PARAM_DEFAULT_VAR 32 + +public class Bayes extends Thread { + public int[] global_params; /* 256 = ascii limit */ + public int global_maxNumEdgeLearned; + public int global_insertPenalty; + public float global_operationQualityFactor; + + /* Number of threads */ + int numThread; + + /* thread id */ + int myId; + + /* Global learn pointer */ + Learner learnerPtr; + + public Bayes() { + global_params = new int[256]; + global_maxNumEdgeLearned = PARAM_DEFAULT_EDGE; + global_insertPenalty = PARAM_DEFAULT_INSERT; + global_operationQualityFactor = PARAM_DEFAULT_QUALITY; + } + + public Bayes(int numThread, int myId, Learner learnerPtr) { + this.numThread = numThread; + this.myId = myId; + this.learnerPtr = learnerPtr; + } + + + /* ============================================================================= + * displayUsage + * ============================================================================= + */ + public void + displayUsage () + { + System.out.println("Usage: ./Bayes.bin [options]"); + System.out.println(" e Max [e]dges learned per variable "); + System.out.println(" i Edge [i]nsert penalty "); + System.out.println(" n Max [n]umber of parents "); + System.out.println(" p [p]ercent chance of parent "); + System.out.println(" q Operation [q]uality factor "); + System.out.println(" r Number of [r]ecords "); + System.out.println(" s Random [s]eed "); + System.out.println(" t Number of [t]hreads "); + System.out.println(" v Number of [v]ariables "); + System.exit(1); + } + + + /* ============================================================================= + * setDefaultParams + * ============================================================================= + */ + public void + setDefaultParams () + { + global_params[PARAM_EDGE] = PARAM_DEFAULT_EDGE; + global_params[PARAM_INSERT] = PARAM_DEFAULT_INSERT; + global_params[PARAM_NUMBER] = PARAM_DEFAULT_NUMBER; + global_params[PARAM_PERCENT] = PARAM_DEFAULT_PERCENT; + global_params[PARAM_RECORD] = PARAM_DEFAULT_RECORD; + global_params[PARAM_SEED] = PARAM_DEFAULT_SEED; + global_params[PARAM_THREAD] = PARAM_DEFAULT_THREAD; + global_params[PARAM_VAR] = PARAM_DEFAULT_VAR; + } + + + /* ============================================================================= + * parseArgs + * ============================================================================= + */ + public static void + parseArgs (String[] args, Bayes b) + { + int i = 0; + String arg; + b.setDefaultParams(); + while(i < args.length && args[i].startsWith("-")) { + arg = args[i++]; + //check options + if(arg.equals("-e")) { + if(i < args.length) { + b.global_params[PARAM_EDGE] = new Integer(args[i++]).intValue(); + } + } else if(arg.equals("-i")) { + if (i < args.length) { + b.global_params[PARAM_INSERT] = new Integer(args[i++]).intValue(); + } + } else if (arg.equals("-n")) { + if (i < args.length) { + b.global_params[PARAM_NUMBER] = new Integer(args[i++]).intValue(); + } + } else if (arg.equals("-p")) { + if (i < args.length) { + b.global_params[PARAM_PERCENT] = new Integer(args[i++]).intValue(); + } + } else if (arg.equals("-r")) { + if (i < args.length) { + b.global_params[PARAM_RECORD] = new Integer(args[i++]).intValue(); + } + } else if (arg.equals("-s")) { + if (i < args.length) { + b.global_params[PARAM_SEED] = new Integer(args[i++]).intValue(); + } + } else if (arg.equals("-t")) { + if (i < args.length) { + b.global_params[PARAM_THREAD] = new Integer(args[i++]).intValue(); + } + } else if (arg.equals("-v")) { + if (i < args.length) { + b.global_params[PARAM_VAR] = new Integer(args[i++]).intValue(); + } + } else if(arg.equals("-h")) { + b.displayUsage(); + } + } + + if (b.global_params[PARAM_THREAD] == 0) { + b.displayUsage(); + } + } + + + /* ============================================================================= + * score + * ============================================================================= + */ + public float + score (Net netPtr, Adtree adtreePtr) + { + /* + * Create dummy data structures to conform to learner_score assumptions + */ + + Data dataPtr = Data.data_alloc(1, 1, null); + + Learner learnerPtr = Learner.learner_alloc(dataPtr, adtreePtr, 1); + + //learner_t* learnerPtr = learner_alloc(dataPtr, adtreePtr, 1); + + Net tmpNetPtr = learnerPtr.netPtr; + learnerPtr.netPtr = netPtr; + + float score = learnerPtr.learner_score(); + + learnerPtr.netPtr = tmpNetPtr; + learnerPtr.learner_free(); + dataPtr.data_free(); + + return score; + } + + + /** + * parallel execution + **/ + public void run() { + /* + Barrier.enterBarrier(); + Learner.learner_run(myId, numThread, learnerPtr); + Barrier.enterBarrier(); + */ + } + + + /* ============================================================================= + * main + * ============================================================================= + */ + + public static void main(String[] args) { + /* + * Initialization + */ + Bayes b = new Bayes(); + Bayes.parseArgs(args, b); + int numThread = b.global_params[PARAM_THREAD]; + int numVar = b.global_params[PARAM_VAR]; + int numRecord = b.global_params[PARAM_RECORD]; + int randomSeed = b.global_params[PARAM_SEED]; + int maxNumParent = b.global_params[PARAM_NUMBER]; + int percentParent = b.global_params[PARAM_PERCENT]; + b.global_insertPenalty = b.global_params[PARAM_INSERT]; + b.global_maxNumEdgeLearned = b.global_params[PARAM_EDGE]; + //SIM_GET_NUM_CPU(numThread); + //TM_STARTUP(numThread); + //P_MEMORY_STARTUP(numThread); + + /* Initiate Barriers */ + //Barrier.setBarrier(numThread); + + Bayes[] binit = new Bayes[numThread]; + + System.out.println("Random seed \n" + randomSeed); + System.out.println("Number of vars \n" + numVar); + System.out.println("Number of records \n" + numRecord); + System.out.println("Max num parents \n" + maxNumParent); + System.out.println("%% chance of parent \n" + percentParent); + System.out.println("Insert penalty \n" + b.global_insertPenalty); + System.out.println("Max num edge learned / var \n" + b.global_maxNumEdgeLearned); + System.out.println("Operation quality factor \n" + b.global_operationQualityFactor); + + /* + * Generate data + */ + + System.out.println("Generating data... "); + + Random randomPtr = new Random(); + randomPtr.random_alloc(); + randomPtr.random_seed(randomSeed); + //random_t* randomPtr = random_alloc(); + //assert(randomPtr); + //random_seed(randomPtr, randomSeed); + + Data dataPtr = Data.data_alloc(numVar, numRecord, randomPtr); + + //Data* dataPtr = data_alloc(numVar, numRecord, randomPtr); + //assert(dataPtr); + Net netPtr = dataPtr.data_generate(-1, maxNumParent, percentParent); + //Net* netPtr = data_generate(dataPtr, -1, maxNumParent, percentParent); + System.out.println("done."); + //puts("done."); + //fflush(stdout); + + /* + * Generate adtree + */ + + Adtree adtreePtr = Adtree.adtree_alloc(); + //adtree_t* adtreePtr = adtree_alloc(); + //assert(adtreePtr); + + System.out.println("Generating adtree... "); + //fflush(stdout); + + //TIMER_T adtreeStartTime; + //TIMER_READ(adtreeStartTime); + + adtreePtr.adtree_make(dataPtr); + + //TIMER_T adtreeStopTime; + //TIMER_READ(adtreeStopTime); + + System.out.println("done."); + //fflush(stdout); + //System.out.println("Adtree time = %f\n", + // TIMER_DIFF_SECONDS(adtreeStartTime, adtreeStopTime)); + //fflush(stdout); + + /* + * Score original network + */ + + float actualScore = b.score(netPtr, adtreePtr); + netPtr.net_free(); + + /* + * Learn structure of Bayesian network + */ + + //START FROM HERE + Learner learnerPtr = Learner.learner_alloc(dataPtr, adtreePtr, numThread); + //learner_t* learnerPtr = learner_alloc(dataPtr, adtreePtr, numThread); + //assert(learnerPtr); + dataPtr.data_free(); /* save memory */ + + System.out.println("Learning structure..."); + //fflush(stdout); + + /* Create and Start Threads */ + for(int i = 1; i numRecord * numVar) { + System.out.println("value should be != DATA_INIT in data_generate()"); + System.exit(0); + } + //assert(record <= (dataPtr.records + numRecord * numVar)); + } + + /* + * Clean up + */ + + doneBitmapPtr.bitmap_free(); + orderedBitmapPtr.bitmap_free(); + dependencyVectorPtr.vector_free(); + workQueuePtr.queue_free(); + order = null; + //bitmap_free(doneBitmapPtr); + //bitmap_free(orderedBitmapPtr); + //vector_free(dependencyVectorPtr); + //queue_free(workQueuePtr); + //free(order); + for (v = 0; v < numVar; v++) { + thresholdsTable[v] = null; + //free(thresholdsTable[v]); + } + thresholdsTable = null; + //free(thresholdsTable); + + return netPtr; + } + + + /* ============================================================================= + * data_getRecord + * -- Returns null if invalid index + * ============================================================================= + */ + /* + char* + data_getRecord (data_t* dataPtr, int index) + { + if (index < 0 || index >= (dataPtr.numRecord)) { + return null; + } + + return &dataPtr.records[index * dataPtr.numVar]; + } + */ + + + /* ============================================================================= + * data_copy + * -- Returns false on failure + * ============================================================================= + */ + public static boolean + data_copy (Data dstPtr, Data srcPtr) + { + int numDstDatum = dstPtr.numVar * dstPtr.numRecord; + int numSrcDatum = srcPtr.numVar * srcPtr.numRecord; + if (numDstDatum != numSrcDatum) { + dstPtr.records = null; + //free(dstPtr.records); + dstPtr.records = new char[numSrcDatum]; + //dstPtr.records = (char*)calloc(numSrcDatum, sizeof(char)); + if (dstPtr.records == null) { + return false; + } + } + + dstPtr.numVar = srcPtr.numVar; + dstPtr.numRecord = srcPtr.numRecord; + for(int i=0; i 0) { + unsigned char u1 = (unsigned char)*s1++; + unsigned char u2 = (unsigned char)*s2++; + if (u1 != u2) { + return (u1 - u2); + } + } + + return 0; + } + */ + + + /* ============================================================================= + * data_sort + * -- In place + * ============================================================================= + */ + public void + data_sort (int start, + int num, + int offset) + { + if((start < 0) || (start > numRecord)) + System.out.println("start: Assert failed in data_sort"); + if((num < 0) || (num > numRecord)) + System.out.println("num: Assert failed in data_sort"); + if((start + num < 0) || (start + num > numRecord)) + System.out.println("start + num: Assert failed in data_sort"); + + //assert(start >= 0 && start <= dataPtr.numRecord); + //assert(num >= 0 && num <= dataPtr.numRecord); + //assert(start + num >= 0 && start + num <= dataPtr.numRecord); + + //int numVar = dataPtr.numVar; + + //FIXME + //Sort.sort((dataPtr.records + (start * numVar)), + Sort.sort(records, + start * numVar, + num, + numVar, + numVar, + offset); + } + + + /* ============================================================================= + * data_findSplit + * -- Call data_sort first with proper start, num, offset + * -- Returns number of zeros in offset column + * ============================================================================= + */ + public int + data_findSplit (int start, int num, int offset) + { + int low = start; + int high = start + num - 1; + + //int numVar = dataPtr.numVar; + //char* records = dataPtr.records; + + while (low <= high) { + int mid = (low + high) / 2; + if (records[numVar * mid + offset] == 0) { + low = mid + 1; + } else { + high = mid - 1; + } + } + + return (low - start); + } +} + +/* ============================================================================= + * + * End of data.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/FindBestTaskArg.java b/Robust/src/Benchmarks/SingleTM/Bayes/FindBestTaskArg.java new file mode 100644 index 00000000..cbeb4059 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/FindBestTaskArg.java @@ -0,0 +1,17 @@ +public class FindBestTaskArg { + int toId; + Learner learnerPtr; + Query queries; + Vector_t queryVectorPtr; + Vector_t parentQueryVectorPtr; + int numTotalParent; + float basePenalty; + float baseLogLikelihood; + BitMap bitmapPtr; + Queue workQueuePtr; + Vector_t aQueryVectorPtr; + Vector_t bQueryVectorPtr; + + public FindBestTaskArg() { + } +} diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/IntList.java b/Robust/src/Benchmarks/SingleTM/Bayes/IntList.java new file mode 100644 index 00000000..a41d6d78 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/IntList.java @@ -0,0 +1,329 @@ +/* ============================================================================= + * + * Intlist.java + * -- Sorted singly linked list + * -- Options: -DLIST_NO_DUPLICATES (default: allow duplicates) + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * + * Ported to Java June 2006, Alokika Dash + * adash@uci.edu + * University of California, Irvine + * + * ============================================================================= + * + * For the license of bayes/sort.h and bayes/sort.c, please see the header + * of the files. + * + * ------------------------------------------------------------------------ + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * 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. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * * Neither the name of Stanford 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 STANFORD UNIVERSITY ``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 STANFORD UNIVERSITY 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. + * + * ============================================================================= + */ + +public class IntList { + public IntListNode head; + public int size; + public IntList() { + + } + /* ============================================================================= + * list_iter_reset + * ============================================================================= + */ + public void + list_iter_reset (IntListNode itPtr) + { + itPtr = head; + } + + /* ============================================================================= + * list_iter_hasNext + * ============================================================================= + */ + public boolean + list_iter_hasNext (IntListNode itPtr) + { + return ((itPtr.nextPtr != null) ? true : false); + } + + + /* ============================================================================= + * list_iter_next + * ============================================================================= + */ + public int + list_iter_next (IntListNode itPtr) + { + //itPtr = itPtr.nextPtr; + return itPtr.dataPtr; + } + + /* ============================================================================= + * allocNode + * -- Returns null on failure + * ============================================================================= + */ + public IntListNode + allocNode (int dataPtr) + { + IntListNode nodePtr = new IntListNode(); + if (nodePtr == null) { + return null; + } + + nodePtr.dataPtr = dataPtr; + nodePtr.nextPtr = null; + + return nodePtr; + } + + /* ============================================================================= + * list_alloc + * -- If 'compare' function return null, compare data pointer addresses + * -- Returns null on failure + * ============================================================================= + */ + public static IntList list_alloc () + { + IntList listPtr = new IntList(); + if (listPtr == null) { + System.out.println("Cannot allocate IntList"); + return null; + } + + listPtr.head = new IntListNode(); + listPtr.head.dataPtr = 0; + listPtr.head.nextPtr = null; + listPtr.size = 0; + + return listPtr; + } + + + /* ============================================================================= + * freeNode + * ============================================================================= + */ + public void + freeNode (IntListNode nodePtr) + { + nodePtr = null; + //free(nodePtr); + } + + + /* ============================================================================= + * freeList + * ============================================================================= + */ + public void + freeList (IntListNode nodePtr) + { + if(nodePtr != null) { + freeList(nodePtr.nextPtr); + freeNode(nodePtr); + } + } + + /* ============================================================================= + * list_free + * ============================================================================= + */ + public void + list_free () + { + freeList(head.nextPtr); + } + + /* ============================================================================= + * list_isEmpty + * -- Return true if list is empty, else false + * ============================================================================= + */ + public boolean + list_isEmpty () + { + return (head.nextPtr == null); + } + + + /* ============================================================================= + * list_getSize + * -- Returns the size of the list + * ============================================================================= + */ + public int + list_getSize () + { + return size; + } + + /* ============================================================================= + * findPrevious + * ============================================================================= + */ + public IntListNode + findPrevious (int dataPtr) + { + IntListNode prevPtr = head; + IntListNode nodePtr = prevPtr.nextPtr; + + for (; nodePtr != null; nodePtr = nodePtr.nextPtr) { + if (compareId(nodePtr.dataPtr, dataPtr) >= 0) { + return prevPtr; + } + prevPtr = nodePtr; + } + + return prevPtr; + } + + + /* ============================================================================= + * list_insert + * -- Return true on success, else false + * ============================================================================= + */ + public boolean + list_insert (int dataPtr) + { + IntListNode prevPtr; + IntListNode nodePtr; + IntListNode currPtr; + + prevPtr = findPrevious(dataPtr); + currPtr = prevPtr.nextPtr; + +#ifdef LIST_NO_DUPLICATES + if ((currPtr != null) && + compareId(currPtr.dataPtr, dataPtr) == 0) { + return false; + } +#endif + + nodePtr = allocNode(dataPtr); + if (nodePtr == null) { + return false; + } + + nodePtr.nextPtr = currPtr; + prevPtr.nextPtr = nodePtr; + size++; + + return true; + } + + /* ================================= + * compareId + * ================================= + */ + public static int compareId(int a, int b) { + return (a - b); + } + + + /* ============================================================================= + * list_remove + * -- Returns TRUE if successful, else FALSE + * ============================================================================= + */ + public boolean + list_remove (int dataPtr) + { + IntListNode prevPtr; + IntListNode nodePtr; + + prevPtr = findPrevious(dataPtr); + + nodePtr = prevPtr.nextPtr; + if ((nodePtr != null) && + (compareId(nodePtr.dataPtr, dataPtr) == 0)) + { + prevPtr.nextPtr = nodePtr.nextPtr; + nodePtr.nextPtr = null; + freeNode(nodePtr); + size--; + if(size < 0) { + System.out.println("Assert failed: size cannot be negative in list_remove()"); + System.exit(0); + } + + return true; + } + + return false; + } + + + /* =========================== + * Test IntList + * ========================== + */ + /* + public static void main(String[] args) { + testList mylist = testList.list_alloc(); + mylist.list_insert(1); + mylist.list_insert(2); + mylist.list_insert(3); + mylist.list_insert(4); + mylist.list_insert(5); + mylist.list_insert(6); + mylist.list_insert(7); + + testList testmyList = mylist; + testListNode it = testmyList.head; + testmyList.list_iter_reset(it); + System.out.println("mylist.head= " + mylist.head + " it= " + it); + while(testmyList.list_iter_hasNext(it)){ + it = it.nextPtr; + int tmp = testmyList.list_iter_next(it); + System.out.println("tmp= " + tmp); + } + System.out.println("mylist.head= " + mylist.head + " it= " + it); + System.out.println("testmyList.list_getSize()= " + testmyList.list_getSize()); + } + */ +} + +/* ============================================================================= + * + * End of Intlist.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/IntListNode.java b/Robust/src/Benchmarks/SingleTM/Bayes/IntListNode.java new file mode 100644 index 00000000..bb66db9a --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/IntListNode.java @@ -0,0 +1,8 @@ +public class IntListNode { + public int dataPtr; + public IntListNode nextPtr; + + public IntListNode() { + + } +} diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/IntVector.java b/Robust/src/Benchmarks/SingleTM/Bayes/IntVector.java new file mode 100644 index 00000000..b07a76c8 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/IntVector.java @@ -0,0 +1,155 @@ +public class IntVector { + int size; + int capacity; + int[] elements; + QuickSort qsort; + + public IntVector() { + qsort = new QuickSort(); + } + + /* ============================================================================= + * Vector_alloc + * -- Returns null if failed + * ============================================================================= + */ + public static IntVector vector_alloc (int initCapacity) { + int capacity = Math.imax(initCapacity, 1); + IntVector vectorPtr = new IntVector(); + if(vectorPtr != null) { + vectorPtr.size = 0; + vectorPtr.capacity = capacity; + vectorPtr.elements = new int[capacity]; + if(vectorPtr.elements == null) + return null; + } + return vectorPtr; + } + + /* ============================================================================= + * Vector_free + * ============================================================================= + */ + public void + vector_free () + { + elements = null; + } + + /* ============================================================================= + * Vector_at + * -- Returns null if failed + * ============================================================================= + */ + public int vector_at (int i) { + if ((i < 0) || (i >= size)) { + System.out.println("Illegal Vector.element\n"); + return -1; + } + return (elements[i]); + } + + + /* ============================================================================= + * Vector_pushBack + * -- Returns false if fail, else true + * ============================================================================= + */ + public boolean vector_pushBack (int dataPtr) { + if (size == capacity) { + int newCapacity = capacity * 2; + int[] newElements = new int[newCapacity]; + + //void** newElements = (void**)malloc(newCapacity * sizeof(void*)); + if (newElements == null) { + return false; + } + capacity = newCapacity; + for (int i = 0; i < size; i++) { + newElements[i] = elements[i]; + } + elements = null; + elements = newElements; + } + + elements[size++] = dataPtr; + + return true; + } + + /* ============================================================================= + * Vector_popBack + * -- Returns null if fail, else returns last element + * ============================================================================= + */ + public int + vector_popBack () + { + if (size < 1) { + return 0; + } + + return (elements[--(size)]); + } + + /* ============================================================================= + * Vector_getSize + * ============================================================================= + */ + public int + vector_getSize () + { + return (size); + } + + /* ============================================================================= + * Vector_clear + * ============================================================================= + */ + public void + vector_clear () + { + size = 0; + } + + /* ============================================================================= + * Vector_sort + * ============================================================================= + */ + public void + vector_sort () + { + //qsort.sort(elements, 0, (elements.length - 1)); + //qsort(elements, size, 4, compare); + } + + /* ============================================================================= + * Vector_copy + * ============================================================================= + */ + public static boolean + vector_copy (IntVector dstVectorPtr, IntVector srcVectorPtr) + { + int dstCapacity = dstVectorPtr.capacity; + int srcSize = srcVectorPtr.size; + if (dstCapacity < srcSize) { + int srcCapacity = srcVectorPtr.capacity; + int[] elements = new int[srcCapacity]; + + if (elements == null) { + return false; + } + dstVectorPtr.elements = null; + dstVectorPtr.elements = elements; + dstVectorPtr.capacity = srcCapacity; + } + + for(int i = 0; i< srcSize; i++) { + dstVectorPtr.elements[i] = srcVectorPtr.elements[i]; + } + + dstVectorPtr.size = srcSize; + + return true; + } +} diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Learner.java b/Robust/src/Benchmarks/SingleTM/Bayes/Learner.java new file mode 100644 index 00000000..0ae389fc --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Learner.java @@ -0,0 +1,1666 @@ +/* ============================================================================= + * + * learner.java + * -- Learns structure of Bayesian net from data + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * + * ============================================================================= + * + * The penalized log-likelihood score (Friedman & Yahkani, 1996) is used to + * evaluated the "goodness" of a Bayesian net: + * + * M n_j + * --- --- --- + * -N_params * ln(R) / 2 + R > > > P((a_j = v), X_j) ln P(a_j = v | X_j) + * --- --- --- + * j=1 X_j v=1 + * + * Where: + * + * N_params total number of parents across all variables + * R number of records + * M number of variables + * X_j parents of the jth variable + * n_j number of attributes of the jth variable + * a_j attribute + * + * The second summation of X_j varies across all possible assignments to the + * values of the parents X_j. + * + * In the code: + * + * "local log likelihood" is P((a_j = v), X_j) ln P(a_j = v | X_j) + * "log likelihood" is everything to the right of the '+', i.e., "R ... X_j)" + * "base penalty" is -ln(R) / 2 + * "penalty" is N_params * -ln(R) / 2 + * "score" is the entire expression + * + * For more notes, refer to: + * + * A. Moore and M.-S. Lee. Cached sufficient statistics for efficient machine + * learning with large datasets. Journal of Artificial Intelligence Research 8 + * (1998), pp 67-91. + * + * ============================================================================= + * + * The search strategy uses a combination of local and global structure search. + * Similar to the technique described in: + * + * D. M. Chickering, D. Heckerman, and C. Meek. A Bayesian approach to learning + * Bayesian networks with local structure. In Proceedings of Thirteenth + * Conference on Uncertainty in Artificial Intelligence (1997), pp. 80-89. + * + * ============================================================================= + * + * For the license of bayes/sort.h and bayes/sort.c, please see the header + * of the files. + * + * ------------------------------------------------------------------------ + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * 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. +* +* * Redistributions in binary form must reproduce the above copyright +* notice, this list of conditions and the following disclaimer in +* the documentation and/or other materials provided with the +* distribution. +* +* * Neither the name of Stanford 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 STANFORD UNIVERSITY ``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 STANFORD UNIVERSITY 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. +* +* ============================================================================= +*/ + + +#define CACHE_LINE_SIZE 64 +#define QUERY_VALUE_WILDCARD -1 + +public class Learner { + Adtree adtreePtr; + Net netPtr; + float[] localBaseLogLikelihoods; + float baseLogLikelihood; + LearnerTask[] tasks; + List taskListPtr; + int numTotalParent; + int global_insertPenalty; + int global_maxNumEdgeLearned; + float global_operationQualityFactor; + + public Learner() { +#ifdef TEST_LEARNER + global_maxNumEdgeLearned = -1; + global_insertPenalty = 1; + global_operationQualityFactor = 1.0F; +#endif + } + + /* ============================================================================= + * compareTask + * -- Want greatest score first + * -- For list + * ============================================================================= + */ + /* + static int + compareTask (const void* aPtr, const void* bPtr) + { + learner_task_t* aTaskPtr = (learner_task_t*)aPtr; + learner_task_t* bTaskPtr = (learner_task_t*)bPtr; + float aScore = aTaskPtr.score; + float bScore = bTaskPtr.score; + + if (aScore < bScore) { + return 1; + } else if (aScore > bScore) { + return -1; + } else { + return (aTaskPtr.toId - bTaskPtr.toId); + } + } + */ + + + /* ============================================================================= + * compareQuery + * -- Want smallest ID first + * -- For vector_sort + * ============================================================================= + */ + /* + static int + compareQuery (const void* aPtr, const void* bPtr) + { + query_t* aQueryPtr = (query_t*)(*(void**)aPtr); + query_t* bQueryPtr = (query_t*)(*(void**)bPtr); + + return (aQueryPtr.index - bQueryPtr.index); + } + */ + + + /* ============================================================================= + * learner_alloc + * ============================================================================= + */ + public static Learner + learner_alloc (Data dataPtr, Adtree adtreePtr, int numThread) + { + Learner learnerPtr = new Learner(); + + //learnerPtr = (learner_t*)malloc(sizeof(learner_t)); + if (learnerPtr != null) { + learnerPtr.adtreePtr = adtreePtr; + learnerPtr.netPtr = Net.net_alloc(dataPtr.numVar); + learnerPtr.localBaseLogLikelihoods = new float[dataPtr.numVar]; + learnerPtr.baseLogLikelihood = 0.0f; + learnerPtr.tasks = new LearnerTask[dataPtr.numVar]; + learnerPtr.taskListPtr = List.list_alloc(); + learnerPtr.numTotalParent = 0; + } + + return learnerPtr; + } + + + /* ============================================================================= + * learner_free + * ============================================================================= + */ + public void + //learner_free (learner_t* learnerPtr) + learner_free () + { + taskListPtr.list_free(); + tasks = null; + localBaseLogLikelihoods = null; + netPtr.net_free(); + //free(learnerPtr.tasks); + //free(learnerPtr.localBaseLogLikelihoods); + //net_free(learnerPtr.netPtr); + this = null; + //free(learnerPtr); + } + + + /* ============================================================================= + * computeSpecificLocalLogLikelihood + * -- Query vectors should not contain wildcards + * ============================================================================= + */ + public float + computeSpecificLocalLogLikelihood (Adtree adtreePtr, + Vector_t queryVectorPtr, + Vector_t parentQueryVectorPtr) + { + int count = adtreePtr.adtree_getCount(queryVectorPtr); + if (count == 0) { + return 0.0f; + } + + double probability = (double)count / (double)adtreePtr.numRecord; + int parentCount = adtreePtr.adtree_getCount(parentQueryVectorPtr); + + if(parentCount < count || parentCount <= 0) { + System.out.println("Assert failed for computeSpecificLocalLogLikelihood()"); + System.exit(0); + } + + //assert(parentCount >= count); + //assert(parentCount > 0); + + float fval = (float)(probability * (Math.log((double)count/ (double)parentCount))); + return fval; + } + + + /* ============================================================================= + * createPartition + * ============================================================================= + */ + /* + static void + createPartition (int min, int max, int id, int n, + int* startPtr, int* stopPtr) + { + int range = max - min; + int chunk = MAX(1, ((range + n/2) / n)); // rounded + int start = min + chunk * id; + int stop; + if (id == (n-1)) { + stop = max; + } else { + stop = MIN(max, (start + chunk)); + } + + *startPtr = start; + *stopPtr = stop; + } + */ + + + /* ============================================================================= + * createTaskList + * -- baseLogLikelihoods and taskListPtr are updated + * ============================================================================= + */ + /* + static void + createTaskList (void* argPtr) + { + TM_THREAD_ENTER(); + + int myId = thread_getId(); + int numThread = thread_getNumThread(); + + learner_t* learnerPtr = (learner_t*)argPtr; + list_t* taskListPtr = learnerPtr.taskListPtr; + + boolean status; + + adtree_t* adtreePtr = learnerPtr.adtreePtr; + float* localBaseLogLikelihoods = learnerPtr.localBaseLogLikelihoods; + learner_task_t* tasks = learnerPtr.tasks; + + query_t queries[2]; + vector_t* queryVectorPtr = PVECTOR_ALLOC(2); + assert(queryVectorPtr); + status = vector_pushBack(queryVectorPtr, (void*)&queries[0]); + assert(status); + + query_t parentQuery; + vector_t* parentQueryVectorPtr = PVECTOR_ALLOC(1); + assert(parentQueryVectorPtr); + + int numVar = adtreePtr.numVar; + int numRecord = adtreePtr.numRecord; + float baseLogLikelihood = 0.0; + float penalty = (float)(-0.5 * log((double)numRecord)); // only add 1 edge + + int v; + + int v_start; + int v_stop; + createPartition(0, numVar, myId, numThread, &v_start, &v_stop); + */ + + /* + * Compute base log likelihood for each variable and total base loglikelihood + */ + + /* + for (v = v_start; v < v_stop; v++) { + + float localBaseLogLikelihood = 0.0; + queries[0].index = v; + + queries[0].value = 0; + localBaseLogLikelihood += + computeSpecificLocalLogLikelihood(adtreePtr, + queryVectorPtr, + parentQueryVectorPtr); + + queries[0].value = 1; + localBaseLogLikelihood += + computeSpecificLocalLogLikelihood(adtreePtr, + queryVectorPtr, + parentQueryVectorPtr); + + localBaseLogLikelihoods[v] = localBaseLogLikelihood; + baseLogLikelihood += localBaseLogLikelihood; + + } // foreach variable + + TM_BEGIN(); + float globalBaseLogLikelihood = + TM_SHARED_READ_F(learnerPtr.baseLogLikelihood); + TM_SHARED_WRITE_F(learnerPtr.baseLogLikelihood, + (baseLogLikelihood + globalBaseLogLikelihood)); + TM_END(); + */ + + /* + * For each variable, find if the addition of any edge _to_ it is better + */ + + /* + status = PVECTOR_PUSHBACK(parentQueryVectorPtr, (void*)&parentQuery); + assert(status); + + for (v = v_start; v < v_stop; v++) { + + //Compute base log likelihood for this variable + + queries[0].index = v; + int bestLocalIndex = v; + float bestLocalLogLikelihood = localBaseLogLikelihoods[v]; + + status = PVECTOR_PUSHBACK(queryVectorPtr, (void*)&queries[1]); + assert(status); + + int vv; + for (vv = 0; vv < numVar; vv++) { + + if (vv == v) { + continue; + } + parentQuery.index = vv; + if (v < vv) { + queries[0].index = v; + queries[1].index = vv; + } else { + queries[0].index = vv; + queries[1].index = v; + } + + float newLocalLogLikelihood = 0.0; + + queries[0].value = 0; + queries[1].value = 0; + parentQuery.value = 0; + newLocalLogLikelihood += + computeSpecificLocalLogLikelihood(adtreePtr, + queryVectorPtr, + parentQueryVectorPtr); + + queries[0].value = 0; + queries[1].value = 1; + parentQuery.value = ((vv < v) ? 0 : 1); + newLocalLogLikelihood += + computeSpecificLocalLogLikelihood(adtreePtr, + queryVectorPtr, + parentQueryVectorPtr); + + queries[0].value = 1; + queries[1].value = 0; + parentQuery.value = ((vv < v) ? 1 : 0); + newLocalLogLikelihood += + computeSpecificLocalLogLikelihood(adtreePtr, + queryVectorPtr, + parentQueryVectorPtr); + + queries[0].value = 1; + queries[1].value = 1; + parentQuery.value = 1; + newLocalLogLikelihood += + computeSpecificLocalLogLikelihood(adtreePtr, + queryVectorPtr, + parentQueryVectorPtr); + + if (newLocalLogLikelihood > bestLocalLogLikelihood) { + bestLocalIndex = vv; + bestLocalLogLikelihood = newLocalLogLikelihood; + } + + } // foreach other variable + + PVECTOR_POPBACK(queryVectorPtr); + + if (bestLocalIndex != v) { + float logLikelihood = numRecord * (baseLogLikelihood + + + bestLocalLogLikelihood + - localBaseLogLikelihoods[v]); + float score = penalty + logLikelihood; + learner_task_t* taskPtr = &tasks[v]; + taskPtr.op = OPERATION_INSERT; + taskPtr.fromId = bestLocalIndex; + taskPtr.toId = v; + taskPtr.score = score; + TM_BEGIN(); + status = TMLIST_INSERT(taskListPtr, (void*)taskPtr); + TM_END(); + assert(status); + } + + } // for each variable + + PVECTOR_FREE(queryVectorPtr); + PVECTOR_FREE(parentQueryVectorPtr); + +#ifdef TEST_LEARNER + list_iter_t it; + list_iter_reset(&it, taskListPtr); + while (list_iter_hasNext(&it, taskListPtr)) { + learner_task_t* taskPtr = (learner_task_t*)list_iter_next(&it, taskListPtr); + printf("[task] op=%i from=%li to=%li score=%lf\n", + taskPtr.op, taskPtr.fromId, taskPtr.toId, taskPtr.score); + } +#endif // TEST_LEARNER + + TM_THREAD_EXIT(); + } +*/ + + /* ============================================================================= + * TMpopTask + * -- Returns NULL is list is empty + * ============================================================================= + */ +/* + learner_task_t* + TMpopTask (TM_ARGDECL list_t* taskListPtr) + { + learner_task_t* taskPtr = NULL; + + list_iter_t it; + TMLIST_ITER_RESET(&it, taskListPtr); + if (TMLIST_ITER_HASNEXT(&it, taskListPtr)) { + taskPtr = (learner_task_t*)TMLIST_ITER_NEXT(&it, taskListPtr); + boolean status = TMLIST_REMOVE(taskListPtr, (void*)taskPtr); + assert(status); + } + + return taskPtr; + } + */ + + + /* ============================================================================= + * populateParentQuery + * -- Modifies contents of parentQueryVectorPtr + * ============================================================================= + */ + public void + populateParentQueryVector (Net netPtr, + int id, + Query[] queries, + Vector_t parentQueryVectorPtr) + { + parentQueryVectorPtr.vector_clear(); + + IntList parentIdListPtr = netPtr.net_getParentIdListPtr(id); + IntListNode it = parentIdListPtr.head; + parentIdListPtr.list_iter_reset(it); + while (parentIdListPtr.list_iter_hasNext(it)) { + it = it.nextPtr; + int parentId = parentIdListPtr.list_iter_next(it); + boolean status = parentQueryVectorPtr.vector_pushBack(queries[parentId]); + if(status == false) { + System.out.println("Assert failed: unable to pushBack in queue"); + System.exit(0); + } + } + } + + + /* ============================================================================= + * TMpopulateParentQuery + * -- Modifies contents of parentQueryVectorPtr + * ============================================================================= + */ + /* + static void + TMpopulateParentQueryVector (TM_ARGDECL + net_t* netPtr, + int id, + query_t* queries, + vector_t* parentQueryVectorPtr) + { + vector_clear(parentQueryVectorPtr); + + list_t* parentIdListPtr = net_getParentIdListPtr(netPtr, id); + list_iter_t it; + TMLIST_ITER_RESET(&it, parentIdListPtr); + while (TMLIST_ITER_HASNEXT(&it, parentIdListPtr)) { + int parentId = (int)TMLIST_ITER_NEXT(&it, parentIdListPtr); + boolean status = PVECTOR_PUSHBACK(parentQueryVectorPtr, + (void*)&queries[parentId]); + assert(status); + } + } + */ + + + /* ============================================================================= + * populateQueryVectors + * -- Modifies contents of queryVectorPtr and parentQueryVectorPtr + * ============================================================================= + */ + public void + populateQueryVectors (Net netPtr, + int id, + Query[] queries, + Vector_t queryVectorPtr, + Vector_t parentQueryVectorPtr) + { + populateParentQueryVector(netPtr, id, queries, parentQueryVectorPtr); + + boolean status; + status = Vector_t.vector_copy(queryVectorPtr, parentQueryVectorPtr); + //TODO CHECK ASSERT + //assert(status); + status = queryVectorPtr.vector_pushBack(queries[id]); + //TODO CHECK ASSERT + //assert(status); + queryVectorPtr.vector_sort(); + } + + + /* ============================================================================= + * TMpopulateQueryVectors + * -- Modifies contents of queryVectorPtr and parentQueryVectorPtr + * ============================================================================= + */ + /* + static void + TMpopulateQueryVectors (TM_ARGDECL + net_t* netPtr, + int id, + query_t* queries, + vector_t* queryVectorPtr, + vector_t* parentQueryVectorPtr) + { + TMpopulateParentQueryVector(TM_ARG netPtr, id, queries, parentQueryVectorPtr); + + boolean status; + status = PVECTOR_COPY(queryVectorPtr, parentQueryVectorPtr); + assert(status); + status = PVECTOR_PUSHBACK(queryVectorPtr, (void*)&queries[id]); + assert(status); + PVECTOR_SORT(queryVectorPtr, &compareQuery); + } +*/ + + /* ============================================================================= + * computeLocalLogLikelihoodHelper + * -- Recursive helper routine + * ============================================================================= + */ + public float + computeLocalLogLikelihoodHelper (int i, + int numParent, + Adtree adtreePtr, + Query[] queries, + Vector_t queryVectorPtr, + Vector_t parentQueryVectorPtr) + { + if (i >= numParent) { + return computeSpecificLocalLogLikelihood(adtreePtr, + queryVectorPtr, + parentQueryVectorPtr); + } + + float localLogLikelihood = 0.0f; + + //query_t* parentQueryPtr = vector_at(parentQueryVectorPtr, i); + Query parentQueryPtr = (Query) (parentQueryVectorPtr.vector_at(i)); + int parentIndex = parentQueryPtr.index; + + queries[parentIndex].value = 0; + localLogLikelihood += computeLocalLogLikelihoodHelper((i + 1), + numParent, + adtreePtr, + queries, + queryVectorPtr, + parentQueryVectorPtr); + + queries[parentIndex].value = 1; + localLogLikelihood += computeLocalLogLikelihoodHelper((i + 1), + numParent, + adtreePtr, + queries, + queryVectorPtr, + parentQueryVectorPtr); + + queries[parentIndex].value = QUERY_VALUE_WILDCARD; + + return localLogLikelihood; + } + + + /* ============================================================================= + * computeLocalLogLikelihood + * -- Populate the query vectors before passing as args + * ============================================================================= + */ + public float + computeLocalLogLikelihood (int id, + Adtree adtreePtr, + Net netPtr, + Query[] queries, + Vector_t queryVectorPtr, + Vector_t parentQueryVectorPtr) + { + int numParent = parentQueryVectorPtr.vector_getSize(); + float localLogLikelihood = 0.0f; + + queries[id].value = 0; + localLogLikelihood += computeLocalLogLikelihoodHelper(0, + numParent, + adtreePtr, + queries, + queryVectorPtr, + parentQueryVectorPtr); + + queries[id].value = 1; + localLogLikelihood += computeLocalLogLikelihoodHelper(0, + numParent, + adtreePtr, + queries, + queryVectorPtr, + parentQueryVectorPtr); + + queries[id].value = QUERY_VALUE_WILDCARD; + + return localLogLikelihood; + } + + + /* ============================================================================= + * TMfindBestInsertTask + * ============================================================================= + */ + /* + static learner_task_t + TMfindBestInsertTask (TM_ARGDECL findBestTaskArg_t* argPtr) + { + int toId = argPtr.toId; + learner_t* learnerPtr = argPtr.learnerPtr; + query_t* queries = argPtr.queries; + vector_t* queryVectorPtr = argPtr.queryVectorPtr; + vector_t* parentQueryVectorPtr = argPtr.parentQueryVectorPtr; + int numTotalParent = argPtr.numTotalParent; + float basePenalty = argPtr.basePenalty; + float baseLogLikelihood = argPtr.baseLogLikelihood; + bitmap_t* invalidBitmapPtr = argPtr.bitmapPtr; + queue_t* workQueuePtr = argPtr.workQueuePtr; + vector_t* baseParentQueryVectorPtr = argPtr.aQueryVectorPtr; + vector_t* baseQueryVectorPtr = argPtr.bQueryVectorPtr; + + boolean status; + adtree_t* adtreePtr = learnerPtr.adtreePtr; + net_t* netPtr = learnerPtr.netPtr; + float* localBaseLogLikelihoods = learnerPtr.localBaseLogLikelihoods; + + TMpopulateParentQueryVector(TM_ARG netPtr, toId, queries, parentQueryVectorPtr); + */ + + /* + * Create base query and parentQuery + */ + + /* + status = PVECTOR_COPY(baseParentQueryVectorPtr, parentQueryVectorPtr); + assert(status); + + status = PVECTOR_COPY(baseQueryVectorPtr, baseParentQueryVectorPtr); + assert(status); + status = PVECTOR_PUSHBACK(baseQueryVectorPtr, (void*)&queries[toId]); + assert(status); + PVECTOR_SORT(queryVectorPtr, &compareQuery); + */ + + /* + * Search all possible valid operations for better local log likelihood + */ + + /* + float bestFromId = toId; // flag for not found + float oldLocalLogLikelihood = + (float)TM_SHARED_READ_F(localBaseLogLikelihoods[toId]); + float bestLocalLogLikelihood = oldLocalLogLikelihood; + + status = TMNET_FINDDESCENDANTS(netPtr, toId, invalidBitmapPtr, workQueuePtr); + assert(status); + int fromId = -1; + + list_t* parentIdListPtr = net_getParentIdListPtr(netPtr, toId); + + int maxNumEdgeLearned = global_maxNumEdgeLearned; + + if ((maxNumEdgeLearned < 0) || + (TMLIST_GETSIZE(parentIdListPtr) <= maxNumEdgeLearned)) + { + + list_iter_t it; + TMLIST_ITER_RESET(&it, parentIdListPtr); + while (TMLIST_ITER_HASNEXT(&it, parentIdListPtr)) { + int parentId = (int)TMLIST_ITER_NEXT(&it, parentIdListPtr); + bitmap_set(invalidBitmapPtr, parentId); // invalid since already have edge + } + + while ((fromId = bitmap_findClear(invalidBitmapPtr, (fromId + 1))) >= 0) { + + if (fromId == toId) { + continue; + } + + status = PVECTOR_COPY(queryVectorPtr, baseQueryVectorPtr); + assert(status); + status = PVECTOR_PUSHBACK(queryVectorPtr, (void*)&queries[fromId]); + assert(status); + PVECTOR_SORT(queryVectorPtr, &compareQuery); + + status = PVECTOR_COPY(parentQueryVectorPtr, baseParentQueryVectorPtr); + assert(status); + status = PVECTOR_PUSHBACK(parentQueryVectorPtr, (void*)&queries[fromId]); + assert(status); + PVECTOR_SORT(parentQueryVectorPtr, &compareQuery); + + float newLocalLogLikelihood = + computeLocalLogLikelihood(toId, + adtreePtr, + netPtr, + queries, + queryVectorPtr, + parentQueryVectorPtr); + + if (newLocalLogLikelihood > bestLocalLogLikelihood) { + bestLocalLogLikelihood = newLocalLogLikelihood; + bestFromId = fromId; + } + + } // foreach valid parent + + } // if have not exceeded max number of edges to learn + */ + + /* + * Return best task; Note: if none is better, fromId will equal toId + */ + + /* + learner_task_t bestTask; + bestTask.op = OPERATION_INSERT; + bestTask.fromId = bestFromId; + bestTask.toId = toId; + bestTask.score = 0.0; + + if (bestFromId != toId) { + int numRecord = adtreePtr.numRecord; + int numParent = TMLIST_GETSIZE(parentIdListPtr) + 1; + float penalty = + (numTotalParent + numParent * global_insertPenalty) * basePenalty; + float logLikelihood = numRecord * (baseLogLikelihood + + + bestLocalLogLikelihood + - oldLocalLogLikelihood); + float bestScore = penalty + logLikelihood; + bestTask.score = bestScore; + } + + return bestTask; + } + */ + + +#ifdef LEARNER_TRY_REMOVE + /* ============================================================================= + * TMfindBestRemoveTask + * ============================================================================= + */ + /* + static learner_task_t + TMfindBestRemoveTask (TM_ARGDECL findBestTaskArg_t* argPtr) + { + int toId = argPtr.toId; + learner_t* learnerPtr = argPtr.learnerPtr; + query_t* queries = argPtr.queries; + vector_t* queryVectorPtr = argPtr.queryVectorPtr; + vector_t* parentQueryVectorPtr = argPtr.parentQueryVectorPtr; + int numTotalParent = argPtr.numTotalParent; + float basePenalty = argPtr.basePenalty; + float baseLogLikelihood = argPtr.baseLogLikelihood; + vector_t* origParentQueryVectorPtr = argPtr.aQueryVectorPtr; + + boolean status; + adtree_t* adtreePtr = learnerPtr.adtreePtr; + net_t* netPtr = learnerPtr.netPtr; + float* localBaseLogLikelihoods = learnerPtr.localBaseLogLikelihoods; + + TMpopulateParentQueryVector(TM_ARG + netPtr, toId, queries, origParentQueryVectorPtr); + int numParent = PVECTOR_GETSIZE(origParentQueryVectorPtr); + */ + + /* + * Search all possible valid operations for better local log likelihood + */ + + /* + float bestFromId = toId; // flag for not found + float oldLocalLogLikelihood = + (float)TM_SHARED_READ_F(localBaseLogLikelihoods[toId]); + float bestLocalLogLikelihood = oldLocalLogLikelihood; + + int i; + for (i = 0; i < numParent; i++) { + + query_t* queryPtr = (query_t*)PVECTOR_AT(origParentQueryVectorPtr, i); + int fromId = queryPtr.index; + */ + + /* + * Create parent query (subset of parents since remove an edge) + */ + + /* + + PVECTOR_CLEAR(parentQueryVectorPtr); + + int p; + for (p = 0; p < numParent; p++) { + if (p != fromId) { + query_t* queryPtr = PVECTOR_AT(origParentQueryVectorPtr, p); + status = PVECTOR_PUSHBACK(parentQueryVectorPtr, + (void*)&queries[queryPtr.index]); + assert(status); + } + } // create new parent query + */ + + /* + * Create query + */ + /* + + status = PVECTOR_COPY(queryVectorPtr, parentQueryVectorPtr); + assert(status); + status = PVECTOR_PUSHBACK(queryVectorPtr, (void*)&queries[toId]); + assert(status); + PVECTOR_SORT(queryVectorPtr, &compareQuery); + */ + + /* + * See if removing parent is better + */ + + /* + float newLocalLogLikelihood = + computeLocalLogLikelihood(toId, + adtreePtr, + netPtr, + queries, + queryVectorPtr, + parentQueryVectorPtr); + + if (newLocalLogLikelihood > bestLocalLogLikelihood) { + bestLocalLogLikelihood = newLocalLogLikelihood; + bestFromId = fromId; + } + + } // for each parent + */ + + /* + * Return best task; Note: if none is better, fromId will equal toId + */ + + /* + learner_task_t bestTask; + bestTask.op = OPERATION_REMOVE; + bestTask.fromId = bestFromId; + bestTask.toId = toId; + bestTask.score = 0.0; + + if (bestFromId != toId) { + int numRecord = adtreePtr.numRecord; + float penalty = (numTotalParent - 1) * basePenalty; + float logLikelihood = numRecord * (baseLogLikelihood + + + bestLocalLogLikelihood + - oldLocalLogLikelihood); + float bestScore = penalty + logLikelihood; + bestTask.score = bestScore; + } + + return bestTask; + } + */ +#endif /* LEARNER_TRY_REMOVE */ + + +#ifdef LEARNER_TRY_REVERSE + /* ============================================================================= + * TMfindBestReverseTask + * ============================================================================= + */ + /* + static learner_task_t + TMfindBestReverseTask (TM_ARGDECL findBestTaskArg_t* argPtr) + { + int toId = argPtr.toId; + learner_t* learnerPtr = argPtr.learnerPtr; + query_t* queries = argPtr.queries; + vector_t* queryVectorPtr = argPtr.queryVectorPtr; + vector_t* parentQueryVectorPtr = argPtr.parentQueryVectorPtr; + int numTotalParent = argPtr.numTotalParent; + float basePenalty = argPtr.basePenalty; + float baseLogLikelihood = argPtr.baseLogLikelihood; + bitmap_t* visitedBitmapPtr = argPtr.bitmapPtr; + queue_t* workQueuePtr = argPtr.workQueuePtr; + vector_t* toOrigParentQueryVectorPtr = argPtr.aQueryVectorPtr; + vector_t* fromOrigParentQueryVectorPtr = argPtr.bQueryVectorPtr; + + boolean status; + adtree_t* adtreePtr = learnerPtr.adtreePtr; + net_t* netPtr = learnerPtr.netPtr; + float* localBaseLogLikelihoods = learnerPtr.localBaseLogLikelihoods; + + TMpopulateParentQueryVector(TM_ARG + netPtr, toId, queries, toOrigParentQueryVectorPtr); + int numParent = PVECTOR_GETSIZE(toOrigParentQueryVectorPtr); + */ + + /* + * Search all possible valid operations for better local log likelihood + */ + + /* + int bestFromId = toId; // flag for not found + float oldLocalLogLikelihood = + (float)TM_SHARED_READ_F(localBaseLogLikelihoods[toId]); + float bestLocalLogLikelihood = oldLocalLogLikelihood; + int fromId = 0; + + int i; + for (i = 0; i < numParent; i++) { + + query_t* queryPtr = (query_t*)PVECTOR_AT(toOrigParentQueryVectorPtr, i); + fromId = queryPtr.index; + + bestLocalLogLikelihood = + oldLocalLogLikelihood + + (float)TM_SHARED_READ_F(localBaseLogLikelihoods[fromId]); + + TMpopulateParentQueryVector(TM_ARG + netPtr, + fromId, + queries, + fromOrigParentQueryVectorPtr); + */ + + /* + * Create parent query (subset of parents since remove an edge) + */ + + /* + + PVECTOR_CLEAR(parentQueryVectorPtr); + + int p; + for (p = 0; p < numParent; p++) { + if (p != fromId) { + query_t* queryPtr = PVECTOR_AT(toOrigParentQueryVectorPtr, p); + status = PVECTOR_PUSHBACK(parentQueryVectorPtr, + (void*)&queries[queryPtr.index]); + assert(status); + } + } // create new parent query + */ + + /* + * Create query + */ + + /* + status = PVECTOR_COPY(queryVectorPtr, parentQueryVectorPtr); + assert(status); + status = PVECTOR_PUSHBACK(queryVectorPtr, (void*)&queries[toId]); + assert(status); + PVECTOR_SORT(queryVectorPtr, &compareQuery); + */ + + /* + * Get log likelihood for removing parent from toId + */ + /* + + float newLocalLogLikelihood = + computeLocalLogLikelihood(toId, + adtreePtr, + netPtr, + queries, + queryVectorPtr, + parentQueryVectorPtr); + */ + + /* + * Get log likelihood for adding parent to fromId + */ + + /* + + status = PVECTOR_COPY(parentQueryVectorPtr, fromOrigParentQueryVectorPtr); + assert(status); + status = PVECTOR_PUSHBACK(parentQueryVectorPtr, (void*)&queries[toId]); + assert(status); + PVECTOR_SORT(parentQueryVectorPtr, &compareQuery); + + status = PVECTOR_COPY(queryVectorPtr, parentQueryVectorPtr); + assert(status); + status = PVECTOR_PUSHBACK(queryVectorPtr, (void*)&queries[fromId]); + assert(status); + PVECTOR_SORT(queryVectorPtr, &compareQuery); + + newLocalLogLikelihood += + computeLocalLogLikelihood(fromId, + adtreePtr, + netPtr, + queries, + queryVectorPtr, + parentQueryVectorPtr); + */ + + /* + * Record best + */ + /* + if (newLocalLogLikelihood > bestLocalLogLikelihood) { + bestLocalLogLikelihood = newLocalLogLikelihood; + bestFromId = fromId; + } + + } // for each parent + */ + + /* + * Check validity of best + */ + + /* + if (bestFromId != toId) { + boolean isTaskValid = TRUE; + TMNET_APPLYOPERATION(netPtr, OPERATION_REMOVE, bestFromId, toId); + if (TMNET_ISPATH(netPtr, + bestFromId, + toId, + visitedBitmapPtr, + workQueuePtr)) + { + isTaskValid = FALSE; + } + TMNET_APPLYOPERATION(netPtr, OPERATION_INSERT, bestFromId, toId); + if (!isTaskValid) { + bestFromId = toId; + } + } + */ + + /* + * Return best task; Note: if none is better, fromId will equal toId + */ + + /* + learner_task_t bestTask; + bestTask.op = OPERATION_REVERSE; + bestTask.fromId = bestFromId; + bestTask.toId = toId; + bestTask.score = 0.0; + + if (bestFromId != toId) { + float fromLocalLogLikelihood = + (float)TM_SHARED_READ_F(localBaseLogLikelihoods[bestFromId]); + int numRecord = adtreePtr.numRecord; + float penalty = numTotalParent * basePenalty; + float logLikelihood = numRecord * (baseLogLikelihood + + + bestLocalLogLikelihood + - oldLocalLogLikelihood + - fromLocalLogLikelihood); + float bestScore = penalty + logLikelihood; + bestTask.score = bestScore; + } + + return bestTask; + } + */ +#endif /* LEARNER_TRY_REVERSE */ + + + /* ============================================================================= + * learnStructure + * + * Note it is okay if the score is not exact, as we are relaxing the greedy + * search. This means we do not need to communicate baseLogLikelihood across + * threads. + * ============================================================================= + */ + /* + static void + learnStructure (void* argPtr) + { + TM_THREAD_ENTER(); + + learner_t* learnerPtr = (learner_t*)argPtr; + net_t* netPtr = learnerPtr.netPtr; + adtree_t* adtreePtr = learnerPtr.adtreePtr; + int numRecord = adtreePtr.numRecord; + float* localBaseLogLikelihoods = learnerPtr.localBaseLogLikelihoods; + list_t* taskListPtr = learnerPtr.taskListPtr; + + float operationQualityFactor = global_operationQualityFactor; + + bitmap_t* visitedBitmapPtr = PBITMAP_ALLOC(learnerPtr.adtreePtr.numVar); + assert(visitedBitmapPtr); + queue_t* workQueuePtr = PQUEUE_ALLOC(-1); + assert(workQueuePtr); + + int numVar = adtreePtr.numVar; + query_t* queries = (query_t*)P_MALLOC(numVar * sizeof(query_t)); + assert(queries); + int v; + for (v = 0; v < numVar; v++) { + queries[v].index = v; + queries[v].value = QUERY_VALUE_WILDCARD; + } + + float basePenalty = (float)(-0.5 * log((double)numRecord)); + + vector_t* queryVectorPtr = PVECTOR_ALLOC(1); + assert(queryVectorPtr); + vector_t* parentQueryVectorPtr = PVECTOR_ALLOC(1); + assert(parentQueryVectorPtr); + vector_t* aQueryVectorPtr = PVECTOR_ALLOC(1); + assert(aQueryVectorPtr); + vector_t* bQueryVectorPtr = PVECTOR_ALLOC(1); + assert(bQueryVectorPtr); + + findBestTaskArg_t arg; + arg.learnerPtr = learnerPtr; + arg.queries = queries; + arg.queryVectorPtr = queryVectorPtr; + arg.parentQueryVectorPtr = parentQueryVectorPtr; + arg.bitmapPtr = visitedBitmapPtr; + arg.workQueuePtr = workQueuePtr; + arg.aQueryVectorPtr = aQueryVectorPtr; + arg.bQueryVectorPtr = bQueryVectorPtr; + + while (1) { + + learner_task_t* taskPtr; + TM_BEGIN(); + taskPtr = TMpopTask(TM_ARG taskListPtr); + TM_END(); + if (taskPtr == NULL) { + break; + } + + operation_t op = taskPtr.op; + int fromId = taskPtr.fromId; + int toId = taskPtr.toId; + + boolean isTaskValid; + + TM_BEGIN(); + */ + + /* + * Check if task is still valid + */ + /* + isTaskValid = TRUE; + switch (op) { + case OPERATION_INSERT: { + if (TMNET_HASEDGE(netPtr, fromId, toId) || + TMNET_ISPATH(netPtr, + toId, + fromId, + visitedBitmapPtr, + workQueuePtr)) + { + isTaskValid = FALSE; + } + break; + } + case OPERATION_REMOVE: { + // Can never create cycle, so always valid + break; + } + case OPERATION_REVERSE: { + // Temporarily remove edge for check + TMNET_APPLYOPERATION(netPtr, OPERATION_REMOVE, fromId, toId); + if (TMNET_ISPATH(netPtr, + fromId, + toId, + visitedBitmapPtr, + workQueuePtr)) + { + isTaskValid = FALSE; + } + TMNET_APPLYOPERATION(netPtr, OPERATION_INSERT, fromId, toId); + break; + } + default: + assert(0); + } + +#ifdef TEST_LEARNER + printf("[task] op=%i from=%li to=%li score=%lf valid=%s\n", + taskPtr.op, taskPtr.fromId, taskPtr.toId, taskPtr.score, + (isTaskValid ? "yes" : "no")); + fflush(stdout); +#endif +*/ + + /* + * Perform task: update graph and probabilities + */ + + /* + if (isTaskValid) { + TMNET_APPLYOPERATION(netPtr, op, fromId, toId); + } + + TM_END(); + + float deltaLogLikelihood = 0.0; + + if (isTaskValid) { + + switch (op) { + float newBaseLogLikelihood; + case OPERATION_INSERT: { + TM_BEGIN(); + TMpopulateQueryVectors(TM_ARG + netPtr, + toId, + queries, + queryVectorPtr, + parentQueryVectorPtr); + newBaseLogLikelihood = + computeLocalLogLikelihood(toId, + adtreePtr, + netPtr, + queries, + queryVectorPtr, + parentQueryVectorPtr); + float toLocalBaseLogLikelihood = + (float)TM_SHARED_READ_F(localBaseLogLikelihoods[toId]); + deltaLogLikelihood += + toLocalBaseLogLikelihood - newBaseLogLikelihood; + TM_SHARED_WRITE_F(localBaseLogLikelihoods[toId], + newBaseLogLikelihood); + TM_END(); + TM_BEGIN(); + int numTotalParent = (int)TM_SHARED_READ(learnerPtr.numTotalParent); + TM_SHARED_WRITE(learnerPtr.numTotalParent, (numTotalParent + 1)); + TM_END(); + break; + } +#ifdef LEARNER_TRY_REMOVE + case OPERATION_REMOVE: { + TM_BEGIN(); + TMpopulateQueryVectors(TM_ARG + netPtr, + fromId, + queries, + queryVectorPtr, + parentQueryVectorPtr); + newBaseLogLikelihood = + computeLocalLogLikelihood(fromId, + adtreePtr, + netPtr, + queries, + queryVectorPtr, + parentQueryVectorPtr); + float fromLocalBaseLogLikelihood = + (float)TM_SHARED_READ_F(localBaseLogLikelihoods[fromId]); + deltaLogLikelihood += + fromLocalBaseLogLikelihood - newBaseLogLikelihood; + TM_SHARED_WRITE_F(localBaseLogLikelihoods[fromId], + newBaseLogLikelihood); + TM_END(); + TM_BEGIN(); + int numTotalParent = (int)TM_SHARED_READ(learnerPtr.numTotalParent); + TM_SHARED_WRITE(learnerPtr.numTotalParent, (numTotalParent - 1)); + TM_END(); + break; + } +#endif // LEARNER_TRY_REMOVE +#ifdef LEARNER_TRY_REVERSE + case OPERATION_REVERSE: { + TM_BEGIN(); + TMpopulateQueryVectors(TM_ARG + netPtr, + fromId, + queries, + queryVectorPtr, + parentQueryVectorPtr); + newBaseLogLikelihood = + computeLocalLogLikelihood(fromId, + adtreePtr, + netPtr, + queries, + queryVectorPtr, + parentQueryVectorPtr); + float fromLocalBaseLogLikelihood = + (float)TM_SHARED_READ_F(localBaseLogLikelihoods[fromId]); + deltaLogLikelihood += + fromLocalBaseLogLikelihood - newBaseLogLikelihood; + TM_SHARED_WRITE_F(localBaseLogLikelihoods[fromId], + newBaseLogLikelihood); + TM_END(); + + TM_BEGIN(); + TMpopulateQueryVectors(TM_ARG + netPtr, + toId, + queries, + queryVectorPtr, + parentQueryVectorPtr); + newBaseLogLikelihood = + computeLocalLogLikelihood(toId, + adtreePtr, + netPtr, + queries, + queryVectorPtr, + parentQueryVectorPtr); + float toLocalBaseLogLikelihood = + (float)TM_SHARED_READ_F(localBaseLogLikelihoods[toId]); + deltaLogLikelihood += + toLocalBaseLogLikelihood - newBaseLogLikelihood; + TM_SHARED_WRITE_F(localBaseLogLikelihoods[toId], + newBaseLogLikelihood); + TM_END(); + break; + } +#endif // LEARNER_TRY_REVERSE + default: + assert(0); + } // switch op + + } // if isTaskValid +*/ + + /* + * Update/read globals + */ + /* + float baseLogLikelihood; + int numTotalParent; + + TM_BEGIN(); + float oldBaseLogLikelihood = + (float)TM_SHARED_READ_F(learnerPtr.baseLogLikelihood); + float newBaseLogLikelihood = oldBaseLogLikelihood + deltaLogLikelihood; + TM_SHARED_WRITE_F(learnerPtr.baseLogLikelihood, newBaseLogLikelihood); + baseLogLikelihood = newBaseLogLikelihood; + numTotalParent = (int)TM_SHARED_READ(learnerPtr.numTotalParent); + TM_END(); + */ + + /* + * Find next task + */ + /* + float baseScore = ((float)numTotalParent * basePenalty) + + (numRecord * baseLogLikelihood); + + learner_task_t bestTask; + bestTask.op = NUM_OPERATION; + bestTask.toId = -1; + bestTask.fromId = -1; + bestTask.score = baseScore; + + learner_task_t newTask; + + arg.toId = toId; + arg.numTotalParent = numTotalParent; + arg.basePenalty = basePenalty; + arg.baseLogLikelihood = baseLogLikelihood; + + TM_BEGIN(); + newTask = TMfindBestInsertTask(TM_ARG &arg); + TM_END(); + + if ((newTask.fromId != newTask.toId) && + (newTask.score > (bestTask.score / operationQualityFactor))) + { + bestTask = newTask; + } + +#ifdef LEARNER_TRY_REMOVE + TM_BEGIN(); + newTask = TMfindBestRemoveTask(TM_ARG &arg); + TM_END(); + + if ((newTask.fromId != newTask.toId) && + (newTask.score > (bestTask.score / operationQualityFactor))) + { + bestTask = newTask; + } +#endif // LEARNER_TRY_REMOVE + +#ifdef LEARNER_TRY_REVERSE + TM_BEGIN(); + newTask = TMfindBestReverseTask(TM_ARG &arg); + TM_END(); + + if ((newTask.fromId != newTask.toId) && + (newTask.score > (bestTask.score / operationQualityFactor))) + { + bestTask = newTask; + } +#endif // LEARNER_TRY_REVERSE + + if (bestTask.toId != -1) { + learner_task_t* tasks = learnerPtr.tasks; + tasks[toId] = bestTask; + TM_BEGIN(); + TMLIST_INSERT(taskListPtr, (void*)&tasks[toId]); + TM_END(); +#ifdef TEST_LEARNER + printf("[new] op=%i from=%li to=%li score=%lf\n", + bestTask.op, bestTask.fromId, bestTask.toId, bestTask.score); + fflush(stdout); +#endif + } + + } // while (tasks) + + PBITMAP_FREE(visitedBitmapPtr); + PQUEUE_FREE(workQueuePtr); + PVECTOR_FREE(bQueryVectorPtr); + PVECTOR_FREE(aQueryVectorPtr); + PVECTOR_FREE(queryVectorPtr); + PVECTOR_FREE(parentQueryVectorPtr); + P_FREE(queries); + + TM_THREAD_EXIT(); + } +*/ + + + /* ============================================================================= + * learner_run + * -- Call adtree_make before this + * ============================================================================= + */ + public void + learner_run (int myId, int numThread, Learner learnerPtr) + //learner_run (learner_t* learnerPtr) + { + /* +#ifdef OTM +#pragma omp parallel + { + createTaskList((void*)learnerPtr); + } +#pragma omp parallel + { + learnStructure((void*)learnerPtr); + } +#else + thread_start(&createTaskList, (void*)learnerPtr); + thread_start(&learnStructure, (void*)learnerPtr); +#endif +*/ + } + + /* ============================================================================= + * learner_score + * -- Score entire network + * ============================================================================= + */ + public float + learner_score () + { + //adtree_t* adtreePtr = learnerPtr.adtreePtr; + //net_t* netPtr = learnerPtr.netPtr; + + Vector_t queryVectorPtr = Vector_t.vector_alloc(1); + //assert(queryVectorPtr); + Vector_t parentQueryVectorPtr = Vector_t.vector_alloc(1); + //vector_t* parentQueryVectorPtr = vector_alloc(1); + //assert(parentQueryVectorPtr); + + int numVar = adtreePtr.numVar; + Query[] queries = new Query[numVar]; + //query_t* queries = (query_t*)malloc(numVar * sizeof(query_t)); + //assert(queries); + //int v; + for (int v = 0; v < numVar; v++) { + queries[v] = new Query(); + queries[v].index = v; + queries[v].value = QUERY_VALUE_WILDCARD; + } + + int numTotalParent = 0; + float logLikelihood = 0.0f; + + for (int v = 0; v < numVar; v++) { + + IntList parentIdListPtr = netPtr.net_getParentIdListPtr(v); + //list_t* parentIdListPtr = net_getParentIdListPtr(netPtr, v); + numTotalParent += parentIdListPtr.list_getSize(); + + + populateQueryVectors(netPtr, + v, + queries, + queryVectorPtr, + parentQueryVectorPtr); + float localLogLikelihood = computeLocalLogLikelihood(v, + adtreePtr, + netPtr, + queries, + queryVectorPtr, + parentQueryVectorPtr); + logLikelihood += localLogLikelihood; + } + + queryVectorPtr.vector_free(); + parentQueryVectorPtr.vector_free(); + queries = null; + //vector_free(queryVectorPtr); + //vector_free(parentQueryVectorPtr); + //free(queries); + + int numRecord = adtreePtr.numRecord; + float penalty = (float)(-0.5f * (double)numTotalParent * Math.log((double)numRecord)); + float score = penalty + (float)numRecord * logLikelihood; + + return score; + } + + + /* ############################################################################# + * TEST_LEARNER + * ############################################################################# + */ + /* +#ifdef TEST_LEARNER + +#include + + +static void +testPartition (int min, int max, int n) +{ +int start; +int stop; + +printf("min=%li max=%li, n=%li\n", min, max, n); + +int i; +for (i = 0; i < n; i++) { +createPartition(min, max, i, n, &start, &stop); +printf("%li: %li . %li\n", i, start, stop); +} +puts(""); +} + + +int +main (int argc, char* argv[]) +{ +thread_startup(1); + +puts("Starting..."); + +testPartition(0, 4, 8); +testPartition(0, 15, 8); +testPartition(3, 103, 7); + +int numVar = 56; +int numRecord = 256; + +random_t* randomPtr = random_alloc(); +data_t* dataPtr = data_alloc(numVar, numRecord, randomPtr); +assert(dataPtr); +data_generate(dataPtr, 0, 10, 10); + +adtree_t* adtreePtr = adtree_alloc(); +assert(adtreePtr); +adtree_make(adtreePtr, dataPtr); + + +learner_t* learnerPtr = learner_alloc(dataPtr, adtreePtr, 1); +assert(learnerPtr); + +data_free(dataPtr); + +learner_run(learnerPtr); + +assert(!net_isCycle(learnerPtr.netPtr)); + +float score = learner_score(learnerPtr); +printf("score = %lf\n", score); + +learner_free(learnerPtr); + +puts("Done."); + +adtree_free(adtreePtr); +random_free(randomPtr); + +thread_shutdown(); + +return 0; +} + +#endif // TEST_LEARNER +*/ + +} + +/* ============================================================================= + * + * End of learner.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/LearnerTask.java b/Robust/src/Benchmarks/SingleTM/Bayes/LearnerTask.java new file mode 100644 index 00000000..9f01d6eb --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/LearnerTask.java @@ -0,0 +1,10 @@ +public class LearnerTask { + Operation op; + int fromId; + int toId; + float score; + + public LearnerTask(){ + + } +} diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Net.java b/Robust/src/Benchmarks/SingleTM/Bayes/Net.java new file mode 100644 index 00000000..872436a4 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Net.java @@ -0,0 +1,1143 @@ +/* ============================================================================= + * + * net.java + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * + * ============================================================================= + * + * For the license of bayes/sort.h and bayes/sort.c, please see the header + * of the files. + * + * ------------------------------------------------------------------------ + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * 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. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * * Neither the name of Stanford 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 STANFORD UNIVERSITY ``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 STANFORD UNIVERSITY 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. + * + * ============================================================================= + * Ported to Java June 2009 by Alokika Dash + * -- adash@uci.edu + * University of California, Irvine + * + * Copyright (c) 2009, University of California, Irvine + * ============================================================================ + */ + + +/* +#include +#include +#include "bitmap.h" +#include "learner.h" +#include "list.h" +#include "net.h" +#include "operation.h" +#include "queue.h" +#include "tm.h" +#include "vector.h" +*/ + +#define NET_NODE_MARK_INIT 0 +#define NET_NODE_MARK_DONE 1 +#define NET_NODE_MARK_TEST 2 +#define OPERATION_INSERT 0 +#define OPERATION_REMOVE 1 +#define OPERATION_REVERSE 2 + +public class Net { + NetNode nn; + Vector_t nodeVectorPtr; + + public Net() { + } + + /* + typedef enum net_node_mark { + NET_NODE_MARK_INIT = 0, + NET_NODE_MARK_DONE = 1, + NET_NODE_MARK_TEST = 2, + } net_node_mark_t; + + typedef struct net_node { + int id; + list_t* parentIdListPtr; + list_t* childIdListPtr; + net_node_mark_t mark; + } net_node_t; + + struct net { + vector_t* nodeVectorPtr; + }; + */ + + + /* ============================================================================= + * compareId + * ============================================================================= + */ + /* + public static int + compareId (const void* aPtr, const void* bPtr) + { + int a = (int)aPtr; + int b = (int)bPtr; + + return (a - b); + } + */ + + + /* ============================================================================= + * allocNode + * ============================================================================= + */ + public static NetNode allocNode (int id) + { + NetNode nodePtr = new NetNode(); + + //nodePtr = (net_node_t*)malloc(sizeof(net_node_t)); + //if (nodePtr) { + nodePtr.parentIdListPtr = IntList.list_alloc(); + if (nodePtr.parentIdListPtr == null) { + nodePtr = null; + return null; + } + nodePtr.childIdListPtr = IntList.list_alloc(); + if (nodePtr.childIdListPtr == null) { + nodePtr.parentIdListPtr.list_free(); + nodePtr = null; + return null; + } + nodePtr.id = id; + //} + + return nodePtr; + } + + + /* ============================================================================= + * net_alloc + * ============================================================================= + */ + public static Net net_alloc (int numNode) + { + Net netPtr = new Net(); + Vector_t nodeVectorPtr = Vector_t.vector_alloc(numNode); + if (nodeVectorPtr == null) { + netPtr = null; + return null; + } + //netPtr = (net_t*)malloc(sizeof(net_t)); + //if (netPtr) { + // vector_t* nodeVectorPtr = vector_alloc(numNode); + // if (nodeVectorPtr == null) { + // free(netPtr); + // return null; + // } + // int i; + for (int i = 0; i < numNode; i++) { + NetNode nodePtr = allocNode(i); + //net_node_t* nodePtr = allocNode(i); + if (nodePtr == null) { + for (int j = 0; j < i; j++) { + //nodePtr = (net_node_t*)vector_at(nodeVectorPtr, j); + nodePtr = (NetNode)(nodeVectorPtr.vector_at(j)); + nodePtr.freeNode(); + } + nodeVectorPtr.vector_free(); + netPtr = null; + //free(netPtr); + return null; + } + + boolean status = nodeVectorPtr.vector_pushBack(nodePtr); + //boolean status = vector_pushBack(nodeVectorPtr, (void*)nodePtr); + //assert(status); + } + netPtr.nodeVectorPtr = nodeVectorPtr; + //} + + return netPtr; + } + + + /* ============================================================================= + * net_free + * ============================================================================= + */ + public void + net_free () + { + //int i; + //vector_t* nodeVectorPtr = netPtr.nodeVectorPtr; + int numNode = nodeVectorPtr.vector_getSize(); + for (int i = 0; i < numNode; i++) { + NetNode nodePtr = (NetNode)(nodeVectorPtr.vector_at(i)); + //net_node_t* nodePtr = (net_node_t*)vector_at(nodeVectorPtr, i); + nodePtr.freeNode(); + } + nodeVectorPtr.vector_free(); + //free(netPtr); + } + + + /* ============================================================================= + * insertEdge + * ============================================================================= + */ + public void + insertEdge (int fromId, int toId) + { + //vector_t* nodeVectorPtr = netPtr.nodeVectorPtr; + boolean status; + + NetNode childNodePtr = (NetNode)(nodeVectorPtr.vector_at(toId)); + IntList parentIdListPtr = childNodePtr.parentIdListPtr; + //net_node_t* childNodePtr = (net_node_t*)vector_at(nodeVectorPtr, toId); + //list_t* parentIdListPtr = childNodePtr.parentIdListPtr; + if((status = parentIdListPtr.list_insert(fromId)) != true) { + System.out.println("Assert failed for parentIdListPtr.list_insert in insertEdge()"); + System.exit(0); + } + //status = list_insert(parentIdListPtr, (void*)fromId); + //assert(status); + + NetNode parentNodePtr = (NetNode)(nodeVectorPtr.vector_at(fromId)); + IntList childIdListPtr = parentNodePtr.childIdListPtr; + //net_node_t* parentNodePtr = (net_node_t*)vector_at(nodeVectorPtr, fromId); + //list_t* childIdListPtr = parentNodePtr.childIdListPtr; + if((status = childIdListPtr.list_insert(toId)) != true) { + System.out.println("Assert failed for childIdListPtr.list_insert in insertEdge()"); + System.exit(0); + } + //status = list_insert(childIdListPtr, (void*)toId); + //assert(status); + } + + + /* ============================================================================= + * TMinsertEdge + * ============================================================================= + */ + /* + static void + TMinsertEdge (TM_ARGDECL net_t* netPtr, int fromId, int toId) + { + vector_t* nodeVectorPtr = netPtr.nodeVectorPtr; + boolean status; + + net_node_t* childNodePtr = (net_node_t*)vector_at(nodeVectorPtr, toId); + list_t* parentIdListPtr = childNodePtr.parentIdListPtr; + status = TMLIST_INSERT(parentIdListPtr, (void*)fromId); + assert(status); + + net_node_t* parentNodePtr = (net_node_t*)vector_at(nodeVectorPtr, fromId); + list_t* childIdListPtr = parentNodePtr.childIdListPtr; + status = TMLIST_INSERT(childIdListPtr, (void*)toId); + assert(status); + } + */ + + + /* ============================================================================= + * removeEdge + * ============================================================================= + */ + public void + removeEdge (int fromId, int toId) + { + boolean status; + + NetNode childNodePtr = (NetNode)(nodeVectorPtr.vector_at(toId)); + //net_node_t* childNodePtr = (net_node_t*)vector_at(nodeVectorPtr, toId); + IntList parentIdListPtr = childNodePtr.parentIdListPtr; + //list_t* parentIdListPtr = childNodePtr.parentIdListPtr; + status = parentIdListPtr.list_remove(fromId); + if(status == false) { + System.out.println("Assert failed: when removing from list"); + System.exit(0); + } + //assert(status); + + NetNode parentNodePtr = (NetNode)(nodeVectorPtr.vector_at(fromId)); + //net_node_t* parentNodePtr = (net_node_t*)vector_at(nodeVectorPtr, fromId); + IntList childIdListPtr = parentNodePtr.childIdListPtr; + //list_t* childIdListPtr = parentNodePtr.childIdListPtr; + status = childIdListPtr.list_remove(toId); + if(status == false) { + System.out.println("Assert failed: when removing from list"); + System.exit(0); + } + } + + /* ============================================================================= + * TMremoveEdge + * ============================================================================= + */ + /* + static void + TMremoveEdge (TM_ARGDECL net_t* netPtr, int fromId, int toId) + { + vector_t* nodeVectorPtr = netPtr.nodeVectorPtr; + boolean status; + + net_node_t* childNodePtr = (net_node_t*)vector_at(nodeVectorPtr, toId); + list_t* parentIdListPtr = childNodePtr.parentIdListPtr; + status = TMLIST_REMOVE(parentIdListPtr, (void*)fromId); + assert(status); + + net_node_t* parentNodePtr = (net_node_t*)vector_at(nodeVectorPtr, fromId); + list_t* childIdListPtr = parentNodePtr.childIdListPtr; + status = TMLIST_REMOVE(childIdListPtr, (void*)toId); + assert(status); + } + */ + + /* ============================================================================= + * reverseEdge + * ============================================================================= + */ + public void + //reverseEdge (net_t* netPtr, int fromId, int toId) + reverseEdge (int fromId, int toId) + { + removeEdge(fromId, toId); + insertEdge(toId, fromId); + } + + + /* ============================================================================= + * TMreverseEdge + * ============================================================================= + */ + /* + static void + TMreverseEdge (TM_ARGDECL net_t* netPtr, int fromId, int toId) + { + TMremoveEdge(TM_ARG netPtr, fromId, toId); + TMinsertEdge(TM_ARG netPtr, toId, fromId); + } + */ + + + /* ============================================================================= + * net_applyOperation + * ============================================================================= + */ + public void + net_applyOperation (Operation op, int fromId, int toId) + { + if(op.insert == OPERATION_INSERT) { + insertEdge(fromId, toId); + } else if(op.remove == OPERATION_REMOVE) { + removeEdge(fromId, toId); + } else if(op.reverse == OPERATION_REVERSE) { + reverseEdge(fromId, toId); + } else { + System.out.println("Operation failed"); + System.exit(0); + } + } + + + /* ============================================================================= + * TMnet_applyOperation + * ============================================================================= + */ + /* + void + TMnet_applyOperation (TM_ARGDECL + net_t* netPtr, operation_t op, int fromId, int toId) + { + switch (op) { + case OPERATION_INSERT: TMinsertEdge(TM_ARG netPtr, fromId, toId); break; + case OPERATION_REMOVE: TMremoveEdge(TM_ARG netPtr, fromId, toId); break; + case OPERATION_REVERSE: TMreverseEdge(TM_ARG netPtr, fromId, toId); break; + default: + assert(0); + } + } + + */ + + + /* ============================================================================= + * net_hasEdge + * ============================================================================= + */ + public boolean + net_hasEdge (int fromId, int toId) + { + //vector_t* nodeVectorPtr = netPtr.nodeVectorPtr; + NetNode childNodePtr = (NetNode)(nodeVectorPtr.vector_at(toId)); + //net_node_t* childNodePtr = (net_node_t*)vector_at(nodeVectorPtr, toId); + + IntList parentIdListPtr = childNodePtr.parentIdListPtr; + IntListNode it = parentIdListPtr.head; //intialize iterator + parentIdListPtr.list_iter_reset(it); + //list_iter_t it; + //list_iter_reset(&it, parentIdListPtr); + //while (list_iter_hasNext(&it, parentIdListPtr)) { + + while (parentIdListPtr.list_iter_hasNext(it)) { + it = it.nextPtr; + int parentId = parentIdListPtr.list_iter_next(it); + if (parentId == fromId) { + return true; + } + } + + return false; + } + + + /* ============================================================================= + * TMnet_hasEdge + * ============================================================================= + */ + /* + boolean + TMnet_hasEdge (TM_ARGDECL net_t* netPtr, int fromId, int toId) + { + vector_t* nodeVectorPtr = netPtr.nodeVectorPtr; + net_node_t* childNodePtr = (net_node_t*)vector_at(nodeVectorPtr, toId); + list_t* parentIdListPtr = childNodePtr.parentIdListPtr; + + list_iter_t it; + TMLIST_ITER_RESET(&it, parentIdListPtr); + while (TMLIST_ITER_HASNEXT(&it, parentIdListPtr)) { + int parentId = (int)TMLIST_ITER_NEXT(&it, parentIdListPtr); + if (parentId == fromId) { + return true; + } + } + + return false; + } + */ + + + /* ============================================================================= + * net_isPath + * ============================================================================= + */ + public boolean + net_isPath (int fromId, + int toId, + BitMap visitedBitmapPtr, + Queue workQueuePtr) + { + boolean status; + + //Vector_t nodeVectorPtr = netPtr.nodeVectorPtr; + if(visitedBitmapPtr.numBit != nodeVectorPtr.vector_getSize()) { + System.out.println("Assert failed for numbit == vector size in net_isPath()"); + System.exit(0); + } + //vector_t* nodeVectorPtr = netPtr.nodeVectorPtr; + //assert(visitedBitmapPtr.numBit == vector_getSize(nodeVectorPtr)); + + visitedBitmapPtr.bitmap_clearAll(); + workQueuePtr.queue_clear(); + //bitmap_clearAll(visitedBitmapPtr); + //queue_clear(workQueuePtr); + + if((status = workQueuePtr.queue_push(fromId)) != true) { + System.out.println("Assert failed while inserting into Queue in net_isPath()"); + System.exit(0); + } + //status = queue_push(workQueuePtr, (void*)fromId); + //assert(status); + + while (!workQueuePtr.queue_isEmpty()) { + int id = workQueuePtr.queue_pop(); + if (id == toId) { + workQueuePtr.queue_clear(); + return true; + } + if((status = visitedBitmapPtr.bitmap_set(id)) != true) { + System.out.println("Assert failed while checking bitmap_set in net_isPath()"); + System.exit(0); + } + //status = bitmap_set(visitedBitmapPtr, id); + //assert(status); + NetNode nodePtr = (NetNode) (nodeVectorPtr.vector_at(id)); + IntList childIdListPtr = nodePtr.childIdListPtr; + IntListNode it = childIdListPtr.head; + childIdListPtr.list_iter_reset(it); + //net_node_t* nodePtr = (net_node_t*)vector_at(nodeVectorPtr, id); + //list_t* childIdListPtr = nodePtr.childIdListPtr; + //list_iter_t it; + //list_iter_reset(&it, childIdListPtr); + //while (list_iter_hasNext(&it, childIdListPtr)) + while (childIdListPtr.list_iter_hasNext(it)) { + it = it.nextPtr; + int childId = childIdListPtr.list_iter_next(it); + if (!visitedBitmapPtr.bitmap_isSet(childId)) { + status = workQueuePtr.queue_push(childId); + if(status == false) { + System.out.println("Assert failed: queue_push failed in net_isPath()"); + System.exit(0); + } + //assert(status); + } + } + } + + return false; + } + + + /* ============================================================================= + * TMnet_isPath + * ============================================================================= + */ + /* + boolean + TMnet_isPath (TM_ARGDECL + net_t* netPtr, + int fromId, + int toId, + Bitmap* visitedBitmapPtr, + Queue* workQueuePtr) + { + boolean status; + + vector_t* nodeVectorPtr = netPtr.nodeVectorPtr; + assert(visitedBitmapPtr.numBit == vector_getSize(nodeVectorPtr)); + + PBITMAP_CLEARALL(visitedBitmapPtr); + PQUEUE_CLEAR(workQueuePtr); + + status = PQUEUE_PUSH(workQueuePtr, (void*)fromId); + assert(status); + + while (!PQUEUE_ISEMPTY(workQueuePtr)) { + int id = (int)queue_pop(workQueuePtr); + if (id == toId) { + queue_clear(workQueuePtr); + return true; + } + status = PBITMAP_SET(visitedBitmapPtr, id); + assert(status); + net_node_t* nodePtr = (net_node_t*)vector_at(nodeVectorPtr, id); + list_t* childIdListPtr = nodePtr.childIdListPtr; + list_iter_t it; + TMLIST_ITER_RESET(&it, childIdListPtr); + while (TMLIST_ITER_HASNEXT(&it, childIdListPtr)) { + int childId = (int)TMLIST_ITER_NEXT(&it, childIdListPtr); + if (!PBITMAP_ISSET(visitedBitmapPtr, childId)) { + status = PQUEUE_PUSH(workQueuePtr, (void*)childId); + assert(status); + } + } + } + + return false; + } + */ + + + /* ============================================================================= + * isCycle + * ============================================================================= + */ + public boolean + isCycle (Vector_t nodeVectorPtr, NetNode nodePtr) + { + if(nodePtr.mark == NET_NODE_MARK_INIT ) { + nodePtr.mark = NET_NODE_MARK_TEST; + IntList childIdListPtr = nodePtr.childIdListPtr; + IntListNode it = childIdListPtr.head; + childIdListPtr.list_iter_reset(it); + //list_iter_t it; + //list_iter_reset(&it, childIdListPtr); + //while (list_iter_hasNext(&it, childIdListPtr)) + while (childIdListPtr.list_iter_hasNext(it)) { + it = it.nextPtr; + int childId = childIdListPtr.list_iter_next(it); + NetNode childNodePtr = (NetNode)(nodeVectorPtr.vector_at(childId)); + //net_node_t* childNodePtr = + // (net_node_t*)vector_at(nodeVectorPtr, childId); + if (isCycle(nodeVectorPtr, childNodePtr)) { + return true; + } + } + } else if(nodePtr.mark == NET_NODE_MARK_TEST) { + return true; + } else if(nodePtr.mark == NET_NODE_MARK_DONE) { + return false; + } else { + System.out.println("We should have never come here in isCycle()"); + System.exit(0); + } + + nodePtr.mark = NET_NODE_MARK_DONE; + return false; + } + + + /* ============================================================================= + * net_isCycle + * ============================================================================= + */ + public boolean + //net_isCycle (net_t* netPtr) + net_isCycle () + { + //vector_t* nodeVectorPtr = netPtr.nodeVectorPtr; + int numNode = nodeVectorPtr.vector_getSize(); + //int n; + for (int n = 0; n < numNode; n++) { + NetNode nodePtr = (NetNode)(nodeVectorPtr.vector_at(n)); + //net_node_t* nodePtr = (net_node_t*)vector_at(nodeVectorPtr, n); + nodePtr.mark = NET_NODE_MARK_INIT; + } + + for (int n = 0; n < numNode; n++) { + NetNode nodePtr = (NetNode)(nodeVectorPtr.vector_at(n)); + //net_node_t* nodePtr = (net_node_t*)vector_at(nodeVectorPtr, n); + if(nodePtr.mark == NET_NODE_MARK_INIT) { + if(isCycle(nodeVectorPtr, nodePtr)) + return true; + } else if(nodePtr.mark == NET_NODE_MARK_DONE) { + /* do nothing */ + ; + } else if(nodePtr.mark == NET_NODE_MARK_TEST) { + /* Assert 0 */ + System.out.println("We should have never come here in net_isCycle()"); + System.exit(0); + break; + } else { + /* Assert 0 */ + System.out.println("We should have never come here in net_isCycle()"); + System.exit(0); + break; + } + } + + return false; + } + + + /* ============================================================================= + * net_getParentIdListPtr + * ============================================================================= + */ + public IntList + net_getParentIdListPtr (int id) + { + NetNode nodePtr = (NetNode) (nodeVectorPtr.vector_at(id)); + if(nodePtr == null) { + System.out.println("Assert failed for nodePtr"); + System.exit(0); + } + + return nodePtr.parentIdListPtr; + } + + + /* ============================================================================= + * net_getChildIdListPtr + * ============================================================================= + */ + public IntList + net_getChildIdListPtr (int id) + { + NetNode nodePtr = (NetNode) (nodeVectorPtr.vector_at(id)); + if(nodePtr == null) { + System.out.println("Assert failed for nodePtr"); + System.exit(0); + } + + return nodePtr.childIdListPtr; + } + + + /* ============================================================================= + * net_findAncestors + * -- Contents of bitmapPtr set to 1 if ancestor, else 0 + * -- Returns false if id is not root node (i.e., has cycle back id) + * ============================================================================= + */ + public boolean + net_findAncestors (int id, + BitMap ancestorBitmapPtr, + Queue workQueuePtr) + { + boolean status; + + //vector_t* nodeVectorPtr = netPtr.nodeVectorPtr; + + if(ancestorBitmapPtr.numBit != nodeVectorPtr.vector_getSize()) { + System.out.println("Assert failed for numbit == vector size in net_findAncestors()"); + System.exit(0); + } + //assert(ancestorBitmapPtr.numBit == vector_getSize(nodeVectorPtr)); + + ancestorBitmapPtr.bitmap_clearAll(); + workQueuePtr.queue_clear(); + + { + NetNode nodePtr = (NetNode)(nodeVectorPtr.vector_at(id)); + //net_node_t* nodePtr = (net_node_t*)vector_at(nodeVectorPtr, id); + IntList parentIdListPtr = nodePtr.parentIdListPtr; + IntListNode it = parentIdListPtr.head; + parentIdListPtr.list_iter_reset(it); + //list_t* parentIdListPtr = nodePtr.parentIdListPtr; + //list_iter_t it; + //list_iter_reset(&it, parentIdListPtr); + //while (list_iter_hasNext(&it, parentIdListPtr)) + while (parentIdListPtr.list_iter_hasNext(it)) { + it = it.nextPtr; + int parentId = parentIdListPtr.list_iter_next(it); + status = ancestorBitmapPtr.bitmap_set(parentId); + if(status == false) { + System.out.println("Assert failed: for bitmap_set in net_findAncestors()"); + System.exit(0); + } + //assert(status); + if((status = workQueuePtr.queue_push(parentId)) == false) { + System.out.println("Assert failed: for workQueuePtr.queue_push in net_findAncestors()"); + System.exit(0); + } + //assert(status); + } + } + + while (!workQueuePtr.queue_isEmpty()) { + int parentId = workQueuePtr.queue_pop(); + if (parentId == id) { + workQueuePtr.queue_clear(); + return false; + } + NetNode nodePtr = (NetNode)(nodeVectorPtr.vector_at(parentId)); + //net_node_t* nodePtr = (net_node_t*)vector_at(nodeVectorPtr, parentId); + IntList grandParentIdListPtr = nodePtr.parentIdListPtr; + IntListNode it = grandParentIdListPtr.head; + grandParentIdListPtr.list_iter_reset(it); + //list_t* grandParentIdListPtr = nodePtr.parentIdListPtr; + //list_iter_t it; + //list_iter_reset(&it, grandParentIdListPtr); + while (grandParentIdListPtr.list_iter_hasNext(it)) { + it = it.nextPtr; + int grandParentId = grandParentIdListPtr.list_iter_next(it); + if (!ancestorBitmapPtr.bitmap_isSet(grandParentId)) { + if((status = ancestorBitmapPtr.bitmap_set(grandParentId)) == false) { + System.out.println("Assert failed: for ancestorBitmapPtr bitmap_set in net_findAncestors()"); + System.exit(0); + } + //assert(status); + if((status = workQueuePtr.queue_push(grandParentId)) == false) { + System.out.println("Assert failed: for workQueuePtr.queue_push in net_findAncestors()"); + System.exit(0); + } + //assert(status); + } + } + } + + return true; + } + + + /* ============================================================================= + * TMnet_findAncestors + * -- Contents of bitmapPtr set to 1 if ancestor, else 0 + * -- Returns false if id is not root node (i.e., has cycle back id) + * ============================================================================= + */ + /* + boolean + TMnet_findAncestors (TM_ARGDECL + net_t* netPtr, + int id, + Bitmap* ancestorBitmapPtr, + Queue* workQueuePtr) + { + boolean status; + + vector_t* nodeVectorPtr = netPtr.nodeVectorPtr; + assert(ancestorBitmapPtr.numBit == vector_getSize(nodeVectorPtr)); + + PBITMAP_CLEARALL(ancestorBitmapPtr); + PQUEUE_CLEAR(workQueuePtr); + + { + net_node_t* nodePtr = (net_node_t*)vector_at(nodeVectorPtr, id); + list_t* parentIdListPtr = nodePtr.parentIdListPtr; + list_iter_t it; + TMLIST_ITER_RESET(&it, parentIdListPtr); + while (TMLIST_ITER_HASNEXT(&it, parentIdListPtr)) { + int parentId = (int)TMLIST_ITER_NEXT(&it, parentIdListPtr); + status = PBITMAP_SET(ancestorBitmapPtr, parentId); + assert(status); + status = PQUEUE_PUSH(workQueuePtr, (void*)parentId); + assert(status); + } + } + + while (!PQUEUE_ISEMPTY(workQueuePtr)) { + int parentId = (int)PQUEUE_POP(workQueuePtr); + if (parentId == id) { + PQUEUE_CLEAR(workQueuePtr); + return false; + } + net_node_t* nodePtr = (net_node_t*)vector_at(nodeVectorPtr, parentId); + list_t* grandParentIdListPtr = nodePtr.parentIdListPtr; + list_iter_t it; + TMLIST_ITER_RESET(&it, grandParentIdListPtr); + while (TMLIST_ITER_HASNEXT(&it, grandParentIdListPtr)) { + int grandParentId = (int)TMLIST_ITER_NEXT(&it, grandParentIdListPtr); + if (!PBITMAP_ISSET(ancestorBitmapPtr, grandParentId)) { + status = PBITMAP_SET(ancestorBitmapPtr, grandParentId); + assert(status); + status = PQUEUE_PUSH(workQueuePtr, (void*)grandParentId); + assert(status); + } + } + } + + return true; + } + */ + + + /* ============================================================================= + * net_findDescendants + * -- Contents of bitmapPtr set to 1 if descendants, else 0 + * -- Returns false if id is not root node (i.e., has cycle back id) + * ============================================================================= + */ + public boolean + net_findDescendants (int id, + BitMap descendantBitmapPtr, + Queue workQueuePtr) + { + boolean status; + + //vector_t* nodeVectorPtr = netPtr.nodeVectorPtr; + if(descendantBitmapPtr.numBit == nodeVectorPtr.vector_getSize()) { + System.out.println("Assert failed: for descendantBitmapPtr.numbit in net_findDescendants()"); + System.exit(0); + } + //assert(descendantBitmapPtr.numBit == vector_getSize(nodeVectorPtr)); + + descendantBitmapPtr.bitmap_clearAll(); + workQueuePtr.queue_clear(); + + { + NetNode nodePtr = (NetNode)(nodeVectorPtr.vector_at(id)); + IntList childIdListPtr = nodePtr.childIdListPtr; + IntListNode it = childIdListPtr.head; + childIdListPtr.list_iter_reset(it); + + //net_node_t* nodePtr = (net_node_t*)vector_at(nodeVectorPtr, id); + //list_t* childIdListPtr = nodePtr.childIdListPtr; + //list_iter_t it; + //list_iter_reset(&it, childIdListPtr); + while (childIdListPtr.list_iter_hasNext(it)) { + it = it.nextPtr; + int childId = childIdListPtr.list_iter_next(it); + if((status = descendantBitmapPtr.bitmap_set(childId)) == false) { + System.out.println("Assert failed: for descendantBitmapPtr.bitmap_set in net_findDescendants()"); + System.exit(0); + } + //assert(status); + if((status = workQueuePtr.queue_push(childId)) == false) { + System.out.println("Assert failed: for workQueuePtr.queue_push in net_findDescendants()"); + System.exit(0); + } + //assert(status); + } + } + + while (!workQueuePtr.queue_isEmpty()) { + int childId = workQueuePtr.queue_pop(); + if (childId == id) { + workQueuePtr.queue_clear(); + return false; + } + + NetNode nodePtr = (NetNode)(nodeVectorPtr.vector_at(childId)); + IntList grandChildIdListPtr = nodePtr.childIdListPtr; + IntListNode it = grandChildIdListPtr.head; + grandChildIdListPtr.list_iter_reset(it); + //net_node_t* nodePtr = (net_node_t*)vector_at(nodeVectorPtr, childId); + //list_t* grandChildIdListPtr = nodePtr.childIdListPtr; + //list_iter_t it; + //list_iter_reset(&it, grandChildIdListPtr); + //while (list_iter_hasNext(&it, grandChildIdListPtr)) + while (grandChildIdListPtr.list_iter_hasNext(it)) { + it = it.nextPtr; + int grandChildId = grandChildIdListPtr.list_iter_next(it); + if (!descendantBitmapPtr.bitmap_isSet(grandChildId)) { + if((status = descendantBitmapPtr.bitmap_set(grandChildId)) == false) { + System.out.println("Assert failed: for descendantBitmapPtr.bitmap_set in net_findDescendants()"); + System.exit(0); + } + //assert(status); + if((status = workQueuePtr.queue_push(grandChildId)) == false) { + System.out.println("Assert failed: for workQueuePtr.queue_push in net_findDescendants()"); + System.exit(0); + } + //assert(status); + } + } + } + + return true; + } + + + /* ============================================================================= + * TMnet_findDescendants + * -- Contents of bitmapPtr set to 1 if descendants, else 0 + * -- Returns false if id is not root node (i.e., has cycle back id) + * ============================================================================= + */ + /* + boolean + TMnet_findDescendants (TM_ARGDECL + net_t* netPtr, + int id, + Bitmap* descendantBitmapPtr, + Queue* workQueuePtr) + { + boolean status; + + vector_t* nodeVectorPtr = netPtr.nodeVectorPtr; + assert(descendantBitmapPtr.numBit == vector_getSize(nodeVectorPtr)); + + PBITMAP_CLEARALL(descendantBitmapPtr); + PQUEUE_CLEAR(workQueuePtr); + + { + net_node_t* nodePtr = (net_node_t*)vector_at(nodeVectorPtr, id); + list_t* childIdListPtr = nodePtr.childIdListPtr; + list_iter_t it; + TMLIST_ITER_RESET(&it, childIdListPtr); + while (TMLIST_ITER_HASNEXT(&it, childIdListPtr)) { + int childId = (int)TMLIST_ITER_NEXT(&it, childIdListPtr); + status = PBITMAP_SET(descendantBitmapPtr, childId); + assert(status); + status = PQUEUE_PUSH(workQueuePtr, (void*)childId); + assert(status); + } + } + + while (!PQUEUE_ISEMPTY(workQueuePtr)) { + int childId = (int)PQUEUE_POP(workQueuePtr); + if (childId == id) { + queue_clear(workQueuePtr); + return false; + } + net_node_t* nodePtr = (net_node_t*)vector_at(nodeVectorPtr, childId); + list_t* grandChildIdListPtr = nodePtr.childIdListPtr; + list_iter_t it; + TMLIST_ITER_RESET(&it, grandChildIdListPtr); + while (TMLIST_ITER_HASNEXT(&it, grandChildIdListPtr)) { + int grandChildId = (int)TMLIST_ITER_NEXT(&it, grandChildIdListPtr); + if (!PBITMAP_ISSET(descendantBitmapPtr, grandChildId)) { + status = PBITMAP_SET(descendantBitmapPtr, grandChildId); + assert(status); + status = PQUEUE_PUSH(workQueuePtr, (void*)grandChildId); + assert(status); + } + } + } + + return true; + } + */ + + + /* ============================================================================= + * net_generateRandomEdges + * ============================================================================= + */ + public void + net_generateRandomEdges ( + int maxNumParent, + int percentParent, + Random randomPtr) + { + //Vector_t nodeVectorPtr = netPtr.nodeVectorPtr; + + int numNode = nodeVectorPtr.vector_getSize(); + BitMap visitedBitmapPtr = BitMap.bitmap_alloc(numNode); + if(visitedBitmapPtr == null) { + System.out.println("Assert failed: during bitmap_alloc in net_generateRandomEdges()"); + System.exit(0); + } + //assert(visitedBitmapPtr); + Queue workQueuePtr = Queue.queue_alloc(-1); + //Queue* workQueuePtr = queue_alloc(-1); + + //int n; + + for (int n = 0; n < numNode; n++) { + //int p; + for (int p = 0; p < maxNumParent; p++) { + int value = randomPtr.random_generate() % 100; + if (value < percentParent) { + int parent = randomPtr.random_generate() % numNode; + if ((parent != n) && + !net_hasEdge(parent, n) && + !net_isPath(n, parent, visitedBitmapPtr, workQueuePtr)) + { +#ifdef TEST_NET + System.out.println("node=" + n + " parent= " + parent); +#endif + insertEdge(parent, n); + } + } + } + } + + if(net_isCycle()) { + System.out.println("Assert failed: Cycle detected in net_generateRandomEdges()"); + System.exit(0); + } + //assert(!net_isCycle(netPtr)); + + visitedBitmapPtr.bitmap_free(); + workQueuePtr.queue_free(); + } + + + /* ############################################################################# + * TEST_NET + * ############################################################################# + */ + /* +#ifdef TEST_NET + +#include + + +int +main () +{ +int numNode = 100; + +puts("Starting tests..."); + +boolean status; + +net_t* netPtr = net_alloc(numNode); +assert(netPtr); +Bitmap* visitedBitmapPtr = bitmap_alloc(numNode); +assert(visitedBitmapPtr); +Queue* workQueuePtr = queue_alloc(-1); +assert(workQueuePtr); + +assert(!net_isCycle(netPtr)); + +int aId = 31; +int bId = 14; +int cId = 5; +int dId = 92; + +net_applyOperation(netPtr, OPERATION_INSERT, aId, bId); +assert(net_isPath(netPtr, aId, bId, visitedBitmapPtr, workQueuePtr)); +assert(!net_isPath(netPtr, bId, aId, visitedBitmapPtr, workQueuePtr)); +assert(!net_isPath(netPtr, aId, cId, visitedBitmapPtr, workQueuePtr)); +assert(!net_isPath(netPtr, aId, dId, visitedBitmapPtr, workQueuePtr)); +assert(!net_isCycle(netPtr)); + +net_applyOperation(netPtr, OPERATION_INSERT, bId, cId); +net_applyOperation(netPtr, OPERATION_INSERT, aId, cId); +net_applyOperation(netPtr, OPERATION_INSERT, dId, aId); +assert(!net_isCycle(netPtr)); +net_applyOperation(netPtr, OPERATION_INSERT, cId, dId); +assert(net_isCycle(netPtr)); +net_applyOperation(netPtr, OPERATION_REVERSE, cId, dId); +assert(!net_isCycle(netPtr)); +net_applyOperation(netPtr, OPERATION_REVERSE, dId, cId); +assert(net_isCycle(netPtr)); +assert(net_isPath(netPtr, aId, dId, visitedBitmapPtr, workQueuePtr)); +net_applyOperation(netPtr, OPERATION_REMOVE, cId, dId); +assert(!net_isPath(netPtr, aId, dId, visitedBitmapPtr, workQueuePtr)); + +Bitmap* ancestorBitmapPtr = bitmap_alloc(numNode); +assert(ancestorBitmapPtr); +status = net_findAncestors(netPtr, cId, ancestorBitmapPtr, workQueuePtr); +assert(status); +assert(bitmap_isSet(ancestorBitmapPtr, aId)); +assert(bitmap_isSet(ancestorBitmapPtr, bId)); +assert(bitmap_isSet(ancestorBitmapPtr, dId)); +assert(bitmap_getNumSet(ancestorBitmapPtr) == 3); + +Bitmap* descendantBitmapPtr = bitmap_alloc(numNode); +assert(descendantBitmapPtr); +status = net_findDescendants(netPtr, aId, descendantBitmapPtr, workQueuePtr); +assert(status); +assert(bitmap_isSet(descendantBitmapPtr, bId)); +assert(bitmap_isSet(descendantBitmapPtr, cId)); +assert(bitmap_getNumSet(descendantBitmapPtr) == 2); + +bitmap_free(visitedBitmapPtr); +queue_free(workQueuePtr); +bitmap_free(ancestorBitmapPtr); +bitmap_free(descendantBitmapPtr); + net_free(netPtr); + + random_t* randomPtr = random_alloc(); + assert(randomPtr); + netPtr = net_alloc(numNode); + assert(netPtr); + net_generateRandomEdges(netPtr, 10, 10, randomPtr); + net_free(netPtr); + + puts("All tests passed."); + + return 0; +} + + +#endif // TEST_NET +*/ + +} + + +/* ============================================================================= + * + * End of net.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/NetNode.java b/Robust/src/Benchmarks/SingleTM/Bayes/NetNode.java new file mode 100644 index 00000000..50a81da6 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/NetNode.java @@ -0,0 +1,26 @@ +public class NetNode { + int id; + int mark; + IntList parentIdListPtr; + IntList childIdListPtr; + int NET_NODE_MARK_INIT; + int NET_NODE_MARK_DONE; + int NET_NODE_MARK_TEST; + + public NetNode() { + mark = 0; + NET_NODE_MARK_INIT = 0; + NET_NODE_MARK_DONE = 1; + NET_NODE_MARK_TEST = 2; + } + + /* ============================================================================= + * freeNode + * ============================================================================= + */ + public void freeNode () + { + childIdListPtr = null; + parentIdListPtr = null; + } +} diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Operation.java b/Robust/src/Benchmarks/SingleTM/Bayes/Operation.java new file mode 100644 index 00000000..f346daa8 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Operation.java @@ -0,0 +1,72 @@ +/* ============================================================================= + * + * operation.java + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * Modified : Ported to Java on June 2009 by Alokika Dash + * University of California, Irvine + * + * ============================================================================= + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * 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. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * * Neither the name of Stanford 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 STANFORD UNIVERSITY ``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 STANFORD UNIVERSITY 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. + * + * ============================================================================= + */ + +public class Operation { + int insert; + int remove; + int reverse; + int num_operation; + + /* + * All operations are performed from:other to:this + */ + public Operation() { + insert = 0; + remove = 1; + reverse = 2; + num_operation = 3; + } +} + +/* ============================================================================= + * + * End of operation.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Query.java b/Robust/src/Benchmarks/SingleTM/Bayes/Query.java new file mode 100644 index 00000000..a006f745 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Query.java @@ -0,0 +1,66 @@ +/* ============================================================================= + * + * query.java + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * + * Modified: Ported to Java on June 2009 by Alokika Dash + * University of California, Irvine + * + * + * ============================================================================= + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * 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. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * * Neither the name of Stanford 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 STANFORD UNIVERSITY ``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 STANFORD UNIVERSITY 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. + * + * ============================================================================= + */ + +public class Query { + int index; + int value; + + public Query() { + + } +} + +/* ============================================================================= + * + * End of query.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Queue.java b/Robust/src/Benchmarks/SingleTM/Bayes/Queue.java new file mode 100644 index 00000000..a6b816a4 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Queue.java @@ -0,0 +1,489 @@ +/* ============================================================================= + * + * queue.java + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * + * Ported to Java June 2009 Alokika Dash + * adash@uci.edu + * University of California, Irvine + * + * ============================================================================= + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * 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. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * * Neither the name of Stanford 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 STANFORD UNIVERSITY ``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 STANFORD UNIVERSITY 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. + * + * ============================================================================= + */ + +#define QUEUE_GROWTH_FACTOR 2 + +public class Queue { + int pop; /* points before element to pop */ + int push; + int capacity; + int[] elements; + + public Queue() { + } + + /* ============================================================================= + * queue_alloc + * ============================================================================= + */ + public static Queue queue_alloc (int initCapacity) + { + Queue queuePtr = new Queue(); + + int capacity = ((initCapacity < 2) ? 2 : initCapacity); + queuePtr.elements = new int[capacity]; + if (queuePtr.elements == null) { + queuePtr = null; + return null; + } + queuePtr.pop = capacity - 1; + queuePtr.push = 0; + queuePtr.capacity = capacity; + + return queuePtr; + } + + + /* ============================================================================= + * Pqueue_alloc + * ============================================================================= + */ + public Queue + Pqueue_alloc (int initCapacity) + { + Queue queuePtr = new Queue(); + + int capacity = ((initCapacity < 2) ? 2 : initCapacity); + queuePtr.elements = new int[capacity]; + if (queuePtr.elements == null) { + queuePtr = null; + return null; + } + queuePtr.pop = capacity - 1; + queuePtr.push = 0; + queuePtr.capacity = capacity; + + return queuePtr; + } + + + /* ============================================================================= + * TMqueue_alloc + * ============================================================================= + */ + public Queue TMqueue_alloc (int initCapacity) + { + Queue queuePtr = new Queue(); + + int capacity = ((initCapacity < 2) ? 2 : initCapacity); + queuePtr.elements = new int[capacity]; + if (queuePtr.elements == null) { + queuePtr = null; + return null; + } + queuePtr.pop = capacity - 1; + queuePtr.push = 0; + queuePtr.capacity = capacity; + + return queuePtr; + } + + + /* ============================================================================= + * queue_free + * ============================================================================= + */ + public void + queue_free () + { + elements = null; + } + + + /* ============================================================================= + * Pqueue_free + * ============================================================================= + */ + public void + Pqueue_free () + { + elements = null; + } + + + /* ============================================================================= + * TMqueue_free + * ============================================================================= + */ + public void + TMqueue_free () + { + elements = null; + } + + + /* ============================================================================= + * queue_isEmpty + * ============================================================================= + */ + public boolean + queue_isEmpty () + { + //int pop = queuePtr.pop; + //int push = queuePtr.push; + //int capacity = queuePtr.capacity; + + return (((pop + 1) % capacity == push) ? true : false); + } + + + /* ============================================================================= + * queue_clear + * ============================================================================= + */ + public void + queue_clear () + { + pop = capacity - 1; + push = 0; + } + + + /* ============================================================================= + * TMqueue_isEmpty + * ============================================================================= + */ + public boolean + TMqueue_isEmpty (Queue queuePtr) + { + int pop = queuePtr.pop; + int push = queuePtr.push; + int capacity = queuePtr.capacity; + + return (((pop + 1) % capacity == push) ? true : false); + } + + + /* ============================================================================= + * queue_shuffle + * ============================================================================= + */ + public void + queue_shuffle (Queue queuePtr, Random randomPtr) + { + int pop = queuePtr.pop; + int push = queuePtr.push; + int capacity = queuePtr.capacity; + + int numElement; + if (pop < push) { + numElement = push - (pop + 1); + } else { + numElement = capacity - (pop - push + 1); + } + + int[] elements = queuePtr.elements; + int i; + int base = pop + 1; + for (i = 0; i < numElement; i++) { + int r1 = randomPtr.random_generate() % numElement; + int r2 = randomPtr.random_generate() % numElement; + int i1 = (base + r1) % capacity; + int i2 = (base + r2) % capacity; + int tmp = elements[i1]; + elements[i1] = elements[i2]; + elements[i2] = tmp; + } + } + + + /* ============================================================================= + * queue_push + * ============================================================================= + */ + public boolean + queue_push (int dataPtr) + { + if(pop == push) { + System.out.println("push == pop in Queue.java"); + return false; + } + + /* Need to resize */ + int newPush = (push + 1) % capacity; + if (newPush == pop) { + + int newCapacity = capacity * QUEUE_GROWTH_FACTOR; + int[] newElements = new int[newCapacity]; + if (newElements == null) { + return false; + } + + int dst = 0; + int[] tmpelements = elements; + if (pop < push) { + int src; + for (src = (pop + 1); src < push; src++, dst++) { + newElements[dst] = elements[src]; + } + } else { + int src; + for (src = (pop + 1); src < capacity; src++, dst++) { + newElements[dst] = elements[src]; + } + for (src = 0; src < push; src++, dst++) { + newElements[dst] = elements[src]; + } + } + + //elements = null; + elements = newElements; + pop = newCapacity - 1; + capacity = newCapacity; + push = dst; + newPush = push + 1; /* no need modulo */ + } + + elements[push] = dataPtr; + push = newPush; + + return true; + } + + + /* ============================================================================= + * Pqueue_push + * ============================================================================= + */ + public boolean + Pqueue_push (Queue queuePtr, int dataPtr) + { + int pop = queuePtr.pop; + int push = queuePtr.push; + int capacity = queuePtr.capacity; + + if(pop == push) { + System.out.println("push == pop in Queue.java"); + return false; + } + + /* Need to resize */ + int newPush = (push + 1) % capacity; + if (newPush == pop) { + + int newCapacity = capacity * QUEUE_GROWTH_FACTOR; + int[] newElements = new int[newCapacity]; + if (newElements == null) { + return false; + } + + int dst = 0; + int[] elements = queuePtr.elements; + if (pop < push) { + int src; + for (src = (pop + 1); src < push; src++, dst++) { + newElements[dst] = elements[src]; + } + } else { + int src; + for (src = (pop + 1); src < capacity; src++, dst++) { + newElements[dst] = elements[src]; + } + for (src = 0; src < push; src++, dst++) { + newElements[dst] = elements[src]; + } + } + + elements = null; + queuePtr.elements = newElements; + queuePtr.pop = newCapacity - 1; + queuePtr.capacity = newCapacity; + push = dst; + newPush = push + 1; /* no need modulo */ + + } + + queuePtr.elements[push] = dataPtr; + queuePtr.push = newPush; + + return true; + } + + + /* ============================================================================= + * TMqueue_push + * ============================================================================= + */ + public boolean + TMqueue_push (Queue queuePtr, int dataPtr) + { + int pop = (queuePtr.pop); + int push = (queuePtr.push); + int capacity = (queuePtr.capacity); + + if(pop == push) { + System.out.println("push == pop in Queue.java"); + return false; + } + + /* Need to resize */ + int newPush = (push + 1) % capacity; + if (newPush == pop) { + int newCapacity = capacity * QUEUE_GROWTH_FACTOR; + int[] newElements = new int[newCapacity]; + if (newElements == null) { + return false; + } + + int dst = 0; + int[] elements = queuePtr.elements; + if (pop < push) { + int src; + for (src = (pop + 1); src < push; src++, dst++) { + newElements[dst] = (elements[src]); + } + } else { + int src; + for (src = (pop + 1); src < capacity; src++, dst++) { + newElements[dst] = (elements[src]); + } + for (src = 0; src < push; src++, dst++) { + newElements[dst] = (elements[src]); + } + } + + elements = null; + queuePtr.elements = newElements; + queuePtr.pop = newCapacity - 1; + queuePtr.capacity = newCapacity; + push = dst; + newPush = push + 1; /* no need modulo */ + + } + + int[] elements = queuePtr.elements; + elements[push] = dataPtr; + queuePtr.push = newPush; + + return true; + } + + + /* ============================================================================= + * queue_pop + * ============================================================================= + */ + public int + //queue_pop (Queue queuePtr) + queue_pop () + { + //int pop = queuePtr.pop; + //int push = queuePtr.push; + //int capacity = queuePtr.capacity; + + int newPop = (pop + 1) % capacity; + if (newPop == push) { + return 0; + } + + //int dataPtr = queuePtr.elements[newPop]; + //queuePtr.pop = newPop; + int dataPtr = elements[newPop]; + pop = newPop; + + return dataPtr; + } + + + /* ============================================================================= + * TMqueue_pop + * ============================================================================= + */ + public int + TMqueue_pop (Queue queuePtr) + { + int pop = queuePtr.pop; + int push = queuePtr.push; + int capacity = queuePtr.capacity; + + int newPop = (pop + 1) % capacity; + if (newPop == push) { + return 0; + } + + int[] elements = queuePtr.elements; + int dataPtr = elements[newPop]; + queuePtr.pop = newPop; + + return dataPtr; + } + + /**** + * main method for testing + **/ + /* + public static void main(String[] args) { + testQueue queuePtr = testQueue.queue_alloc(-1); + int numData = 4; + if(queuePtr.queue_isEmpty()) + System.out.println("Queue is empty"); + + for(int i = 0; i \ + -i \ + -n \ + -p \ + -q \ + -r \ + -s \ + -t \ + -v + +The data to learn from is randomly generated from a randomly generated Bayesian +network with the following properties: + + 1) Consists of -v variables + 2) Each variable has at most -n parents + 3) The number of parents per variable will be, on average, -n * -p + +From this "master" Bayesian network, -r random records are generated and used +as the input for the structure learning algorithm. + +The following arguments are recommended for simulated runs: + + -v 32 -r 1024 -n 2 -p 20 -s 0 -i 2 -e 2 -t 1 + +For non-simulator runs, a larger Bayesian network can be learned: + + -v 32 -r 4096 -n 10 -p 40 -i 2 -e 8 -s 1 -t 1 + +For multithreaded runs, the runing time can vary depending on the insertion +order of edges. + + +References +---------- + +[1] C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford + Transactional Applications for Multi-processing. In IISWC '08: Proceedings + of The IEEE International Symposium on Workload Characterization, + September 2008. + +[2] D. M. Chickering, D. Heckerman, and C. Meek. A Bayesian approach to learning + Bayesian networks with local structure. In Proceedings of Thirteenth + Conference on Uncertainty in Artificial Intelligence, 1997. + +[3] A. Moore and M.-S. Lee. Cached sufficient statistics for efficient machine + learning with large datasets. Journal of Artificial Intelligence Research 8, + 1998. diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Sort.java b/Robust/src/Benchmarks/SingleTM/Bayes/Sort.java new file mode 100644 index 00000000..30272640 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Sort.java @@ -0,0 +1,282 @@ +/* ============================================================================= + * + * sort.java + * + * ============================================================================= + * + * Quick sort + * + * Copyright (C) 2002 Michael Ringgaard. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the project 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 COPYRIGHT HOLDERS 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 COPYRIGHT OWNER 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 + * + * ============================================================================= + * + * Modifed October 2007 by Chi Cao Minh + * -- Changed signature of comparison function + * + * ============================================================================= + * + * For the license of bayes/sort.h and bayes/sort.c, please see the header + * of the files. + * + * ------------------------------------------------------------------------ + * + * For the license of kmeans, please see kmeans/LICENSE.kmeans + * + * ------------------------------------------------------------------------ + * + * For the license of ssca2, please see ssca2/COPYRIGHT + * + * ------------------------------------------------------------------------ + * + * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the + * header of the files. + * + * ------------------------------------------------------------------------ + * + * For the license of lib/rbtree.h and lib/rbtree.c, please see + * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree + * + * ------------------------------------------------------------------------ + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * 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. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * * Neither the name of Stanford 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 STANFORD UNIVERSITY ``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 STANFORD UNIVERSITY 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. + * + * ============================================================================= + */ + +//#include "sort.h" + +#define CUTOFF 8 + +public class Sort { + + public Sort() { + + } + /* ============================================================================= + * swap + * ============================================================================= + */ + public static void + swap (char[] base, int a, int b, int width) + { + if (a != b) { + while (width--) { + char tmp = base[a]; + base[a++] = base[b]; + base[b++] = tmp; + } + } + } + + + /* ============================================================================= + * shortsort + * ============================================================================= + */ + public static void + shortsort (char[] base, + int lo, + int hi, + int width, + int n, + int offset) + { + while (hi > lo) { + int max = lo; + int p; + for (p = (lo + width); p <= hi; p += width) { + if (cmp(base, p, max, n, offset) > 0) { + max = p; + } + } + swap(base, max, hi, width); + hi -= width; + } + } + + + /* ============================================================================= + * sort + * ============================================================================= + */ + public void + sort (char[] base, + int start, + int num, + int width, + int n, + int offset) + { + if (num < 2 || width == 0) { + return; + } + + int lo = start; + int hi = start + (width * (num - 1)); + + //System.out.println("start= " + start + " base.length= " + base.length + " hi= " + hi); + + recurse(base, lo, hi, width, n, offset); + + } + + public void recurse(char[] base, int lo, int hi, int width, int n, int offset) + { + char[] lostk= new char[30]; + char[] histk= new char[30]; + + int stkptr = 0; + int size; + //recurse: + + size = (hi - lo) / width + 1; + + if (size <= CUTOFF) { + + shortsort(base, lo, hi, width, n, offset); + + } else { + + int mid = lo + (size / 2) * width; + swap(base, mid, lo, width); + + int loguy = lo; + int higuy = hi + width; + + boolean status = true; + while(true) { + do { + loguy += width; + } while (loguy <= hi && cmp(base, loguy, lo, n, offset) <= 0); + do { + higuy -= width; + } while (higuy > lo && cmp(base, higuy, lo, n, offset) >= 0); + if (higuy < loguy) { + break; + } + swap(base, loguy, higuy, width); + } + + swap(base, lo, higuy, width); + + if ((higuy - 1 - lo) >= (hi - loguy)) { + if (lo + width < higuy) { + lostk[stkptr] = base[lo]; + histk[stkptr] = base[higuy - width]; + ++stkptr; + } + + if (loguy < hi) { + lo = loguy; + recurse(base, lo, hi, width, n, offset); + } + } else { + if (loguy < hi) { + lostk[stkptr] = base[loguy]; + histk[stkptr] = base[hi]; + ++stkptr; + } + if (lo + width < higuy) { + hi = higuy - width; + recurse(base, lo, hi, width, n, offset); + } + } + } + + --stkptr; + if (stkptr >= 0) { + base[lo] = lostk[stkptr]; + base[hi] = histk[stkptr]; + recurse(base, lo, hi, width, n, offset); + } + } + + /* ============================================================================= + * compareRecord + * ============================================================================= + */ + public static int + cmp(char[] base, int p1, int p2, int n, int offset) + { + int i = n - offset; + int s1 = p1 + offset; + int s2 = p2 + offset; + + //const char* s1 = (const char*)p1 + offset; + //const char* s2 = (const char*)p2 + offset; + + while (i-- > 0) { + char u1 = base[s1]; + char u2 = base[s2]; + //unsigned char u1 = (unsigned char)*s1++; + //unsigned char u2 = (unsigned char)*s2++; + if (u1 != u2) { + return (u1 - u2); //CAN YOU DO THIS + } + } + + return 0; + } +} +/* ============================================================================= + * + * End of sort.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/makefile b/Robust/src/Benchmarks/SingleTM/Bayes/makefile new file mode 100644 index 00000000..52305979 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/makefile @@ -0,0 +1,58 @@ +MAINCLASS=Bayes +SRC=tmp${MAINCLASS}.java \ + Adtree.java \ + AdtreeNode.java \ + AdtreeVary.java \ + tmpData.java \ + FindBestTaskArg.java \ + tmpLearner.java \ + LearnerTask.java \ + tmpNet.java \ + NetNode.java \ + Operation.java \ + Query.java \ + tmpSort.java \ + tmpBitMap.java \ + tmpIntList.java \ + IntListNode.java \ + tmpQueue.java \ + ../common/Random.java \ + ../common/Vector_t.java \ + ../common/ListNode.java \ + ../common/List.java \ + ../common/QuickSort.java \ + IntVector.java + +FLAGS=-mainclass ${MAINCLASS} -thread -nooptimize -debug + +default: + cpp Bayes.java > tmp1Bayes.java + cpp Data.java > tmp1Data.java + cpp Net.java > tmp1Net.java + cpp Sort.java > tmp1Sort.java + cpp ../common/BitMap.java > tmp1BitMap.java + cpp Queue.java > tmp1Queue.java + cpp -DLEARNER_TRY_REMOVE -DLEARNER_TRY_REVERSE Learner.java > tmp1Learner.java + cpp -DLIST_NO_DUPLICATES IntList.java > tmp1IntList.java + ./extractLines + ../../../buildscript ${FLAGS} -o ${MAINCLASS} ${SRC} + +clean: + rm tmp1Bayes.java + rm tmpBayes.java + rm tmp1Learner.java + rm tmpLearner.java + rm tmp1IntList.java + rm tmpIntList.java + rm tmp1Data.java + rm tmpData.java + rm tmp1Net.java + rm tmpNet.java + rm tmp1Sort.java + rm tmpSort.java + rm tmp1BitMap.java + rm tmpBitMap.java + rm tmp1Queue.java + rm tmpQueue.java + rm -rf tmpbuilddirectory + rm *.bin -- 2.34.1