3

ブースト グラフで、整数または文字の頂点を持つグラフを作成する方法を知っています (以下のコメント付きのコードを参照)。問題は、このコードを文字列の頂点で動作するように書き直す方法です。 

#include <string>
#include <boost/graph/adjacency_list.hpp>

using namespace boost;

int main (int argc, char **argv)
{
        typedef adjacency_list <vecS, vecS, undirectedS> vector_graph_t;

        //works
        //typedef std::pair <int, int> E;
        //E edges[] = { E (2, 5), E (5, 3), E (3, 1), E (5, 1)};
        //vector_graph_t g (&edges[0],&edges[0] + sizeof(edges) / sizeof(E), 4);

        //works
        //typedef std::pair <char, char> E;
        //E edges[] = { E ('a', 'b'), E ('a', 'c'), E ('x', 'a'), E ('b', 'x')};
        //vector_graph_t g (&edges[0],&edges[0] + sizeof(edges) / sizeof(E), 4);

        //does not work
        typedef std::pair <std::string, std::string> E;
        E edges[] = { E ("aaa", "bbb"), E ("bbb", "ccc"), E ("aaa", "xxx"), E ("bbb", "ccc")};
        vector_graph_t g (&edges[0],&edges[0] + sizeof(edges) / sizeof(E), 4); 

        return 0;
}

上記のプログラムをコンパイルすると、次のエラーが発生します。

/usr/local/include/boost/graph/detail/adjacency_list.hpp:2076: error: no matching function for call to ‘add_edge(std::basic_string<char, std::char_traits<char>, std::allocator<char> >&, std::basic_string<char, std::char_traits<char>, std::allocator<char> >&, boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>&)’
/usr/local/include/boost/graph/detail/adjacency_list.hpp:1030: note: candidates are: std::pair<typename Config::edge_descriptor, bool> boost::add_edge(typename Config::vertex_descriptor, typename Config::vertex_descriptor, boost::undirected_graph_helper<C>&) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>::config]
4

1 に答える 1

5

この2つのタイプは頂点インデックスとして使用されるため、intとcharで動作すると思います。ただし、コメント付きのコードでは、頂点 8 から始まるエッジを 4 つの頂点を含むグラフに追加します...

明示的な方法で正しい結果が得られる場合があります。頂点プロパティをグラフ自体に格納する場合は、プロパティを宣言してグラフ タイプにリンクする必要があります。また、インデックスを使用して頂点にアクセスする必要があります。これは、プロパティから直接行うことはできません (異なる頂点が同じプロパティを持つ場合があります)。

#include <string>
#include <map>
#include <boost/graph/adjacency_list.hpp>

using namespace boost;

int main (int argc, char **argv)
{
  typedef property<vertex_name_t, std::string> VertexProperty;

  typedef adjacency_list <vecS, vecS, undirectedS, VertexProperty> vector_graph_t;

  typedef std::pair <std::string, std::string> E;
  E edges[] = { E ("aaa", "bbb"), E ("bbb", "ccc"), E ("aaa", "xxx"), E ("bbb", "ccc")};

  const char* vertices[] = {"aaa", "bbb", "ccc", "xxx"};
  std::map<std::string, vector_graph_t::vertex_descriptor> indexes;

  const int nb_vertices = sizeof(vertices)/sizeof(vertices[0]);

  // creates a graph with 4 vertices
  vector_graph_t g (nb_vertices); 

  // fills the property 'vertex_name_t' of the vertices
  for(int i = 0; i < nb_vertices; i++)
  {
    boost::put(vertex_name_t(), g, i, vertices[i]); // set the property of a vertex
    indexes[vertices[i]] = boost::vertex(i, g);     // retrives the associated vertex descriptor
  }

  // adds the edges
  // indexes[edges[0].first] maps "aaa" to the associated vertex index
  for(int i = 0; i < sizeof(edges)/sizeof(edges[0]); i++)
  {
    boost::add_edge(indexes[edges[i].first], indexes[edges[i].second], g);
  }

  return 0;
}
于 2013-09-16T09:54:10.547 に答える