在BGL中恢复一个星形搜索

Question

我在一个部分(？)隐式的图上运行astar算法 - 它是从一个大的分页数据源构建的,但是图是持久的.每当astar算法到达一个未完全分页的区域时,我需要在图形的新部分处理分页 - 理想情况下,不完全启动astar搜索.

我尝试了几种解决方案,但遇到了一些障碍,我想知道我是否遗漏了一些显而易见的问题,或者只是接近问题.

我目前正在使用boost 1.45但计划升级到1.51.

首先,我尝试修改astar访问者,以便当它确定需要在新数据中进行分页时,它会调用图上的函数并加载它 - 但是,由于图是const,所以这是不可能的.我环顾四周,发现另一个问题是提升隐式图和astar_search_no_init引用了一个表示有人完成了这项工作的演示文稿,但看起来实际代码不可用.

其次,当我到达需要在更多数据中分页的地方时,我想我可以退出算法,并保存distance_map,predecessor_map和color_map的状态,以便我可以使用它们来"恢复"使用astar_search_no_init进行搜索.我不确定这是否会起作用,因为一旦我切换到使用astar_search_no_init,我看到当访问者似乎做了寻路工作时,前一个地图是空的 - 因为我使用前一个来构建路径之后访问者完成后,我需要知道访问者如何构建路径.

这是我的图表的定义以及我如何调用astar_search,如果这有帮助的话.

typedef adjacency_list<
     vecS,         
     vecS,        
     undirectedS, 
     VertexInfo,        //contains geographic location     
     EdgeInfo,          //contains weight information             
     no_property,     
     setS>            
        BoostGraph;
...
ColorMap cmap = get(vertex_color_t, myGraph);           
astar_search(
     myGraph, 
     source,
     distance_heuristic(myGraph, destination), //geometric distance heuristic
     predecessor_map(&srcPredmap[0]).
     distance_map(&distMap[0]).
     color_map(cmap).
     visitor(astar_goal_visitor<vertex_descriptor>(destination, this)). //throws an exception when it finds the goal
     weight_map(make_function_property_map<edge_descriptor>(  //copied make_function_property_map functionality from boost 1.51 since I can't upgrade just yet
        EdgeWeightAdjuster(&myGraph, weightFactors))));       //modifies edge weights based on weightFactors construct

Answer 1

你写道：“但是，由于图是常量，所以这是不可能的......”那么简单的 CAST（事件是旧的 C-cast）又如何呢？您应该至少尝试一下这个选项。修改图可能会使迭代器等失效。这是事实。尽管如此，你还是应该尝试一下。

“技术恒定性”和“概念恒定性”之间是有区别的。就您而言，您只会破坏技术方面的问题，而不是概念方面的问题。