Stimuler graphique: appliquer des algorithmes en considérant un sous-ensemble de bord spécifique

Question

J'ai un énorme graphique avec le bord typé (c'est-à-dire le bord avec une propriété de type). Dites

typedef adjacency_list<vecS, vecS, vertex_prop, edge_prop> Graph; 

Le « type » du bord est membre de edge_prop et a une valeur {A, B, C, D},
j'aimerais courir l'ampleur premier algorithme de recherche ne considérant que bords de type A ou B.
Comment le feriez-vous?

Answer 1

Enfin, je pense que le boost :: manière graphique pour le faire est d'utiliser boost:filtered_graph et demo for usage

« Le modèle de classe filtered_graph est un adaptateur qui crée une vue filtrée d'un graphique. Les objets fonction sous-jacente déterminer qui les arêtes et les sommets du graphique d'origine apparaîtront dans le graphique filtré. " Par conséquent, vous pouvez fournir une base de foncteur de filtrage de bord (ou vertex) sur une carte_propriété. Dans mon cas, j'utilise des propriétés groupées internes. Voir les cartes des propriétés de bundled properties.

Answer 2

Je ne suis pas du tout familier avec boost :: graph mais je suppose que c'est ce que vous cherchez BFSVisitor. Il vous permet de changer le comportement de l'algorithme et votre cas spécifique serait de changer l'examen des arêtes sortantes après la découverte de vertex et d'ignorer celles qui ne sont pas du "type" requis (en réalité {A, B, C, D } sont des valeurs pour autant que je comprends et non des types au sens strict).

Answer 3

Parce qu'il est difficile de trouver par exemple un simple mélange différents sujets du BGL, je poste ci-dessous un exemple complet et de travail en utilisant filtered_graph et propriétés empaquetés .:

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

using namespace boost; 

enum edge_type_e { 
    A, B, C, D 
}; 

class edge_property_c { 
public: 
    edge_property_c(void) : type_m(A) {} 
    edge_property_c(edge_type_e type) : type_m(type) {} 
    edge_type_e type_m; 
}; 

typedef adjacency_list<vecS, vecS, undirectedS, no_property, edge_property_c> graph_t; 
typedef graph_t::edge_descriptor edge_id_t; 

class edge_predicate_c { 
public: 
    edge_predicate_c() : graph_m(0) {} 
    edge_predicate_c(graph_t& graph) : graph_m(&graph) {} 
    bool operator()(const edge_id_t& edge_id) const { 
    edge_type_e type = (*graph_m)[edge_id].type_m; 
    return (type == A || type == B); 
    } 
private: 
    graph_t* graph_m; 
}; 

int main() { 
    enum { a, b, c, d, e, n }; 
    const char* name = "abcde"; 
    graph_t g(n); 
    add_edge(a, b, edge_property_c(A), g); 
    add_edge(a, c, edge_property_c(C), g); 
    add_edge(c, d, edge_property_c(A), g); 
    add_edge(c, e, edge_property_c(B), g); 
    add_edge(d, b, edge_property_c(D), g); 
    add_edge(e, c, edge_property_c(B), g); 

    filtered_graph<graph_t, edge_predicate_c> fg(g, edge_predicate_c(g)); 

    std::cout << "edge set: "; 
    print_edges(g, name); 
    std::cout << "filtered edge set: "; 
    print_edges(fg, name); 

    return 0; 
}