Claire sommet de tous les voisins de v

Question 1

Je suis l'implémentation d'un algorithme en C++ avec Boost Graph.

Je veux trouver tous les vertex dans le voisinage de v (donc, l'ensemble de ses voisins), puis changez la propriété de leurs et enfin effacer tous leurs bords.

J'ai trouvé dans la fonction Boost adjacent_vertices(v,g) (où v est le sommet et g est le graphe) pour trouver tous les voisins. Alors je veux appliquer sur toutes les fonction clear_vertex(v,g) (encore une fois, v est le sommet et g est le graphe) pour supprimer l'ensemble de leurs bords.

À ce stade, j'ai un problème. L' adjacent_vertices la fonction retourne une paire de adjacency_iteratortandis que pour les clear_vertex fonction que j'ai besoin vertex_iterator (si je comprends bien la façon dont ces fonctions de travail).

Donc, il ya un moyen facile de transformer l' adjacency_iterator dans vertex_iterator? Si je garde le adjacency_iterator et passer à la clear_vertex la fonction, le problème est qu'il ne supprime pas les bords (ou de les supprimer de manière aléatoire à certains sommets).

Mon mal de code est:

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

Question 2

Il repose sur le bord du conteneur sélecteurs.

Le plus simple est lorsque les conteneurs sont basées sur les nœuds, c'est à dire uniquement les itérateurs/descripteurs de toute retiré les arêtes sont invalidés.

Une autre façon est quand vous divisez la "requête" et "modification" aspects, par exemple la

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

De sortie possibles:

Before: 2000
After: 1983

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

Il repose sur le bord du conteneur sélecteurs.

Le plus simple est lorsque les conteneurs sont basées sur les nœuds, c'est à dire uniquement les itérateurs/descripteurs de toute retiré les arêtes sont invalidés.

Une autre façon est quand vous divisez la "requête" et "modification" aspects, par exemple la

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

De sortie possibles:

Before: 2000
After: 1983

Claire sommet de tous les voisins de v

La question

La meilleure réponse

Dans d'autres langues

Cette page est dans d'autres langues

Populaires dans cette catégorie

Questions populaires dans cette catégorie