hypercube.cpp

Go to the documentation of this file.

// Copyright (c) 2020, the GRAPHGEN contributors, as
// shown by the AUTHORS file. All rights reserved.
//
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
 
#include "hypercube.h"
 
#include "utilities.h"
 
using namespace std;
 
void CreateTree_rec(BinaryDrag<conact>& t, BinaryDrag<conact>::node *n, const rule_set& rs, const VHyperCube &hcube, const VIndex &idx) {
    VNode node = hcube[idx];
    if (node.uiAction == 0) {
        n->data.t = conact::type::CONDITION;
        n->data.condition = rs.conditions[node.uiMaxGainIndex];
 
        // Extract the two (n-1)-cubes
        string sChild0(idx.GetIndexString());
        string sChild1(sChild0);
        sChild0[node.uiMaxGainIndex] = '0';
        sChild1[node.uiMaxGainIndex] = '1';
        VIndex idx0(sChild0), idx1(sChild1);
 
        CreateTree_rec(t, n->left = t.make_node(), rs, hcube, idx0);
        CreateTree_rec(t, n->right = t.make_node(), rs, hcube, idx1);
    }
    else {
        n->data.t = conact::type::ACTION;
        n->data.action = node.uiAction;
    }
}
 
BinaryDrag<conact> VHyperCube::optimize(bool bVerbose)
{
    std::string s;
    s.resize(m_iDim, '0');
    VIndex idx(s);
    if (bVerbose) {
        // Print the table
        do {
            std::cout << idx.GetIndexString() << "\t" << m_arrIndex[idx.GetIndex()].uiProb << "\t";
            if (m_arrIndex[idx.GetIndex()].uiAction == 0)
                std::cout << "0";
            else
                for (size_t i = 1; i < 128; i++)
                    if (m_arrIndex[idx.GetIndex()].uiAction[i - 1])
                        std::cout << i << ",";
            std::cout << "\n";
        } while (idx.MoveNext());
        std::cout << "------------------------\n";
    }
 
    for (size_t iNumIndifference = 1; iNumIndifference <= m_iDim; iNumIndifference++) {
        if (!bVerbose)
            std::cout << iNumIndifference << " " << std::flush;
        // Initialize the Indifferences
        bool bFine;
        std::vector<size_t> arrPosIndifference(iNumIndifference);
        int iPos = 0;
        for (size_t i = 0; i < iNumIndifference; i++) {
            arrPosIndifference[i] = iPos;
            iPos++;
        }
 
        std::vector</*unsigned*/unsigned long long> arrProb(iNumIndifference);
        std::vector</*unsigned*/unsigned long long> arrGain(iNumIndifference);
        std::vector<unsigned> arrNEq(iNumIndifference);
 
        // Do all the combinations
        do {
            // Generate the Indifference Mask
            std::string s;
            s.resize(m_iDim, '0');
            for (size_t i = 0; i < iNumIndifference; i++)
                s[arrPosIndifference[i]] = '-';
 
            // Print all the combinations
            if (!idx.SetIndex(s))
                throw;
            do {
                for (size_t i = 0; i < iNumIndifference; i++) {
                    std::string sChild0(idx.GetIndexString());
                    std::string sChild1(sChild0);
                    sChild0[arrPosIndifference[i]] = '0';
                    sChild1[arrPosIndifference[i]] = '1';
                    VIndex idx0(sChild0), idx1(sChild1);
                    VNode node0(m_arrIndex[idx0.GetIndex()]), node1(m_arrIndex[idx1.GetIndex()]);
 
                    // Calculate the intersection of all possible actions
                    auto uiIntersezione = node0.uiAction & node1.uiAction;
 
                    m_arrIndex[idx.GetIndex()].uiAction = uiIntersezione;
                    arrProb[i] = node0.uiProb + node1.uiProb;
                    arrGain[i] = node0.uiGain + node1.uiGain;
                    arrNEq[i] = node0.neq * node1.neq;
 
                    if (uiIntersezione != 0) {
                        arrGain[i] += arrProb[i];
                        arrNEq[i] = 0;
                    }
                }
                /*unsigned*/unsigned long long uiMaxGain(0);
                /*unsigned*/unsigned long long uiMaxGainProb(0);
                size_t uiMaxGainIndex(0);
                unsigned uiNEq(0);
                for (size_t i = 0; i < iNumIndifference; i++) {
                    if (uiMaxGain <= arrGain[i]) {
                        if (uiMaxGain < arrGain[i])
                            uiNEq = arrNEq[i];
                        else
                            uiNEq += arrNEq[i];
                        uiMaxGain = arrGain[i];
                        uiMaxGainProb = arrProb[i];
                        uiMaxGainIndex = arrPosIndifference[i];
                    }
                }
                m_arrIndex[idx.GetIndex()].uiGain = uiMaxGain;
                m_arrIndex[idx.GetIndex()].uiProb = uiMaxGainProb;
                m_arrIndex[idx.GetIndex()].uiMaxGainIndex = static_cast<::byte>(uiMaxGainIndex);
                m_arrIndex[idx.GetIndex()].neq = std::max(uiNEq, 1u);
 
                if (bVerbose) {
                    std::cout << idx.GetIndexString() << "\t" << m_arrIndex[idx.GetIndex()].uiProb << "\t";
                    if (m_arrIndex[idx.GetIndex()].uiAction == 0)
                        std::cout << "0";
                    else
                        for (unsigned j = 1; j < 32; j++)
                            if (m_arrIndex[idx.GetIndex()].uiAction[j - 1])
                                std::cout << j << ",";
                    std::cout << "\t";
 
                    for (size_t i = 0; i < iNumIndifference; i++) {
                        std::cout << arrGain[i];
                        if (arrPosIndifference[i] == uiMaxGainIndex)
                            std::cout << "*";
                        else if (arrGain[i] == uiMaxGain)
                            std::cout << "#";
                        std::cout << "\t";
                    }
 
                    std::cout << m_arrIndex[idx.GetIndex()].neq << "\n";
                }
            } while (idx.MoveNext());
            if (bVerbose)
                std::cout << "\n";
 
            // Move on to the next permutation of indifference
            bFine = true;
            for (int i = int(iNumIndifference) -1; i >= 0; i--) {
                arrPosIndifference[i]++;
                // Does this have a valid position?
                if (arrPosIndifference[i] < m_iDim) {
                    // Are there any other indifferences?
                    if (m_iDim - 1 - arrPosIndifference[i] >= iNumIndifference - 1 - i) {
                        // The position is valid, there are positions, 
                        // therefore, we fix the following indifferences
                        iPos = int(arrPosIndifference[i]) + 1;
                        for (size_t j = i + 1; j < iNumIndifference; j++) {
                            arrPosIndifference[j] = iPos;
                            iPos++;
                        }
                        bFine = false;
                        break;
                    }
                }
            }
        } while (!bFine);
        if (bVerbose)
            std::cout << "------------------------\n";
    }
 
    BinaryDrag<conact> t;
    CreateTree_rec(t, t.make_root(), m_rs, *this, string(m_iDim, '-'));
    return t;
}
 
BinaryDrag<conact> GenerateOdt(const rule_set& rs) {
    TLOG("Allocating hypercube",
        VHyperCube hcube(rs);
    );
 
    TLOG("Optimizing rules",
        auto t = hcube.optimize(false);
    );
 
    return t;
}
 
BinaryDrag<conact> GenerateOdt(const rule_set& rs, const string& filename) 
{
    auto t = GenerateOdt(rs);
    WriteConactTree(t, filename);
    return t;
}
 
BinaryDrag<conact> GetOdt(const rule_set& rs, bool force_generation) {
    string odt_filename = conf.odt_path_.string();
    BinaryDrag<conact> t;
    if (conf.force_odt_generation_ || force_generation || !LoadConactTree(t, odt_filename)) {
        t = GenerateOdt(rs, odt_filename);
    }
    return t;
}
 
BinaryDrag<conact> GetOdtWithFileSuffix(const rule_set& rs, const string& file_suffix, bool force_generation) {
    string odt_filename = conf.GetCustomOdtPath(file_suffix).string();
    BinaryDrag<conact> t;
    if (conf.force_odt_generation_ || force_generation || !LoadConactTree(t, odt_filename)) {
        t = GenerateOdt(rs, odt_filename);
    }
    return t;
}