Очистить вершину от всех соседей v

Question 1

Я реализую алгоритм на C++ с помощью Boost Graph.

Я хочу найти всю вершину в окрестности v (то есть всех ее соседей), затем изменить их свойство и, наконец, очистить все их ребра.

Я нашел в Boost функцию adjacent_vertices(v,g) (где v-вершина, а g-граф), чтобы найти всех соседей. Затем я хочу применить ко всем из них функцию clear_vertex(v,g) (опять же, v-вершина, а g-граф), чтобы удалить все их ребра.

На данный момент у меня есть проблема. То adjacent_vertices функция возвращает пару adjacency_iterator, в то время как для clear_vertex функция, которая мне нужна vertex_iterator (если я правильно понимаю, как работают эти функции).

Итак, есть простой способ преобразовать adjacency_iterator в vertex_iterator? Если я сохраню adjacency_iterator и передайте его в clear_vertex функция, проблема в том, что она не удаляет ребра (или удаляет их случайным образом в некоторые вершины).

Мой неправильный код-это:

Graph::adjacency_iterator v,vend;
        for(boost::tie(v,vend) = neighbours; v != vend ; ++v) {
            clear_vertex(*v,g2);
        }

Question 2

Это зависит от селекторов пограничных контейнеров.

Самый простой способ-это когда контейнеры основаны на узлах, т. Е. Недействительны только итераторы/дескрипторы любых удаленных ребер.

Другой способ заключается в разделении аспектов "запрос" и "модификация", например

Обозреватель компиляторов

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

void clear_all_neighbours(auto v, auto& g) {
    auto neigh = adjacent_vertices(v, g);
    std::set to_clear(neigh.first, neigh.second);

    for (auto u : to_clear)
        clear_vertex(u, g);
}

int main()
{
    std::mt19937            prng(std::random_device{}());
    boost::adjacency_list<> g;
    generate_random_graph(g, 1000,2000, prng);
    std::cout << "Before: " << num_edges(g) << "\n";

    auto v = vertex(prng() % num_vertices(g), g);
    clear_all_neighbours(v, g);

    std::cout << "After: " << num_edges(g) << "\n";
}

Возможный выход:

Before: 2000
After: 1983

sehe · Answer 1 · 2021-11-20T16:24:20

Это зависит от селекторов пограничных контейнеров.

Самый простой способ-это когда контейнеры основаны на узлах, т. Е. Недействительны только итераторы/дескрипторы любых удаленных ребер.

Другой способ заключается в разделении аспектов "запрос" и "модификация", например

Обозреватель компиляторов

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

void clear_all_neighbours(auto v, auto& g) {
    auto neigh = adjacent_vertices(v, g);
    std::set to_clear(neigh.first, neigh.second);

    for (auto u : to_clear)
        clear_vertex(u, g);
}

int main()
{
    std::mt19937            prng(std::random_device{}());
    boost::adjacency_list<> g;
    generate_random_graph(g, 1000,2000, prng);
    std::cout << "Before: " << num_edges(g) << "\n";

    auto v = vertex(prng() % num_vertices(g), g);
    clear_all_neighbours(v, g);

    std::cout << "After: " << num_edges(g) << "\n";
}

Возможный выход:

Before: 2000
After: 1983

Очистить вершину от всех соседей v

Вопрос

Лучший ответ

На других языках

Эта страница на других языках

Популярное в этой категории

Популярные вопросы в этой категории