C boost graph library

C++ Boost Graph Library. Библиотека программиста

Автор: Сик Л. Дж.
Другие авторы: Ламсдэйн Ли. Э.
Издательство: СПб.: Питер
Год издания: 2006
Страницы: 304
ISBN 5-469-00352-3
Читать: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
Скачать: bootsgrathlibrari2006.pdf

БИБЛИОТЕКА ПРОГРАММИСТА Джереми Сик, Лай-КванЛи, Эндрю Ламсдэйн

Boost Graph Ubranr

Москва • Санкт-Петербург • Нижний Новгород • Воронеж Ростов-на-Дону ¦ Екатеринбург • Самара • Новосибирск Киев ¦ Харьков • Минск

2006
Джереми Сик, Лай-Кван Ли, Эндрю Ламсдэйн С++ Boost Graph Library. Библиотека программиста

Перевел с английского Р. Сузи

Главный редактор Е. Строганова

Заведующий редакцией А. Кривцов

Руководитель проекта А. Адаменко

Научный редактор В, Лаптев

Иллюстрации В. Демидова, Л. Родионова

Литературный редактор Е. Яковлева

Художник Л. Адуеве кая

Корректоры И. Викторова, И, Смирнова

Верстка Л. Родионова

ББК 32.973-018.1 УДК 004.43

Дж. Сик, Л. Ли, Э. Ламсдэйн

С35 С++ Boost Graph Library. Библиотека программиста / Пер. с английского Сузи Р. СПб.: Питер, 2006. — 304 с.: ил.

Издание, являющееся переводом одной из книг серни «С++ in Depth», посвящено описанию Boost Graph Library (BGL) — библиотеки для построения структур данных и алгоритмов вычислений ка графах, предназначенных для решения самых разнообразных Задач: от оптимизации интернет-маршрутизации и планирования телефонных сетей до задач молекулярной биологии. Содержит развернутое описание BGL, демонстрирует примеры приложений к реальным задачам. Первая часть является полным руководством пользователя, начинается с введения понятий теории графов, терминологии и описания обобщенных алгоритмов на графах, знакомит пользователя со всеми основными возможностями библиотеки BGL. Вторая часть — полное справочное руководство, содержит документацию ко всем концепциям BGL, ее алгоритмам и классам.

© Pearson Education Inc., 2002

© Перевод на русский язык, ЗАО Издательский дом «Питер», 2006 © Издание на русском языке, оформление, ЗАО Издательский дом «Питер», 2006

Прае? на издание получены по соглашению с Addreon-Westey Longman,

Вое права защищены Никакая часть данной книги не мо*вг быть воспроизведена в какой бы то ни было форме без письменного разрешения владельцев авторских прав,

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

ISBN 0-201-72914-8 (англ.)

ООО «Питер Принт», 194044, Санісг-Петербург, Б. СампсониевскиЙ пр., д. 29а.

Лицензия ИД № 05784 от 07.09.01.

Налоговая льгота — общероссийский классификатор продукции OK 005-93, том 2; 95 3005 “литература учебная П Уел > м. л. 24t51, Тираж 2000. Заказ 3 75

Отпечатано с готовых диапозитивов в ОАО «Техническая книга»

190005, Санкт-Петербург, Измайловский пр,, 29
Краткое содержание

Часть I. Руководство пользователя. 23

Глава 1. Введение . 24

Глава 2. Обобщенное программирование в С++. 39

Глава 3. Изучаем BGL. 59

Глава 4. Основные алгоритмы на графах. 77

Глава 5. Задачи нахождения кратчайших путей. 89

Глава 6. Задача минимального остовного дерева. 102

Глава 7. Компоненты связности. 109

Глава 8. Максимальный поток. 117

Глава 9. Неявные графы: обход конем. 124

Глава 10. Взаимодействие с другими графовыми библиотеками. 130

Глава 11. Руководство по производительности. 137

Часть II. Справочное руководство. 145

Глава 12. Концепции BGL. 146

Глава 13. Алгоритмы BGL. 170

Глава 14. Классы BGL. 215

Глава 15. Библиотека отображений свойств. 274

Глава 16. Вспомогательные концепции, классы и функции. 284

Дополнение к библиографии. 297

Алфавитньїй указатель. 299
Содержание

Обобщенное программирование. 16

Немного из истории BGL. 17

Что такое Boost. 18
2 3 4 5 6 7 .. 119 >> Следующая

I am confused about how to actually create a Graph using the boost library, I have looked at the example code and there are no comments explaining what it does.

How do you make a graph, and add vertices and edges as you go?

5 Answers 5

Here’s a simple example, using an adjacency list and executing a topological sort:

I agree that the boost::graph documentation can be intimidating, but it’s worth having a look.

I can’t recall if the contents of the printed book is the same, I suspect it’s a bit easier on the eyes. I actually learnt to use boost:graph from the book. The learning curve can feel pretty steep though. The book I refer to and reviews can be found here.

This is based off the example given on the boost::graph website, with comments added:

Boost’s adjacency_list is a good way to go, this example creates a directed graph and outputs an image of the graph using AT&T’s GraphViz:

The output is a DOT file that you can quickly feed into the dot utility that comes with GraphViz.

I think you will find the following resources very helpful.

Graph Theory Primer

If you are unfamiliar with graph theory or need a refresher, then take a look at boost’s Review of Elementary Graph Theory: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/graph_theory_review.html

This primer is helpful in understanding the terminology, how data structures represent graphs (adjacency matrix, adjacency list, etc…), and algorithms (breadth-first search, depth-first search, shortest-path, etc…).

Sample Code Described in Detail

For sample code for creating graphs that is described in detail, then take a look at the following section of Boris Schäling’s online book — The Boost C++ Libraries: http://theboostcpplibraries.com/boost.graph-vertices-and-edges

Boris explains how to work with vertices and edges using the adjacenty_list. The code is thoroughly explained so you can understand each example.

Understanding adjacency_list Template Parameters

It is important to understand the template parameters for the adjacency_list. For example, do you want a directed or undirected graph? Do you want your graph to contain multiple edges with the same end nodes (i.e. multigraphs)? Performance also comes into play. Boris’ book explains some of these, but you will find additional information on using the adjacenty_list here: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/using_adjacency_list.html

Using Custom Objects for Vertices, Edges, or Graphs

If you want to use custom objects for the vertices, edges, or even the graph itself, then you will want to use bundled properties. The following links will be helpful for using bundled properties: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/bundles.html

And perhaps this one too for an example: adding custom vertices to a boost graph

Detecting Circular Dependencies (Cycles)

There are multiple ways to detect circular dependencies including:

. one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Graphs are mathematical abstractions that are useful for solving many types of problems in computer science. Consequently, these abstractions must also be represented in computer programs. A standardized generic interface for traversing graphs is of utmost importance to encourage reuse of graph algorithms and data structures. Part of the Boost Graph Library is a generic interface that allows access to a graph’s structure, but hides the details of the implementation. This is an “open” interface in the sense that any graph library that implements this interface will be interoperable with the BGL generic algorithms and with other algorithms that also use this interface. The BGL provides some general purpose graph classes that conform to this interface, but they are not meant to be the “only” graph classes; there certainly will be other graph classes that are better for certain situations. We believe that the main contribution of the The BGL is the formulation of this interface.

The BGL graph interface and graph components are generic , in the same sense as the Standard Template Library (STL) [2]. In the following sections, we review the role that generic programming plays in the STL and compare that to how we applied generic programming in the context of graphs.

Of course, if you are already familiar with generic programming, please dive right in! Here’s the Table of Contents. For distributed-memory parallelism, you can also look at the Parallel BGL.

The source for the BGL is available as part of the Boost distribution, which you can download from here.

How to Build the BGL

DON’T! The Boost Graph Library is a header-only library and does not need to be built to be used. The only exceptions are the GraphViz input parser and the GraphML parser.

When compiling programs that use the BGL, be sure to compile with optimization. For instance, select “Release” mode with Microsoft Visual C++ or supply the flag -O2 or -O3 to GCC.

Genericity in STL

There are three ways in which the STL is generic.

Algorithm/Data-Structure Interoperability

First, each algorithm is written in a data-structure neutral way, allowing a single template function to operate on many different classes of containers. The concept of an iterator is the key ingredient in this decoupling of algorithms and data-structures. The impact of this technique is a reduction in the STL’s code size from O(M*N) to O(M+N), where M is the number of algorithms and N is the number of containers. Considering a situation of 20 algorithms and 5 data-structures, this would be the difference between writing 100 functions versus only 25 functions! And the differences continues to grow faster and faster as the number of algorithms and data-structures increase.

Extension through Function Objects

The second way that STL is generic is that its algorithms and containers are extensible. The user can adapt and customize the STL through the use of function objects. This flexibility is what makes STL such a great tool for solving real-world problems. Each programming problem brings its own set of entities and interactions that must be modeled. Function objects provide a mechanism for extending the STL to handle the specifics of each problem domain.

Element Type Parameterization

The third way that STL is generic is that its containers are parameterized on the element type. Though hugely important, this is perhaps the least “interesting” way in which STL is generic. Generic programming is often summarized by a brief description of parameterized lists such as std::list . This hardly scratches the surface!

Genericity in the Boost Graph Library

Like the STL, there are three ways in which the BGL is generic.

Algorithm/Data-Structure Interoperability

First, the graph algorithms of the BGL are written to an interface that abstracts away the details of the particular graph data-structure. Like the STL, the BGL uses iterators to define the interface for data-structure traversal. There are three distinct graph traversal patterns: traversal of all vertices in the graph, through all of the edges, and along the adjacency structure of the graph (from a vertex to each of its neighbors). There are separate iterators for each pattern of traversal.

This generic interface allows template functions such as breadth_first_search() to work on a large variety of graph data-structures, from graphs implemented with pointer-linked nodes to graphs encoded in arrays. This flexibility is especially important in the domain of graphs. Graph data-structures are often custom-made for a particular application. Traditionally, if programmers want to reuse an algorithm implementation they must convert/copy their graph data into the graph library’s prescribed graph structure. This is the case with libraries such as LEDA, GTL, Stanford GraphBase; it is especially true of graph algorithms written in Fortran. This severely limits the reuse of their graph algorithms.

In contrast, custom-made (or even legacy) graph structures can be used as-is with the generic graph algorithms of the BGL, using external adaptation (see Section How to Convert Existing Graphs to the BGL). External adaptation wraps a new interface around a data-structure without copying and without placing the data inside adaptor objects. The BGL interface was carefully designed to make this adaptation easy. To demonstrate this, we have built interfacing code for using a variety of graph structures (LEDA graphs, Stanford GraphBase graphs, and even Fortran-style arrays) in BGL graph algorithms.

Extension through Visitors

Second, the graph algorithms of the BGL are extensible. The BGL introduces the notion of a visitor , which is just a function object with multiple methods. In graph algorithms, there are often several key “event points” at which it is useful to insert user-defined operations. The visitor object has a different method that is invoked at each event point. The particular event points and corresponding visitor methods depend on the particular algorithm. They often include methods like start_vertex() , discover_vertex() , examine_edge() , tree_edge(), and finish_vertex() .

Vertex and Edge Property Multi-Parameterization

The third way that the BGL is generic is analogous to the parameterization of the element-type in STL containers, though again the story is a bit more complicated for graphs. We need to associate values (called “properties”) with both the vertices and the edges of the graph. In addition, it will often be necessary to associate multiple properties with each vertex and edge; this is what we mean by multi-parameterization. The STL std::list class has a parameter T for its element type. Similarly, BGL graph classes have template parameters for vertex and edge “properties”. A property specifies the parameterized type of the property and also assigns an identifying tag to the property. This tag is used to distinguish between the multiple properties which an edge or vertex may have. A property value that is attached to a particular vertex or edge can be obtained via a property map . There is a separate property map for each property.

Traditional graph libraries and graph structures fall down when it comes to the parameterization of graph properties. This is one of the primary reasons that graph data-structures must be custom-built for applications. The parameterization of properties in the BGL graph classes makes them well suited for re-use.

Algorithms

The BGL algorithms consist of a core set of algorithm patterns (implemented as generic algorithms) and a larger set of graph algorithms. The core algorithm patterns are

• Breadth First Search
• Depth First Search
• Uniform Cost Search

By themselves, the algorithm patterns do not compute any meaningful quantities over graphs; they are merely building blocks for constructing graph algorithms. The graph algorithms in the BGL currently include

• Dijkstra’s Shortest Paths
• Bellman-Ford Shortest Paths
• Johnson’s All-Pairs Shortest Paths
• Kruskal’s Minimum Spanning Tree
• Prim’s Minimum Spanning Tree
• Connected Components
• Strongly Connected Components
• Dynamic Connected Components (using Disjoint Sets)
• Topological Sort
• Transpose
• Reverse Cuthill Mckee Ordering
• Smallest Last Vertex Ordering
• Sequential Vertex Coloring

Data Structures

The BGL currently provides two graph classes and an edge list adaptor:

The adjacency_list class is the general purpose “swiss army knife” of graph classes. It is highly parameterized so that it can be optimized for different situations: the graph is directed or undirected, allow or disallow parallel edges, efficient access to just the out-edges or also to the in-edges, fast vertex insertion and removal at the cost of extra space overhead, etc.