Claro vértice de todos os vizinhos de v

Question 1

Eu sou a implementação de um algoritmo em C++ com Boost Graph.

Eu quero encontrar todos os vértices no bairro de v (então, todos os seus vizinhos) e, em seguida, alterar a propriedade de seus e finalmente limpar todas as suas arestas.

Eu encontrei em Aumentar a função adjacent_vertices(v,g) (onde v é o vértice a e g é o gráfico) para encontrar todos os vizinhos. Então eu quero aplicar em todas elas, a função clear_vertex(v,g) (novamente, v é o vértice e g é o gráfico) para remover todas as bordas.

Neste ponto, eu tenho um problema. O adjacent_vertices a função retorna um par de adjacency_iteratorenquanto que , para o clear_vertex a função que eu preciso vertex_iterator (se eu entendi corretamente como estas funções de trabalho).

Assim, não há uma maneira fácil de transformar o adjacency_iterator no vertex_iterator? Se eu manter o adjacency_iterator e passar para o clear_vertex função, o problema é que ele não remover as bordas (ou removê-los aleatoriamente para alguns vértices).

Minha errado código é:

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

Question 2

Depende da borda do recipiente de seletores.

A maneira mais fácil é quando os recipientes estão nó-com base, por exemplo, apenas os iteradores/descritores para qualquer removido bordas são invalidadas.

Outra forma é quando você divide a "consulta" e "modificação" aspectos, por exemplo,

Compilador Explorer

#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";
}

Saída possível:

Before: 2000
After: 1983

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

Depende da borda do recipiente de seletores.

A maneira mais fácil é quando os recipientes estão nó-com base, por exemplo, apenas os iteradores/descritores para qualquer removido bordas são invalidadas.

Outra forma é quando você divide a "consulta" e "modificação" aspectos, por exemplo,

Compilador Explorer

#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";
}

Saída possível:

Before: 2000
After: 1983

Claro vértice de todos os vizinhos de v

Pergunta

Melhor resposta

Em outros idiomas

Esta página está em outros idiomas

Popular nesta categoria

Perguntas populares nesta categoria