30 Ocak 2018 Salı

graph adjacency_list Sınıfı

Giriş
Şu satırı dahil ederiz.
#include <boost/graph/adjacency_list.hpp>
İsim alanı da dahil edilir.
using namespace boost;
Adjacency List ve Adjacency Matrix'in Farkı Nedir?
Klasik Adjacency List şöyledir. 1 numaralı düğüm 2,3,4,5 numaralı düğümlere bağlıdır. Yani düğüm komşularını liste olarak sakalr.
2 3 4 5
1 4
1 5 4
1 2 5 3
1 3 4
Klasik Adjaceny Matrix ise şöyledir. Yani liste yerine matris kullanılır.
01111
10010
10011
11101
10110
Bu sınıf esas olarak vertex'leri saklar. Her vertex ise kendi komşu vertex'lerini saklar. Böylece bir graph oluşur. Bu sınıf VertexAndEdgeListGraph kavramını geçekleştirir.



Template Parametreleri
1. İlk parametre edge'lerin nasıl tutulacağını belirtir.
  listS, vectorS, setS olabilir.

vecS
boost::vecS kullanılıyorsa vertex_descriptor vector'e verilen indeks olarak düşünülebilir.

listS
Eğer   boost::listS kullanılıyorsa vertex_descriptor list yapısına pointer olarak düşünülmeli.

setS
Eğer boost::setS kullanılıyorsa artık vector descriptor ve vector index ortada olmadığı için bu değerleri saklamak gerekebilir. Şöyle yaparız.
using graph = boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, 
    boost::property<boost::vertex_index_t, size_t> >;
Böylece vertex eklesek bile bu değerlere erişebiliriz.
auto A = add_vertex(3, g);
auto B = add_vertex(44, g);
auto C = add_vertex(1024102400, g);
2. vertex'lerin nasıl tutulacağını belirtir.
  listS, vectorS, setS olabilir. Açıklaması şöyle
"adjacency list" normally implies a representation as an array or a linked-list rather than a HashSet: in other words, adjacency lists are optimized for iterating over a vertex's neighbors rather than for querying if two vertices are neighbors. 
3. Yönü belirtir.
  directedS, undirectedS, bidirectionalS olabilir.

4. vertex property map'i belirtir.

5. edge property map'i belirtir.

6. graph property map'i belirtir.

7. edgelist diye geçiyor ama anlamadım.

Reason for not allowing random access to the vector of edges in adjacency lists
Açıklaması şöyle
Adjacency lists store a list of adjacencies.

That is, per vertex, it stores a list of adjacent vertices.

That means that vertices can be stored in a single container, but each vertex contains its own (separate) container of adjacencies ("other vertex references").

This should explain: there is no such thing as "the edge container", making it impossible to directly address the edges by index or as a single adjacent container.

Note there are other graph models (e.g. EdgeList concept, as modeled by edge_list)

Bazı Tanımlama Örnekleri - Bundled Properties yani  Kendi Yapılarım
Vertex için property tanımlayan bir sınıf şöyledir.
struct VertexInfo {
  std::string stateName;
};

typedef adjacency_list<...,...,..., VertexInfo> Graph;
Vertex ve Edge için property tanımlayan bir sınıf şöyledir.
struct VertexInfo {...};
struct EdgeInfo   {...};

typedef adjacency_list<...,...,...,VertexInfo, EdgeInfo> Graph;
graph property ve edgelist tanımlayan bir sınıf şöyledir.
typedef adjacency_list<setS, vecS, directedS, 
  property<vertex_name_t, std::string>,
  property<edge_capacity_t, double,
  property<edge_residual_capacity_t, double,
  property<edge_reverse_t, Traits::edge_descriptor> > >
> Graph;
Bazı Tanımlama Örnekleri - Named Properties yani Hazır Yapılar
Bu tanımlama yöntemini tercih etmemek lazım.
Şöyledir
vertex
vertex_index_t
vertex_name_t
edge
edge_capacity_t
edge_weight_t

Hazır property'leri kullanmak istersek boost::noproperty veya boost::property<...,...> şeklide kullanırız.

Şöyle yaparız
typedef boost::adjacency_list<
   ...,
   ...,
   ...,
   boost::property<vertex_index_t, std::size_t>,
   boost::no_property
> Graph;
Şöyle yaparız.
typedef boost::adjacency_list<
   ...,
   ...,
   ...,
   boost::no_property
   boost::property<edge_weight_t, float>,> Graph;
Şöyle yaparız.
typedef boost::adjacency_list<
   ...,
   ...,
   ...,
   boost::property<vertex_name_t,char
   boost::property<edge_weight_t,float> > Graph;
Constructor - default
Şöyle yaparız.
Graph g;
Constructor
Belirtilen sayıda vertex ile kurmak için şöyle yaparız.
Graph g (50);
edge_descriptor tipi
Şöyle yaparız. add_edge () çağrısı il yeni eklenen edge nesnesinin tipidir.
typedef GraphType::edge_descriptor edge;
get metodu
Property Map alanlarına erişmek için şöyle yaparız.
property_map<Graph, std::string VertexProperties::*>::type
    stateName = get(&VertexProperties::stateName, g);
vertex_descriptor tipi
Şöyle yaparız. add_vertex () çağrısı ile yeni eklenen vertex nesnesinin tipidir.
typedef GraphType::vertex_descriptor vertex;
Şöyle yaparız.
GraphType g;
...
GraphType::vertex_descriptor v = ...;
g [v] = ...;
Serialization Desteği
1. boost archive
Örnek
Şu satırı dahil ederiz.
#include <boost/graph/adj_list_serialize.hpp>
Şöyle yaparız.
#include <boost/archive/text_oarchive.hpp>
Graph g;
...
boost::archive::text_oarchive oa(std::cout);
oa << g;
Örnek
Elimizde şu kod olsun.
struct myVertex {
    int a;
    float b;
};

namespace boost {
  namespace serialization {
    template <class Archive> void serialize(Archive &ar, myVertex &mv,
                                            unsigned /*version*/) {
            ar & mv.a & mv.b;
        }
    } // namespace serialization
} // namespace boost

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, myVertex>
 graph_t;
Şöyle yaparız.
{
  graph_t g;
  std::ifstream ifs("file_out"); // read from file
  boost::archive::text_iarchive ia(ifs);
  ia >> g;

  std::cout << "Read " << num_vertices(g) << " vertices\n";
}

{
  graph_t g(100);
  std::ofstream ofs("file_out"); // save to file
  boost::archive::text_oarchive oa(ofs);
  oa << g;
}

2. write_graphviz metodu
write_graphviz metodu yazısına taşıdım.

Hiç yorum yok:

Yorum Gönder