У меня есть 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 для отфильтрованного графа как такового.
Пожалуйста, предложите.
Когда отфильтрованный граф исключает некоторую вершину, он также исключает все связанные с ним ребра. Это означает, что некоторые ребра отфильтровываются, даже если вы укажете keep_all
.
Internally, filtered_graph
имеет специальный предикат края (объединенный из предиката края и предиката вершин), который используется для фильтрации краев. Когда вы запрашиваете внешние грани данной вершины, BGL возвращает вам пару итераторов фильтров.
Итератор "End" тривиально основан на "конце" функции out_edges
для лежащего в основе графика. Итератор "Начало" начинается с "начала" функции out_edges
и проверяет, является ли "цель" ребра частью графика. Если это не так, итератор пропускает его, пока не найдет хорошую вершину (или не ударит "конец").
Поэтому итератор постоянно проверяет "целевую" вершину и вызывает предикат вершин.