我正在使用Boost BGL C,我需要Graph从Source顶点到目标顶点执行BFS并返回所有唯一路径 .
现在,我想到了一种方法来使用过滤图来获取包含从源到目标的路径的图的子集但我意识到它基本上没有过滤,因为过滤后的图包含被访问但不是路径的一部分的顶点从源头到目标 . 有没有办法获得这些信息或更好的方法?
代码:
boost::filtered_graph<DirectedGraph, boost::keep_all, std::function<bool(VertexDescr)>> Graph::getUniquePathsFromSource(VertexDescr source, VertexDescr target, DirectedGraph const & g)
{
std::vector<double> distances(num_vertices(g));
std::vector<boost::default_color_type> colormap(num_vertices(g));
// Run BFS and record all distances from the source node
breadth_first_search(g, source,
visitor(make_bfs_visitor(boost::record_distances(distances.data(), boost::on_tree_edge())))
.color_map(colormap.data())
);
for (auto vd : boost::make_iterator_range(vertices(g)))
if (colormap.at(vd) == boost::default_color_type{})
distances.at(vd) = -1;
distances[source] = -2;
boost::filtered_graph<DirectedGraph, boost::keep_all, std::function<bool(VertexDescr)>>
fg(g, {}, [&](VertexDescr vd) { return distances[vd] != -1; });
// Print edge list
std::cout << "filtered out-edges:" << std::endl;
std::cout << "Source Vertex: " << source << std::endl;
auto ei = boost::edges(fg);
typedef boost::property_map<DirectedGraph, boost::edge_weight_t>::type WeightMap;
WeightMap weights = get(boost::edge_weight, fg);
for (auto it = ei.first; it != ei.second; ++it)
{
if (source != boost::target(*it, g)) {
std::cout << "Edge Probability " << *it << ": " << get(weights, *it) << std::endl;
}
}
return fg;
}
输入(vertex1,vertex2,weight):
0 1 0.001
0 2 0.1
0 3 0.001
1 5 0.001
2 3 0.001
3 4 0.1
1 482 0.1
482 635 0.001
4 705 0.1
705 5 0.1
1 1491 0.01
1 1727 0.01
1 1765 0.01
输出(For Source = 0,Target = 5):
Source Vertex: 0
Edge Probability (0,1): 0.001
Edge Probability (0,2): 0.1
Edge Probability (0,3): 0.001
Edge Probability (1,5): 0.001
Edge Probability (1,482): 0.1
Edge Probability (1,1491): 0.01
Edge Probability (1,1727): 0.01
Edge Probability (1,1765): 0.01
Edge Probability (2,3): 0.001
Edge Probability (3,4): 0.1
Edge Probability (4,705): 0.1
Edge Probability (482,635): 0.001
Edge Probability (705,5): 0.1
预期产出:
0->1->5
0->3->4->705->5
0->2->3->4->705->5
1 回答
我不会使用BFS算法,因为它使用色彩映射来跟踪被访问的节点 . 但是,如果您想要所有不同的路径,则不希望跳过已访问过的节点(因为您可能会跳过备用路径) .
相反,我实现了一个蛮力广度优先递归算法,它只是访问它们已经在当前路径中的所有相邻节点 unless .
所需的所有状态是当前路径 .
这个想法在这里有更详细的解释:https://www.quora.com/How-should-I-find-all-distinct-simple-paths-between-2-given-nodes-in-an-undirected-graph
Live On Coliru
哪个印刷品: