NPC series of articles (2)—A greedy algorithm for the minimum coverage problem Set Cover Problem to find the entire coverage set

QT = core

CONFIG+=c++11 cmdline

# You can make your code fail to compile if it uses deprecated APIs.
# In order to do so, uncomment the following line.
#DEFINES + = QT_DISABLE_DEPRECATED_BEFORE=0x060000 # disables all the APIs deprecated before Qt 6.0.0

SOURCES + = \
        cprecisetimer.cpp\
        main.cpp\
        simplegraph.cpp

# Default rules for deployment.
qnx: target.path = /tmp/$${TARGET}/bin
else: unix:!android: target.path = /opt/$${TARGET}/bin
!isEmpty(target.path): INSTALLS + = target

HEADERS + = \
    commondatastructure.h \
    cprecisetimer.h \
    simplegraph.h

#ifndef COMMONDATASTRUCTURE_H
#defineCOMMONDATASTRUCTURE_H

#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <map>
#include <list>

#include "assert.h"
//using namespace std;

const int MAXVERTEX = 40;

typedef std::set<int> ADJPOINTSSET; //Adjacent vertex set
typedef std::pair<int, ADJPOINTSSET> ADJPOINTSPAIR; //Adjacent vertex set and its base (size)
typedef std::map<int, ADJPOINTSPAIR> VERTEXMAP; //The mapping between a vertex and its adjacent vertex set
typedef VERTEXMAP GRAPH_ADJLIST_MAP; //G’s adjacency list List representation

typedef std::vector<std::vector<bool> > GRAPH_ADJARRAY_VECTOR; //Adjacency matrix Vector representation of G
typedef std::vector<int> OFFSET_VECTOR;

typedef ADJPOINTSSET VERTEXCOVER;

#endif //COMMONDATASTRUCTURE_H

#ifndef CPRECISETIMER_H
#define CPRECISETIMER_H

#include <windows.h>

classCPreciseTimer
{
public:
    CPreciseTimer();

    bool SupportsHighResCounter();
    void StartTimer();
    void StopTimer();
    __int64 GetTime();

private:
    //Auxiliary Function
    void UpdateElapsed();

    //Member variables
    bool m_bRunning;
    __int64 m_i64Start;
    __int64 m_i64Elapsed;

    //Some auxiliary variables
    __int64 m_i64Counts;
    LARGE_INTEGER m_liCount;

    //Static Variables
    static bool sm_bInit;
    static bool sm_bPerformanceCounter;
    static __int64 sm_i64Freq;
};

inline bool CPreciseTimer::SupportsHighResCounter()
{
    return sm_bPerformanceCounter;
}

//Auxiliary Function
inline void CPreciseTimer::UpdateElapsed()
{
    if(true == sm_bPerformanceCounter)
    {
        QueryPerformanceCounter( & amp;m_liCount);
        m_i64Counts = ((__int64)m_liCount.HighPart << 32) + (__int64)m_liCount.LowPart;
        //Transform in microseconds
        (m_i64Counts *= 1000000) /= sm_i64Freq;
    }
    else
        //Transform milliseconds to microseconds
        m_i64Counts = (__int64)GetTickCount() * 1000;
    if(m_i64Counts > m_i64Start)
        m_i64Elapsed = m_i64Counts - m_i64Start;
    else
        //Eliminate possible number overflow (0x7ffffffffffffffff is the maximal __int64 positive number)
        m_i64Elapsed = (0x7ffffffffffffffff - m_i64Start) + m_i64Counts;
}

#endif // CPRECISETIMER_H

#include "cprecisetimer.h"

bool CPreciseTimer::sm_bInit = false;
bool CPreciseTimer::sm_bPerformanceCounter;
__int64 CPreciseTimer::sm_i64Freq;

//CONSTRUCTOR
CPreciseTimer::CPreciseTimer() : m_i64Start(0), m_i64Elapsed(0), m_bRunning(false)
{
    //Only if not already initialized
    if(false == sm_bInit)
    {
        //Initializing some static variables dependent on the system just once
        LARGE_INTEGER liFreq;
        if(TRUE == QueryPerformanceFrequency( & amp;liFreq))
        {
            //Only if the system is supporting High Performance
            sm_i64Freq = ((__int64)liFreq.HighPart << 32) + (__int64)liFreq.LowPart;
            sm_bPerformanceCounter = true;
        }
        else
            sm_bPerformanceCounter = false;
        sm_bInit = true;
    }
}

void CPreciseTimer::StartTimer()
{
    if(true == sm_bPerformanceCounter)
    {
        QueryPerformanceCounter( & amp;m_liCount);
        m_i64Start = ((__int64)m_liCount.HighPart << 32) + (__int64)m_liCount.LowPart;
        //Transform in microseconds
        (m_i64Start *= 1000000) /= sm_i64Freq;
    }
    else
        //Transform milliseconds to microseconds
        m_i64Start = (__int64)GetTickCount() * 1000;
    m_bRunning = true;
}

void CPreciseTimer::StopTimer()
{
    UpdateElapsed();
    m_bRunning = false;
}

__int64 CPreciseTimer::GetTime()
{
    if(true == m_bRunning)
        UpdateElapsed();
    return m_i64Elapsed;
}

#ifndef SIMPLEGRAPH_H
#define SIMPLEGRAPH_H

#include "commondatastructure.h"

class SimpleGraph
{
public:
    SimpleGraph(const GRAPH_ADJARRAY_VECTOR adjgraph);

    VERTEXCOVER getVertexCover();

    void help(); //print adj array
    void print(); //print adj list

    void inc(int keyVertex, int targetVertex);
    void dec(int keyVertex, int targetVertex);

    bool checkIsCover(std::vector<int> & amp;vertexSet);

    static void printVertexSet(VERTEXCOVER s);

    static std::vector<std::vector<int> > getCombineNK(int n, int k);
    static void showCombinationvector( std::vector<std::vector<int> > va );

    static OFFSET_VECTOR globalOffset;

private:
    GRAPH_ADJLIST_MAP m_dstAdjList;
    GRAPH_ADJARRAY_VECTOR m_srcAdjArray;

    void adjArray2adjList(const GRAPH_ADJARRAY_VECTOR & amp;srcAdjArray, GRAPH_ADJLIST_MAP & amp;dstAdjList);
};

#endif // SIMPLEGRAPH_H

#include "simplegraph.h"

#define PRINTINFO 1
//const int N = 10;
//const int K = 5;

OFFSET_VECTOR SimpleGraph::globalOffset = \
    {\
        0,1,2,3,4,5,6,7,8,9\
        ,10,11,12,13,14,15,16,17,18,19\
        ,20,21,22,23,24,25,26,27,28,29\
        ,30,31,32,33,34,35,36,37,38,39\
    };

SimpleGraph::SimpleGraph(const GRAPH_ADJARRAY_VECTOR adjgraph)
    :m_srcAdjArray(adjgraph)
{
    adjArray2adjList(m_srcAdjArray,m_dstAdjList);
}

void SimpleGraph::adjArray2adjList(const GRAPH_ADJARRAY_VECTOR & amp;srcAdjArray, GRAPH_ADJLIST_MAP & amp;dstAdjList)
{
    int ncount;

    assert( srcAdjArray.size() < MAXVERTEX);

    for (int i = 0; i < srcAdjArray.size(); + + i){
        ADJPOINTSSET s;
        ncount = 0;
        for(int j= 0; j< srcAdjArray[i].size(); + + j)
        {
            if(srcAdjArray[i][j] != 0)
            {
                s.insert(j + globalOffset[i]);
                ncount + + ;
            }
        }

        ADJPOINTSPAIR adjPointsPair(ncount,s);
        dstAdjList.insert(make_pair(i,adjPointsPair));
    }

    GRAPH_ADJLIST_MAP::iterator it;
    for(it = m_dstAdjList.begin(); it != m_dstAdjList.end(); it + + )
    {
        ADJPOINTSSET s = it->second.second;
        ADJPOINTSSET::iterator adjset_it;
        for(adjset_it = s.begin(); adjset_it != s.end(); adjset_it + + ) {
            if(*adjset_it > it->first)
            {
                inc(*adjset_it, it->first);
            }
        }
    }

}

VERTEXCOVER SimpleGraph::getVertexCover()
{
    VERTEXCOVER s;
    ADJPOINTSSET tmps;
    ADJPOINTSSET::iterator adjset_it;

#if PRINTINFO
    std::cout << "============================================== =========" << std::endl;
    std::cout << "v d s" << std::endl;
    std::cout << "-----" << std::endl;

    print();
#endif
    //1.put the highest degree vertex in the cover set
    GRAPH_ADJLIST_MAP::iterator it, it_target;

    while (1) {
#if PRINTINFO
        std::cout << "step1.put the highest degree vertex in the cover set" << std::endl;
#endif
        int nMaxDegree = 0;
        it_target = m_dstAdjList.begin();
        for(it = m_dstAdjList.begin(); it != m_dstAdjList.end(); it + + )
        {
            // cout << it->first << " " << it->second.first << endl;
            if(nMaxDegree < it->second.first)
            {
                nMaxDegree = it->second.first;
                it_target = it;
            }
        }

#if PRINTINFO
        std::cout << "it_target is " << it_target->first << " " << it_target->second.first << std::endl;
#endif
        if(it_target->second.first == 0) break;

        s.insert(it_target->first);

#if PRINTINFO
        std::cout << "one of highest degree vertex is vertex: " << it_target->first << std::endl;

        SimpleGraph::printVertexSet(s);

        std::cout << "step2.update the degree of vertexes in the list.if 0, remove it." << std::endl;
#endif
    //2.update the degree of vertexes in the list.if 0, remove it.

        tmps= it_target->second.second;
        for(adjset_it = tmps.begin(); adjset_it != tmps.end(); adjset_it + + ) {
            dec(*adjset_it, it_target->first);
        }

        it_target->second.first = 0;
        it_target->second.second.clear();

#if PRINTINFO
        SimpleGraph::print();
#endif
    }

    m_dstAdjList.clear();
    adjArray2adjList(m_srcAdjArray,m_dstAdjList); //restore m_dstAdjList

#if PRINTINFO
    std::cout << "step3.Exit the loop,get the one of cover set" << std::endl;
#endif

    return s;
}

bool SimpleGraph::checkIsCover(std::vector<int> & amp;vertexSet)
{
    bool bret = false;
    int n = 1;

    ADJPOINTSSET tmps;
    ADJPOINTSSET::iterator adjset_it;

    //1.put the highest degree vertex in the cover set
    GRAPH_ADJLIST_MAP::iterator it, it_target;
    std::vector<int>::iterator vit;


    int nMaxDegree = 0;
    it_target = m_dstAdjList.begin();
    vit = vertexSet.begin();
    for (vit = vertexSet.begin(); vit != vertexSet.end(); vit + + )
    {
        for(it = m_dstAdjList.begin(); it != m_dstAdjList.end(); it + + )
        {
            // cout << it->first << " " << it->second.first << endl;
            if(*vit == it->first + 1)
            {
                it_target = it;
            }
        }

        tmps= it_target->second.second;
        for(adjset_it = tmps.begin(); adjset_it != tmps.end(); adjset_it + + ) {
            dec(*adjset_it, it_target->first);
        }

        it_target->second.first = 0;
        it_target->second.second.clear();


    }

    for(it = m_dstAdjList.begin(); it != m_dstAdjList.end(); it + + )
    {
        if(it->second.first != 0)
        {
            n = 0;
            break;
        }
    }

    m_dstAdjList.clear();
    adjArray2adjList(m_srcAdjArray,m_dstAdjList); //restore m_dstAdjList

    if (n == 1) bret = true;

    return bret;
}

void SimpleGraph::help()
{
    if(m_srcAdjArray.size() == 0)
    {
        std::cout << "Adjacency Array vector is null\
";
        return;
    }

    int i = 0;
    for (auto & amp; line : m_srcAdjArray) {
        for (int j=0; j< i; j + + ) {
            std::cout << " ";
        }
        for (const auto & amp; v : line) {
            std::cout << v << " ";
        }
        std::cout << std::endl;
        i + + ;
    }
}

void SimpleGraph::printVertexSet(VERTEXCOVER s)
{
#if 1
    ADJPOINTSSET::iterator adjset_it;
    std::cout << "{";
    for(adjset_it = s.begin(); adjset_it != s.end(); adjset_it + + ) {
        std::cout << *adjset_it << " ";
    }
    std::cout << "}" << std::endl;
#endif
}

void SimpleGraph::print()
{
#if 1
    GRAPH_ADJLIST_MAP::iterator it;
    for(it = m_dstAdjList.begin(); it != m_dstAdjList.end(); it + + )
    {
        //Output Node's key value, degree value and adjacent vertex set
        std::cout << it->first << " " << it->second.first << " ";
        SimpleGraph::printVertexSet(it->second.second);
    }
#endif
}

void SimpleGraph::inc(int keyVertex, int targetVertex)
{
    m_dstAdjList.at(keyVertex).first + = 1;
    m_dstAdjList.at(keyVertex).second.insert(targetVertex);
}

void SimpleGraph::dec(int keyVertex, int targetVertex)
{
    m_dstAdjList.at(keyVertex).first -= 1;
    m_dstAdjList.at(keyVertex).second.erase(targetVertex);
}

std::vector<std::vector<int> > SimpleGraph::getCombineNK(int n, int k)
{
    std::vector<int> nums = std::vector<int>();
    for(int i = 1; i < k + 1; + + i)
        nums.push_back(i);
    nums.push_back(n + 1);

    std::vector<std::vector<int>> retvv = std::vector<std::vector<int>>();
    int j = 0;
    while (j < k) {
        retvv.push_back(std::vector<int>(nums.begin(), nums.begin() + k));
        j = 0;
        while ((j < k) & amp; & amp; (nums[j + 1] == nums[j] + 1))
        {
            nums[j] = j + 1;
            j + + ;
        }

        nums[j] + + ;

    }
    return retvv;
}

void SimpleGraph::showCombinationvector( std::vector<std::vector<int> > va)
{
    std::cout << "C(N,K) = " << va.size() << "\
";
    std::cout << "[ \
";
    for (int var = 0; var < va.size(); + + var) {
        std::cout << " [ ";
        for(int j=0; j< va[var].size();j + + )
        {
            std::cout << va[var][j] - 1 << " ";
        }
        std::cout << "]\
";
    }

    std::cout << "]\
";
}

#include "simplegraph.h"
#include "cprecisetimer.h"

//using namespace std;

int main(int argc, char *argv[])
{
// const int N = 5;
// /*
// (0)--(1)--(2)
// | / \ |
// | / \ |
// | / \ |
// (3)-------(4)
// */
// GRAPH_ADJARRAY_VECTOR graph = {
// {0, 1, 0, 1, 0},
// {0, 1, 1, 1},
// {0, 0, 1},
// {0, 1},
//{0}
// };

// const int N = 6;
// /*
// (0)--(1)--(2)
// | / \ | \
// | / \ | \
// | / \ | \
// (3)-------(4)--(5)
// */
// GRAPH_ADJARRAY_VECTOR graph = {
// {0, 1, 0, 1, 0, 0},
// {0, 1, 1, 1, 0},
// {0, 0, 1, 1},
// {0, 1, 0},
// {0, 1},
//{0}
// };

    const int N = 30;
    GRAPH_ADJARRAY_VECTOR graph = {
        {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 , 0, 1, 0, 1, 0},
        {0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0 , 1, 0, 1, 0},
        {0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1 , 0, 1, 0},
        {0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0 , 1, 0},
        {0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1 , 0},
        {0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 },
        {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0},
        {0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0},
        {0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0},
        {0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0},
        {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0},
        {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0},
        {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0},
        {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0},
        {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0},
        {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0},
        {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1},
        {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0},
        {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1},
        {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0},
        {0, 1, 0, 1, 0, 0, 1, 0, 1, 0},
        {0, 1, 1, 1, 0, 1, 0, 1, 0},
        {0, 1, 0, 1, 0, 0, 1, 0},
        {0, 1, 1, 1, 0, 1, 0},
        {0, 1, 0, 1, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 1, 1},
        {0, 1, 0},
        {0, 1},
        {0}
    };

    CPreciseTimer preciseTimer;

    std::cout << "G Upper Triangle Matrix" << std::endl;
    SimpleGraph G(graph);
    G.help();

    std::cout << "Computing Min Vertex Cover..." << std::endl;
    VERTEXCOVER coverSet = G.getVertexCover();
    std::cout << "Print Min Vertex Cover..." << std::endl;
    SimpleGraph::printVertexSet(coverSet);

    int k= coverSet.size();
    std::cout << "cover vertex number should be:" << k << std::endl;

    std::vector<std::vector<int>> va = SimpleGraph::getCombineNK(N,k);
    SimpleGraph::showCombinationvector(va);

    std::vector<std::vector<int>> allCover;

    preciseTimer.StartTimer();
    for (int index = 0; index < va.size(); + + index) {
        bool bIsCover = G.checkIsCover(va[index]);
        if(bIsCover) {
            allCover.push_back(va[index]);
        }
    }
    preciseTimer.StopTimer();

    __int64 timeElasps = preciseTimer.GetTime();
    std::cout << "time elapse is " << timeElasps << " microseonds" << std::endl;

    std::cout << "all cover set is as follows!!!" << std::endl;
    SimpleGraph::showCombinationvector(allCover);

    std::cout << "Finish!!!" << std::endl;
}

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56557 people are learning the system