ConnectivityChecker.cpp

Go to the documentation of this file.

#include "ConnectivityChecker.hpp"
#include <iostream>

namespace ISM
{

        ConnectivityChecker::ConnectivityChecker(std::map<std::string, unsigned int> numObjectsPerPattern)
        {
                mNumObjectsPerPattern = numObjectsPerPattern;
                for (std::map<std::string, unsigned int>::iterator it = numObjectsPerPattern.begin(); it != numObjectsPerPattern.end(); ++it)
                {
                        unsigned int numObjects = it->second;

                        std::vector<Relation> relations;

                        for (unsigned int i = 0; i < numObjects; ++i)
                        {
                                for (unsigned int j = i + 1; j < numObjects; ++j)
                                {
                                        relations.push_back({i, j});
                                }
                        }

                        mRelationsPerPattern[it->first] = relations;
                }
        }

        bool ConnectivityChecker::isConnected(std::vector<bool> bitvector, const std::string& patternName)
        {
                unsigned int numOnesInVector = 0;
                for (bool bit : bitvector)
                {
                        numOnesInVector += bit;
                }

                if (numOnesInVector < mNumObjectsPerPattern[patternName] - 1)
                {
                        //A topology needs at least #objects - 1 relations to be connected.
                        return false;
                }

                std::stack<unsigned int>().swap(mToVisit);
                mVisited.clear();

                visitNeighbours(patternName, 0, bitvector);

                while(!mToVisit.empty())
                {
                        unsigned int toVisit = mToVisit.top();
                        mToVisit.pop();
                        visitNeighbours(patternName, toVisit, bitvector);
                }

                return mVisited.size() == mNumObjectsPerPattern[patternName];
        }

        void ConnectivityChecker::checkNeighbour(const::std::string &patternName, unsigned int from, unsigned int index, std::vector<bool> bitvector)
        {
                if (bitvector[index])
                {
                        int neighbour = mRelationsPerPattern[patternName][index].getNeighbour(from);
                        if (mVisited.find(neighbour) == mVisited.end())
                        {
                                mToVisit.push(neighbour);
                        }
                }
        }

        void ConnectivityChecker::visitNeighbours(const std::string& patternName, unsigned int from, std::vector<bool> bitvector)
        {
                mVisited.insert(from);
                unsigned int numObjects = mNumObjectsPerPattern[patternName];
                int index = 0;
                for (unsigned int i = 0; i < from; ++i)
                {
                        checkNeighbour(patternName, from, index + from - (i + 1), bitvector);
                        index += numObjects - (i + 1);
                }

                for (unsigned int i = index; i < index + numObjects - (from + 1); ++i)
                {
                        checkNeighbour(patternName, from, i, bitvector);
                }
        }
}