dijkstra的算法未计算我的boost图中顶点的前任 [英] dijkstra's algorithm not computing the predecessors of the vertices in my boost graph

问题描述

我正在尝试编写一个程序，该程序使用Boost图形库从文本文件构造图形，然后对它执行用户选择的某些算法.我的代码运行良好，但是boost::dijkstra_shortest_paths()或boost::prim_minimum_spanning_tree()完成执行后，每个顶点的predecessor属性将设置为该相同的顶点！就像算法在不做任何事情的情况下运行一样.我不太确定为什么会这样，并且想知道是否有人可以对此问题发表一些看法. 这是我的程序:

I am trying to write a program which uses the boost graph library to construct a graph from a text file and then perform certain algorithms of the user's choice on it. My code runs fine, but once boost::dijkstra_shortest_paths() or boost::prim_minimum_spanning_tree() finishes executing, the predecessor property for each vertex is set to that self-same vertex! It's like the algorithm runs without doing its job. I am rather unsure why this is happening, and was wondering if someone could shine some light on the issue. Here is my program:

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <stack>
#include <vector>

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_iterator.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/properties.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>

using namespace boost;
using namespace std;

typedef adjacency_list_traits<vecS, vecS, undirectedS> GraphTraits;

typedef GraphTraits::vertex_descriptor vertex_descriptor;

struct EdgeData                                                                         // property bundle for edges
{
    double weight;
    EdgeData(double someWeight)
        : weight(someWeight) {};
};

struct VertexData                                                                       // property bundle for vertices
{
    string first_name;
    int dist;
    vertex_descriptor pred;
    default_color_type color;
};

struct do_nothing_dijkstra_visitor : default_dijkstra_visitor {};

typedef adjacency_list<vecS, vecS, undirectedS,                                         // graph type
VertexData, EdgeData> MyGraphType;                                                      // this is the bundled version

vertex_descriptor findVertex(const string& name, const MyGraphType& G)                  // utility for finding a vertex_descriptor for a name
{
    bool found = false;
    auto it = vertices(G).first;
    vertex_descriptor vDescriptor = *it;
    auto vNameMap = get(&VertexData::first_name, G);

    while (!found)
    {
        if (vNameMap[vDescriptor] == name)
        {
            found = true;
            break;
        }

        it++;
        vDescriptor = *it;
    }
    return vDescriptor;
}

int main()
{
    MyGraphType G;
    char userInput = ' ';
    bool isRunning = true;

    string graphFile;

    cout << "Enter the name of the file in which your graph data is stored: " << endl;
    cout << "(Please be sure you have one space between each vertex name and between each piece of edge data)" << endl;
    cin >> graphFile;

    ifstream ifs(graphFile);

    if (!ifs)                                                                           // error if file not opened
    {
        cout << "Error! could not read graph file. Please exit program and try again." << endl;
    }
    else
    {
        G;

        string line = "";
        string vertexName = "junk";                                                     // current vertex name

        getline(ifs, line);                                                             // takes out the "Vertices:" line
        getline(ifs, line);                                                             // line of vertex names

        istringstream isstream(line);                                                   // create string stream to parse vertex names from

        int i = 0;                                                                      // counter variable
        while (isstream >> vertexName)                                                  // get the vertex names from input stream
        {
            string vName;
            if (vertexName.size() != 1 && vertexName[vertexName.size() - 1] == ',')     // potentially remove comma
            {
                vName = vertexName.substr(0, (vertexName.size() - 1));
            }
            else
            {
                vName = vertexName;
            }

            vertex_descriptor vd = add_vertex(G);                                       // add a vertex for the current name
            G[i].first_name = vName;                                                    // give the vertex its name
            i++;                                                                        // increment counter
        }

        getline(ifs, line);                                                             // takes out the "Edges:" line

        while (getline(ifs, line))                                                      // get the graph's edges
        {
            string vertex2;                                                             // the two vertices for the edge
            string vertex1;
            double inWeight = 0.0;                                                      // the edge's weight

            istringstream iss(line);                                                    // create a string stream to parse edge data from

            iss >> vertexName;                                                          // get first vertex name from input
            vertex1 = vertexName.substr(1, (vertexName.size() - 2));                    // remove comma and '('

            iss >> vertexName;                                                          // get second vertex name from input
            vertex2 = vertexName.substr(0, (vertexName.size() - 1));                    // lopp off comma

            iss >> inWeight;                                                            // get the weight

            auto e = add_edge(findVertex(vertex1, G), findVertex(vertex2, G), { inWeight }, G).first;   // add the edge
        }
    }

    ifs.close();

    while (isRunning)
    {
        cout << "What would you like to do?\n" << endl;
        cout << "1.) Calculate the shortest path between two vertices" << endl;
        cout << "2.) Calculate the minimum spanning tree" << endl;
        cout << "3.) Calculate shortest path to visit all vertices (Traveling Salesman Problem)" << endl;
        cout << "   note: Only works on completely connected graph" << endl;
        cout << "4.) Exit the program\n" << endl;
        cout << "Please enter the number that corresponds with your choice:" << endl;

        cin >> userInput;

        switch (userInput)
        {
        case '1':
        {
            string startVertex;
            string endVertex;
            stack<vertex_descriptor> predStack;                                                 // stack for storing predecessor names

            cout << "Enter the name of the starting vertex: ";
            cin >> startVertex;
            cout << "\nEnter the name of the ending vertex: ";
            cin >> endVertex;
            cout << endl;

            dijkstra_shortest_paths(G, findVertex(startVertex, G),
                get(&VertexData::pred, G), get(&VertexData::dist, G),
                get(&EdgeData::weight, G), identity_property_map(),
                less<double>(), plus<double>(), numeric_limits<double>::infinity(), 0,
                do_nothing_dijkstra_visitor(), get(&VertexData::color, G));

            vertex_descriptor eVertex = findVertex(endVertex, G);                               // vertex_descriptor for ending vertex
            vertex_descriptor sVertex = findVertex(startVertex, G);                             // vertex_descriptor for starting vertex
            vertex_descriptor counter = get(&VertexData::pred, G, eVertex);

            predStack.push(counter);                                                            // prime the stack

            while (counter != sVertex)                                                          // push predecessors onto stack
            {
            counter = G[counter].pred;
            predStack.push(counter);
            }

            cout << "The shortest path between " << startVertex << " and " << endVertex << " is: ";

            while (!predStack.empty())                                                          // print the path
            {
            cout << get(&VertexData::first_name, G, predStack.top()) << ", ";
            predStack.pop();
            }

            cout << endVertex << endl;                                                          // print the ending vertex
            system("pause");
            break;
        }
        case '2':
        {
            vector<vertex_descriptor> predecessors(num_vertices(G));

            prim_minimum_spanning_tree(G, *vertices(G).first, &predecessors[0],
                /*get(&VertexData::pred, G),*/ get(&VertexData::dist, G),
                get(&EdgeData::weight, G), identity_property_map(),
                do_nothing_dijkstra_visitor());

            cout << "\nThe Minimum Spanning tree contains these edges: " << endl;

            for (auto vd : make_iterator_range(vertices(G)))
            {
                auto p = G[vd].pred;
                if (G[vd].first_name != G[p].first_name)
                {
                    cout << "(" << G[vd].first_name << ",  " << G[p].first_name << ")" << endl;
                }
            }
            system("pause");
            break;
        }
        case '3':
        {
            cout << "This would perform the TSP calculation, only it hasn't been written yet." << endl;
            break;
        }
        case '4':
        {
            //delete graph;
            isRunning = false;
            break;
        }
        default:
            cout << "The wheel's spinning, but the hamster's dead! " << userInput << " is not a choice!" << endl;
        }
    }

    return EXIT_SUCCESS;
}

如果很重要，我将使用MS Visual Studio 2017和增强版boost_1_67_0.

In case it is important, I am using MS visual studio 2017 and boost version boost_1_67_0.

推荐答案

解析非常挑剔，不检查任何错误.更糟糕的是，findVertex在查找不存在的名称时会执行任何操作"(例如，如果解析出错并且查找空字符串).如果幸运的话，它会崩溃的.¹

Parsing is very finicky and doesn't check for any errors whatsoever. What's worse, findVertex will do "whatever" when it looks for a name that doesn't exist (e.g. if parsing went wrong and it looks for the empty string). If you're lucky it will crash.¹

如果调试程序(或者确实像我一样添加一些跟踪)，则可能会发现所有边都将添加错误的顶点.

If you debug the program (or, indeed add some tracing like I did), you might find that all your edges will be added the wrong vertices.

此外，您的dist属性是int，它不能表示您指定的infinity.

Further, your dist property is int, which cannot represent the infinity that you specify.

修复这些问题后，我至少能够运行第一个算法:

Fixing these, I was able to at least run the first algo:

在Coliru上直播

#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#include <boost/config.hpp>
#include <boost/graph/adjacency_iterator.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/property_map/property_map.hpp>

using namespace boost;
using namespace std;

typedef adjacency_list_traits<vecS, vecS, undirectedS> GraphTraits;

typedef GraphTraits::vertex_descriptor vertex_descriptor;

struct EdgeData // property bundle for edges
{
    double weight;
    EdgeData(double someWeight) : weight(someWeight){};
};

struct VertexData // property bundle for vertices
{
    string first_name;
    double dist;
    vertex_descriptor pred;
    default_color_type color;
};

struct do_nothing_dijkstra_visitor : default_dijkstra_visitor {};

typedef adjacency_list<vecS, vecS, undirectedS, // graph type
                       VertexData, EdgeData>
MyGraphType; // this is the bundled version

vertex_descriptor findVertex(const string &name, const MyGraphType &G) // utility for finding a vertex_descriptor for a name
{
    bool found = false;
    auto it = vertices(G).first;
    vertex_descriptor vDescriptor = *it;
    auto vNameMap = get(&VertexData::first_name, G);

    while (!found) {
        if (vNameMap[vDescriptor] == name) {
            found = true;
            break;
        }

        it++;
        vDescriptor = *it;
    }
    std::cout << "Found " << vDescriptor << " for " << std::quoted(name) << "\n";
    return vDescriptor;
}

int main() {
    MyGraphType G;
    char userInput = ' ';
    bool isRunning = true;

    string graphFile;

    cout << "Enter the name of the file in which your graph data is stored: " << endl;
    cout << "(Please be sure you have one space between each vertex name and between each piece of edge data)" << endl;
    cin >> graphFile;

    ifstream ifs(graphFile);

    if (!ifs) // error if file not opened
    {
        cout << "Error! could not read graph file. Please exit program and try again." << endl;
    } else {
        string line = "";
        string vertexName = "junk"; // current vertex name

        getline(ifs, line); // takes out the "Vertices:" line
        getline(ifs, line); // line of vertex names

        istringstream isstream(line); // create string stream to parse vertex names from

        int i = 0;                     // counter variable
        while (isstream >> vertexName) // get the vertex names from input stream
        {
            string vName;
            if (vertexName.size() != 1 && vertexName[vertexName.size() - 1] == ',') // potentially remove comma
            {
                vName = vertexName.substr(0, (vertexName.size() - 1));
            } else {
                vName = vertexName;
            }

            vertex_descriptor vd = add_vertex(G); // add a vertex for the current name
            G[i].first_name = vName;              // give the vertex its name
            i++;                                  // increment counter

            std::cout << "Debug: " << std::quoted(vName) << " --> " << vd << "\n";
        }

        getline(ifs, line); // takes out the "Edges:" line

        while (getline(ifs, line)) // get the graph's edges
        {
            string vertex2; // the two vertices for the edge
            string vertex1;
            double inWeight = 0.0; // the edge's weight

            istringstream iss(line); // create a string stream to parse edge data from

            iss >> vertexName;                                       // get first vertex name from input
            vertex1 = vertexName.substr(1, (vertexName.size() - 2)); // remove comma and '('

            iss >> vertexName;                                       // get second vertex name from input
            vertex2 = vertexName.substr(0, (vertexName.size() - 1)); // lopp off comma

            iss >> inWeight; // get the weight

            std::cout << "Parsing " << std::quoted(line) << " into edge (" << vertex1 << ", " << vertex2 << ", " << inWeight << ")\n";

            auto e = add_edge(findVertex(vertex1, G), findVertex(vertex2, G), { inWeight }, G).first; // add the edge
        }

        boost::print_graph(G, get(&VertexData::first_name, G));
    }

    ifs.close();

    while (isRunning) {
        cout << "What would you like to do?\n" << endl;
        cout << "1.) Calculate the shortest path between two vertices" << endl;
        cout << "2.) Calculate the minimum spanning tree" << endl;
        cout << "3.) Calculate shortest path to visit all vertices (Traveling Salesman Problem)" << endl;
        cout << "   note: Only works on completely connected graph" << endl;
        cout << "4.) Exit the program\n" << endl;
        cout << "Please enter the number that corresponds with your choice:" << endl;

        cin >> userInput;

        switch (userInput) {
        case '1': {
            string startVertex;
            string endVertex;
            stack<vertex_descriptor> predStack; // stack for storing predecessor names

            cout << "Enter the name of the starting vertex: ";
            cin >> startVertex;
            cout << "\nEnter the name of the ending vertex: ";
            cin >> endVertex;
            cout << endl;

            dijkstra_shortest_paths(G, findVertex(startVertex, G), get(&VertexData::pred, G), get(&VertexData::dist, G),
                                    get(&EdgeData::weight, G), identity_property_map(), less<double>(), plus<double>(),
                                    numeric_limits<double>::infinity(), 0, do_nothing_dijkstra_visitor(),
                                    get(&VertexData::color, G));

            vertex_descriptor eVertex = findVertex(endVertex, G);   // vertex_descriptor for ending vertex
            vertex_descriptor sVertex = findVertex(startVertex, G); // vertex_descriptor for starting vertex
            vertex_descriptor counter = get(&VertexData::pred, G, eVertex);

            predStack.push(counter); // prime the stack

            while (counter != sVertex) // push predecessors onto stack
            {
                counter = G[counter].pred;
                predStack.push(counter);
            }

            cout << "The shortest path between " << startVertex << " and " << endVertex << " is: ";

            while (!predStack.empty()) // print the path
            {
                cout << get(&VertexData::first_name, G, predStack.top()) << ", ";
                predStack.pop();
            }

            cout << endVertex << endl; // print the ending vertex
            system("pause");
            break;
        }
        case '2': {
            vector<vertex_descriptor> predecessors(num_vertices(G));

            prim_minimum_spanning_tree(G, *vertices(G).first, &predecessors[0],
                                       /*get(&VertexData::pred, G),*/ get(&VertexData::dist, G),
                                       get(&EdgeData::weight, G), identity_property_map(),
                                       do_nothing_dijkstra_visitor());

            cout << "\nThe Minimum Spanning tree contains these edges: " << endl;

            for (auto vd : make_iterator_range(vertices(G))) {
                auto p = G[vd].pred;
                if (G[vd].first_name != G[p].first_name) {
                    cout << "(" << G[vd].first_name << ",  " << G[p].first_name << ")" << endl;
                }
            }
            system("pause");
            break;
        }
        case '3': {
            cout << "This would perform the TSP calculation, only it hasn't been written yet." << endl;
            break;
        }
        case '4': {
            // delete graph;
            isRunning = false;
            break;
        }
        default:
            cout << "The wheel's spinning, but the hamster's dead! " << userInput << " is not a choice!" << endl;
        }
    }

    return EXIT_SUCCESS;
}

使用input.txt:

With input.txt:

Vertices:
a b c d
Edges:
(a, b, 1)
(b, c, 2)
(b, d, 4)
(c, d, 1)

并输入"input.txt 1 a d 4"，打印:

And input "input.txt 1 a d 4", prints:

Enter the name of the file in which your graph data is stored: 
(Please be sure you have one space between each vertex name and between each piece of edge data)
Debug: "a" --> 0
Debug: "b" --> 1
Debug: "c" --> 2
Debug: "d" --> 3
Parsing "(a, b, 1)" into edge (a, b, 1)
Found 0 for "a"
Found 1 for "b"
Parsing "(b, c, 2)" into edge (b, c, 2)
Found 1 for "b"
Found 2 for "c"
Parsing "(b, d, 4)" into edge (b, d, 4)
Found 1 for "b"
Found 3 for "d"
Parsing "(c, d, 1)" into edge (c, d, 1)
Found 2 for "c"
Found 3 for "d"
a <--> b 
b <--> a c d 
c <--> b d 
d <--> b c 
What would you like to do?

1.) Calculate the shortest path between two vertices
2.) Calculate the minimum spanning tree
3.) Calculate shortest path to visit all vertices (Traveling Salesman Problem)
   note: Only works on completely connected graph
4.) Exit the program

Please enter the number that corresponds with your choice:
Enter the name of the starting vertex: 
Enter the name of the ending vertex: 
Found 0 for "a"
Found 3 for "d"
Found 0 for "a"
The shortest path between a and d is: a, b, c, d
sh: 1: pause: not found
What would you like to do?

1.) Calculate the shortest path between two vertices
2.) Calculate the minimum spanning tree
3.) Calculate shortest path to visit all vertices (Traveling Salesman Problem)
   note: Only works on completely connected graph
4.) Exit the program

Please enter the number that corresponds with your choice:

---

¹在c ++中通常不会那么幸运.使用valgrind和asan/ubsan！

---

¹ you don't usually get that lucky in c++. Use valgrind and asan/ubsan!

这篇关于dijkstra的算法未计算我的boost图中顶点的前任的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！