标签: boost-graph

我读过，当将 A* 应用于问题时，如果您的启发式是一致的，那么您可以进一步优化 A* 搜索。Boost Graph Library 提供两个版本的 A* 算法：astar_search和astar_search_tree。该文档对于两者之间的区别不是很清楚；其中之一是否执行假设一致启发式的优化搜索？

我正在使用 Boost C++ 库来构建一个邻接表来表示一个无向图。图上的每条边都与各自的权重相关联，我想检查权重是否大于某个阈值，而不是将两个顶点合并在一起。

我如何合并：

• 对于要合并的顶点，收集进出该顶点的所有边并将这些边指向新顶点
• 清除合并顶点
• 移除顶点

我的问题： 我使用一个简单的程序首先构造算法，然后再将其用于目的。在这个程序中，我使用简单的家谱方法来执行上述步骤。当我使用函数remove_vertex(vertex, Graph)删除顶点时， 出现分段错误。

• 我无法弄清楚一旦顶点被移除，图形是否会自动更新其结构？

我的 C++ 代码如下：

#include <boost/graph/adjacency_list.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/config.hpp>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

typedef boost::property<boost::vertex_index_t, int> vertex_property;
typedef boost::property<boost::edge_weight_t, float> edge_property;
typedef typename boost::adjacency_list <boost::vecS,
                                    boost::vecS,
                                    boost::undirectedS,
                                    vertex_property,
                                    edge_property> Graph;
void boostSampleGraph() {

enum family {
  Jeanie, Debbie, Rick, John, Amanda, Margaret, Benjamin, N };
const char *name[] = { "Jeanie", "Debbie", "Rick", "John", "Amanda",
                       "Margaret", "Benjamin", "N"
 }; …

我正在学习呼吸优先搜索算法。该图是一个完全二叉树。我想打印每个节点到根的距离。例如，d[0, 0] = 0, d[0, 1] = 1, d[0, 2] = 1, d[0, 3] = 2, d[0, 7] = 3。

点文件在这里。

digraph G {
0;
1;
2;
3;
4;
5;
6;
7;
8;
9;
10;
11;
12;
13;
14;
0->1 ;
0->2 ;
1->3 ;
1->4 ;
2->5 ;
2->6 ;
3->7 ;
3->8 ;
4->9 ;
4->10 ;
5->11 ;
5->12 ;
6->13 ;
6->14 ;
}

程序非常简单，make_bfs_visitor用adistance_recorder记录树边之间的距离。

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include …

我正在尝试从一组对 (int,int) 边（其中每个 int 代表一个顶点索引）中定义一个具有无向边的图。每个这样的边都有自己的索引。

问题是我希望图的内部顶点索引与原始顶点索引一致。我还希望能够从边缘描述符中提取原始边缘索引。

从http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/using_property_maps.html（外部属性部分）我明白我应该使用以下图形类型：

typedef adjacency_list<vecS, vecS, udirectedS, 
no_property, property<edge_index_t, std::size_t> > Graph;

不幸的是，没有关于如何使用 edge_index_t 属性的解释。

很明显，我可以只使用 map(pair(int,int),int) 但我正在寻找一个更优雅的面向提升的解决方案。

谢谢你，基里尔

我正在将用于Google AI挑战的机器人从Python重写为C++,我想使用boost的图形库来处理路径查找,而不是像以前在Python中那样滚动我自己的图形和搜索代码.

地图是一个简单的方形网格,包裹着边缘.

我之前没有使用过boost或C++(我非常了解C)而且我发现boost图文档真的很难理解,所以我需要一些帮助.

我遇到问题的具体文档:

• http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/dijkstra_shortest_paths.html
• http://www.boost.org/doc/libs/1_47_0/libs/graph/example/dijkstra-example.cpp
• 等,目前限于两个链接:)

这是工作python代码的片段:

def do_turn(self, ants):
    # update path-finding graph
    for row in range(ants.rows):
        for col in range(ants.cols):
            key = (row, col)
            self.graph[key] = []

            def append_if_unoccupied(coord):
                if ants.passable(coord) and coord not in ants.my_hills():
                    self.graph[key].append(coord)

            if row - 1 >= 0:
                append_if_unoccupied((row - 1, col))
            else:
                append_if_unoccupied((ants.rows + (row - 1), col))

            if col - 1 >= 0:
                append_if_unoccupied((row, col - 1))
            else:
                append_if_unoccupied((row, ants.cols + (col - 1)))

            if row + 1 < …

我在读某人的密码.这是来自boost图库的函数.这是原始的函数定义.

 void dijkstra_shortest_paths
      (const Graph& g,
       typename graph_traits<Graph>::vertex_descriptor s, 
       PredecessorMap predecessor, DistanceMap distance, WeightMap weight, 
       VertexIndexMap index_map,
       CompareFunction compare, CombineFunction combine, DistInf inf, DistZero zero,
       DijkstraVisitor vis, ColorMap color = default)

这是我从某人那里挑选出的一段代码.它有效,但我只是不明白他为什么在中间使用点predecessor_map weight_map而distance_map不是逗号？他传入函数的参数是多少？

dijkstra_shortest_paths(graph, source_vertex,
                          predecessor_map(&predecessors[0])
                          .weight_map(get(&Edge::cost, graph))
                          .distance_map(&distances[0]));