Sửa đổi các thuộc tính đỉnh trong Boost :: Graph

Question

Tôi đang cố gắng tìm hiểu cách sử dụng boost :: graph để lưu trữ một số thông tin. Tuy nhiên, có thông tin tôi muốn gắn với mỗi đỉnh. Nhìn chằm chằm vào tài liệu cho thư viện cho thấy một trong hai (a) tài liệu viết sai, hoặc (b), tôi rõ ràng là không tốt ở C++ như tôi nghĩ. Chọn hai.

Tôi đang tìm kiếm một ví dụ sử dụng đơn giản.

Answer 1

Tôi xem Boost.Graph để có tài liệu rất tốt, nhưng không thực sự cho người mới bắt đầu về vấn đề này. Vì vậy, ở đây đi một ví dụ mà tôi hy vọng là đơn giản, đủ!

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

Dưới đây là mã tôi đã sử dụng để đính kèm một số thuộc tính vào đỉnh, cạnh và biểu đồ. Lưu ý rằng tên đỉnh và tên biểu đồ là các thuộc tính được xác định trước (xem boost/properties.hpp để có danh sách đầy đủ) để vertex_name_t và graph_name_t đã được xác định. Tuy nhiên, vertex_location_t, edge_length_t và graph_notes_t là các thuộc tính của riêng tôi và do đó cần định nghĩa. Tôi đã trộn lẫn mã này với các ví dụ và tài liệu khác nhau và tôi không chắc chắn chính xác những gì BOOST_INSTALL_PROPERTY làm, nhưng mã dường như hoạt động tốt.

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

Tôi thấy các ví dụ khá hữu ích. Trên cửa sổ, nó sẽ nằm trong thư mục \ Program Files \ boost \ boost_1_38 \ libs \ graph \ example của bạn.

kevin_bacon2.cpp sử dụng thuộc tính đỉnh để lưu trữ tên của diễn viên.

Thuộc tính đỉnh và cạnh của bạn có thể được lưu trữ trong cấu trúc hoặc lớp thông thường.

Answer 4

Tôi không thích cách tiếp cận thuộc tính lồng nhau của biểu đồ tăng :: vì vậy tôi đã viết một gói nhỏ xung quanh mọi thứ, về cơ bản cho phép đặt bất kỳ cấu trúc/lớp nào làm thuộc tính đỉnh/cạnh. Người ta có thể truy cập các thuộc tính truy cập vào các thành viên struct.

Để giữ cho nó linh hoạt, các cấu trúc này được định nghĩa là tham số mẫu.

Ở đây 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; 
}; 

Sử dụng này, bạn có thể truy cập các thuộc tính như thế này:

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; 

Tất nhiên bạn có thể có những nhu cầu khác cho cấu trúc của biểu đồ của bạn, nhưng việc sửa đổi mã nên trên khá dễ dàng.

Answer 5

Điều gì về việc sử dụng các thuộc tính đi kèm?

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

[...] 

v.v.

Tôi sử dụng BGL rất nhiều và làm việc với các thuộc tính đi kèm thực sự đơn giản (see the docs).

Loại thuộc tính đỉnh khác mà tôi thường sử dụng là thuộc tính bên ngoài. Bạn có thể khai báo std::vectors kích thước phù hợp và sử dụng chúng làm thuộc tính phần lớn thời gian và trong hầu hết các thuật toán.