Реализация out_edges () в BOOST Filter_graph без edge_predicate

0

У меня есть boost :: filter_graph <Graph_t, boost :: keep_all, vertex_predicate>

Скажем, FG - мой фильтрованный граф. и v1 - любой узел, для которого я хочу найти все внешние ребра, используя out_edge_iterators

edge_predicate здесь предикат vertex "keep_all" - это некоторый предикат, который используется для изменения свойств узла графика.

В документации дается:

graph_traits<filtered_graph>::out_edge_iterator 
//The type for the iterators returned by out_edges(), which is:
filter_iterator<EdgePredicate, graph_traits<Graph>::out_edge_iterator>
The iterator is a model of MultiPassInputIterator.

теперь, когда я определяю out_edge_iterators:

out_edge_iterator begin, end;
boost::tie( begin, end) = out_edges ( v1, FG )

Я ожидаю, что следующее: 1. Он должен учитывать предоставленный edge_predicate и фильтровать края в соответствии с этим. в основном итераторы begin и end должны быть filter_iterators, основанные на краевом предикате. 2. Я не думаю, что vertex_predicate следует вызывать на другом узле ребер. например, предположим, что v1 имеет 3 внешних ребра (v1, v2), (v1, v4), (v1, v6).

Мое наблюдение: в процессе нахождения out_edges v1, vertex_predicate вызывается на самом первом противоположном узле v1. В приведенном выше случае,

suppose begin --> points to edge (v1, v2), then, 
out_edges(v1, G) ---> calls vertex_predicate on **v2**

Почему это так? Это из-за реализации функции out_edges(), которая связана с поиском соседних узлов и возвратом первого найденного узла?

В том же случае я наблюдаю, когда вызывается смежный_версии(). документация говорит, что он моделируется как out_edge_iterator <edge_predicate,...>.

Я получаю ожидаемые результаты. но я хочу знать, правильна ли моя догадка или нет? Я не предоставляю никакого edge_predicate для отфильтрованного графа как такового.

Пожалуйста, предложите.

Теги:
iterator
boost
boost-graph

1 ответ

1
Лучший ответ

Когда отфильтрованный граф исключает некоторую вершину, он также исключает все связанные с ним ребра. Это означает, что некоторые ребра отфильтровываются, даже если вы укажете keep_all.

Internally, filtered_graph имеет специальный предикат края (объединенный из предиката края и предиката вершин), который используется для фильтрации краев. Когда вы запрашиваете внешние грани данной вершины, BGL возвращает вам пару итераторов фильтров.

Итератор "End" тривиально основан на "конце" функции out_edges для лежащего в основе графика. Итератор "Начало" начинается с "начала" функции out_edges и проверяет, является ли "цель" ребра частью графика. Если это не так, итератор пропускает его, пока не найдет хорошую вершину (или не ударит "конец").

Поэтому итератор постоянно проверяет "целевую" вершину и вызывает предикат вершин.

Ещё вопросы

Сообщество Overcoder
Наверх
Меню