Поиск с ограниченной глубиной в 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)? Будем надеяться, что первоначальное окрашивание вершин также прекратится, когда Terminator вернет true, но, похоже, об этом уже позаботились. Может быть, связанный с этим вопрос: как насчет индексации, если граф использует что-то еще, кроме vecS? Может ли BFS/DFS обойтись без индексации в этом случае? Спасибо за любую помощь.


c++ boost-graph
person user1226313    schedule 29.12.2012    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

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

person user1226313    schedule 05.07.2013