38

boost::graph を使用して情報を保存する方法を理解しようとしています。ただし、各頂点に関連付けたい情報があります。ライブラリのドキュメントをじっと見ると、(a)ドキュメントの書き方が悪いか、(b)思ったほど C++ が得意ではないことがわかります。2つ選んでください。

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

4

5 に答える 5

78

バンドルされたプロパティは簡単に使用できます。

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

[...]

等々。

ドキュメントも参照してください。

非常に便利な頂点プロパティのもう 1 つのタイプは、外部プロパティです。std::vectors適切なサイズを宣言して、プロパティとして使用できます。

于 2010-03-16T20:19:13.323 に答える
16

私は、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;

もちろん、グラフの構造に他のニーズがあるかもしれませんが、上記のコードの変更は非常に簡単です。

于 2009-06-04T12:18:48.907 に答える
4

以下は、いくつかのプロパティを頂点、エッジ、およびグラフにアタッチするために使用したコードです。頂点名とグラフ名は定義済みのプロパティ (完全なリストについては 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;
于 2009-05-12T21:36:41.037 に答える
1

例はかなり役に立ちました。Windows では、\Program Files\boost\boost_1_38\libs\graph\example ディレクトリにあります。

kevin_bacon2.cpp は頂点プロパティを使用してアクタの名前を保存します。

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

于 2009-06-02T21:43:56.693 に答える
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;
}
于 2009-03-23T06:08:32.173 に答える