Hamiton图系列文章 (3) ：Hamilton图的判定与实现

0) 作为最后一篇完结版本，为了完整起见，将道路矩阵与乘法定义用论文中的表述，方便大家理解道路矩阵与定义的乘法，这里选用蔡文康论文的内容：

 基于前面道路（路径）矩阵类的实现，包括矩阵乘法的重载设计。

1）道路矩阵类头文件patharray4simplegraph.h

#ifndef PATHARRAY4SIMPLEGRAPH_H

#define PATHARRAY4SIMPLEGRAPH_H

#include 

#include 

using namespace std;

typedef vector PATH;

typedef vector PATHS;

typedef vector > GRAPH_ADJ;

typedef vector > SINGLE_PATH_ARRAY;

typedef vector > MULTI_PATHS_ARRAY;

class PathArray4SimpleGraph

{

public:

    PathArray4SimpleGraph(const GRAPH_ADJ adjgraph);

    PathArray4SimpleGraph operator*(const PathArray4SimpleGraph rc);

private:

    GRAPH_ADJ m_srcAdjArray;

    SINGLE_PATH_ARRAY m_srcPathArray;

    MULTI_PATHS_ARRAY m_multiPathsArray;

private:

    void printAdjArray(const GRAPH_ADJ &adjArray);

    void printPathArray(const SINGLE_PATH_ARRAY &pathArray);

    void printPathsArray(const MULTI_PATHS_ARRAY &pathsArray);

public:

    void adjArray2PathArray(const GRAPH_ADJ &srcAdjArray, SINGLE_PATH_ARRAY &dstPathArray);

    void pathArray2PathsArray(const SINGLE_PATH_ARRAY &pathArray, MULTI_PATHS_ARRAY &pathsArray);

    bool isZero();

    void help();

    PathArray4SimpleGraph* clone() const { return new PathArray4SimpleGraph( *this );}

};

#endif // PATHARRAY4SIMPLEGRAPH_H

2）道路矩阵类源文件patharray4simplegraph.cpp

#include "patharray4simplegraph.h"

#include 

#include

PathArray4SimpleGraph::PathArray4SimpleGraph(const GRAPH_ADJ adjgraph):

    m_srcAdjArray(adjgraph)

{

    adjArray2PathArray(m_srcAdjArray,m_srcPathArray);

    pathArray2PathsArray(m_srcPathArray, m_multiPathsArray);

}

//print the source adjacency matrices to debug

void PathArray4SimpleGraph::printAdjArray(const GRAPH_ADJ &adjArray)

{

    if(adjArray.size() == 0)

    {

        cout << "Adjacency Array vector is null\n";

        return;

    }

    for (auto& line : adjArray) {

        for (const auto& v : line) {

            cout << v << " ";

        }

        cout << endl;

    }

}

//print the source path Array to debug

void PathArray4SimpleGraph::printPathArray(const SINGLE_PATH_ARRAY &pathArray)

{

    if(pathArray.size() == 0)

    {

        cout << "Path Array vector is null\n";

        return;

    }

    for (auto& line : pathArray) {

        for (const auto& path : line) {

            if (path.size() == 1){

                cout << "[0]";

                continue;

            }

            cout << "[";

            for (size_t i = 0; i < path.size(); ++i) {

                cout << path[i];

                if (i != path.size() - 1)

                    cout << "->";

            }

            cout << "] ";

        }

        cout << endl;

    }

}

//print the source paths Array to debug

void PathArray4SimpleGraph::printPathsArray(const MULTI_PATHS_ARRAY &pathsArray)

{

    if(pathsArray.size() == 0)

    {

        cout << "Paths Array vector is null\n";

        return;

    }

    for (auto& line : pathsArray) {

        for (const auto& column : line) {

            cout << "[";

            for (const auto& path: column) {

                if (path.size() == 1){

                    cout << "[0]";

                    continue;

                }

                cout << "[";

                for (size_t i = 0; i < path.size(); ++i) {

                    cout << path[i];

                    if (i != path.size() - 1)

                        cout << "->";

                }

                cout << "]";

            }

            cout << "]";

        }

        cout << endl;

    }

}

void PathArray4SimpleGraph::help()

{

    printPathsArray(m_multiPathsArray);

}

void PathArray4SimpleGraph::adjArray2PathArray(const GRAPH_ADJ &srcAdjArray, SINGLE_PATH_ARRAY &dstPathArray)

{

    dstPathArray.resize(srcAdjArray.size());

    for (int i = 0; i < srcAdjArray.size(); ++i){

        dstPathArray[i].resize(srcAdjArray.size());

    }

    for (int i = 0; i < srcAdjArray.size(); ++i){

        for(int j= 0; j< srcAdjArray.size(); ++j)

        {

            if(srcAdjArray[i][j] == 0)

            {

                dstPathArray[i][j].push_back(0);

            } else {

                dstPathArray[i][j].push_back(i);

                dstPathArray[i][j].push_back(j);

            }

        }

    }

}

void PathArray4SimpleGraph::pathArray2PathsArray(const SINGLE_PATH_ARRAY &pathArray, MULTI_PATHS_ARRAY &pathsArray)

{

    pathsArray.resize(pathArray.size());

    for (int i = 0; i < pathArray.size(); ++i){

        pathsArray[i].resize(pathArray.size());

    }

    for (int i = 0; i < pathArray.size(); ++i){

        for(int j= 0; j< pathArray.size(); ++j)

        {

            pathsArray[i][j].resize(1);

            pathsArray[i][j][0]=pathArray[i][j];

        }

    }

}

PathArray4SimpleGraph PathArray4SimpleGraph::operator*(const PathArray4SimpleGraph pathArrayG)

{

    PathArray4SimpleGraph retgraph(pathArrayG.m_srcAdjArray);

    retgraph.m_multiPathsArray.clear();

    MULTI_PATHS_ARRAY retPathsArr;

    //initialize the retPathArray

    retPathsArr.resize(this->m_multiPathsArray.size());

    for (int i=0; i < this->m_multiPathsArray.size(); ++i) {

        retPathsArr[i].resize(this->m_multiPathsArray.size());

    }

    for (int i = 0; i < this->m_multiPathsArray.size(); ++i){

        for(int j= 0; j< this->m_multiPathsArray.size(); ++j)

        {

            PATHS retPaths;

            for (int k=0; k < this->m_multiPathsArray.size(); ++k) {

                //if one of path is [0], the result is 0

                if(((this->m_multiPathsArray[i][k].size() == 1) && (this->m_multiPathsArray[i][k][0].size() == 1))

                        || ((pathArrayG.m_multiPathsArray[k][j].size() == 1) && (pathArrayG.m_multiPathsArray[k][j][0].size() == 1)))

                {

                    continue;

                }

                for (int x = 0; x < this->m_multiPathsArray[i][k].size(); ++x){

                    for(int y= 0; y< pathArrayG.m_multiPathsArray[k][j].size(); ++y)

                    {

                        PATH tempPath;

                        PATH op1path = this->m_multiPathsArray[i][k][x];

                        PATH op2path = pathArrayG.m_multiPathsArray[k][j][y];

                        bool bFlagCross = false;

                        if(op1path[op1path.size() -1] == op2path[0])

                        {

                            for (int m = 0; m < op1path.size() - 1; ++m) {

                                for (int n=0; n < op2path.size(); ++n) {

                                    if (op1path[m] == op2path[n]){

                                        bFlagCross = true;

                                    }

                                }

                            }

                            if(op1path[0] == op2path[op2path.size() -1])

                            {

                                if(this->m_multiPathsArray.size() == op1path.size() + op2path.size()  - 2)

                                    bFlagCross = false;

                            }

                            if( !bFlagCross ){

                                tempPath = op1path;

                                for(int n=1; n< op2path.size(); ++n)

                                {

                                    tempPath.push_back(op2path[n]);

                                }

                            }

                        }

                        retPaths.push_back(tempPath);

                    }

                }

            }

            for (const auto& path: retPaths) {

                if (path.size() !=0){

                    retPathsArr[i][j].push_back(path);

                }

            }

            //if the path is null, fill it with zero

            if(retPathsArr[i][j].size() == 0)

            {

                retPathsArr[i][j].resize(1);

                retPathsArr[i][j][0].push_back(0);

            }

        }

    }

    retgraph.m_multiPathsArray.assign(retPathsArr.begin(),retPathsArr.end());

    return retgraph;

}

bool PathArray4SimpleGraph::isZero()

{

    bool bRet = true;

    for (int i = 0; i < m_multiPathsArray.size(); ++i){

        for(int j= 0; j< m_multiPathsArray.size(); ++j)

        {

            if (!((m_multiPathsArray[i][j].size() == 1) && (m_multiPathsArray[i][j][0][0] == 0)

                    || (m_multiPathsArray[i][j].size() ==0)))

                return false;

        }

    }

    return bRet;

}

3）测试主程序

#include "patharray4simplegraph.h"

#include 

#include 

using namespace std;

int main(int argc, char *argv[])

{

    /*

    (0)--(1)--(2)

    |   / \   |

    |  /   \  |

    | /     \ |

    (3)-------(4)

    */

    vector> graph = {

            {0, 1, 0, 1, 0},

            {1, 0, 1, 1, 1},

            {0, 1, 0, 0, 1},

            {1, 1, 0, 0, 1},

            {0, 1, 1, 1, 0}

        };

    cout << "G1" << endl;

    PathArray4SimpleGraph G1(graph);

    G1.help();

    PathArray4SimpleGraph G = G1;

    for (int i=0; i<4; i++) {

        G = G * G1;

        cout << "G" << i+2 << endl;

        G.help();

    }

    if(G.isZero()){

        cout << "G does not have Hamilton circle\n";

    } else {

        cout << "G is Hamilton Graph with hamilton circle\n";

    }

    return 1;

}

4) 运行结果展示