Ändern von Vertex-Eigenschaften in einem Boost :: Graph

Question

Ich versuche herauszufinden, wie boost :: graph verwendet wird, um einige Informationen zu speichern. Es gibt jedoch Informationen, die ich an jeden Knoten binden möchte. Wenn ich auf die Dokumentation der Bibliothek stoße, enthüllt sich entweder (a) schlecht geschriebene Dokumentation, oder (b) ich bin offensichtlich nicht so gut in C++ wie ich dachte. Suche dir zwei aus.

Ich bin auf der Suche nach einem einfachen Beispiel zu verwenden.

Answer 1

Ich halte Boost.Graph für eine sehr gute Dokumentation, aber nicht wirklich für Anfänger in der Sache. Also hier ein Beispiel, das hoffentlich einfach genug ist!

//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

Unten ist Code, den ich verwendet habe, um einige Eigenschaften an Scheitelpunkte, Kanten und Graphen anzuhängen. Beachten Sie, dass der Scheitelpunktname und der Diagrammname vordefinierte Eigenschaften sind (siehe boost/properties.hpp für eine vollständige Liste), so dass vertex_name_t und graph_name_t bereits definiert sind. Jedoch sind vertex_location_t, edge_length_t und graph_notes_t meine eigenen Eigenschaften und müssen daher definiert werden. Ich habe diesen Code aus verschiedenen Beispielen und Dokumentationen zusammengeschustert, und ich bin mir nicht sicher, was genau BOOST_INSTALL_PROPERTY tut, aber der Code scheint gut zu funktionieren.

// 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

Ich fand die Beispiele ziemlich nützlich. Unter Windows befindet es sich im Verzeichnis \ Programme \ boost \ boost_1_38 \ libs \ graph \ example.

kevin_bacon2.cpp verwendet Vertex-Eigenschaften, um die Namen von Aktoren zu speichern.

Ihre Eckpunkt- und Kanteneigenschaften können in regulären Strukturen oder Klassen gespeichert werden.

Answer 4

Ich mag nicht die verschachtelte Vorlage Eigenschaft Ansatz von boost :: graph, also schrieb ich einen kleinen Wrapper um alles, das im Grunde erlaubt, jede Struktur/Klasse als eine Vertex/Edge-Eigenschaft. Man kann auf Eigenschaften zugreifen, die auf die Strukturelemente zugreifen.

Um es flexibel zu halten, werden diese Strukturen als Vorlagenparameter definiert.

Hier ist der Code:

/* 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; 
}; 

das Verwenden Sie die Eigenschaften wie folgt zugreifen können:

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; 

Natürlich können Sie andere Bedürfnisse haben für Struktur Ihres Diagramms, aber Modifikation des Codes oben sollte sei ziemlich einfach.

Answer 5

Wie wäre es mit gebündelten Eigenschaften?

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

[...] 

und so weiter.

Ich benutze BGL viel und die Arbeit mit gebündelten Eigenschaften ist wirklich einfach (see the docs).

Die andere Art der Vertex-Eigenschaft, die ich sehr oft verwende, sind externe Eigenschaften. Sie können std::vectors der entsprechenden Größe deklarieren und sie als Eigenschaften meistens und in den meisten Algorithmen verwenden.