BGL Dijkstra具有捆绑属性的最短路径-Java 学习之路

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

我也在跟踪多个边缘和顶点属性，所以到目前为止我已经完成了bundled properties example，这似乎是我最接近我正在尝试做的事情 .

现在我正在试图弄清楚如何让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;
}

我'm getting tripped up on the right parameters for the call to dijkstra'的算法 . 他们采用图形，一个起始顶点，然后是前一个 Map 和距离图 . 到目前为止我见过的例子，比如this one，只用边缘权重设置他们的图形，没有捆绑的边缘属性，这简化了事情 .

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

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

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

2 回答

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

好 . 您使用属性映射 . 可以使用"Bundled Properties"页面上的一些时髦语法文档访问捆绑属性：http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/bundles.html，请参阅 Headers "Property maps from bundled properties" .

现在进行快速演示：

// 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

回复于 2024-05-05T22:30:50+08:00

我正在添加一个'完成'版本的dijkstra最短路径搜索，它计算从S到T的最短路径用于存档目的 .

我确信有更好的“提升”方法可以做到这一点，但它可以在我的最后工作 .

http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/bundles.html是一个非常有用的链接 .

///
/// @file bgl_st_example.cpp
///
/// @brief bundled property example
///
/// @ref http://programmingexamples.net/wiki/CPP/Boost/BGL/BundledProperties
///
#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
typedef struct vertex_properties
{
  std::string label;
  int p1;
} vertex_properties_t;


// Create a struct to hold properties for each edge
typedef struct edge_properties
{
  std::string label;
  int   p1;
  int   weight;
} edge_properties_t;


// Define the type of the graph
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, vertex_properties_t, edge_properties_t> graph_t;
typedef graph_t::vertex_descriptor vertex_descriptor_t;
typedef graph_t::edge_descriptor   edge_descriptor_t;
typedef boost::property_map<graph_t, boost::vertex_index_t>::type index_map_t;
typedef boost::iterator_property_map<vertex_descriptor_t*, index_map_t*, vertex_descriptor_t, vertex_descriptor_t&> predecessor_map_t;

//  The graph, with edge weights labeled.
//
//   v1  --(1)--  v2
//   |  \_        |
//   |    \       |
//  (1)    (3)   (2)
//   |        \_  |
//   |          \ |
//   v4  --(1)--  v3
//
//

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

  // Add vertices
  vertex_descriptor_t v1 = boost::add_vertex(g);
  vertex_descriptor_t v2 = boost::add_vertex(g);
  vertex_descriptor_t v3 = boost::add_vertex(g);
  vertex_descriptor_t v4 = boost::add_vertex(g);

  // Set vertex properties
  g[v1].p1 = 1;  g[v1].label = "v1";
  g[v2].p1 = 2;  g[v2].label = "v2";
  g[v3].p1 = 3;  g[v3].label = "v3";
  g[v4].p1 = 4;  g[v4].label = "v4";

  // Add edges
  std::pair<edge_descriptor_t, bool> e01 = boost::add_edge(v1, v2, g);
  std::pair<edge_descriptor_t, bool> e02 = boost::add_edge(v2, v3, g);
  std::pair<edge_descriptor_t, bool> e03 = boost::add_edge(v3, v4, g);
  std::pair<edge_descriptor_t, bool> e04 = boost::add_edge(v4, v1, g);
  std::pair<edge_descriptor_t, bool> e05 = boost::add_edge(v1, v3, g);

  // Set edge properties
  g[e01.first].p1 = 1;     g[e01.first].weight = 1;     g[e01.first].label = "v1-v2";
  g[e02.first].p1 = 2;     g[e02.first].weight = 2;     g[e02.first].label = "v2-v3";
  g[e03.first].p1 = 3;     g[e03.first].weight = 1;     g[e03.first].label = "v3-v4";
  g[e04.first].p1 = 4;     g[e04.first].weight = 1;     g[e04.first].label = "v4-v1";
  g[e05.first].p1 = 5;     g[e05.first].weight = 3;     g[e05.first].label = "v1-v3";

  // Print out some useful information
  std::cout << "Graph:" << std::endl;
  boost::print_graph(g, boost::get(&vertex_properties_t::label,g));
  std::cout << "num_verts: " << boost::num_vertices(g) << std::endl;
  std::cout << "num_edges: " << boost::num_edges(g) << std::endl;


  // BGL Dijkstra's Shortest Paths here...
  std::vector<int> distances( boost::num_vertices(g));
  std::vector<vertex_descriptor_t> predecessors(boost::num_vertices(g));

  boost::dijkstra_shortest_paths(g, v1,
                                 boost::weight_map(boost::get(&edge_properties_t::weight,g))
                                 .distance_map(boost::make_iterator_property_map(distances.begin(), boost::get(boost::vertex_index,g)))
                                 .predecessor_map(boost::make_iterator_property_map(predecessors.begin(), boost::get(boost::vertex_index,g)))
                                 );

  // Extract the shortest path from v1 to v3.
  typedef std::vector<edge_descriptor_t> path_t;
  path_t path;

  vertex_descriptor_t v = v3;
  for(vertex_descriptor_t u = predecessors[v]; u != v; v=u, u=predecessors[v])
  {
    std::pair<edge_descriptor_t,bool> edge_pair = boost::edge(u,v,g);
    path.push_back( edge_pair.first );
  }

  std::cout << std::endl;
  std::cout << "Shortest Path from v1 to v3:" << std::endl;
  for(path_t::reverse_iterator riter = path.rbegin(); riter != path.rend(); ++riter)
  {
    vertex_descriptor_t u_tmp = boost::source(*riter, g);
    vertex_descriptor_t v_tmp = boost::target(*riter, g);
    edge_descriptor_t   e_tmp = boost::edge(u_tmp, v_tmp, g).first;

    std::cout << "  " << g[u_tmp].label << " -> " << g[v_tmp].label << "    (weight: " << g[e_tmp].weight << ")" << std::endl;
  }

  return 0;
}

这是一个适合我的CMakeLists.txt文件：

cmake_minimum_required(VERSION 2.8)

project ( bgl_example )

find_package( Boost REQUIRED COMPONENTS  )

include_directories( ${Boost_INCLUDE_DIR} )

add_executable( bgl_st_example  bgl_st_example.cpp)
target_link_libraries( bgl_st_example ${Boost_LIBRARIES} )

我看到的结果输出：

Graph:
v1 <--> v2 v4 v3
v2 <--> v1 v3
v3 <--> v2 v4 v1
v4 <--> v3 v1
num_verts: 4
num_edges: 5

Shortest Path from v1 to v3:
  v1 -> v4    (weight: 1)
  v4 -> v3    (weight: 1)

回复于 2024-05-05T22:30:50+08:00

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

2 回答

相关问题