如何将Direceted Graph（邻接列表）传递到Dijkstra Algorithm Boost中以找到最短路径？ [英] How to Pass Direceted Graph (adjacency list) into Dijkstra Algorithm Boost to find shortest path?

问题描述

我已经写了该类作为开始构建我的算法的开始，但是我可以在控制台上看到 Before一词，但是看不到 After！

I have written this Class as a start to build My Algorithm, but I can see Before word on console, but not After ! what is my mistake in using Dijkstra Algorithm of Boost ??

#include <myalgorithm.h>
#include<mygraphbuilder.h>
//===============================================
using namespace std;
using namespace boost;
//===============================================

MyAlgorithm::MyAlgorithm()// Default constructor
{
}
//===========================================================================
MyAlgorithm::MyAlgorithm(graph_t AnyGraph, Vertex VSource){//}, Vertex VTarget){ // Parameters Constructor

  MyGraph = AnyGraph;
  vector<Vertex> p(num_vertices(AnyGraph));
  vector<double> d(num_edges(AnyGraph));
  //===========================================================================
  //Dijkstra_Algorithm
  //===========================================================================
  cout<<"Before\t"<<endl;
  dijkstra_shortest_paths(AnyGraph, VSource,
                          predecessor_map(boost::make_iterator_property_map(p.begin(), get(boost::vertex_index, AnyGraph))).
                          distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, AnyGraph))));
 cout<<"After\t"<<endl;
  //===========================================================================
}// End of Parameters Constructor
//===========================================================================
MyAlgorithm::~MyAlgorithm(){ //Destructur
}
//===========================================================================
// Accessors
// function to call ShortPath
vector <Vertex> MyAlgorithm::getShortPath(){
  return MyAlgorithm::ShortPath;
}
// function to call the Graph
graph_t MyAlgorithm::getGraph(){
  return MyGraph;
}
//===========================================================================
// Mutators
//function to set short path Vector as whole
void MyAlgorithm::setShortPath(vector<Vertex> PathVector){
  MyAlgorithm::ResetShortPath();
  MyAlgorithm::ShortPath = PathVector;
}
//function to inject node to Short Path
void MyAlgorithm::setShortPath(Vertex MyNode){
  ShortPath.emplace_back(MyNode);
}
// function to set a graph
void MyAlgorithm::setGraph(graph_t YourGraph){
  MyGraph = YourGraph;
}
//============================================================================
//function to reset short path
void MyAlgorithm::ResetShortPath(){
  MyAlgorithm::ShortPath.clear();
}
//function to Print Out Results
void MyAlgorithm::PrintOut(){
  cout << "distances and parents:" << endl;
  graph_traits < graph_t >::vertex_iterator vi, vend;
  for (boost::tie(vi, vend) = vertices(MyAlgorithm::MyGraph); vi != vend; ++vi) {
      vector<Vertex> p(num_vertices(MyAlgorithm::MyGraph));
      vector<double> d(num_vertices(MyAlgorithm::MyGraph));
      cout << "distance(" << *vi << ") = " << d[*vi] << ", ";
      cout << "parent(" << *vi << ") = " << p[*vi] << endl;
    } // End of Print Loop
}// end of Print Function

我的图定义如下：

typedef adjacency_list < vecS, vecS, directedS, property < vertex_name_t, idType >, property < edge_weight_t, double > > graph_t;

其中idType是unsigned long long int；但这没用，我该怎么做？

Where idType is unsigned long long int; but it didn't work, how I can Make it work ??

推荐答案

我看不出问题是什么。您的代码只需编译即可，请参见在Coliru上直播。

I don't see what the question is. Your code would simply compile, see Live On Coliru.

说

• 您可能无需复制图表就可以这样做



• 您应将距离图制作为顶点数而不是边数：

• you can probably do without copying the graph quite so many times

• you should make the distance-map to number of vertices instead of edges:

std::vector<double> d(num_edges(MyGraph));

应该是

std::vector<double> d(num_vertices(MyGraph));

到问题中添加的代码：

• 就像我说的，您可能不应该复制太多了特别是为什么 MyAlgorithm 拥有拥有 AnyGraph 作为成员<$ c的副本的原因$ c> MyGraph ？

类似地，添加的代码也存在相同的问题，尤其是

Similarly, the added code has the same problem, specifically with

for (auto v : make_iterator_range(vertices(MyGraph))) {
    std::vector<Vertex> p(num_vertices(MyGraph));
    std::vector<double> d(num_vertices(MyGraph));
    std::cout << "distance(" << v << ") = " << d[v] << ", ";
    std::cout << "parent(" << v << ") = " << p[v] << std::endl;
}

d 和 p 向量是通过循环中的每次迭代简单地使用默认初始化值创建的。您希望找到什么？

The d and p vectors are simply created with default-initialized values every iteration through the loop. What did you expect to find?

我可以猜测，您打算得到 dijkstra_shortest_paths 的结果 code>可以在此处使用，但是您从来没有做任何事情来实现这一目标。至少看起来您应该已经将 d 和 p 成员变量做成了

I can guess that you intended the result of dijkstra_shortest_paths to be used there, but you never did anything to make that happen. At the very least it looks like you should have made d and p member varlables

从不使用 setShortPath 成员函数。通过扩展， ShortPath 成员永远不会正确设置。看来您已经意识到这一点，因为您也不想在 PrintOut

The setShortPath member functions are never used. By extension, the ShortPath member is never properly set. It seems you are aware of this because you also don't attempt to use it in PrintOut

中使用它打印最短路径存在一个概念上的问题，因为它显然取决于目标顶点...我要编写一个 getShortPath 访问器，以计算特定路径：

There is a conceptual problem with printing "The Shortest Path" as it obviously depends on the target vertex... I'd write a getShortPath accessor that calculates a specific path:

Path getShortPath(Vertex destination) {
    Path path;

    while (destination != MyGraph.null_vertex()) {
        path.push_front(destination);
        if (destination == src)
            return path;

        if (predecessors.at(destination) == destination)
            break;
        destination = predecessors.at(destination);
    }
    throw std::runtime_error("Unreachable");
}

现在您可以为任何路径添加打印功能：

Now you can add a print function for any path:

void PrintPath(MyAlgorithm::Path const& path, graph_t const& g) {
    std::cout << "Path: ";
    auto idmap = get(boost::vertex_name, g);
    auto wmap = get(boost::edge_weight, g);

    auto previous = g.null_vertex();
    for (auto v : path) {
        if (previous != g.null_vertex()) {
            for (auto e : make_iterator_range(out_edges(previous, g))) {
                if (target(e, g) == v) {
                    std::cout << " -> (w:" << " << " << wmap[e] << ") ";
                }
            }
        }
        std::cout << "#" << v << " (id:" << idmap[v] << ") ";
        previous = v;
    }
    std::cout << "\n";
}

它还会在每条边上打印权重（您会看到它与总距离匹配） ）

It also prints weights on every edge (you will see it matches the total distance)

以下是修复的版本上述所有的。我停止生成随机图，因为现在测试用例对可达的路径进行了假设：

Here's a version that fixes all of the above. I stopped generating random graphs as now the "test cases" make assumptions about which paths are reachable:

在Coliru上直播

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dag_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>

using boost::make_iterator_range;

using idType = unsigned long long;

typedef boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::directedS,
    boost::property<boost::vertex_name_t, idType>,
    boost::property<boost::edge_weight_t, double>> graph_t;

struct MyGraphBuilder {
    void generate();
    void printGraph() const;

    graph_t const& getGraph() const { return MyGraph; }
    graph_t&       getGraph()       { return MyGraph; }
  private:
    graph_t MyGraph;
};

void MyGraphBuilder::printGraph() const {
    std::cout << "Number of Vertices is:" << num_vertices(MyGraph) << "\n";
    std::cout << "Number of Edges is:" << num_edges(MyGraph) << "\n";

    boost::print_graph(MyGraph, boost::get(boost::vertex_name, MyGraph), std::cout);

    // to print with edge weights:
    for (auto v : make_iterator_range(vertices(MyGraph))) {
        for (auto oe : make_iterator_range(out_edges(v, MyGraph))) {
            std::cout << "Edge " << oe << " weight " << get(boost::edge_weight, MyGraph, oe) << "\n";
        }
    }
}

void MyGraphBuilder::generate() {
    MyGraph = graph_t(5); // clear graph, 5 vertices

    auto idmap = get(boost::vertex_name, MyGraph);
    idmap[0] = 0ull;
    idmap[1] = 100ull;
    idmap[2] = 200ull;
    idmap[3] = 300ull;
    idmap[4] = 400ull;

    add_edge(1, 3, { 1.52275 }, MyGraph);
    add_edge(2, 0, { 8.79559 }, MyGraph);
    add_edge(2, 0, { 6.41004 }, MyGraph);
    add_edge(3, 2, { 7.37265 }, MyGraph);
    add_edge(4, 0, { 1.18526 }, MyGraph);
}

struct MyAlgorithm {
    using Vertex = graph_t::vertex_descriptor;

    graph_t MyGraph;
    Vertex src;
    std::vector<Vertex> predecessors;
    std::vector<double> distances;

    MyAlgorithm(graph_t const& AnyGraph, Vertex VSource)
        : MyGraph(AnyGraph),
          src(VSource),
          predecessors(num_vertices(MyGraph)),
          distances(num_vertices(MyGraph))
    {
        dijkstra_shortest_paths(MyGraph, src,
                predecessor_map(make_iterator_property_map(predecessors.begin(), get(boost::vertex_index, MyGraph)))
                .distance_map(boost::make_iterator_property_map(distances.begin(), get(boost::vertex_index, MyGraph))));
    }

    using Path = std::deque<Vertex>;
    Path getShortPath(Vertex destination) {
        Path path;

        while (destination != MyGraph.null_vertex()) {
            path.push_front(destination);
            if (destination == src)
                return path;

            if (predecessors.at(destination) == destination)
                break;
            destination = predecessors.at(destination);
        }
        throw std::runtime_error("Unreachable");
    }

    void PrintRawData() const {
        std::cout << "distances and parents:" << std::endl;
        for (auto v : make_iterator_range(vertices(MyGraph))) {
            std::cout << "distance(" << v << ") = " << distances.at(v) << ", ";
            std::cout << "parent(" << v << ") = " << predecessors.at(v) << std::endl;
        }
    }

    graph_t const& getGraph() const { return MyGraph; }
    graph_t&       getGraph()       { return MyGraph; }
};

void PrintPath(MyAlgorithm::Path const& path, graph_t const& g) {
    std::cout << "Path: ";
    auto idmap = get(boost::vertex_name, g);
    auto wmap = get(boost::edge_weight, g);

    auto previous = g.null_vertex();
    for (auto v : path) {
        if (previous != g.null_vertex()) {
            for (auto e : make_iterator_range(out_edges(previous, g))) {
                if (target(e, g) == v) {
                    std::cout << " -> (w:" << " << " << wmap[e] << ") ";
                }
            }
        }
        std::cout << "#" << v << " (id:" << idmap[v] << ") ";
        previous = v;
    }
    std::cout << "\n";
}

int main() {
    MyGraphBuilder builder;
    builder.generate();
    //builder.printGraph();

    MyAlgorithm algo(builder.getGraph(), 1); // 1 is first vertex, not idmap

    algo.PrintRawData();

    auto p0 = algo.getShortPath(0);
    auto p1 = algo.getShortPath(1);
    auto p2 = algo.getShortPath(2);
    auto p3 = algo.getShortPath(3);

    for (auto path : {p0, p1, p2, p3}) {
        PrintPath(path, algo.getGraph());
    }

    // vertex 4 is unreachable:
    try {
        auto p4 = algo.getShortPath(4);
    } catch(std::exception const& e) {
        std::cout << "Error getting path for vertex 4: " << e.what() << "\n";
    }
}

打印

distances and parents:
distance(0) = 15.3054, parent(0) = 2
distance(1) = 0, parent(1) = 1
distance(2) = 8.8954, parent(2) = 3
distance(3) = 1.52275, parent(3) = 1
distance(4) = 1.79769e+308, parent(4) = 4
Path: #1 (id:100)  -> (w: << 1.52275) #3 (id:300)  -> (w: << 7.37265) #2 (id:200)  -> (w: << 8.79559)  -> (w: << 6.41004) #0 (id:0) 
Path: #1 (id:100) 
Path: #1 (id:100)  -> (w: << 1.52275) #3 (id:300)  -> (w: << 7.37265) #2 (id:200) 
Path: #1 (id:100)  -> (w: << 1.52275) #3 (id:300) 
Error getting path for vertex 4: Unreachable

这篇关于如何将Direceted Graph（邻接列表）传递到Dijkstra Algorithm Boost中以找到最短路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！