Ограниченный поиск глубины в BGL без O (number_of_vertices) используемой памяти или времени?

Можно ли выполнить поиск / посещение на глубину или ширину на некотором расстоянии от вершины в BGL без доступа, фильтрации, индексации и т. Д. Ко всем вершинам графа?

Самое близкое, что мне удалось написать, это (создает график 0<-> 1<-> 2<-> 3<-> 4<-> 5, но посещает только вершины от 0 до 3):

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

using namespace std;

struct custom_dfs_visitor : public boost::default_dfs_visitor {
template < typename Vertex, typename Graph >
void discover_vertex(const Vertex& v, const Graph& g) const {
std::cout << v << std::endl;
}
};

struct Terminator {
template<class Vertex, class Graph>
bool operator()(const Vertex& v, const Graph& g) {
return v > 2;
}
};

int main()
{
typedef boost::adjacency_list<
boost::vecS,
boost::vecS,
boost::undirectedS
> Graph_T;

Graph_T g(6);
boost::add_edge(0, 1, g);
boost::add_edge(1, 2, g);
boost::add_edge(2, 3, g);
boost::add_edge(3, 4, g);
boost::add_edge(4, 5, g);

std::vector<boost::default_color_type> color_map(boost::num_vertices(g));
boost::depth_first_visit(
g,
boost::vertex(0, g),
custom_dfs_visitor(),
boost::make_iterator_property_map(
color_map.begin(),
boost::get(boost::vertex_index, g),
color_map[0]
),
Terminator()
);

return 0;
}

который печатает только 0 1 2 3 вместо посещения всех вершин, но для кода все равно требуется цветная карта, такая же большая, как весь граф (boost :: num_vertices (g)). Есть ли способ сделать сложность поиска не сопоставимой с общим количеством ребер / вершин в графе?

Использование связанного цвета было бы приемлемым, потому что много запросов было бы сделано в различных частях графика, но возможно ли уменьшить сложность каждого отдельного поиска в одном и том же графике с O (number_of_vertices)?
Мы надеемся, что начальная окраска вершин также прекратится, когда Терминатор вернет истину, но об этом, похоже, уже позаботились.
Может быть, связанный вопрос: как насчет индексации, если график использует что-то еще, кроме vecS? Может ли BFS / DFS обойтись без индексации в этом случае?
Спасибо за любую помощь.

2

Решение

Оказывается, использование связанных свойств — самый простой способ сделать это. Тот факт, что свойство color включено в каждую вершину, лучше, чем создание свойства color для каждой вершины каждый раз, когда выполняется dfs. Тип графика должен быть

typedef boost::adjacency_list<
boost::vecS,
boost::vecS,
boost::undirectedS,
property<vertex_color_t, boost::default_color_type>
> Graph_T;

и вызов DFV является

depth_first_visit(
g,
vertex(0, g),
custom_dfs_visitor(),
get(vertex_color_t(), g),
Terminator()
);

С учетом вышесказанного, выполнение ограниченного dfs в графе с 100 M вершинами не увеличивает потребление памяти (76,2% от общей памяти), в то время как при внешнем векторе использования цветов использование памяти увеличивается с 76,2% до 78,5% при поиске.

0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector