Modificar las propiedades de los vértices en un Boost :: Graph

Question

Estoy intentando averiguar cómo usar boost :: graph para almacenar cierta información. Sin embargo, hay información que quiero atada a cada vértice. Al mirar la documentación de la biblioteca, aparece (a) documentación mal escrita, o (b), obviamente no soy tan bueno en C++ como pensaba. Elige dos.

Estoy buscando un ejemplo simple de uso.

Answer 1

Considero que Boost.Graph tiene una muy buena documentación, pero no es realmente para principiantes en la materia. ¡Así que aquí va un ejemplo que espero sea lo suficientemente simple!

//includes 

// Create a name for your information 
struct VertexInformation 
{ 
    typedef boost::vertex_property_type type; 
}; 

// Graph type, customize it to your needs 
// This is when you decide what information will be attached to vertices and/or edges 
// of MyGraph objects 
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, 
    boost::property<VertexInformation, double> > MyGraph; 

int main() 
{ 
    MyGraph graph; 

    // Create accessor for information 
    typedef boost::property_map<MyGraph, VertexInformation>::type InformationAccessor; 
    InformationAccessor information(get(VertexInformation(), graph)); 

    // Create a vertex (for example purpose) 
    typedef boost::graph_traits<MyGraph>::vertex_descriptor MyVertex; 
    MyVertex vertex = add_vertex(graph); 

    // Now you can access your information 
    put(information, vertex, 1.); 

    // returns 1 ! 
    get(information, vertex); 
    return 0; 
} 

Answer 2

A continuación se muestra el código que solía adjuntar algunas propiedades a los vértices, los bordes y los gráficos. Tenga en cuenta que el nombre del vértice y el nombre del gráfico son propiedades predefinidas (consulte boost/properties.hpp para obtener una lista completa) de modo que vertex_name_t y graph_name_t ya estén definidos. Sin embargo, vertex_location_t, edge_length_t y graph_notes_t son mis propias propiedades y, por lo tanto, necesitan definición. Construí este código a partir de varios ejemplos y documentación, y no estoy seguro de qué es exactamente lo que BOOST_INSTALL_PROPERTY hace, pero el código parece funcionar bien.

// Define custom properties 
enum vertex_location_t { vertex_location }; 
enum edge_length_t  { edge_length  }; 
enum graph_notes_t  { graph_notes  }; 

namespace boost 
{ 
    BOOST_INSTALL_PROPERTY(vertex, location); 
    BOOST_INSTALL_PROPERTY(edge, length ); 
    BOOST_INSTALL_PROPERTY(graph, notes ); 
} 

// Define vertex properties: vertex name and location 
typedef property<vertex_name_t,  string, 
     property<vertex_location_t, Point3> > 
VertexProperties; 

// Define edge properties: length 
typedef property<edge_length_t, double> EdgeProperties; 

// Define graph properties: graph name and notes 
typedef property<graph_name_t, string, 
     property<graph_notes_t, string> > 
GraphProperties; 

// Define a graph type 
typedef adjacency_list 
< 
    vecS,  // edge container type 
    vecS,  // vertex container type 
    undirectedS, 
    VertexProperties, 
    EdgeProperties, 
    GraphProperties 
> Graph; 

Answer 3

Encontré los ejemplos bastante útiles. En Windows, estará en su directorio \ Program Files \ boost \ boost_1_38 \ libs \ graph \ example.

kevin_bacon2.cpp utiliza las propiedades de los vértices para almacenar los nombres de los actores.

Sus propiedades de vértice y borde se pueden almacenar en estructuras normales o clases.

Answer 4

No me gusta el enfoque de propiedad de plantilla anidada de boost :: graph, así que escribí un pequeño contenedor alrededor de todo, que básicamente permite poner cualquier estructura/clase como una propiedad vertex/edge. Se puede acceder a las propiedades que acceden a los miembros de la estructura.

Para mantenerla flexible, estas estructuras se definen como parámetros de plantilla.

el código aquí:

/* definition of basic boost::graph properties */ 
enum vertex_properties_t { vertex_properties }; 
enum edge_properties_t { edge_properties }; 
namespace boost { 
    BOOST_INSTALL_PROPERTY(vertex, properties); 
    BOOST_INSTALL_PROPERTY(edge, properties); 
} 


/* the graph base class template */ 
template < typename VERTEXPROPERTIES, typename EDGEPROPERTIES > 
class Graph 
{ 
public: 

    /* an adjacency_list like we need it */ 
    typedef adjacency_list< 
     setS, // disallow parallel edges 
     listS, // vertex container 
     bidirectionalS, // directed graph 
     property<vertex_properties_t, VERTEXPROPERTIES>, 
     property<edge_properties_t, EDGEPROPERTIES> 
    > GraphContainer; 


    /* a bunch of graph-specific typedefs */ 
    typedef typename graph_traits<GraphContainer>::vertex_descriptor Vertex; 
    typedef typename graph_traits<GraphContainer>::edge_descriptor Edge; 
    typedef std::pair<Edge, Edge> EdgePair; 

    typedef typename graph_traits<GraphContainer>::vertex_iterator vertex_iter; 
    typedef typename graph_traits<GraphContainer>::edge_iterator edge_iter; 
    typedef typename graph_traits<GraphContainer>::adjacency_iterator adjacency_iter; 
    typedef typename graph_traits<GraphContainer>::out_edge_iterator out_edge_iter; 

    typedef typename graph_traits<GraphContainer>::degree_size_type degree_t; 

    typedef std::pair<adjacency_iter, adjacency_iter> adjacency_vertex_range_t; 
    typedef std::pair<out_edge_iter, out_edge_iter> out_edge_range_t; 
    typedef std::pair<vertex_iter, vertex_iter> vertex_range_t; 
    typedef std::pair<edge_iter, edge_iter> edge_range_t; 


    /* constructors etc. */ 
    Graph() 
    {} 

    Graph(const Graph& g) : 
     graph(g.graph) 
    {} 

    virtual ~Graph() 
    {} 


    /* structure modification methods */ 
    void Clear() 
    { 
     graph.clear(); 
    } 

    Vertex AddVertex(const VERTEXPROPERTIES& prop) 
    { 
     Vertex v = add_vertex(graph); 
     properties(v) = prop; 
     return v; 
    } 

    void RemoveVertex(const Vertex& v) 
    { 
     clear_vertex(v, graph); 
     remove_vertex(v, graph); 
    } 

    EdgePair AddEdge(const Vertex& v1, const Vertex& v2, const EDGEPROPERTIES& prop_12, const EDGEPROPERTIES& prop_21) 
    { 
     /* TODO: maybe one wants to check if this edge could be inserted */ 
     Edge addedEdge1 = add_edge(v1, v2, graph).first; 
     Edge addedEdge2 = add_edge(v2, v1, graph).first; 

     properties(addedEdge1) = prop_12; 
     properties(addedEdge2) = prop_21; 

     return EdgePair(addedEdge1, addedEdge2); 
    } 


    /* property access */ 
    VERTEXPROPERTIES& properties(const Vertex& v) 
    { 
     typename property_map<GraphContainer, vertex_properties_t>::type param = get(vertex_properties, graph); 
     return param[v]; 
    } 

    const VERTEXPROPERTIES& properties(const Vertex& v) const 
    { 
     typename property_map<GraphContainer, vertex_properties_t>::const_type param = get(vertex_properties, graph); 
     return param[v]; 
    } 

    EDGEPROPERTIES& properties(const Edge& v) 
    { 
     typename property_map<GraphContainer, edge_properties_t>::type param = get(edge_properties, graph); 
     return param[v]; 
    } 

    const EDGEPROPERTIES& properties(const Edge& v) const 
    { 
     typename property_map<GraphContainer, edge_properties_t>::const_type param = get(edge_properties, graph); 
     return param[v]; 
    } 


    /* selectors and properties */ 
    const GraphContainer& getGraph() const 
    { 
     return graph; 
    } 

    vertex_range_t getVertices() const 
    { 
     return vertices(graph); 
    } 

    adjacency_vertex_range_t getAdjacentVertices(const Vertex& v) const 
    { 
     return adjacent_vertices(v, graph); 
    } 

    int getVertexCount() const 
    { 
     return num_vertices(graph); 
    } 

    int getVertexDegree(const Vertex& v) const 
    { 
     return out_degree(v, graph); 
    } 


    /* operators */ 
    Graph& operator=(const Graph &rhs) 
    { 
     graph = rhs.graph; 
     return *this; 
    } 

protected: 
    GraphContainer graph; 
}; 

El uso de este se puede acceder a las propiedades de esta manera:

struct VertexProperties { 
    int i; 
}; 

struct EdgeProperties { 
}; 

typedef Graph<VertexProperties, EdgeProperties> MyGraph; 

MyGraph g; 

VertexProperties vp; 
vp.i = 42; 

MyGraph::Vertex v = g.AddVertex(vp); 

g.properties(v).i = 23; 

Por supuesto, es posible que tenga otras necesidades de la estructura de su gráfico, pero la modificación del código anterior debe se muy fácil

Answer 5

¿Qué tal el uso de propiedades agrupadas?

using namespace boost; 

struct vertex_info { 
    std::string whatever; 
    int othervalue; 
    std::vector<int> some_values; 
}; 

typedef adjacency_list<vecS, vecS, undirectedS, vertex_info> graph_t; 

graph_t g(n); 

g[0].whatever = "Vertex 0"; 

[...] 

y así sucesivamente.

Uso mucho BGL y trabajar con propiedades empaquetadas es muy sencillo (see the docs).

El otro tipo de propiedad de vértice que utilizo a menudo son propiedades externas. Puede declarar std::vectors del tamaño apropiado y usarlos como propiedades la mayoría de las veces y en la mayoría de los algoritmos.