Увеличить граф: перебирая все вершины и печатая смежные вершины - PullRequest
Новая
       34

Увеличить граф: перебирая все вершины и печатая смежные вершины

0 голосов
/ 18 мая 2018

Я хочу напечатать все вершины с их смежными вершинами.Я нашел несколько примеров того, как это сделать, но у меня это не сработает.Я получаю ошибку, что оператор ++ не может быть использован на ai.Также я думаю, что это должно быть vertex_idMap[*ai], а не vertex_idMap[ai], но это вызывает ошибку.Кто-нибудь знает, почему это не так? 

typedef adjacency_list<vecS, listS, directedS, VertexIDPorperty, EdgeWeight> Graph;  //the type of g
graph_traits <Graph>::vertex_iterator i, end;
graph_traits <Graph>::adjacency_iterator ai, a_end;
for (boost::tie(i, end) = vertices(g); i != end; ++i) {
    std::cout << vertex_idMap[*i];
    for (; ai != a_end; ++ai) {   //the ++ai seems to be wrong?
        std::cout << vertex_idMap[ai];
        if (boost::next(ai) != a_end)
            std::cout << ", ";
    }
std::cout << std::endl;

1 Ответ

0 голосов
/ 18 мая 2018

Наблюдения:

  1. Где остальная часть кода?Очевидно, что это зависит от используемых типов.
  2. ai и a_end не инициализируются (возможно, вы не имели в виду, что код не компилируется, и это была вся ваша проблема)
  3. vertex_idMap[ai] не скомпилируется, поскольку vertex_iterator не является допустимым vertex_descriptor

Вот фиксированный пример с воображаемыми недостающими битами:

Live On Coliru 

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

using VertexIDPorperty = boost::property<boost::vertex_index_t, int>;
using EdgeWeight       = boost::property<boost::edge_weight_t, double>;
typedef boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, VertexIDPorperty, EdgeWeight> Graph;

Graph sample();

int main() {
    Graph g = sample();
    auto vertex_idMap = get(boost::vertex_index, g);
    boost::graph_traits <Graph>::vertex_iterator i, end;
    boost::graph_traits <Graph>::adjacency_iterator ai, a_end;

    for (boost::tie(i, end) = vertices(g); i != end; ++i) {
        std::cout << vertex_idMap[*i] << ": ";

        for (boost::tie(ai, a_end) = adjacent_vertices(*i, g); ai != a_end; ++ai) {
            std::cout << vertex_idMap[*ai];
            if (boost::next(ai) != a_end)
                std::cout << ", ";
        }
        std::cout << std::endl;
    }
}

Реализация sample() для создания случайного графа: 

#include <boost/graph/random.hpp>
#include <random>

Graph sample() {
    Graph g;
    std::mt19937 prng { std::random_device{}() };

    generate_random_graph(g, 10, 20, prng);
    int id = 0;
    for (auto vd : boost::make_iterator_range(vertices(g))) {
        put(boost::vertex_index, g, vd, ++id);
    }

    return g;
}

Он печатает что-то вроде: 

1: 9, 9, 4
2: 6
3: 
4: 
5: 9, 9, 8, 9
6: 9, 3, 1
7: 2, 10
8: 6
9: 8
10: 7, 3, 8, 1, 4

Из коробки

Печать графика может быть выполнена проще: 

#include <boost/graph/graph_utility.hpp>
// ...

int main() {
    print_graph(sample());
}

Live On Coliru 

1 --> 
2 --> 3 10 9 6 6 10 
3 --> 8 
4 --> 
5 --> 4 
6 --> 1 5 8 
7 --> 4 9 2 2 1 
8 --> 6 
9 --> 5 7 
10 --> 7
...