BGL Dijkstra具有捆绑属性的最短路径

Question

我正在尝试在BGL中使用dijkstra最短路径算法来计算未加权无向图上的简单ST路径.我可能会关注未来的边缘权重,但是现在我只想将边缘遍历视为统一的成本.

我也在跟踪多个边缘和顶点属性,所以我基于我迄今为止所做的基于捆绑属性的例子,这个例子似乎与我试图做的最接近.

现在我正在试图弄清楚如何让dijkstra工作,这样我就可以进行ST搜索,但是我仍然坚持为它设置正确的参数.

这是我到目前为止的代码的简化示例:

#include <iostream>
#include <vector>

#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>

// Create a struct to hold properties for each vertex
typedef struct VertexProperties
{
  int p1;
} VertexProperties;

// Create a struct to hold properties for each edge
typedef struct EdgeProperties
{
  int   p1;
} EdgeProperties;

// Define the type of the graph
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties> Graph;


int main(int,char*[])
{
  // Create a graph object
  Graph g;

  // Add vertices
  Graph::vertex_descriptor v0 = boost::add_vertex(g);
  Graph::vertex_descriptor v1 = boost::add_vertex(g);
  Graph::vertex_descriptor v2 = boost::add_vertex(g);

  // Set vertex properties
  g[v0].p1 = 1;
  g[v1].p1 = 2;
  g[v2].p1 = 3;

  // Add edges
  std::pair<Graph::edge_descriptor, bool> e01 = boost::add_edge(v0, v1, g);
  std::pair<Graph::edge_descriptor, bool> e02 = boost::add_edge(v1, v2, g);

  // Set edge properties
  g[e01.first].p1 = 1;
  g[e02.first].p1 = 2;

  std::cout << "num_verts: " << boost::num_vertices(g) << std::endl;
  std::cout << "num_edges: " << boost::num_edges(g) << std::endl;

  // compute ST shortest paths here...

  return 0;
}

我正在绊倒dijkstra算法调用的正确参数.他们采用图形,一个起始顶点,然后是前一个地图和距离图.我到目前为止看到的例子,就像这样,只用边缘权重设置他们的图形而没有捆绑的边缘属性,这简化了事情.

最终,我在ST最短路径之后,所以我需要恢复从S到T的路径.从事物的外观来看,我们需要设置一个前驱地图,然后我们可以使用它来从中提取路径特别是T回到S？

我还应该注意,我所处的环境不允许使用C++ 11语言功能.:(

这里的任何帮助将不胜感激!

Answer 1

所以问题是"如何使用捆绑属性作为Boost Graph Library的权重图？".

好.您使用属性映射.可以通过"捆绑属性"页面上的一些时髦语法文档访问捆绑属性:http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/bundles.html,请参阅标题"捆绑属性的属性映射".

现在进行快速演示:

// set up a weight map:
auto weights = boost::get(&EdgeProperties::p1, g);

将最少量的参数传递给dijkstra:

// you can pass it to dijkstra using direct or named params. Let's do the simplest
boost::dijkstra_shortest_paths(g, v0, boost::no_named_parameters() .weight_map(weights));

你会想要添加更多参数,但是嘿,这是你的开始:)

Live On Coliru

#include <iostream>
#include <vector>

#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graph_utility.hpp>

// Create a struct to hold properties for each vertex
struct VertexProperties { int p1; };

// Create a struct to hold properties for each edge
struct EdgeProperties { int p1; };

// Define the type of the graph
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties> Graph;

int main() {
    // Create a graph object
    Graph g;

    // Add vertices
    auto v0 = boost::add_vertex({1}, g),
         v1 = boost::add_vertex({2}, g),
         v2 = boost::add_vertex({3}, g);

    // Add edges
    boost::add_edge(v0, v1, EdgeProperties{1}, g);
    boost::add_edge(v1, v2, EdgeProperties{2}, g);

    boost::print_graph(g, boost::get(&VertexProperties::p1, g));

    // set up a weight map:
    auto weights = boost::get(&EdgeProperties::p1, g);

    // you can pass itprint_graph`enter code here` to dijkstra using direct or named params. Let's do the simplest
    boost::dijkstra_shortest_paths(g, v0, boost::no_named_parameters() .weight_map(weights));
}

您会注意到我也简化了顶点/边缘属性的初始化.如果你想知道图形"看起来"的样子(没有使用Graphviz),print_graph实用程序很整洁.

Coliru的输出是:

1 <--> 2 
2 <--> 1 3 
3 <--> 2