4

ブースト グラフ クラスを試してみました。このために、以下に示すように簡単なサンプルを作成しました。深さ優先検索アルゴリズムを使用してグラフをトラバースするとき、追加しなかったノード。コードは次のとおりです。

#include <boost\graph\adjacency_list.hpp>
#include <boost\graph\depth_first_search.hpp>
#include <iostream>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> GraphType;
typedef boost::graph_traits<GraphType>::vertex_descriptor VertexType;

class VertexVisitor : public boost::default_dfs_visitor
{
public:
  void discover_vertex(VertexType v, GraphType g)
  {
    std::cout << v << std::endl;
  }
};

int main() 
{ 
  GraphType g;
  boost::add_edge(1,2,g);
  boost::add_edge(1,3,g);
  boost::add_edge(2,3,g);
  boost::add_edge(1,4,g);
  boost::add_edge(4,5,g);

  VertexVisitor vis;
  boost::depth_first_search(g, boost::visitor(vis));

  return 0;
}

これの出力は

0
1
2
3
4
5

しかし、0 はどこから来ているのですか? これはある種のダミーノードですか？しかし、もしそうなら、なぜそれはトラバーサルで訪問され、どうすれば望ましい動作を達成できますか?

編集 1: PlasmaHH が提案したことを試し、見つけたブースト コードを使用してデバッグした後、boost::add_edge はグラフの頂点構造のサイズ変更を呼び出します。したがって、相互に接続されていませんが、より多くの要素が追加され、検索アルゴリズムによってアクセスされます。ところで：ブースト1.47を使用しています。

編集 2: DFS は接続されていなくても、グラフ内のすべてのノードをトラバースするため、アルゴリズムとはdepth_first_search異なる動作 (ネイティブの違いを除く)が示されています。breadth_first_searchこのノードに接続されているあるノードから別のノードへのパスを見つけたいだけなので、その利点はわかりませんが、わかりました。前に述べたように、私の問題の解決策は、すべてのサブグラフをトラバースしない BFS アルゴリズムを使用することでした。興味のある方のために、ちょっとした例を追加します。

#include <boost\graph\adjacency_list.hpp>
#include <boost\graph\depth_first_search.hpp>
#include <boost\graph\breadth_first_search.hpp>
#include <iostream>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS>  GraphType;
typedef boost::graph_traits<GraphType>::vertex_descriptor VertexType;

class DFSVertexVisitor : public boost::default_dfs_visitor
{
public:
  void discover_vertex(GraphType::vertex_descriptor v, GraphType g)
  {
    std::cout << v << std::endl;
  }
};

class BFSVertexVisitor : public boost::default_bfs_visitor
{
public:
  void discover_vertex(GraphType::vertex_descriptor v, GraphType g)
  {
    std::cout << v << std::endl;
  }
};


int main(int argc, char *argv[])
{
  GraphType g;
  boost::add_edge(1, 2, g);
  boost::add_edge(2, 3, g);
  boost::add_edge(1, 3, g);
  boost::add_edge(4, 5, g);

  std::cout << "Performing BFS" << std::endl;
  BFSVertexVisitor bfsVisitor;
  boost::breadth_first_search(g, boost::vertex(1, g), boost::visitor(bfsVisitor));

  std::cout << "Performing DFS" << std::endl;
  DFSVertexVisitor dfsVisitor;
  boost::depth_first_search(g, boost::visitor(dfsVisitor).root_vertex(1));

  return 0;
}

ノード 4 および 5 は、ノード 1、2、および 3 に接続されていないことに注意してください。

出力：

Performing BFS
1
2
3
Performing DFS
1
2
3
0
4
5

EDIT 3:もう一度考え直す必要がありました。私が接続した番号add_edgeは、ノード自体ではなく、nm が提案したインデックスのみです。したがって、頂点の1つを削除しても期待どおりに機能しないため、エッジを追加するだけでは最終的な解決策ではないと思います。

4

1 に答える 1

2

ドキュメントから：

グラフの VertexList が vecS の場合、グラフには vertex_index_t プロパティのプロパティ マップを介してアクセスされる組み込みの頂点インデックスがあります。インデックスは [0, num_vertices(g)) の範囲にあり、連続しています。頂点が削除されると、これらのプロパティが保持されるようにインデックスが調整されます。

vertex_descriptorドキュメントには、それが単なるインデックスであると明示的に書かれているとは思いません。ドキュメントの例のいくつかは、これが実際に当てはまることを示唆しています。他の例vertex_descriptorは、ブラック ボックスとして扱います。

于 2012-07-13T15:01:46.647 に答える