ブースト::グラフの頂点プロパティを変更する

Question

私はいくつかの情報を格納するためにboost :: graphの使い方を理解しようとしています。しかし、各頂点に結びつけたい情報があります。ライブラリのドキュメンテーションを見ると、（a）ひどく書かれたドキュメンテーションか、（b）明らかに私が思っていたほどC++に劣っていることが分かります。 2つを選ぶ。

私は簡単な使用例を探しています。

Answer 1

私はBoost.Graphが非常に優れたドキュメントを持っていると考えていますが、初心者のためのものではありません。だからここでは、私は十分に簡単であることを望む例に行く！

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

以下は、頂点、エッジ、グラフにいくつかのプロパティを付けるために使用するコードです。頂点名とグラフ名は、vertex_name_tとgraph_name_tがすでに定義されているように、事前定義されたプロパティ（完全なリストについてはboost/properties.hppを参照）であることに注意してください。しかし、vertex_location_t,edge_length_t、およびgraph_notes_tは私自身のプロパティであり、定義が必要です。私はさまざまな例とドキュメントからこのコードをまとめましたが、正確にはBOOST_INSTALL_PROPERTYの内容はわかりませんが、コードは正常に動作しているようです。

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

この例は非常に便利です。ウィンドウの\ Program Files \ boost \ boost_1_38 \ libs \ graph \ exampleディレクトリにあります。

kevin_bacon2.cppは、アクターの名前を格納するために頂点プロパティを使用します。

頂点とエッジのプロパティは、通常の構造体またはクラスに格納できます。

Answer 4

boost :: graphのネストテンプレートプロパティのアプローチが気に入らないので、基本的に任意の構造体/クラスを頂点/エッジプロパティとして配置することができるすべての小さなラッパーを作成しました。構造体メンバにアクセスするプロパティにアクセスできます。

柔軟性を保つために、これらの構造体はテンプレートパラメータとして定義されています。ここで

コード：

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

あなたはこのようにプロパティにアクセスすることができ、これを使用する：あなたは、グラフの構造のため、他のニーズを持って

もちろん

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; 

が、コードの変更は、上記のはずかなり簡単です。

Answer 5

バンドルプロパティを使用するとどうなりますか？

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

[...] 

などとなる。

私はBGLをたくさん使用し、バンドルされたプロパティで作業するのは本当に簡単です（see the docs）。

私が頻繁に使用する他のタイプの頂点プロパティは外部プロパティです。適切なサイズのstd::vectorsを宣言し、それらをプロパティのほとんどの時間とほとんどのアルゴリズムで使用できます。