Boost Graph Graph Notlarım

Boost Graph - BGL

Detaylı örnekler burada.
adjecency_list
Include dosyaları şöyle tanımlanırlar. İlk template parametresi edge'lerin nasıl tutulacağını, ikinci template parametresi ise vertex'lerin nasıl tutulacağını belirtir. Örnekte edge'ler list ile vertex'ler ise vector ile tutuluyor.

#include <boost/graph/adjacency_list.hpp>

using namespace boost;

typedef boost::adjacency_list< listS, vecS, directedS > ListGraph;

Bir başka örnek edge ve vertex'ler vector olarak tutuluyor.

typedef boost::adjacency_list<boost::vecS,
                              boost::vecS,
                              boost::undirectedS> Graph;

vecS kullanılıyorsa vertex_descriptor vector'e verilen indeks olarak düşünülebilir. Eğer listS kullanılıyorsa vertex_descriptor list yapısına pointer olarak düşünülmeli.

Bu yapı için kendi tanımladığımı vertex ve edge struct'ları da kullanabiliriz. Yani şöyle olabilirdi. Buradaki örnekte edge'ler vector ile, vertex'ler ise list ile tutuluyor.

typedef boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS, 
MyVertexProperties_t, MyEdgeProperties_t> ListGraph;

adjaceny_matrix
Şöyle tanımlanır.

#include <boost/graph/adjacency_matrix.hpp>

using namespace boost;

typedef boost::adjacency_matrix< directedS > MatrixGraph;

BGL C tabanlı metodlar sunar. Tam anlamıyla nesneye yönelimli değildir.

labeled_graph
Şu satırlar dahil edilir.

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

Şöyle tanımlanır.

struct NodeInfo{int id;};
struct EdgeInfo{};

typedef boost::labeled_graph< boost::adjacency_list<
    boost::vecS, boost::vecS, boost::undirectedS, NodeInfo, EdgeInfo>,
    std::string> Graph;

Vertex şöyle eklenir.

Graph g;
add_vertex("A", NodeInfo(), g);

Edge şöyle eklenir

add_edge_by_label("A", "B", EdgeInfo(), g);

property_map
Edge veya vertex'lerin belli alanlarına erişmek için kullanılır.

Vertex'lere erişmek için şöyle tanımlanır.

typedef boost::adjacency_list<boost::vecS,
                              boost::vecS,
                              boost::undirectedS> Graph;

typedef boost::property_map< Graph, boost::vertex_index_t>::type VertexIndexMap;

Daha sonra map nesnesi yaratılır.

Graph g;
// ... 
// load graph
// ...
VertexIndexMap v_index = get(boost::vertex_index, g);

Tüm vertex değerlerini dolduracağımız bir bellek alanı yaratılır.

std::vector< double > vertex_property_vec(boost::num_vertices(g), 0.0);

Tüm değerler bellek alanına şöyle doldurulur.

boost::iterator_property_map< std::vector< double >::iterator, VertexIndexMap >
          vertex_property_map(vertex_property_vec.begin(), v_index);

Edgelere erişmek için şöyle kullanılır.

struct edge_t {
    double capacity;
    float cost;
    float residual_capacity;
    traits::edge_descriptor reversed_edge;
};
struct node_t {
    std::string name;
    boost::default_color_type color;
    traits::edge_descriptor predecessor;
};

typedef adjacency_list < listS, vecS, directedS, node_t, edge_t > Graph;

Graph g;
property_map<Graph,double edge_t::*>::type capacity = get(&edge_t::capacity, g);

add_edge metodu
İki düğümü birleştirir.

ListGraph lg; 
add_edge (0, 1, lg); 

num_vertices metodu
Düğüm sayısını verir. List graph nesnesini matrix graph nesnesine kopyalamak için düğüm sayısını bilmek gerekir.

MatrixGraph mg( num_vertices(lg));
boost::copy_graph(lg, mg);

Bir başka örnek

std::vector<Vertex_t> p( boost::num_vertices(m_g));

brandes_betweenness_centrality
Örnek burada.

depth_first_search metodu
İmzası şöyle

template <class Graph, class class P, class T, class R>
void depth_first_search(Graph& G,
                        const bgl_named_params<P, T, R>& params);

depth_first_visit metodu
İmzası şöyle

template <class IncidenceGraph, class DFSVisitor, class ColorMap>
void depth_first_visit(IncidenceGraph& g,
  typename graph_traits<IncidenceGraph>::vertex_descriptor s, 
  DFSVisitor& vis, ColorMap color);

Bir visitor tanımlarız. Şöyle yaparız.

class receiver_visitor : public boost::default_dfs_visitor
{
  public:
    receiver_visitor(std::vector<Vertex>& r)
      : recv(r)
    {}

    void discover_vertex(Vertex v, Graph const& g) const
    {
      std::cout << "Visit: " << v << std::endl;
      if (g[v].sch_color) {
        recv.push_back(g[v].sch_color);
      }
    }

    std::vector<Vertex>& recv;
};

Bir color map tanımlarız. Şöyle yaparız.

std::vector<boost::default_color_type> color_map(boost::num_vertices(g));

Şöyle yaparız.

boost::depth_first_visit(g,
                         src,
                         vis,
 boost::make_iterator_property_map(color_map.begin(),
                                   boost::get(boost::vertex_index,g),
                                   color_map[0]));

dijkstra_shortest_paths metodu
Tüm örnek burada. Şu include dosyası gerekir.

#include <boost/graph/dijkstra_shortest_paths.hpp>

Edge ve vertex için struct tanımlarız.

struct EdgeProperties_t {
   EdgeProperties_t( float fWeight ) : m_fWeight( fWeight ) { }
   EdgeProperties_t( ) : m_fWeight( static_cast<float>(0.0) ) { }
   float m_fWeight;
};
struct VertexProperties_t {
   std::string m_sName;
};

vertex_descriptor ve vertex_iterator için typedef tanımlamak ta gerekir.

typedef boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS, 
VertexProperties_t, EdgeProperties_t> Graph_t;
typedef boost::graph_traits<Graph_t>::vertex_descriptor Vertex_t;
typedef boost::graph_traits<Graph_t>::vertex_iterator VertexIterator_t;

Daha sonra bir Graph nesnesi tanımlanır.

Graph_t myGraph;

Graph nesnesi doldurulduktan sonra iterator ile ilk vertex şöyle alınır.

VertexIterator_t departIter = vertices(myGraph).first; //first vertex in you graph
Vertex_t s = *departIter;

Daha sonra distance ve path için iki vector oluştururuz. dijkstra_shortest_paths metodunu çağırırken ilk parametre graph nesnesi, ikinci parametre başlangıç düğümüdür. Üçüncü paramtrenin ne olduğunu ben de anlamadım.

std::vector<Vertex_t> p( boost::num_vertices(myGraph));
std::vector<float> d( boost::num_vertices(myGraph));

boost::dijkstra_shortest_paths(myGraph, s,
 boost::weight_map(get(&VertexProperties_t::m_sName, myGraph))
                                   .predecessor_map(&p[0])
                                   .distance_map(&d[0]));