Свойство Boost property_map проверяет, существует ли ключ?

Question

В контексте BGL мне нужно итерации in_edges и out_edges, но я хочу исключить те, которые являются частью обратных ребер, то есть исключают те, которые являются частью обратных краев property_map. В приведенном ниже коде показано, что я хотел бы сделать, но, конечно, property_map не имеет find и end методов.

UPDATE: Возможное решение состоит в том, чтобы поддерживать отдельную структуру, такую ​​как карта, содержащая обратные ребра при построении графика. Это будет работать, если у меня будет контроль над построением графика, но я не потому, что я использую функцию read_dimacs_max_flow для чтения графического файла в формате DIMACS. Поэтому я могу полагаться только на методы доступности BGL, чтобы выяснить, что это такое.

определение Graph:

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») является просто проверкой, является ли свойство обратного края допустимым дескриптором ребра или нет.

К сожалению, BGL не предоставляет статическую функцию null_edge() (как и для null_vertex()). Вероятно, это было упущением разработчиков (я разработал несколько собственных графических структур, и я включил функцию null_edge(), но не в Boost). Это означает, что было бы трудно найти хорошее и переносимое значение дескриптора нулевого края для использования. Одним из вариантов является использование конкретного двоичных разрядов, как это:

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). То, что вы указываете как EdgeProperty или VertexProperty в шаблоне класса смежности, хранится по значению (вид) для каждой вершины или края графика. Если вы хотите, чтобы поведение std::map (только сохраняет подмножество с назначенным свойством), вы можете просто сделать это извне на граф смежности, хорошая вещь с картами свойств заключается в том, что они не должны соответствовать внутренним свойствам, которые также могут быть полезны.Таким образом, вы можете сделать это:

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

treverse_edge_map rev_edges; 

И если вам нужно использовать rev_edges как BGL свойства-карты, то вы можете использовать:

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); 

Но, конечно же, как только это BGL-свойство свойства-карты, вы больше не можете использовать механизм «найти», чтобы выяснить, установлено ли свойство для данного ребра.