부스트의 property_map은 키가 존재하는지 테스트합니까?

Question

BGL의 문맥에서 나는 in_edges과 out_edges을 반복 할 필요가 있습니다. 그러나 나는 역방향 가장자리의 일부인 것을 제외하고 싶습니다. 즉, 역방향 가장자리의 일부인 제외 할 것입니다. property_map. 아래 코드는 내가하고 싶은 것을 보여 주지만 물론 property_map에는 find과 end 메서드가 없습니다.

업데이트 : 가능한 해결책은 그래프를 만드는 동안 반대쪽 가장자리가 포함 된지도와 같은 별도의 구조를 유지하는 것입니다. 이 함수는 그래프 건물을 제어 할 수는 있지만 작동하지 않습니다. 왜냐하면 read_dimacs_max_flow 함수를 사용하여 DIMACS 형식의 그래프 파일을 읽었 기 때문입니다. 그래서 나는 BGL의 접근성 방법에 의존해서 무엇이 무엇인지 알아낼 수 있습니다.

그래프 정의 :

typedef adjacency_list_traits<vecS, vecS, bidirectionalS> ttraits; 
typedef adjacency_list<vecS, vecS, bidirectionalS, 
     // vertex properties 
     property<vertex_index_t, int, 
     property<vertex_color_t, default_color_type> >, 
     // edge properties 
     property<edge_capacity_t, int, 
     property<edge_residual_capacity_t, int, 
     property<edge_reverse_t, ttraits::edge_descriptor> > >, no_property, vecS> tbgl_adjlist_bidir; 

typedef graph_traits<tbgl_adjlist_bidir>::vertex_descriptor  tvertex; 
typedef graph_traits<tbgl_adjlist_bidir>::edge_descriptor  tedge; 
typedef property_map<tbgl_adjlist_bidir, edge_capacity_t>::type tedge_capacity_map; 
typedef property_map<tbgl_adjlist_bidir, edge_reverse_t>::type treverse_edge_map; 
typedef property_map<tbgl_adjlist_bidir, vertex_color_t>::type tvertex_color_map; 
typedef property_map<tbgl_adjlist_bidir, vertex_index_t>::type tvertex_index_map; 
typedef graph_traits<tbgl_adjlist_bidir>::vertex_iterator  tvertex_iterator; 
typedef graph_traits<tbgl_adjlist_bidir>::edge_iterator   tedge_iterator; 
typedef graph_traits<tbgl_adjlist_bidir>::out_edge_iterator  tout_edge_iterator; 
typedef graph_traits<tbgl_adjlist_bidir>::in_edge_iterator  tin_edge_iterator; 

과 내가하고 싶은 (그러나 아래의 오류와 함께 컴파일되지 않습니다) 무엇의 예를 조각 :

tvertex_index_map indices = get(vertex_index, bgl_adjlist_bidir); 
tedge_capacity_map capacities = get(edge_capacity, bgl_adjlist_bidir); 
treverse_edge_map rev_edges = get(edge_reverse, bgl_adjlist_bidir); 

// iterate all vertices in the right order 
for (int current = 0; current < m_num_vertices; ++current) { 
    printf("processing vertex=%d\n", current); 
    tin_edge_iterator ei1, ei1_end; 
    for (tie(ei1, ei1_end) = in_edges(tvertex(current), bgl_adjlist_bidir); ei1 != ei1_end; ++ei1) { 
     // exclude reverse edges <<<<<<<======= HOW DO I DO THIS?? 
     if (rev_edges.find(*ei1) != rev_edges.end()) { 
      continue; 
     } 
     int in = indices[boost::source(*ei1, bgl_adjlist_bidir)]; 
     printf("in edge: %d <- %d \n", current, in); 
    } 
} 

컴파일러 오류 :

/Users/bravegag/code/fastcode_project/build_debug$ make 2> out ; grep -i "error" ./out 
[ 2%] Building CXX object CMakeFiles/submodularity.dir/src/graph/hp_adjlist_bidir.cc.o 
/Users/bravegag/code/fastcode_project/code/src/api/hp_adjlist_bidir.h:146:18: error: 'treverse_edge_map' has no member named 'find' 
/Users/bravegag/code/fastcode_project/code/src/api/hp_adjlist_bidir.h:146:42: error: 'treverse_edge_map' has no member named 'end' 
make[2]: *** [CMakeFiles/submodularity.dir/src/graph/hp_adjlist_bidir.cc.o] Error 1 
make[1]: *** [CMakeFiles/submodularity.dir/all] Error 2 
make: *** [all] Error 2 

Answer 1

edge_reverse 속성 -지도는 가장자리 설명자를 그래프의 각 가장자리에 연결합니다. 따라서 "찾기"기능은 모든 가장자리가 해당 속성 - 맵에서 해당 항목을 갖기 때문에 의미가 없습니다. (그러한 속성 - 맵은 반드시 std::map 개체로 구현되지는 않으며 실제로는 내부 속성의 경우).

할 수있는 일은 각 가장자리에 대한 역방향 가장자리 속성 값을 설정하여 역방향 가장자리의 가장자리 설명자 또는 잘못된 가장자리 설명자 (역방향 가장자리가 아닌 경우)입니다.). 그런 다음, "find"대신에 검사는 reverse-edge 속성이 유효한 edge-descriptor인지 아닌지를 검사하는 것 중 하나 일뿐입니다.

불행히도 BGL은 null_vertex()처럼 정적 기능인 null_edge()을 제공하지 않습니다. 이것은 아마도 개발자들에 의한 생략 일 것입니다 (저는 자신의 그래프 구조를 몇 개 개발했고, null_edge() 함수를 포함했지만 Boost에서는 포함하지 않았습니다). 이것은 쓸모있는 "null-edge"디스크립터 값을 사용하는 것이 어려울 수 있음을 의미합니다. 하나의 옵션은 다음과 같이 특정 비트 패턴을 사용하는 것입니다, 당신은 확인

ttraits::edge_descriptor my_null_edge; 
memset((char*)&my_null_edge, 0xFF, sizeof(ttraits::edge_descriptor)); 

그리고 모든 역 에지 특성을 위해 가장자리가 my_null_edge로 설정되어 비 반전 한 후이 비교로 루프를 구현합니다

를

for (tie(ei1, ei1_end) = in_edges(tvertex(current), bgl_adjlist_bidir); ei1 != ei1_end; ++ei1) { 
    // exclude reverse edges 
    if (rev_edges[*ei1] != my_null_edge) { 
     continue; 
    } 
    int in = indices[boost::source(*ei1, bgl_adjlist_bidir)]; 
    printf("in edge: %d <- %d \n", current, in); 
} 

역방향 에지 특성이 매우 부족한 경우, 당신은 std::map (또는 std::unordered_map) 같은 맵 클래스를 사용하여 외부 특성-지도를 할 수 있습니다. adjacency-list 클래스 템플릿에서 EdgeProperty 또는 VertexProperty로 지정한 항목은 그래프의 각 꼭지점 또는 가장자리에 대한 값 (종류)으로 저장됩니다. std::map 동작을 원한다면 (할당 된 속성을 가진 부분 집합 만 저장합니다), adjacency-list 그래프에서 외부 적으로 간단히 할 수 있습니다. 속성 - 맵의 좋은 점은 내부 속성과 일치 할 필요가 없다는 것입니다. 유용 할 수도 있습니다.그것이되면, 물론, 다음

typedef boost::associative_property_map<treverse_edge_map> tbgl_reverse_edge_map; 

tbgl_reverse_edge_map bgl_rev_edges = boost::make_assoc_property_map(rev_edges); 

을하지만 :

typedef std::map< tedge, tedge > treverse_edge_map; 

treverse_edge_map rev_edges; 

을 그리고 당신이 BGL 속성 맵으로 rev_edges를 사용해야 할 경우, 당신은 사용할 수 있습니다 : 그래서, 당신은이 작업을 수행 할 수 있습니다 BGL 스타일의 property-map을 사용하면 더 이상 "찾기"메커니즘을 사용하여 속성이 주어진 가장자리에 대해 설정되었는지 여부를 파악할 수 없습니다.