Distributed Adjacency List

Contents

Introduction

Распределенный список смежности реализует структуру данных графа с использованием представления списка смежности. Его интерфейс и поведение примерно эквивалентны шаблону класса библиотеки Boost Graphadjacency_list. Однако распределенный список смежности разбивает вершины графа на несколько процессов (которые не должны разделять адресное пространство). Края, исходящие из любой вершины, хранящейся в процессе, также хранятся в этом процессе, за исключением случаев ненаправленных графиков, где либо источник, либо цель могут хранить край.

template<typename OutEdgeListS, typename ProcessGroup, typename VertexListS,
         typename DirectedS, typename VertexProperty, typename EdgeProperty,
         typename GraphProperty, typename EdgeListS>
class adjacency_list<OutEdgeListS,
                     distributedS<ProcessGroup, VertexListS>,
                     DirectedS, VertexProperty,
                     EdgeProperty, GraphProperty, EdgeListS>;

Defining a Distributed Adjacency List

Чтобы создать распределенный список смежности, сначала определите представление графа в одном адресном пространстве, используя этиРуководство. Заменить селектор списка вершин (VertexListS)) с инстанциациейраспределенных S, которая включает в себя:

Выберите типгруппы процессов, который представляет различные координационные процессы, которые будут хранить распределенный граф. Например, группа процессовMPI.
Селектор, указывающий, как будут храниться списки вершин в каждом процессе. Только селекторыvecSиlistSв настоящее время хорошо поддерживаются.

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

using namespace boost;
typedef adjacency_list<vecS,
                       distributedS<parallel::mpi::bsp_process_group, vecS>,
                       directedS>
  Graph;

Distributed Vertex and Edge Properties

Свойства Vertex и edge для распределенных графов отражают их аналоги для нераспределенных графов. Однако при распределенном графе свойства вершины и края сохраняются только в процессе, которому принадлежит вершина или край.

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

struct City {
  City() { }
  City(const std::string& name, const std::string& mayor = "Unknown", int population = 0)
    : name(name), mayor(mayor), population(population) { }
  std::string name;
  std::string mayor;
  int population;
  // Serialization support is required!
  template<typename Archiver>
  void serialize(Archiver& ar, const unsigned int /*version*/) {
    ar & name & mayor & population;
  }
};
struct Highway {
  Highway() { }
  Highway(const std::string& name, int lanes, int miles_per_hour, int length)
    : name(name), lanes(lanes), miles_per_hour(miles_per_hour), length(length) { }
  std::string name;
  int lanes;
  int miles_per_hour;
  int length;
  // Serialization support is required!
  template<typename Archiver>
  void serialize(Archiver& ar, const unsigned int /*version*/) {
    ar & name & lanes & miles_per_hour & length;
  }
};

Чтобы создать распределённый график для дорожной карты, мы поставляемГородиШоссев качестве четвертого и пятого параметров вadjacency_listсоответственно:

typedef adjacency_list<vecS,
                       distributedS<parallel::mpi::bsp_process_group, vecS>,
                       directedS,
                       City, Highway>
  RoadMap;

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

RoadMap map; // distributed graph instance
typedef property_map<RoadMap, int Highway::*>::type
  road_length = get(&Highway::length, map);

Теперь можно получить доступ к длине любой данной дороги на основе ее дескриптора краяeс выражениемget [road_length,e], независимо от того, какой процесс хранит крайe.

Named Vertices

Вершины графа обычно соответствуют названным объектам в домене приложения. В примере дорожной карты из предыдущего раздела вершины на графике представляют города. Распределенный список смежности поддерживает названные вершины, который обеспечивает имплицитное отображение от имен вершин в домене приложения (например, название города, такого как "Bloomington") до фактического дескриптора вершины, хранящегося в распределенном графе (например, третья вершина на процессоре 1). Включая поддержку названных вершин, можно ссылаться на вершины по имени при манипулировании графом. Например, можно добавить шоссе из Индианаполиса в Чикаго:

add_edge("Indianapolis", "Chicago", Highway("I-65", 4, 65, 151), map);

Распределенный список смежности будет содержать вершины, связанные с именами "Индианаполис" и "Чикаго", а затем добавит к этим вершинам край, представляющий I-65. Вершины могут храниться на любом процессоре, локальном или удаленном.

Чтобы включить названные вершины, нарисуйте свойствоinternal_vertex_nameдля структуры, прикрепленной к вершинам на вашем графике.internal_vertex_nameсодержит один элемент,тип, который является типом функционального объекта, который принимает свойство вершины и возвращает имя, сохраненное в этом свойстве вершины. В случае нашей дорожной карты, полесодержит название каждого города, поэтому мы используем объект функциииз библиотекиBoost.MultiIndexдля извлечения названия, например,

namespace boost { namespace graph {
template<>
struct internal_vertex_name<City>
{
  typedef multi_index::member<City, std::string, &City::name> type;
};
} }

Вот так! Теперь можно ссылаться на вершины по имени при взаимодействии с распределенным списком смежности.

Что происходит, когда человек использует имя вершины, которой не существует? Например, в нашемadd_edgeвызове выше, что произойдет, если вершина, названная "Индианаполис", еще не добавлена к графу? По умолчанию распределенный список смежности забросит исключение, если названная вершина еще не существует. Однако можно настроить это поведение, указав объект функции, который конструирует экземпляр свойства вершины (например,Город) только из названия вершины. Эта настройка происходит черезвнутренний_vertex_constructorпризнак. Например, используя шаблонvertex_from_name(предоставленный параллельной BGL), мы можем утверждать, чтоГородможет быть построен непосредственно из названия города с использованием его второго конструктора:

namespace boost { namespace graph {
template<>
struct internal_vertex_constructor<City>
{
  typedef vertex_from_name<City> type;
};
} }

Теперь можно свободно добавлять края по названию вершины, не беспокоясь о явном добавлении вершин. Полямэраинаселениябудут иметь значения по умолчанию, но структура графа будет правильной.

Building a Distributed Graph

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

1.Конструкторы последовательностей: Если ваши данные могут быть легко сгенерированы парой итераторов, которые производят пары (источник, цель), вы можете использовать конструкторы последовательностей для построения распределенного графа параллельно. Этот метод часто предпочтителен при создании эталонов, поскольку генераторы случайных графов, такие какsorted_erdos_renyi_iterator, создают соответствующую входную последовательность. Обратите внимание, что во всех процессах должна быть одна и та же последовательность входного итератора. Этот метод имеет то преимущество, что последовательный графостроительный код идентичен параллельному графостроительному коду. Пример построения случайного графика таким образом:

typedef boost::sorted_erdos_renyi_iterator<boost::minstd_rand, Graph> ERIter;
boost::minstd_rand gen;
unsigned long n = 1000000; // 1M vertices
Graph g(ERIter(gen, n, 0.00005), ERIter(), n);

2.Добавление краев по вершинному числу: Если вы можете сопоставить свои вершины со значениями в случайном [0,n, гдеn— число вершин в распределенном графе. Используйте этот метод, а не конструкторы последовательностей, когда ваш алгоритм не может быть легко перемещен в итераторы ввода или если вы не можете воспроизвести последовательность ввода. Например, вы можете прочитать график из входного файла:

Graph g(n); // initialize with the total number of vertices, n
if (process_id(g.process_group()) == 0) {
  // Only process 0 loads the graph, which is distributed automatically
  int source, target;
  for (std::cin >> source >> target)
    add_edge(vertex(source, g), vertex(target, g), g);
}
// All processes synchronize at this point, then the graph is complete
synchronize(g.process_group());

3.Добавление краев по имени: Если вы используете названные вершины, вы можете построить свой график, просто позвонивadd_edgeс именами исходных и целевых вершин. Будьте осторожны, чтобы убедиться, что каждый край добавляется только одним процессом (не имеет значения, какой это процесс), иначе вы получите несколько краев. Например, в следующей программе мы читаем края от стандартного ввода процесса 0, добавляя эти края по имени. Вертикали и края будут создаваться и распределяться автоматически.

Graph g;
if (process_id(g.process_group()) == 0) {
  // Only process 0 loads the graph, which is distributed automatically
  std:string source, target;
  for(std::cin >> source >> target)
    add_edge(source, target, g);
}
// All processes synchronize at this point, then the graph is complete
synchronize(g.process_group());

Graph Concepts

Распределенный список смежностей моделирует концепциюГрафаи, в частности, концепциюРаспределенного Графа. Он также моделирует концепциюГрафик СлучаевиГрафик Соседства, но ограничивает входную область операций только для соответствия локальным вершинам. Например, процесс может получить доступ только к исходящим краям вершины, если эта вершина хранится в этом процессе. Ненаправленные и двунаправленные распределенные списки смежности моделируют концепциюBidirectional Graphс теми же ограничениями домена. Распределенные списки смежности также моделируют концепциюMutable Graph(с ограничениями домена; см. разделReference), концепциюProperty Graphи концепциюMutable Property Graph.

В отличие от своего нераспределенного аналога, список распределенных смежностейнемоделируетVertex List GraphилиEdge List Graph, потому что нельзя перечислить все вершины или края в распределенном графе. Вместо этого он моделирует более слабыеDistributed Vertex List GraphиDistributed Edge List Graphконцепции, которые позволяют получить доступ к локальным краям и вершинам на каждом процессоре. Обратите внимание, что если все процессы в группе процессов, по которым распределен граф, итератор поверх их соответствующих списков вершин или краев, все вершины и края будут покрыты один раз.

Reference

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

Where Defined

Associated Types

adjacency_list::process_group_type

Тип группы процессов, по которой будет распределен график.

adjacency_list::distribution_type

Тип распределения, используемый для разделения вершин в графе.

adjacency_list::vertex_name_type

Если граф поддерживает названные вершины, это тип, используемый для названия вершин. В противном случае этот тип не присутствует в списке распределенных смежностей.

Member Functions

adjacency_list(const ProcessGroup& pg = ProcessGroup());
adjacency_list(const GraphProperty& g,
               const ProcessGroup& pg = ProcessGroup());

Постройте пустой распределенный список смежности с данной группой процессов (или по умолчанию) и свойством графа (или по умолчанию).

adjacency_list(vertices_size_type n, const GraphProperty& p,
               const ProcessGroup& pg, const Distribution& distribution);
adjacency_list(vertices_size_type n, const ProcessGroup& pg,
               const Distribution& distribution);
adjacency_list(vertices_size_type n, const GraphProperty& p,
               const ProcessGroup& pg = ProcessGroup());
adjacency_list(vertices_size_type n,
               const ProcessGroup& pg = ProcessGroup());

Постройте распределенный список смежности сnвершинами, необязательно обеспечивая свойство графа, группу процессов или распределение.nвершины будут распределены через данное (или построенное по умолчанию) распределение. Эта операция является коллективной, требуя, чтобы все процессы с группой процессов выполнялись одновременно.

template <class EdgeIterator>
adjacency_list(EdgeIterator first, EdgeIterator last,
               vertices_size_type n,
               const ProcessGroup& pg = ProcessGroup(),
               const GraphProperty& p = GraphProperty());
template <class EdgeIterator, class EdgePropertyIterator>
adjacency_list(EdgeIterator first, EdgeIterator last,
               EdgePropertyIterator ep_iter,
               vertices_size_type n,
               const ProcessGroup& pg = ProcessGroup(),
               const GraphProperty& p = GraphProperty());
template <class EdgeIterator>
adjacency_list(EdgeIterator first, EdgeIterator last,
               vertices_size_type n,
               const ProcessGroup& process_group,
               const Distribution& distribution,
               const GraphProperty& p = GraphProperty());
template <class EdgeIterator, class EdgePropertyIterator>
adjacency_list(EdgeIterator first, EdgeIterator last,
               EdgePropertyIterator ep_iter,
               vertices_size_type n,
               const ProcessGroup& process_group,
               const Distribution& distribution,
               const GraphProperty& p = GraphProperty());

Постройте распределенный список смежности сnвершинами и с краями, указанными в списке краев, заданном диапазоном[первый,последний].EdgeIteratorдолжен быть модельюInputIterator. Тип значенияEdgeIteratorдолжен бытьstd::pair, где тип в паре является целым типом. Целые числа соответствуют вершинам, и все они должны находиться в диапазоне[0,n]. При условии,ep_iterотносится к списку свойств края[ep_iter,ep_iter+m]содержит свойства для каждого из краев.

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

void clear()

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

process_group_type& process_group();
const process_group_type& process_group() const;

Возвращает группу процессов, по которой распределен этот график.

distribution_type&       distribution();
const distribution_type& distribution() const;

Возвращает распределение, используемое для первоначального размещения вершин.

template<typename VertexProcessorMap>
  void redistribute(VertexProcessorMap vertex_to_processor);

Перераспределяет вершины (и, следовательно, края) графа. Карта свойствvertex_to_processorпредоставляет для каждой вершины идентификатор процесса, указывающий, где вершина должна быть перемещена. После завершения этой коллективной рутины распределённый график будет отражать новое распределение. Все вершинные и краевые дескрипторы, а также внутренние и внешние карты свойств недействительны.

template<typename OStreamConstructibleArchive>
  void save(std::string const& filename) const;
template<typename IStreamConstructibleArchive>
  void load(std::string const& filename);

Сериализирует график на повышение.OStreamConstructibleArchiveиIStreamConstructibleArchiveявляются моделями Boost.SerializationArchiveс дополнительным требованием, чтобы они могли быть построены изstd::ostreamиstd::istream.имени файлаимен каталога, который будет содержать файлы для различных процессов.

Non-Member Functions

std::pair<vertex_iterator, vertex_iterator>
vertices(const adjacency_list& g);

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

std::pair<edge_iterator, edge_iterator>
edges(const adjacency_list& g);

Возвращает итератор-диапазон, обеспечивающий доступ к краевому набору графаг, хранящегося в этом процессе.

std::pair<adjacency_iterator, adjacency_iterator>
adjacent_vertices(vertex_descriptor u, const adjacency_list& g);

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

std::pair<out_edge_iterator, out_edge_iterator>
out_edges(vertex_descriptor u, const adjacency_list& g);

Возвращает итератор-диапазон, обеспечивающий доступ к краям вершиныуна графикег. Если график ненаправлен, этот диапазон итератора обеспечивает доступ ко всем краям, падающим на вершинуу. Как для направленных, так и для ненаправленных графов, для крайнихe,источника [e,g]==uи[g]==v, гдеvявляется вершиной, прилегающей ку. Вершинаудолжна быть локальной для этого процесса.

std::pair<in_edge_iterator, in_edge_iterator>
in_edges(vertex_descriptor v, const adjacency_list& g);

Возвращает итератор-диапазон, обеспечивающий доступ к краям вершиныvв графеg. Эта операция доступна только в том случае, еслидвунаправленная Sбыла указана для.Направленныйшаблонный параметр. Для краевогоe,мишени [e,g]==vиисточника [e,g]==удля некоторой вершиныу, которая примыкает кv, независимо от того, направлен ли график или не направлен. Вершинаvдолжна быть локальной для этого процесса.

degree_size_type
out_degree(vertex_descriptor u, const adjacency_list& g);

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

degree_size_type
in_degree(vertex_descriptor u, const adjacency_list& g);

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

vertices_size_type
num_vertices(const adjacency_list& g);

Возвращает число вершин в графег, которые хранятся в процессе выполнения.

edges_size_type
num_edges(const adjacency_list& g);

Возвращает число вершин в графег, которые хранятся в процессе выполнения.

vertex_descriptor
vertex(vertices_size_type n, const adjacency_list& g);

Возвращаетn''thвсписоквершины,согласнораспределениеиспользуемоекразделуграфадолжно быть значением между нулем и суммойnum_vertices(g)в каждом процессе [минус один]. Обратите внимание, что это не обязательно так, чтовершина (0,г)==*num_vertices (g.first. Эта функция гарантирует точность только тогда, когда вершины не были добавлены или удалены из графа после его первоначальной конструкции.

std::pair<edge_descriptor, bool>
edge(vertex_descriptor u, vertex_descriptor v,
     const adjacency_list& g);

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

std::pair<out_edge_iterator, out_edge_iterator>
edge_range(vertex_descriptor u, vertex_descriptor v,
           const adjacency_list& g);

ТОДО: Не реализовано. Возвращает пару передних итераторов, которые дают диапазон для всех параллельных краев отuдоv. Эта функция работает только тогда, когдаOutEdgeListдляadjacency_listпредставляет собой контейнер, который сортирует края в соответствии с вершиной цели и допускает параллельные края.Мультисетселектор выбирает такой контейнер. Вертексудолжен храниться в процессе выполнения.

Structure Modification

unspecified add_edge(vertex_descriptor u, vertex_descriptor v, adjacency_list& g);
unspecified add_edge(vertex_name_type u, vertex_descriptor v, adjacency_list& g);
unspecified add_edge(vertex_descriptor u, vertex_name_type v, adjacency_list& g);
unspecified add_edge(vertex_name_type u, vertex_name_type v, adjacency_list& g);

Добавляет край(u,v)к графу. Сам тип возврата не указан, но тип может быть построен копией и неявно преобразован вstd::pair. Описатель края описывает добавленный (или найденный) край. Для графов, не допускающих параллельных краев, если край уже находится в графе, то не будет добавлен дубликат и флагбудетложным. Кроме того, если u и v являются дескрипторами для одной и той же вершины (создание самопетли) и граф ненаправлен, то край не будет добавлен, и флаг будетложным. Когда флагложный, дескриптор возвратного края указывает на уже существующий край.

Параметрыuиvмогут быть либо дескрипторами вершины, либо, если граф использует названные вершины, имена вершин. Если вершина с заданным именем не существует, внутренний конструктор вершины будет вызван для создания нового свойства вершины, и вершина с этим свойством будет добавлена к графу неявно. Конструктор внутренней вершины по умолчанию делает исключение.

unspecified add_edge(vertex_descriptor u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g);
unspecified add_edge(vertex_name_type u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g);
unspecified add_edge(vertex_descriptor u, vertex_name_type v, const EdgeProperties& p, adjacency_list& g);
unspecified add_edge(vertex_name_type u, vertex_name_type v, const EdgeProperties& p, adjacency_list& g);

Добавляет край(u,v)к графу и прикрепляетpв качестве значения внутреннего хранилища свойств края. См. предыдущийadd_edge()Функция члена для более подробной информации.

void
remove_edge(vertex_descriptor u, vertex_descriptor v,
            adjacency_list& g);

Удаляет край(u,v)из графа. Если направленный селектор являетсядвунаправленным Sилиненаправленным S, то либо исходная, либо целевая вершина графа должна быть локальной. Если направленный селектор являетсянаправленным S, то вершина источника должна быть локальной.

void
remove_edge(edge_descriptor e, adjacency_list& g);

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

void remove_edge(out_edge_iterator iter, adjacency_list& g);

Это имеет тот же эффект, что иremove_edge(*iter,g). Для направленных (но не двунаправленных) графов это будет более эффективно, чемremove_edge(*iter,g).

template <class Predicate >
void remove_out_edge_if(vertex_descriptor u, Predicate predicate,
                        adjacency_list& g);

Удаляет все выступы вершиныуиз графа, удовлетворяющего предикату. То есть, если предикат возвращаетистинноепри нанесении на краевой дескриптор, то край удаляется. Вершинаудолжна быть локальной.

Влияние на стабильность дескриптора и итератора такое же, как и при вызове remove_edge() на каждом из удаленных краев.

template <class Predicate >
void remove_in_edge_if(vertex_descriptor v, Predicate predicate,
                       adjacency_list& g);

Удаляет все выступы вершиныvиз графа, удовлетворяющего предикату. То есть, если предикат возвращается истинным при нанесении на край дескриптора, то край удаляется. Вершинаvдолжна быть локальной.

Влияние на стабильность дескриптора и итератора такое же, как и при вызовеremove_edge()на каждом из удаленных краев.

Эта операция доступна для ненаправленных и двунаправленных графиков смежности, но не для направленных.

template <class Predicate>
void remove_edge_if(Predicate predicate, adjacency_list& g);

Удаляет все края из графа, удовлетворяющего предикату. То есть, если предикат возвращается истинным при нанесении на край дескриптора, то край удаляется.

vertex_descriptor add_vertex(adjacency_list& g);

Добавляет вершину к графу и возвращает дескриптор вершины для новой вершины. Вершина будет храниться в локальном процессе. Эта функция недоступна при использовании названных вершин.

unspecified add_vertex(const VertexProperties& p, adjacency_list& g);
unspecified add_vertex(const vertex_name_type& p, adjacency_list& g);

Добавляет вершину к графу с заданными свойствами. Если граф использует имена вершин, вершина будет добавлена в любой процесс "owns". В противном случае вершина будет храниться в локальном процессе. Обратите внимание, что второй конструктор вызовет пользовательский настраиваемый конструктор внутренней вершины, который (по умолчанию) делает исключение, когда видит неизвестную вершину.

Тип возврата является неопределенным типом, но может быть построен копией и может быть неявно преобразован в дескриптор вершины.

void clear_vertex(vertex_descriptor u, adjacency_list& g);

Удаляет все края до и от вершиныу. Вертикаль все еще появляется в вершинном наборе графа.

Влияние на стабильность дескриптора и итератора такое же, как и при вызовеremove_edge()для всех краев, которые имеютув качестве источника или цели.

Эта операция неприменима к направленным графам, поскольку входящие кромки к вершинеунеизвестны.

void clear_out_edges(vertex_descriptor u, adjacency_list& g);

Удаляет все выступы от вершиныу. Вертикаль все еще появляется в вершинном наборе графа.

Влияние на стабильность дескриптора и итератора такое же, как и при вызовеremove_edge()для всех краев, которые имеютув качестве источника.

Эта операция не применима к ненаправленным графам (использоватьclear_vertex()вместо этого).

void clear_in_edges(vertex_descriptor u, adjacency_list& g);

Удаляет все выступы от вершиныу. Вертикаль все еще появляется в вершинном наборе графа.

Влияние на стабильность дескриптора и итератора такое же, как и при вызовеremove_edge()для всех краев, которые имеютув качестве цели.

Эта операция применима только к двунаправленным графам.

void remove_vertex(vertex_descriptor u, adjacency_list& g);

Удалите вершинууиз вершинного множества графа. Предполагается, что при его удалении нет краев до или от вершиныу. Один из способов убедиться в этом — заранее вызватьclear_vertex(). Вершинаудолжна храниться локально.

Property Map Accessors

template <class PropertyTag>
property_map<adjacency_list, PropertyTag>::type
get(PropertyTag, adjacency_list& g);
template <class PropertyTag>
property_map<adjacency_list, Tag>::const_type
get(PropertyTag, const adjacency_list& g);

Возвращает объект карты свойств для верхнего свойства, указанногоТег собственности..Тег свойствдолжен соответствовать одному из свойств, указанных в графеVertexPropertyшаблонный аргумент. Карта возвращенного имущества будет представлять собойраспределенную карту имущества.

template <class PropertyTag , class X>
typename property_traits<property_map<adjacency_list, PropertyTag>::const_type>::value_type
get(PropertyTag, const adjacency_list& g, X x);

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

template <class PropertyTag , class X, class Value>
void put(PropertyTag, const adjacency_list& g, X x, const Value& value);

Это устанавливает значение свойства дляxк значению.xявляется либо вершинным, либо краевым дескриптором.Значениедолжно быть конвертируемым вимя типаproperty_traitsPropertyTag>::type>::value_type.

template <class GraphProperties, class GraphPropertyTag>
typename graph_property<adjacency_list, GraphPropertyTag>::type&
get_property(adjacency_list& g, GraphPropertyTag);
template <class GraphProperties, class GraphPropertyTag >
const typename graph_property<adjacency_list, GraphPropertyTag>::type&
get_property(const adjacency_list& g, GraphPropertyTag);

Правило: не реализовано.

Верните свойство, указанноеGraphPropertyTag, которое прикреплено к объекту графаg. Класс признаковgraph_propertyопределен вboost/graph/adjacency_list.hpp.

Авторы: Дуглас Грегор и Эндрю Лумсдейн

Статья Parallel BGL Distributed Adjacency List раздела может быть полезна для разработчиков на c++ и boost.

Parallel BGL Distributed Adjacency List

Boost , ,

Boost C++ Libraries