graph kruskal_minimum_spanning_tree

Giriş
Kruskal algoritması "Disjoint set" ile gerçekleştirilebilir. Açıklaması şöyle

Path compression and other optimizations like union-by-rank should be applied any time you call the find operation on your disjoint-set forest.

One way to see this: from the perspective of Kruskal's algorithm, you just need to be able to call find and union and have them work correctly. You shouldn't need to worry about the details of how you're making find and union work correctly, just that they do. It's the responsibility of the disjoint-set forest to ensure that everything runs quickly, and so the calls to find are where you'll see the compression occurring.

İmzası şöyle

template <class Graph, class OutputIterator, class P, class T, class R>
OutputIterator kruskal_minimum_spanning_tree(
  Graph& g, 
  OutputIterator tree_edges, 
  const bgl_named_params<P, T, R>& params = all defaults
);

Örnek
Bir graph'ın weight alanlarına bakarak çalışır. Dolayısıyla weight map verilmesi gerekir. Şöyle yaparız

typedef adjacency_list<vecS, vecS, undirectedS, 
                       property<vertex_name_t,char>,
                       property<edge_weight_t,float>
                      > InternalPropGraph;


vector<edge_t> mst;
kruskal_minimum_spanning_tree(g, std::back_inserter(mst), 
                        weight_map( get(&Edge::weight, g) );

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;
  ...
}