부스트 BGL BFS 소스에서 타겟까지의 모든 고유 경로 찾기

Question

부스트 BGL C++을 사용하고 있으며 소스 버텍스에서 대상 버텍스로 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 중량)

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 

출력 (소스 = 0의 경우, 목표 = 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 

Answer 1

방문한 노드를 추적하기 위해 색상 맵을 사용하므로 BFS 알고리즘을 사용하지 않습니다. 그러나 모두 별개의 경로를 원한다면 이미 방문한 노드를 건너 뛰고 싶지 않을 것입니다. 그 이유는 다른 경로를 건너 뛸 수 있기 때문입니다.

대신, 나는 이미 인접한 모든 노드를 방문하는 무차별 폭 폭 우선 재귀 알고리즘을 구현할 것입니다. 이 이미 현재 경로에 있지 않은 경우입니다.

필요한 모든 상태는 현재 경로입니다.

아이디어는 여기에 더 자세히 설명되어 있습니다 : https://www.quora.com/How-should-I-find-all-distinct-simple-paths-between-2-given-nodes-in-an-undirected-graph

Live On Coliru

#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/graph_utility.hpp> // print_graph 
using namespace boost; 
using Graph = adjacency_list<vecS, listS, directedS, property<vertex_index_t, int>, property<edge_weight_t, double> >; 
Graph read_graph(); 

using Vertex = Graph::vertex_descriptor; 
using Path = std::vector<Vertex>; 

template <typename Report> 
void all_paths_helper(Vertex from, Vertex to, Graph const& g, Path& path, Report const& callback) { 
    path.push_back(from); 

    if (from == to) { 
     callback(path); 
    } else { 
     for (auto out : make_iterator_range(out_edges(from, g))) { 
      auto v = target(out, g); 
      if (path.end() == std::find(path.begin(), path.end(), v)) { 
       all_paths_helper(v, to, g, path, callback); 
      } 
     } 
    } 

    path.pop_back(); 
} 

template <typename Report> 
void all_paths(Vertex from, Vertex to, Graph const& g, Report const& callback) { 
    Path state; 
    all_paths_helper(from, to, g, state, callback); 
} 

int main() { 
    auto g = read_graph(); 
    print_graph(g, std::cout); 

    auto by_vertex_id = [&](int id) { 
     return *find_if(vertices(g), [&](Vertex vd) { return id == get(vertex_index, g, vd); }); 
    }; 

    all_paths(by_vertex_id(0), by_vertex_id(5), g, [&](Path const& path) { 
      std::cout << "Found path "; 
      for (auto v : path) 
       std::cout << get(vertex_index, g, v) << " "; 
      std::cout << "\n"; 
     }); 
    std::cout.flush(); 
} 

// immaterial to the task, reading the graph 
Graph read_graph() { 
    std::istringstream iss(R"(
     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)"); 

    Graph g; 
    auto vertex = [&,idx=std::map<int,Vertex>{}](int id) mutable { 
     auto it = idx.find(id); 
     if (it != idx.end()) 
      return it->second; 
     return idx.emplace(id, add_vertex(id, g)).first->second; 
    }; 

    for (std::string line; getline(iss, line);) { 
     std::istringstream ls(line); 
     int s,t; double w; 
     if (ls >> s >> t >> w) { 
      add_edge(vertex(s), vertex(t), w, g); 
     } else { 
      std::cerr << "Skipped invalid line '" << line << "'\n"; 
     } 
    } 

    return g; 
} 

인쇄 어느 : 대답에 대한

1 --> 5 482 1491 1727 1765 
0 --> 1 2 3 
2 --> 3 
3 --> 4 
5 --> 
4 --> 705 
482 --> 635 
635 --> 
705 --> 5 
1491 --> 
1727 --> 
1765 --> 
Found path 0 1 5 
Found path 0 2 3 4 705 5 
Found path 0 3 4 705 5