相关疑难解决方法(0)

我需要使用Boost库来获得从一个点到另一个点的最短路径.我查看了示例代码,它很容易理解.但是,该示例仅显示如何获得总距离.我试图弄清楚如何迭代前任映射以实际获得最短路径,我似乎无法弄明白.我已经阅读了关于这个主题的这两个问题:

具有VertexList的Dijkstra最短路径=增强图中的ListS

Boost :: Dijkstra Shortest Path,如何从路径迭代器获取顶点索引？

但是在提供的两个示例中,IndexMap typedef似乎不能与Visual Studio编译器一起使用,坦率地说,Boost typedef对我来说有点混乱,我在解决所有这些问题时遇到了一些麻烦.根据这里的Boost示例代码,有人能告诉我如何才能找到它的路径吗？我会非常感激.

http://www.boost.org/doc/libs/1_46_1/libs/graph/example/dijkstra-example.cpp

我在编译一个非常简单的图表的BFS时遇到了问题.无论我做什么,我得到了关于不匹配的方法调用的各种编译器消息(我已尝试boost::visitor和扩展boost::default_bfs_visitor等)

#include <stdint.h>
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>

int main() {
  typedef boost::adjacency_list<boost::vecS, boost::hash_setS, boost::undirectedS, uint32_t, uint32_t, boost::no_property> graph_t;
  graph_t graph(4);
  graph_t::vertex_descriptor a = boost::vertex(0, graph);
  graph_t::vertex_descriptor b = boost::vertex(1, graph);
  graph_t::vertex_descriptor c = boost::vertex(2, graph);
  graph_t::vertex_descriptor d = boost::vertex(3, graph);
  graph[a] = 0;
  graph[b] = 1;
  graph[c] = 2;
  graph[d] = 3;
  std::pair<graph_t::edge_descriptor, bool> result = boost::add_edge(a, b, 0, graph);
  result = boost::add_edge(a, c, 1, graph);
  result = boost::add_edge(c, b, 2, graph); …

我已经花了几天的时间来处理Boost图形库。据我了解，在考虑VertexList和EdgeList存储时：

vecS：

• 拥有索引，因此可以对其进行访问
• 删除顶点时，迭代器无效

listS：

• 没有索引
• 不会使迭代器无效

这有点短，但这是我的问题的关键。我需要这些索引号，并且希望以后能够轻松删除顶点。

我有这种图形结构的工作算法：

typedef boost::adjacency_list<
        boost::vecS, boost::vecS, boost::undirectedS, 
        topologicalmap::Intersection_Graph ,
        boost::edge_weight_t, 
        boost::no_property > Graph_boost;

我有一个Intersection_Graph需要使用的顶点自定义结构。在这里我使用vecS。

我想改用listS来删除顶点。同样，我希望以后能够与Dijkstra算法一起使用。

我有点理解我需要boost::vertex_index_t在列表中，但是我对如何做到并同时保留自定义结构感到非常困惑。

我尝试了一些方法：

typedef boost::adjacency_list<
        boost::listS, boost::listS, boost::undirectedS, 
        boost::property<boost::vertex_index_t, topologicalmap::Intersection_Graph>,
        boost::edge_weight_t, 
        boost::no_property > Graph_boost;

但是我什至无法访问我的自定义结构。另外，索引访问不起作用。

我真的需要那种索引访问功能，因为我的图的算法将取决于返回父节点的索引。我觉得我可以摆脱使用Vertex而不是索引的习惯，但这意味着代码需要大量重写，我想知道是否可以避免使用它。

所以我的问题是：在保持listS优势的同时，有什么方法可以使listS表现得像vecS一样？

请，如果这听起来很愚蠢，请忍受我。我现在很困惑，所以我可能会说些愚蠢的话。如果您需要更多信息，请询问。

使用boost :: graph库的boost示例通常使用如下图

using namespace boost;
typedef adjacency_list
    < vecS, // edge container 
      vecS, // vertex container
      undirectedS,
      property<vertex_index_t, int>,
      property<edge_index_t, int>
    > graph;

因此它们工作得很好。但是我有一个图

typedef adjacency_list
   < setS, // edge container 
     listS, // vertex container
     undirectedS,
     boost::no_property,  // vertex property
     boost::no_property // edge property
   > graph;

而且算法无法立即使用。在大多数情况下，必须提供用于查找特定顶点索引（整数值）的vertex_descriptor的映射。

我想检查我的图是否是平面的，并计算它的平面嵌入。我提供了一个顶点索引图，它确实以这种方式用于（例如connected_components）算法，但显然不适用于boyer_myrvold_planarity_test：

using namespace boost;

typedef adjacency_list
<boost::setS, boost::listS, undirectedS,
     boost::no_property, boost::no_property> graph;

typedef  boost::graph_traits<graph>::edge_descriptor    EdgeDesc;
typedef boost::graph_traits<graph>::vertex_descriptor   VertexDesc;

typedef std::map<VertexDesc, size_t> VertexDescMap;
typedef std::map<EdgeDesc, size_t> EdgeDescMap;
typedef boost::graph_traits<graph>::vertex_iterator VertexIterator;


graph K_4;

std::vector<VertexDesc> …