Использование библиотеки ускорителей С++

Ответ 1

Вот простой пример: использование списка смежности и выполнение топологической сортировки:

#include <iostream>
#include <deque>
#include <iterator>

#include "boost/graph/adjacency_list.hpp"
#include "boost/graph/topological_sort.hpp"

int main()
{
    // Create a n adjacency list, add some vertices.
    boost::adjacency_list<> g(num tasks);
    boost::add_vertex(0, g);
    boost::add_vertex(1, g);
    boost::add_vertex(2, g);
    boost::add_vertex(3, g);
    boost::add_vertex(4, g);
    boost::add_vertex(5, g);
    boost::add_vertex(6, g);

    // Add edges between vertices.
    boost::add_edge(0, 3, g);
    boost::add_edge(1, 3, g);
    boost::add_edge(1, 4, g);
    boost::add_edge(2, 1, g);
    boost::add_edge(3, 5, g);
    boost::add_edge(4, 6, g);
    boost::add_edge(5, 6, g);

    // Perform a topological sort.
    std::deque<int> topo_order;
    boost::topological_sort(g, std::front_inserter(topo_order));

    // Print the results.
    for(std::deque<int>::const_iterator i = topo_order.begin();
        i != topo_order.end();
        ++i)
    {
        cout << tasks[v] << endl;
    }

    return 0;
}

Я согласен с тем, что документация boost:: graph может быть пугающей. Я предлагаю вам посмотреть ссылку ниже:

http://www.boost.org/doc/libs/1_48_0/libs/graph/doc/table_of_contents.html

Я не могу вспомнить, совпадает ли содержимое печатной книги, я подозреваю, что это немного легче на глаза. Я действительно научился использовать boost: graph из книги. Однако кривая обучения может показаться довольно крутой. Книга, на которую я ссылаюсь и отзывы, можно найти здесь:

http://www.amazon.com/Boost-Graph-Library-Reference-Manual/dp/0201729148/ref=sr_1_1?ie=UTF8& QID = 1326242972 & ср = 8-1

Ответ 2

Это основано на примере, приведенном на сайте boost:: graph, с добавленными комментариями:

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>

#include "boost/graph/graph_traits.hpp"
#include "boost/graph/adjacency_list.hpp"

using namespace boost;

int main(int argc, char *argv[])
{
    //create an -undirected- graph type, using vectors as the underlying containers
    //and an adjacency_list as the basic representation
    typedef adjacency_list<vecS, vecS, undirectedS> UndirectedGraph;

    //Our set of edges, which basically are just converted into ints (0-4)
    enum {A, B, C, D, E, N};
    const char *name = "ABCDE";

    //An edge is just a connection between two vertitices. Our verticies above
    //are an enum, and are just used as integers, so our edges just become
    //a std::pair<int, int>
    typedef std::pair<int, int> Edge;

    //Example uses an array, but we can easily use another container type
    //to hold our edges. 
    std::vector<Edge> edgeVec;
    edgeVec.push_back(Edge(A,B));
    edgeVec.push_back(Edge(A,D));
    edgeVec.push_back(Edge(C,A));
    edgeVec.push_back(Edge(D,C));
    edgeVec.push_back(Edge(C,E));
    edgeVec.push_back(Edge(B,D));
    edgeVec.push_back(Edge(D,E));

    //Now we can initialize our graph using iterators from our above vector
    UndirectedGraph g(edgeVec.begin(), edgeVec.end(), N);

    std::cout << num_edges(g) << "\n";

    //Ok, we want to see that all our edges are now contained in the graph
    typedef graph_traits<UndirectedGraph>::edge_iterator edge_iterator;

    //Tried to make this section more clear, instead of using tie, keeping all
    //the original types so it more clear what is going on
    std::pair<edge_iterator, edge_iterator> ei = edges(g);
    for(edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter) {
        std::cout << "(" << source(*edge_iter, g) << ", " << target(*edge_iter, g) << ")\n";
    }

    std::cout << "\n";
    //Want to add another edge between (A,E)?
    add_edge(A, E, g);

    //Print out the edge list again to see that it has been added
    for(edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter) {
        std::cout << "(" << source(*edge_iter, g) << ", " << target(*edge_iter, g) << ")\n";
    }

    //Finally lets add a new vertex - remember the verticies are just of type int
    int F = add_vertex(g);
    std::cout << F << "\n";

    //Connect our new vertex with an edge to A...
    add_edge(A, F, g);

    //...and print out our edge set once more to see that it was added
    for(edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter) {
        std::cout << "(" << source(*edge_iter, g) << ", " << target(*edge_iter, g) << ")\n";
    }
    return 0;
}

Ответ 3

Boost adjacency_list - хороший способ, этот пример создает ориентированный граф и выводит изображение графика, используя AT & T GraphViz:

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>

int main()
{
    using namespace std;
    using namespace boost;

    /* define the graph type
          listS: selects the STL list container to store 
                 the OutEdge list
          vecS: selects the STL vector container to store 
                the vertices
          directedS: selects directed edges
    */
   typedef adjacency_list< listS, vecS, directedS > digraph;

   // instantiate a digraph object with 8 vertices
   digraph g(8);

   // add some edges
   add_edge(0, 1, g);
   add_edge(1, 5, g);
   add_edge(5, 6, g);
   add_edge(2, 3, g);
   add_edge(2, 4, g);
   add_edge(3, 5, g);
   add_edge(4, 5, g);
   add_edge(5, 7, g);

   // represent graph in DOT format and send to cout
   write_graphviz(cout, g);

   return 0;
}

Вывод представляет собой файл DOT, который можно быстро передать в утилиту dot, которая поставляется вместе с GraphViz.

Ответ 4

Я думаю, что вы найдете следующие ресурсы очень полезными.

Графическая схема праймера

Если вы не знакомы с теорией графов или нуждаетесь в переподготовке, то посмотрите на повышение. Обзор теории элементарных графов: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/graph_theory_review.html

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

Пример кода подробно описан

Для примера кода для создания графов, который описан подробно, ознакомьтесь со следующим разделом онлайн-книги Бориса Шэлинга - The Boost С++ Libraries: http://theboostcpplibraries.com/boost.graph-vertices-and-edges

Борис объясняет, как работать с вершинами и ребрами с помощью adjacenty_list. Код полностью объяснен, чтобы вы могли понять каждый пример.

Общие сведения о параметрах шаблона adjacency_list

Важно понять параметры шаблона для adjacency_list. Например, вам нужен направленный или неориентированный граф? Вы хотите, чтобы ваш граф содержал несколько ребер с теми же конечными узлами (т.е. Мультиграфы)? Производительность также вступает в игру. Книга Бориса объясняет некоторые из них, но вы найдете дополнительную информацию об использовании adjacenty_list здесь: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/using_adjacency_list.html

Использование пользовательских объектов для вершин, граней или графов

Если вы хотите использовать пользовательские объекты для вершин, ребер или даже самого графика, тогда вы захотите использовать связанные свойства. Следующие ссылки будут полезны для использования связанных свойств: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/bundles.html

И, возможно, это тоже для примера: добавление пользовательских вершин в графу форсирования

Обнаружение круговых зависимостей (циклов)

Существует множество способов обнаружения круговых зависимостей, включая:

Поиск по глубине: Один простой способ - выполнить поиск по глубине и определить, выполняется ли поиск в уже обнаруженной вершине в текущем дереве поиска. Ниже приведен пример обнаружения циклических зависимостей с использованием поиска глубинной глубины: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html#sec:cycles

Топологическая сортировка: Также можно обнаружить циклы, используя топологическую сортировку . boost обеспечивает топологический алгоритм: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/topological_sort.html

Топологическая сортировка работает на ориентированном ациклическом графе (DAG). Если циклический граф передан, то генерируется исключение, что указывает на то, что граф имеет циклическую зависимость. topological_sort включает в себя поиск по глубине, но также обеспечивает линейный порядок вершин. Вот пример: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html#sec:cycles

Сильно подключенные компоненты: Кроме того, поиск сильно связанных компонентов может указывать, имеет ли график циклы: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/strongComponent.htm

Пример зависимостей файлов

Еще одна полезная ссылка - это тот, который уже был предоставлен. - Увеличьте пример зависимостей файлов, который показывает, как настроить график файлов исходного кода, заказать их на основе их порядка компиляции (топологическая сортировка), определить, какие файлы могут быть скомпилированы одновременно, и определить циклические зависимости: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html

Ответ 5

Некоторые краткие и точные рецепты в начале работы с библиотеками Boost С++ можно найти здесь:

Использование библиотеки Boost Graph

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

Здесь есть несколько рабочих примеров, включая создание направленных и неориентированных графов, печать весов ребер, поиск минимальных связующих деревьев с использованием алгоритма Крускаля и проблемы с максимальным потоком.