Bundled Properties

Boost , ,

Bundled Properties

Шаблоны классов<adjacency_list>и<adjacency_matrix>поддерживают введение названных свойств черезвнутренние свойства.. Однако этот метод является громоздким во многих применениях, где было бы более интуитивно понятно просто указать структуру или класс, который содержит внутренние свойства для краев или вершин. Связанные свойства позволяют использовать<adjacency_list>и<adjacency_matrix>таким образом, обеспечивая простой способ введения и доступа к любому количеству внутренних свойств для вершин и краев.

Можно ввести связанные свойства в любой тип графа, предоставляя тип класса, определенный пользователем для аргументов шаблона<VertexProperties>или<EdgeProperties>. Класс, определяемый пользователем, может быть размещен в конце списка<property>, заменяя аргумент<boost::no_property>.

Example: Route planning

Рассмотрим реализацию простого планировщика маршрутов, который должен найти кратчайшие направления из одного города в другой через набор магистралей. Вершины графа — города, и мы можем хранить несколько бит информации о городе в пределах каждой вершины:

struct City
{
  string name;
  int population;
  vector<int> zipcodes;
};

Края в графе представляют собой магистрали, которые также имеют несколько интересных атрибутов:

struct Highway
{
  string name;
  double miles;
  int speed_limit;
  int lanes;
  bool divided;
};

С помощью комплексных свойств мы можем напрямую использовать структуры<City>и<Highway>для определения графика:

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    City, Highway>
  Map;

Без связанных свойств перевод этого примера непосредственно в инстанциацию<adjacency_list>будет включать в себя несколько пользовательских свойств и приведет к такому типу:

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    // Vertex properties
    boost::property<boost::vertex_name_t, std::string,
    boost::property<population_t, int,
    boost::property<zipcodes_t, std::vector<int> > > >,
    // Edge properties
    boost::property<boost::edge_name_t, std::string,
    boost::property<boost::edge_weight_t, double,
    boost::property<edge_speed_limit_t, int,
    boost::property<edge_lanes_t, int,
    boost::property<edge_divided, bool> > > > > >
  Map;

Связывание вершинных и краевых свойств значительно упрощает декларацию графов.

В дополнение к вершинным и краевым пучкам мы также можем связывать свойства самого графа. Мы расширяем приложение, чтобы включить портфель карт планирования маршрутов для разных стран. В дополнение к<City>и<Highway>пучкам выше, мы можем объявить пучку графа<Country>.

struct Country {
  string name;
  bool use_right;   // Drive on the left or right
  bool use_metric;  // mph or km/h
};

Теперь граф будет объявлен как:

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    City, Highway, Country>
  Map;

Accessing bundled properties

Чтобы получить доступ к упакованному свойству для определенного края или вершины, подпишите свой график с дескриптором края или вершины, к чьему упакованному свойству вы хотите получить доступ. Например:

Map map; // load the map
Map::vertex_descriptor v = *vertices(map).first;
map[v].name = "Troy";
map[v].population = 49170;
map[v].zipcodes.push_back(12180);
Map::edge_descriptor e = *out_edges(v, map).first;
map[e].name = "I-87";
map[e].miles = 10.;
map[e].speed_limit = 65;
map[e].lanes = 4;
map[e].divided = true;

Связка графов, поскольку она не соответствует вершине или краю, доступна с использованием объекта graph_bundle в качестве ключа.

map[graph_bundle].name = "United States";
map[graph_bundle].use_right = true;
map[graph_bundle].use_metric = false;

Properties maps from bundled properties

Часто требуется создать карту свойств из внутреннего свойства для использования в общем алгоритме. Например, используя график без связанных свойств, мы можем вызвать алгоритм кратчайших путейДейкстрыследующим образом:

vector<double> distances(num_vertices(map));
dijkstra_shortest_paths(map, from,
      weight_map(get(edge_length, map))
      .distance_map(make_iterator_property_map(distances.begin(),
                                               get(vertex_index, map))));

С упаковкой свойств мы можем просто передать указательучастникакак свойство<get>. Эквивалентный пример использования комплексных свойств:

vector<double> distances(num_vertices(map));
dijkstra_shortest_paths(map, from,
      weight_map(get(&Highway::miles, map))
      .distance_map(make_iterator_property_map(distances.begin(),
                                               get(vertex_index, map))));

Тип возвращаемой карты свойств<property_map<Map, double Highway::*>::type>или<property_map<Map, double Highway::*>::const_type>, в зависимости от того, является ли граф<map>непостоянным или постоянным.

Вы также можете получить доступ ко всей вершине или кромке в качестве карты свойств, используя свойства<vertex_bundle>или<edge_bundle>соответственно. Например, карта свойств, возвращаемая<get(vertex_bundle, map)>, представляет собойLvalue Property Map, обеспечивающую доступ к<City>значениям, хранящимся в каждой вершине.

Карты свойств для графового пучка

Получение типа связанных свойств

Для получения типа вершинного или краевого пучка для данного графового типаГрафможно использовать классы признаковvertex_bundle_typeиedge_bundle_type. Типvertex_bundle_type::typeбудет типом, упакованным с вершинами (илиno_vertex_bundle, если граф поддерживает пучки, но нет пучка вершины). Точно так жеedge_bundle_type::typeбудет типом, упакованным с краями (илиno_edge_bundle, если отсутствует узел ребра).

Compatibility

Связанные свойства будут работать только на компиляторах, которые поддерживают частичную специализацию шаблона класса.

Статья Bundled Properties раздела может быть полезна для разработчиков на c++ и boost.

:: Главная :: ::