Giriş
Şu satırı dahil ederiz.
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.
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.
listS, vectorS, setS olabilir. Açıklaması şöyle
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
Bazı Tanımlama Örnekleri - Bundled Properties yani Kendi Yapılarım
Vertex için property tanımlayan bir sınıf şöyledir.
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
Şöyle yaparız.
Belirtilen sayıda vertex ile kurmak için şöyle yaparız.
Şöyle yaparız. add_edge () çağrısı il yeni eklenen edge nesnesinin tipidir.
get metodu
Property Map alanlarına erişmek için şöyle yaparız.
Şöyle yaparız. add_vertex () çağrısı ile yeni eklenen vertex nesnesinin tipidir.
1. boost archive
Örnek
Şu satırı dahil ederiz.
Ş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ılarBu 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;
ConstructorBelirtilen 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;
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ği1. 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.
2. write_graphviz metodu
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
Hiç yorum yok:
Yorum Gönder