graph vertices metodu

Giriş
Tüm vertex'leri dolaşmamızı sağlayan bir iterator çifti döner. first iterator ilk vertex'e second iterator ise son vertex'e işaret eder.

Bu metod ile edges metodu kardeştir.
BGL_FORALL_VERTICES macrosu ile aynıdır.

Bu metod vertex_iterator tipinden iterator döner. İki iterator nesnesini dolaşmak için boost::make_iterator_range() kullanılabilir.

vertices - graph
Örnek
Elimizde vector tabanlı bir graph olsun

struct VertexProps { int id; default_color_type color; };

using Graph = adjacency_list<vecS, vecS, directedS, VertexProps>;

Graph g = ...;

Şöyle yaparız.

for (auto vd : boost::make_iterator_range(vertices(g))) {
    std::cout << "Vertex descriptor #" << vd 
         << " degree:" << degree(vd, g)
         << " id:"     << g[vd].id
         << " color:"  << g[vd].color
         << "\n";
}

Örnek
Her graph nesnesinin vertex'i anlamlı bir sayı vermeyebilir. std::vector tabanlı graph'larda sayıyı okuması kolaydır. Şöyle yaparız.

typedef boost::adjacency_list<> Graph;
typedef Graph::vertex_iterator Vit;
Graph g(10);

add_edge(2,5,g);
add_edge(5,3,g);
add_edge(3,8,g);

Vit begin, end;
boost::tie(begin, end) = vertices(g);

for (Vit it = begin; it != end; ++it) {
  unsigned edges = out_degree(*it, g);
  if (edges)
    std::cout << "vertex #" << *it << " has " << edges << " outgoing edge(s)\n";
  }
}

Çıktı olarak şunu alırız.

vertex #2 has 1 outgoing edge(s)
vertex #3 has 1 outgoing edge(s)
vertex #5 has 1 outgoing edge(s)

Eğer graph std::set tabanlı ise çıktıyı okumak zordur. edge eklemek için std::set'i std::vector'e çevirerek kullanırız. Şöyle yaparız.

typedef boost::adjacency_list<boost::setS, boost::listS/*, boost::undirectedS*/> Graph;
typedef Graph::vertex_iterator Vit;
Graph g(10);

Vit begin, end;
boost::tie(begin, end) = vertices(g);

{
  std::vector<Graph::vertex_descriptor> vindex(begin, end);
  add_edge(vindex[2], vindex[5], g);
  add_edge(vindex[5], vindex[3], g);
  add_edge(vindex[3], vindex[8], g);
}

for (Vit it = begin; it != end; ++it) {
  unsigned edges = out_degree(*it, g);
  if (edges)
    std::cout << "vertex #" << *it << " has " << edges << " outgoing edge(s)\n";
}

Çıktı olarak şunu alırız.

vertex #0x994d00 has 1 outgoing edge(s)
vertex #0x994d70 has 1 outgoing edge(s)
vertex #0x994e50 has 1 outgoing edge(s)

Bu durumda vertex'lere property ekleriz ve yine aynı şekilde edge eklemek için std::set'i std::vector'e çevirerek kullanırız.

struct VertexProperties {
    std::string name;
    VertexProperties(std::string name) : name(name) {}
};

typedef boost::adjacency_list<boost::setS, boost::listS, boost::directedS,
  VertexProperties> Graph;
typedef Graph::vertex_iterator Vit;
Graph g;

add_vertex(VertexProperties ("zero"), g);
add_vertex(VertexProperties ("one"), g);
add_vertex(VertexProperties ("two"), g);
add_vertex(VertexProperties ("three"), g);
add_vertex(VertexProperties ("four"), g);
add_vertex(VertexProperties ("five"), g);
add_vertex(VertexProperties ("six"), g);
add_vertex(VertexProperties ("seven"), g);
add_vertex(VertexProperties ("eight"), g);
add_vertex(VertexProperties ("nine"), g);

Vit begin, end;
boost::tie(begin, end) = vertices(g);

{
  std::vector<Graph::vertex_descriptor> vindex(begin, end);

  add_edge(vindex[2], vindex[5], g);
  add_edge(vindex[5], vindex[3], g);
  add_edge(vindex[3], vindex[8], g);
}

for (Vit it = begin; it != end; ++it) {
  unsigned edges = out_degree(*it, g);
  if (edges)
    std::cout << "vertex '" << g[*it].name << "' has " << edges << " outgoing edge(s)\n";
  }
}

Çıktı olarak şunu alırız.

vertex 'two' has 1 outgoing edge(s)
vertex 'three' has 1 outgoing edge(s)
vertex 'five' has 1 outgoing edge(s)

Örnek
Şöyle yaparız.Burada graph.m_vertices ile dokümante edilmemiş bir alana erişiyoruz. Bu alan graph vecS olarak tanımlı ise vector tipendendir.

VertexIterator vi, vi_end;
for (boost::tie(vi, vi_end) = vertices(graph); vi != vi_end; ++vi){
  graph.m_vertices[*vi].m_out_edges.reserve(6);
}

Örnek
Elimizde şöyle bir graph olsun.

struct mytuple
{
  int e1;
  int e2;
  int s;

  bool operator==(const mytuple& a) const
  {
    return ((e1 == a.e1) && (e2 == a.e2) && (s == a.s));
  }
};

struct MyVertex {
  std::string comments;
  int field1;
  mytuple value;
  MyVertex(std::string comments = std::string()) : comments(comments) {}
};

struct MyEdge {
  std::string label;
  MyEdge(std::string label = std::string()) : label(label) {}
};


using MyTree = boost::adjacency_list<boost::vecS, boost::vecS,
 boost::bidirectionalS, MyVertex, MyEdge>;
using Vertex = boost::graph_traits<MyTree>::vertex_descriptor; // Define Vertex
using VertexItr = boost::graph_traits<MyTree>::vertex_iterator; //Vertex iterator
using Edge = std::pair<boost::graph_traits<MyTree>::edge_descriptor, bool>; //Edge
using EdgeItr = boost::graph_traits<MyTree>::edge_iterator; // Edge Iterator

Graph'ı dolduralım

MyTree mytree;

Vertex v1 = boost::add_vertex(mytree);
mytree[v1].value = {1, 1, 1};
mytree[v1].comments = "I am the one you seek";

Vertex v2 = boost::add_vertex(mytree);
mytree[v2].value = {2, 2, 2};

Vertex v3 = boost::add_vertex(mytree);
mytree[v3].value = {3, 3, 3};

Tüm vertex'leri dolaşarak eşitlik kontrolü yapmak için şöyle yaparız.

VertexItr findvertex(const MyTree& g, const mytuple& value){
  VertexItr vi, vi_end;
  for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
    if(g[*vi].value == value) return vi;
  }
  return vi_end;
}

Kullanmak için şöyle yaparız.

mytuple tuple = { 1,1,1};
const auto iter = findvertex(mytree, tuple);
const auto theEnd = boost::vertices(mytree).second;

Örnek - pair

Elimizde şöyle bir grap olsun

struct Vertex { int id; double data; };
struct Edge { float distance; };

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
  Vertex, Edge> Graph;

Vertex'lerin başını ve sonunu std::pair olarak almak için şöyle yaparız

// Iterate through the vertices and print them out
typedef boost::graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = boost::vertices(g); vp.first != vp.second; vp.first++)
{
  std::cout << g[*(vp.first)].id << " " << g[*(vp.first)].data << std::endl;
}

Her vertex'i yazdırınca çıktı olarak şunu alırız.

1 1.1
2 2.2
3 3.3
4 4.4

Örnek
Tüm vertex ve onların tüm komşularını dolaşmak için şöyle yaparız.

Graph g = ...;
Graph::vertex_iterator vertexIt, vertexEnd;

tie(vertexIt, vertexEnd) = vertices(g);

for (; vertexIt != vertexEnd; ++vertexIt) 
{
  Graph::adjacency_iterator neighbourIt, neighbourEnd;

  tie(neighbourIt, neighbourEnd) = adjacent_vertices(*vertexIt, inputgraph);

  for (; neighbourIt != neighbourEnd; ++neighbourIt){
    ...
  }
}

Örnek
vertices() çağrısının döndürdüğü vertex_iterator ile adjacent_vertices() çağrısının döndürdüğü adjacency_iterator tipleri birbirlerinden farklıdır. Şu kod derlenmez.
Elimizde bir grap olsun ve onu dolduralım.

typedef adjacency_list<vecS, vecS, directedS> digraph;
typedef graph_traits<digraph>::vertex_iterator vertex_it;
typedef graph_traits<digraph>::adjacency_iterator adj_it;
graph_traits<digraph>::vertex_descriptor a, b, c;

digraph g;
a = add_vertex(g);
b = add_vertex(g);
c = add_vertex(g);
add_edge(a, b, g);
add_edge(b, c, g);
add_edge(c, a, g);

Daha sonra iki iterator'ü karıştırmaya çalışalım. Kod derlenmez.

vector<vertex_it> stack;

vertex_it v_beg,v_end;
tie(v_beg,v_end) = vertices(g);
stack.push_back(v_beg);

adj_it adj_beg,adj_end;
tie(adj_beg, adj_end) = adjacent_vertices(*v_beg, g);
for (; adj_beg != adj_end; adj_beg++)
  stack.push_back(adj_beg); //error here

Örnek
Tüm vertex'leri rastgele dolaşmak isteyelim. Önce vertex'lerin başlangıcını  saklarız.

std::pair<vertex_iter, vertex_iter> vp;
vp = vertices(g);

Daha sonra sayıları rastgele karıştırırız.

// initialize pseudo random number generator
std::srand(unsigned (std::time(0)));

// create offset vector
std::vector<int> myvector;
for (int i=0; i<3; ++i) {
  myvector.push_back(i);
}

// using myrandom to shuffle offset vector
std::random_shuffle(myvector.begin(), myvector.end(), myrandom);

Rastgele dolaşmak için şöyle yaparız.

vertex_iter dummy_iter;
// Looping on a shuffled vector, values should be 0..N-1
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
{
  dummy_iter = vp.first + *it;
  Vertex* v = *dummy_iter;
  ...
}