Использование библиотеки графов C++ Boost
Я запутался в том, как на самом деле создать Graph, используя библиотеку boost, я посмотрел на пример кода, и нет никаких комментариев, объясняющих, что он делает.
Как вы строите график и добавляете вершины и ребра?
5 ответов
Вот простой пример, использующий список смежности и выполняющий топологическую сортировку:
#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 из книги. Кривая обучения может быть довольно крутой, хотя. Книгу, на которую я ссылаюсь и отзывы, можно найти здесь:
Это основано на примере, приведенном на сайте 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's 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;
}
Я думаю, что вы найдете следующие ресурсы очень полезными.
Учебник по теории графов
Если вы не знакомы с теорией графов или нуждаетесь в переподготовке, посмотрите на обзор Boost по теории элементарных графов: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/graph_theory_review.html
Этот учебник полезен для понимания терминологии, того, как структуры данных представляют графы (матрица смежности, список смежности и т. Д.), И алгоритмов (поиск в ширину, поиск в глубину, кратчайший путь и т. Д.).
Пример кода подробно описан
Для примера кода для создания графиков, который подробно описан, взгляните на следующий раздел онлайн-книги Бориса Шелинга - Библиотеки Boost C++: http://theboostcpplibraries.com/boost.graph-vertices-and-edges
Борис объясняет, как работать с вершинами и ребрами, используя смежный y_list. Код подробно объясняется, чтобы вы могли понять каждый пример.
Понимание параметров шаблона adjacency_list
Важно понимать параметры шаблона для adjacency_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
Топологическая сортировка. Можно также обнаружить циклы, используя топологическую сортировку. boost предоставляет алгоритм topological_sort: 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
Сильно связанные компоненты. Кроме того, поиск сильно связанных компонентов может указывать на наличие циклов на графике: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/strongComponent.htm
Функция boost_components вычисляет сильно связанные компоненты ориентированного графа, используя алгоритм Тарьяна. http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/strong_components.html
Пример зависимости от файла
Еще одна полезная ссылка, которая уже была предоставлена, - пример зависимости от файлов Boost, который показывает, как настроить граф файлов исходного кода, упорядочить их в соответствии с порядком их компиляции (топологическая сортировка), определить, какие файлы могут быть скомпилированы одновременно, и определить циклические зависимости.: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/file_dependency_example.html
Повышение-х adjacency_list Это хороший способ, этот пример создает ориентированный граф и выводит изображение графа с помощью GraphViz AT & T:
#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.
Некоторые краткие и точные рецепты по началу работы с библиотеками Boost C++ можно найти здесь:
Использование библиотеки графов ускорения
Эти примеры кода, перечисленные здесь, выглядят достаточно современными и компилируются и работают нормально. Я обнаружил, что некоторая онлайн-документация, касающаяся использования библиотеки графов ускорения, устарела или приводит к ошибкам компиляции.
Здесь есть ряд рабочих примеров, в том числе создание ориентированных и ненаправленных графов, печать весов ребер, поиск минимальных остовных деревьев с использованием алгоритма Крускала и проблемы максимального потока.