c++ - 如何访问顶点颜色以修改 DFS 搜索？

Question

我试图在 BGL 图中找到起点和终点之间的所有路径。为此，我使用 DFS 算法。不幸的是，DFS 标记已经访问了 Vetrex，我没有得到任何包含 Vetrex 多次的路径。该图如下所示：

我的方法是将访问的节点记录在堆栈中，直到找到目标节点。然后我保存这条路径并取消选择这条路径中的所有节点，直到开始节点。从那里重新开始搜索。如果没有找到目的地并且当前节点没有出边，我丢弃这条路径并重新开始搜索，直到开始节点搜索完所有路径。我在一个简单的 C++ 程序中实现了这个修改后的搜索，它可以工作。现在我想使用 BGL，但我遇到了无法取消选择我已经使用过的节点的问题。

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/unordered_map.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>

using namespace std;
using namespace boost;

namespace graphProps {
    struct VertexProps {
        unsigned int vertexID;
        std::string vertexName;
    };

    struct EdgeProps {
        unsigned int edgeID;
        std::string edgeName;
    };
}

typedef boost::adjacency_list <
    boost::listS, boost::vecS, boost::directedS,
    //vertex properties
    boost::property <
    boost::vertex_name_t, std::string,
    boost::property<boost::vertex_index_t, int, graphProps::VertexProps> >,
    //edge properties
    boost::property<
    boost::edge_weight_t, int,
    boost::property<boost::edge_index_t, int, graphProps::EdgeProps > >,
    boost::property<vertex_color_t, default_color_type>
> mygraph;

typedef boost::unordered_map<std::string, std::size_t> _map;
typedef std::pair<mygraph::vertex_descriptor, mygraph::vertex_descriptor> edgePair;
using colormap = std::map<mygraph::vertex_descriptor, default_color_type>;

class PathDFSVisitor :public boost::default_dfs_visitor {

        public:
            colormap vertex_coloring;
            mygraph *m_path;
            std::vector<edgePair> *m_edgePair;
            boost::unordered_map<std::string, std::size_t> *m_pathNumMap;
            std::vector<mygraph::vertex_descriptor> m_spath;
            int m_source;
            int m_destination;
            bool m_foundDest = false;
            bool m_pathFinished = false;
            bool *m_result;
            int path_index = 0;


        PathDFSVisitor(boost::unordered_map<std::string, std::size_t> *inMap, std::vector<edgePair> *edgePair)
        {
            m_edgePair = edgePair;
            m_pathNumMap = inMap;
        }

        PathDFSVisitor(std::vector<edgePair> *edgePair, int source, int destination, bool *result)
        {
            m_edgePair = edgePair;
            m_source = source;
            m_destination = destination;
            m_result = result;
        }

        template < typename Vertex, typename Graph >
        void discover_vertex(Vertex u, const Graph & g)
        {
            mygraph::vertex_descriptor vertex;
            vertex = boost::vertex(u, g);

            default_color_type color = vertex_coloring[u];
            std::cout << "Discover at: " << u << " with color " << color << std::endl;
            m_spath.push_back(vertex);
            path_index++;
        }

        template < typename Vertex, typename Graph >
        void finish_vertex(Vertex u, const Graph & g)
        {
            mygraph::vertex_descriptor vertex;
            default_color_type color = vertex_coloring[u];
            std::cout << "Finish vertex at: " << u << " with color " << color << std::endl;
            for (int i = path_index; i > 1; i--)
            {
                vertex = boost::vertex(m_spath[i-1], g);
                vertex_coloring[vertex] = white_color;
                std::cout << "Unmarking vertex: " << vertex << std::endl;
                m_spath.pop_back();
                path_index--;
            }
        }


    };

void addVertex(unsigned int vertexID, std::string vertexName, mygraph &graph)
{
    mygraph::vertex_descriptor vert;
    //add vertex and intialize 
    vert = boost::add_vertex(graph);
    graph[vert].vertexID = vertexID;
    graph[vert].vertexName = vertexName;
}

void addEdge(unsigned int edgeID, unsigned int srcVertexID, unsigned int dstVertexID, std::string edgeName, mygraph &graph)
{
    //(1) get vertex descriptor for source and destination vertex
    mygraph::vertex_descriptor src, dst;
    //add vertex and intialize 

    src = boost::vertex(srcVertexID, graph);
    dst = boost::vertex(dstVertexID, graph);
    //set edge properties between source and destination vertex
    boost::add_edge(src, dst, graph);
    //(2)get edge descriptor
    auto e = boost::edge(boost::vertex(srcVertexID, graph), boost::vertex(dstVertexID, graph), graph).first;
    //initialize edge properties
    graph[e].edgeID = edgeID;
    graph[e].edgeName = edgeName;
}

int main()
{
    mygraph g,l; 
    std::vector<edgePair> path;

    addVertex(0, "A", g);
    addVertex(1, "B", g);
    addVertex(2, "C", g);
    addVertex(3, "D", g);
    addVertex(4, "E", g);
    addVertex(5, "F", g);

    addEdge(0, 1, 0, "BA", g);
    addEdge(1, 1, 4, "BD", g);
    addEdge(2, 1, 2, "BC", g);
    addEdge(2, 0, 3, "AD", g);
    addEdge(3, 4, 3, "ED", g);
    addEdge(4, 4, 2, "EC", g);
    addEdge(5, 3, 5, "DF", g);
    addEdge(6, 3, 1, "DB", g);
    addEdge(6, 4, 1, "EB", g);

    bool searchState = false;
    std::size_t start = 1;
    std::size_t stop = 5;
    PathDFSVisitor vis(&path,start,stop,&searchState);
    depth_first_search(g, visitor(vis).root_vertex(start));

    //build graph which contains (only) all paths between start and stop vertex 
    std::vector<edgePair>::iterator it;
    for (it = path.begin(); it != path.end(); ++it)
    {
        boost::add_edge(it->first, it->second, l);
    }

    std::ofstream f("Graph.dot");
    write_graphviz(f, g);
    f.close();
    system("renderGraph.bat");

    std::cin.get();
}

输出是：

Discover at: 1 with color 0
Discover at: 0 with color 0
Discover at: 3 with color 0
Discover at: 5 with color 0
Finish vertex at: 5 with color 0
Unmarking vertex: 5
Unmarking vertex: 3
Unmarking vertex: 0
Finish vertex at: 3 with color 0
Finish vertex at: 0 with color 0
Discover at: 4 with color 0
Discover at: 2 with color 0
Finish vertex at: 2 with color 0
Unmarking vertex: 2
Unmarking vertex: 4
Finish vertex at: 4 with color 0
Finish vertex at: 1 with color 0

我的简单工作算法产生了这个：以下是从 1 到 5 的所有不同路径

Add vertex: 1 to path.
Add vertex: 0 to path.
Add vertex: 3 to path.
Add vertex: 5 to path.
1 0 3 5
Unmark vertex: 5
Unmark vertex: 3
Unmark vertex: 0
Add vertex: 4 to path.
Add vertex: 3 to path.
Add vertex: 5 to path.
1 4 3 5
Unmark vertex: 5
Unmark vertex: 3
Add vertex: 2 to path.
Unmark vertex: 2
Unmark vertex: 4
Add vertex: 2 to path.
Unmark vertex: 2
Unmark vertex: 1

{1,0,3,5} 和 {1,4,3,5} 是我想要得到的两条路径..

标签： c++boost