NPC系列文章（2)---最小覆盖问题Set Cover Problem的一种贪心算法求全部覆盖集

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
#define COMMONDATASTRUCTURE_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;  //相邻顶点集合
typedef std::pair<int, ADJPOINTSSET> ADJPOINTSPAIR; //相邻顶点集合与其基数（大小）
typedef std::map<int, ADJPOINTSPAIR> VERTEXMAP;  //顶点与它的相邻顶点集合的映射
typedef VERTEXMAP GRAPH_ADJLIST_MAP; //G的邻接表List表示

typedef std::vector<std::vector<bool> > GRAPH_ADJARRAY_VECTOR;  //G的邻接矩阵Vector表示
typedef std::vector<int> OFFSET_VECTOR;

typedef ADJPOINTSSET VERTEXCOVER;

#endif // COMMONDATASTRUCTURE_H

#ifndef CPRECISETIMER_H
#define CPRECISETIMER_H

#include <windows.h>

class CPreciseTimer
{
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(&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 (0x7fffffffffffffff is the maximal __int64 positive number)
        m_i64Elapsed = (0x7fffffffffffffff - 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(&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(&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> &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 &srcAdjArray, GRAPH_ADJLIST_MAP &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 &srcAdjArray, GRAPH_ADJLIST_MAP &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> &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\n";
        return;
    }

    int i = 0;
    for (auto& line : m_srcAdjArray) {
        for (int j=0; j< i; j++) {
            std::cout << "  ";
        }
        for (const auto& 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++)
    {
        //输出Node的key值，度数值 和相邻顶点集合
        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) && (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() << "\n";
    std::cout << "[ \n";
    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 << "]\n";
    }

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

#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;
}