使用 Boost 库的 c++ Prim 最小生成树

Question

我正在开展一个项目，我需要在教授提供的输入文件上实现 Dijkstra、Prim 和 A* 算法。我已经成功地为 Dijkstra 编写了工作代码，但我在尝试让我的相同图形也适用于 Prim 时遇到了困难。我觉得我的问题是没有正确地使用最小生成树映射来提取我的信息，但我真的无法理解问题所在，我们将不胜感激任何帮助。

边和顶点的结构和图形特征:

typedef boost::adjacency_list_traits<vecS, vecS, undirectedS, listS> GraphTraits;
// type 'Vertex' identifies each vertex uniquely:
typedef GraphTraits::vertex_descriptor Vertex;
// Property type associated to each vertex:
struct VertexProperty {
    string name;  // Name of vertex (i.e., "location")
    Vertex predecessor; // Predecessor along optimal path.
    double distance; // Distance to the goal, along shortest path.
    default_color_type color; // for use by dijkstra.
    VertexProperty(const string& aName = "") : name(aName) { };
};
// Property type associated to each edge:
struct EdgeProperty {
    double weight; // distance to travel along this edge.
    EdgeProperty(double aWeight = 0.0) : weight(aWeight) { };
};
// Type of the graph used:
typedef adjacency_list<vecS, vecS, undirectedS, VertexProperty, EdgeProperty> Graph;
// Create a global graph object 'g'
Graph g;
// This is a visitor for the dijkstra algorithm. This visitor does nothing special.
struct do_nothing_dijkstra_visitor {
    template <typename Vertex, typename Graph>
    void initialize_vertex(Vertex u, const Graph& g) const { };
    template <typename Vertex, typename Graph>
    void examine_vertex(Vertex u, const Graph& g) const { };
    template <typename Edge, typename Graph>
    void examine_edge(Edge e, const Graph& g) const { };
    template <typename Vertex, typename Graph>
    void discover_vertex(Vertex u, const Graph& g) const { };
    template <typename Edge, typename Graph>
    void edge_relaxed(Edge e, const Graph& g) const { };
    template <typename Edge, typename Graph>
    void edge_not_relaxed(Edge e, const Graph& g) const { };
    template <typename Vertex, typename Graph>
    void finish_vertex(Vertex u, const Graph& g) const { };
};

变量:

string tempName1, tempName2, tempString, data2;
int weight;
string inputFile;
int choice;
Vertex cur_v, start_v, goal_v;
map<string, Vertex> name2v, name1v;
double totalDist, tempDist;
int numVert = 0;

基于上传文件的图构造:

            //build graph based on file loaded
            getline(fin, tempString); 
            getline(fin, tempString);
            stringstream tempSS(tempString);
            while (getline(tempSS, tempName1, ',')) {
                name2v[tempName1] = add_vertex(VertexProperty(tempName1), g);
                numVert++;
            }
            getline(fin, tempString);
            while (getline(fin, tempString)) {
                tempString.erase(tempString.begin(), tempString.begin() + tempString.find('(') + 1);
                tempString.erase(tempString.begin() + tempString.find(')'), tempString.end());
                stringstream temp_ss(tempString);
                getline(temp_ss, tempName1, ',');
                getline(temp_ss, tempName2, ',');
                temp_ss >> weight;
                add_edge(name2v[tempName1], name2v[tempName2], EdgeProperty(weight), g);
            }
            name1v = name2v;

普里姆的电话:

cout << "Please enter the Vertex you would like to start at: ";
            cin >> tempName1;
            transform(tempName1.begin(), tempName1.end(), tempName1.begin(), ::toupper);
            start_v = name1v[tempName1];
            prim_minimum_spanning_tree(g, start_v, 
                get(&VertexProperty::predecessor, g), 
                get(&VertexProperty::distance, g),
                get(&EdgeProperty::weight, g), 
                identity_property_map(), 
                do_nothing_dijkstra_visitor());

我试图只包含重要的代码。就像我说的，这段代码适用于 Dijkstra，但我不确定如何让它适用于 Prim。我在想我需要向 VertexProperty 的结构添加更多内容，或者有一个映射来存储最小生成树。提前致谢。

Answer 1

我不明白你到底在问什么(除了代码风格和质量问题)。

注意这里

• 访客减少
• 删除了令人困惑的评论
• 当然，我在这里生成一个随机图，因为我们没有您的输入

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/random.hpp>
#include <fstream>
#include <map>
#include <random>
#include <sstream>

typedef boost::adjacency_list_traits<boost::vecS, boost::vecS, boost::undirectedS> GraphTraits;
typedef GraphTraits::vertex_descriptor Vertex;

struct DijkstraStuff {
    Vertex predecessor;
    double distance;
    boost::default_color_type color; // for use by dijkstra.
};

struct VertexProperty : DijkstraStuff {
    std::string name;
    VertexProperty(const std::string &aName = "") : name(aName){};
};

struct EdgeProperty {
    double weight; // distance to travel along this edge.
    EdgeProperty(double aWeight = 0.0) : weight(aWeight){};
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty> Graph;

struct do_nothing_dijkstra_visitor : boost::default_dijkstra_visitor {};

int main() {
    Graph g;
    std::map<std::string, Vertex> name_map;

    // read graph (random for now)
    {
        std::mt19937 prng{ 42 };
        generate_random_graph(g, 10, 20, prng);

        for (auto vd : boost::make_iterator_range(vertices(g))) {
            name_map[g[vd].name = "NAME" + std::to_string(vd)] = vd;
        }

        std::uniform_real_distribution<double> weight_dist(0, 1);
        for (auto ed : boost::make_iterator_range(edges(g))) {
            g[ed].weight = weight_dist(prng);
        }
    }

    print_graph(g, get(&VertexProperty::name, g));

    Graph::vertex_descriptor start_v;

    std::cout << "Please enter the Vertex you would like to start at: ";
    {
        std::string startName;
        std::cin >> startName;
        std::transform(startName.begin(), startName.end(), startName.begin(),
                       [](uint8_t ch) { return std::toupper(ch); });
        start_v = name_map.at(startName);
    }

    boost::prim_minimum_spanning_tree(g, start_v, get(&VertexProperty::predecessor, g),
          get(&VertexProperty::distance, g), get(&EdgeProperty::weight, g),
          boost::identity_property_map(), do_nothing_dijkstra_visitor());


}

打印结果

生成的 MST 被编码为前身 map 。打印如下:

for (auto vd : boost::make_iterator_range(vertices(g))) {
    auto p = g[vd].predecessor;
    std::cout << "Pred of " << g[vd].name << " is " << g[p].name << "\n";
}

(为简单起见，假设所有顶点都在 MST 中。这与假设输入中没有未连接的顶点相同)

打印(对于给定的随机种子和起始顶点):

Pred of NAME1 is NAME9
Pred of NAME2 is NAME2
Pred of NAME3 is NAME6
Pred of NAME4 is NAME1
Pred of NAME5 is NAME6
Pred of NAME6 is NAME1
Pred of NAME7 is NAME3
Pred of NAME8 is NAME7
Pred of NAME9 is NAME0