बूस्ट में वर्टेक्स गुणों को संशोधित करना :: ग्राफ

Question

मैं कुछ जानकारी संग्रहीत करने के लिए boost :: graph का उपयोग करने का तरीका जानने का प्रयास कर रहा हूं। हालांकि, ऐसी जानकारी है जो मैं प्रत्येक चरम पर बंधना चाहता हूं। लाइब्रेरी के लिए प्रलेखन में घूरते हुए या तो (ए) बुरी तरह से लिखित दस्तावेज, या (बी), मैं स्पष्ट रूप से सी ++ में उतना अच्छा नहीं हूं जितना मैंने सोचा था। दो चुनें।

मैं एक साधारण उदाहरण उपयोग की तलाश में हूं।

Answer 1

मैं बूस्ट.ग्राफ को बहुत अच्छा दस्तावेज मानता हूं, लेकिन इस मामले पर शुरुआती लोगों के लिए वास्तव में नहीं। तो यहां एक उदाहरण दिया गया है कि मुझे आशा है कि यह काफी आसान है!

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

नीचे कोड है जो मैं कुछ गुणों को ऊर्ध्वाधर, किनारों और ग्राफों से जोड़ता था। ध्यान दें कि वर्टेक्स नाम और ग्राफ़ नाम पूर्वनिर्धारित गुण हैं (पूरी सूची के लिए boost/Properties.hpp देखें) ताकि vertex_name_t और graph_name_t पहले ही परिभाषित किए जा सकें। हालांकि, 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

मैंने उदाहरणों को बहुत उपयोगी पाया। विंडोज़ पर यह आपके \ प्रोग्राम फ़ाइलें \ boost \ boost_1_38 \ libs \ graph \ example निर्देशिका में होगा।

kevin_bacon2.cpp अभिनेताओं के नामों को स्टोर करने के लिए वर्टेक्स गुणों का उपयोग करता है।

आपकी कशेरुक और किनारों के गुण नियमित structs या कक्षाओं में संग्रहीत किया जा सकता है।

Answer 4

मुझे बूस्ट :: ग्राफ़ के नेस्टेड-टेम्पलेट प्रॉपर्टी दृष्टिकोण पसंद नहीं है, इसलिए मैंने सबकुछ के चारों ओर एक छोटा सा रैपर लिखा, जो मूल रूप से किसी भी संरचना/वर्ग को वर्टेक्स/एज प्रॉपर्टी के रूप में रखने की अनुमति देता है। कोई संरचना सदस्यों तक पहुंचने वाले गुणों तक पहुंच सकता है।

इसे लचीला रखने के लिए इन structs को टेम्पलेट पैरामीटर के रूप में परिभाषित किया गया है।

यहाँ कोड:

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

[...] 

और इतने पर।

मैं एक बहुत बीजीएल का उपयोग करें और बंडल गुणों के साथ काम कर वास्तव में सरल है (see the docs)।

अन्य प्रकार की वर्टेक्स संपत्ति जिसका मैं अक्सर उपयोग करता हूं बाहरी गुण होते हैं। आप उपयुक्त आकार के std::vectors घोषित करने और उन्हें गुण समय की सबसे और एल्गोरिदम के अधिकांश में के रूप में उपयोग कर सकते हैं।