Wyczyść szczyt od wszystkich sąsiadów v

Question 1

Realizuję algorytm w C++ za pomocą Boost Graph.

Chcę znaleźć wszystkie szczyt w okolicy v (czyli wszystkich jej sąsiadów), a następnie zmienić ich właściwości i wreszcie, wyczyść wszystkie ich krawędzie.

Znalazłem w funkcji Boost adjacent_vertices(v,g) (gdzie v-wierzchołek, a g-hrabia), aby znaleźć wszystkich sąsiadów. Następnie chcę zastosować do wszystkich z nich funkcję clear_vertex(v,g) (znowu, v-wierzchołek, a g-hrabia), aby usunąć je wszystkie żebra.

W tym momencie mam problem. To adjacent_vertices funkcja zwraca parę adjacency_iterator, podczas gdy dla clear_vertex funkcja, która jest mi potrzebna vertex_iterator (jeśli dobrze rozumiem, jak działają te funkcje).

Tak więc, istnieje prosty sposób, aby przekształcić adjacency_iterator w vertex_iterator? Jeśli zachowam adjacency_iterator i przekazać go w clear_vertex funkcja, problem w tym, że ona nie usuwa żebra (lub usuwa je losowo na niektóre szczyty).

Mój niepoprawny kod to:

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

Question 2

To zależy od selektorów granicznych kontenerów.

Najprostszy sposób-to jest, gdy pojemniki są oparte na węzłach, Czyli Nieskuteczni tylko iteratory/deskryptory wszystkich usuniętych żeber.

Inny sposób polega na podziale aspektów "zapytanie" i "modyfikacja", np.

Program kompilatorów

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

Możliwe wyjście:

Before: 2000
After: 1983

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

To zależy od selektorów granicznych kontenerów.

Najprostszy sposób-to jest, gdy pojemniki są oparte na węzłach, Czyli Nieskuteczni tylko iteratory/deskryptory wszystkich usuniętych żeber.

Inny sposób polega na podziale aspektów "zapytanie" i "modyfikacja", np.

Program kompilatorów

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

Możliwe wyjście:

Before: 2000
After: 1983

Wyczyść szczyt od wszystkich sąsiadów v

Pytanie

Najlepsza odpowiedź

W innych językach

Ta strona jest w innych językach

Popularne w tej kategorii

Najczęściej zadawane pytania w tej kategorii