Чтобы проиллюстрировать использование параллельной графической библиотеки, мы проиллюстрируем использование последовательного и параллельного BGL, чтобы найти кратчайшие пути от вершины А до любой другой вершины на следующем простом графике:
При последовательномBGLпрограмма вычисления кратчайших путей имеет три этапа. Читатели, знакомые с BGL, возможно, захотят перейти к разделу.Распределение графа.
Для этой задачи мы используем представление списка смежности графика, используя BGLadjacency_list''_классШаблон.будетнаправленныйграф(направлено)параметр, вершины которого хранятся вstd: вектор(vecSпараметр), где исходящие края каждой вершины хранятся вstd::list(список Sпараметр). К каждому из краев прикрепляем интегральный вес.
Чтобы построить график, мы объявляем перечисление, содержащее имена узлов (для нашего собственного использования) и создаем два массива: первый,edge_array, содержит источник и цель каждого края, тогда как второй,вес, содержит интегральный вес каждого края. Мы передаем содержимое массивов через указатели (используемые здесь в качестве итераторов) конструктору графов для построения нашего графа:
Чтобы воспользоваться алгоритмом Дейкстры, нужно сначала решить, как мы хотим получить результаты алгоритма, а именно расстояние до каждой вершины и предшественник каждой вершины (позволяя реконструкцию самих кратчайших путей). В нашем случае мы создадим два вектора:pдля предшественников иdдля расстояний.
Далее мы определяем нашу исходную вершинуsс помощью операцииvertexнаadjacency_list''_ивызова''dijkstra_shortest_paths''сграфа''g, стартовой вершиныsи двухсвойствокарт, котороеинструктируеталгоритмхранитьпредшественниковввекторе''ри расстояния в вектореd. Алгоритм автоматически использует краевые веса, хранящиеся в графе, хотя эта возможность может быть переопределена.
// Keeps track of the predecessor of each vertex
std::vector<vertex_descriptor> p(num_vertices(g));
// Keeps track of the distance to each vertex
std::vector<int> d(num_vertices(g));
vertex_descriptor s = vertex(A, g);
dijkstra_shortest_paths
(g, s,
predecessor_map(
make_iterator_property_map(p.begin(), get(vertex_index, g))).
distance_map(
make_iterator_property_map(d.begin(), get(vertex_index, g)))
);
Distributing the graph
Предварительные вычисления полностью последовательны, причем граф хранится в одном адресном пространстве. Чтобы распределить граф по нескольким процессорам без общего адресного пространства, нужно представить процессоры и связь между ними и изменить тип графа.
Процессоры и их взаимодействия абстрагируются черезпроцессную группу. В нашем случае мы будем использоватьMPIдля связи с межпроцессорными сообщениями, отправленными немедленно:
Отметим, что единственным отличием от последовательного BGL является использование селектораdistributedS, который идентифицирует распределенный граф. Вершины графа будут распределены между различными процессорами, и процессор, который владеет вершиной, также хранит края, выходящие из этой вершины, и любые свойства, связанные с этой вершиной или ее краями. С тремя процессорами и распределением блоков по умолчанию график будет распределен таким образом:
Процессор 0 (красный) владеет вершинами A и B, включая все края, выходящие из этих вершин, процессор 1 (зеленый) владеет вершинами C и D (и их краями), а процессор 2 (синий) владеет вершиной E. Построение этого графа использует тот же синтаксис, что и последовательный граф, как в разделеПостройте график.
Звонок вdijkstra_shortest_pathsсинтаксически эквивалентен последовательному вызову, но используемые механизмы очень отличаются. Карты свойств, переданныеdijkstra_shortest_paths, на самом деле являютсяраспределеннымикартами свойств, которые хранят свойства для локальных краев или вершин и выполняют неявную связь для доступа к свойствам удаленных краев или вершин при необходимости. Формулировка алгоритма Дийкстры также немного отличается, потому что каждый процессор может только попытаться расслабить края, выходящие из локальных вершин: по мере обнаружения более коротких путей к вершине сообщения к процессору, владеющему этой вершиной, указывают на то, что вершина может потребовать переработки.
