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

Джереми Сик, Лай-Кван Ли, Эндрю Ламсдэйн

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

Издательство: Питер, 2006 г.

ISBN 5-469-00352-3, 0-201-72914-8

Количество страниц: 304.

Содержание книги «C++ Boost Graph Library. Библиотека программиста»:

11 Предисловие
15 Введение
- 16 Обобщенное программирование
- 17 Немного из истории BGL
- 18 Что такое Boost?
- 18 Получение и установка программного обеспечения BGL
- 19 Как пользоваться книгой
- 20 Грамотное программирование
- 21 Благодарности
- 22 Лицензия
- 22 От издательства
23 Часть I. Руководство пользователя
24 Глава 1. Введение
- 24 1.1. Немного терминологии из теории графов
- 26 1.2. Графовые концепции
  - 26 1.2.1. Описатели вершин и ребер
  - 27 1.2.2. Отображение свойств
  - 28 1.2.3. Обход графа
  - 29 1.2.4. Создание и модификация графа
  - 30 1.2.5. Посетители алгоритмов
- 32 1.3. Классы и адаптеры графов
  - 32 1.3.1. Классы графов
  - 33 1.3.2. Адаптеры графов
- 34 1.4. Обобщенные алгоритмы на графах
  - 34 1.4.1. Обобщенный алгоритм топологической сортировки
  - 38 1.4.2. Обобщенный алгоритм поиска в глубину
39 Глава 2. Обобщенное программирование в C++
- 39 2.1. Введение
  - 40 2.1.1. Полиморфизм в объектно-ориентированном программировании
  - 41 2.1.2. Полиморфизм в обобщенном программировании
  - 41 2.1.3. Сравнение ОП и ООП
- 44 2.2. Обобщенное программирование и STL
- 47 2.3. Концепции и модели
  - 47 2.3.1. Наборы требований
  - 48 2.3.2. Пример: InputIterator
- 49 2.4. Ассоциированные типы и классы свойств
  - 49 2.4.1. Ассоциированные типы в шаблонах функций
  - 49 2.4.2. Определители типов, вложенные в классах
  - 50 2.4.3. Определение класса свойств
  - 51 2.4.4. Частичная специализация
  - 52 2.4.5. Диспетчеризация тегов
- 53 2.5. Проверка концепции
  - 54 2.5.1. Классы для проверки концепций
  - 55 2.5.2. Прототипы концепций
- 56 2.6. Пространство имен
  - 56 2.6.1. Классы
  - 56 2.6.2. Поиск Кенига
- 58 2.7. Именованные параметры функций
59 Глава 3. Изучаем BGL
- 59 3.1. Зависимости между файлами
- 60 3.2. Подготовка графа
  - 61 3.2.1. Решаем, какой графовый класс использовать
  - 61 3.2.2. Строим граф с помощью итераторов ребер
- 62 3.3. Порядок компиляции
  - 62 3.3.1. Топологическая сортировка через поиск в глубину
  - 64 3.3.2. Маркировка вершин с использованием внешних свойств
  - 64 3.3.3. Доступ к смежным вершинам
  - 65 3.3.4. Обход всех вершин
- 66 3.4. Циклические зависимости
- 67 3.5. "На пути" к обобщенному поиску в глубину: посетители
- 69 3.6. Подготовка графа: внутренние свойства
- 71 3.7. Время компиляции
- 72 3.8. Обобщенная топологическая сортировка и поиск в глубину
- 74 3.9. Время параллельной компиляции
- 76 3.10. Итоги
77 Глава 4. Основные алгоритмы на графах
- 77 4.1. Поиск в ширину
  - 77 4.1.1. Определения
  - 78 4.1.2. Шесть степеней Кевина Бэкона
- 82 4.2. Поиск в глубину
  - 83 4.2.1. Определения
  - 84 4.2.2. Нахождение циклов в графах потоков управления программы
89 Глава 5. Задачи нахождения кратчайших путей
- 89 5.1. Определения
- 90 5.2. Маршрутизация в Интернете
- 91 5.3. Алгоритм Беллмана-Форда и маршрутизация с помощью вектора расстояний
- 95 5.4. Маршрутизация с учетом состояния линии и алгоритм Дейкстры
102 Глава 6. Задача минимального остовного дерева
- 102 6.1. Определения
- 102 6.2. Планирование телефонной сети
- 104 6.3. Алгоритм Краскала
- 106 6.4. Алгоритм Прима
109 Глава 7. Компоненты связности
- 109 7.1. Определения
- 110 7.2. Связные компоненты и связность Интернета
- 114 7.3. Сильные компоненты связности и ссылки веб-страниц
117 Глава 8. Максимальный поток
- 117 8.1. Определения
- 118 8.2. Реберная связность
124 Глава 9. Неявные графы: обход конем
- 125 9.1. Ходы конем как граф
- 127 9.2. Поиск с возвратом на графе
- 128 9.3. Эвристика Варнсдорфа
130 Глава 10. Взаимодействие с другими графовыми библиотеками
- 131 10.1. Использование топологической сортировки из BGL с графом из LEDA
- 132 10.2. Использование топологической сортировки из BGL с графом из SGB
- 134 10.3. Реализация адаптеров графов
137 Глава 11. Руководство по производительности
- 137 11.1. Сравнения графовых классов
  - 138 11.1.1. Результаты и обсуждение
- 144 11.2. Итоги главы
145 Часть II. Справочное руководство
146 Глава 12. Концепции BGL
- 146 12.1. Концепции обхода графов
  - 148 12.1.1. Неориентированные графы
  - 151 12.1.2. Graph
  - 152 12.1.3. IncidenceGraph
  - 153 12.1.4. BidirectionalGraph
  - 154 12.1.5. AdjacencyGraph
  - 155 12.1.6. VertexListGraph
  - 156 12.1.7. EdgeListGraph
  - 157 12.1.8. AdjacencyMatrix
- 157 12.2. Концепции для изменения графов
  - 159 12.2.1. VertexMutableGraph
  - 160 12.2.2. EdgeMutableGraph
  - 161 12.2.3. MutableIncidenceGraph
  - 161 12.2.4. MutableBidirectionalGraph
  - 162 12.2.5. MutableEdgeListGraph
  - 162 12.2.6. PropertyGraph
  - 163 12.2.7. VertexMutablePropertyGraph
  - 164 12.2.8. EdgeMutablePropertyGraph
- 164 12.3. Концепции посетителей
  - 165 12.3.1. BFSVisitor
  - 166 12.3.2. DFSVisitor
  - 167 12.3.3. DijkstraVisitor
  - 168 12.3.4. BellmanFordVisitor
170 Глава 13. Алгоритмы BGL
- 170 13.1. Обзор
  - 171 13.1.1. Информация об алгоритме
- 172 13.2. Базовые алгоритмы
  - 172 13.2.1. breadth_first_search
  - 176 13.2.2. breadth_firs_visit
  - 177 13.2.3 depth_first_search
  - 181 13.2.4. depth_first_visit
  - 182 13.2.5. topological_sort
- 183 13.3. Алгоритмы кратчайших путей
  - 183 13.3.1. dijkstra_shortest_paths
  - 188 13.3.2. bellman_ford_shortest_paths
  - 191 13.3.3. Johnson_all_pairs_shortest_paths
- 194 13.4. Алгоритмы минимальных остовных деревьев
  - 194 13.4.1. kruskal_minimum_spanning_tree
  - 197 13.4.2. prim_rninimum_spanning_tree
- 200 13.5. Статические компоненты связности
  - 200 13.5.1. connected_components
  - 202 13.5.2. strong_components
- 205 13.6. Растущие компоненты связности
  - 207 13.6.1. initialize_incremental_components
  - 207 13.6.2. incremental_components
  - 207 13.6.3. same_component
  - 208 13.6.4. component_index
- 209 13.7. Алгоритмы максимального потока
  - 209 13.7.1. edmunds_karp_max_flow
  - 212 13.7.2. push_relabel_max_flow
215 Глава 14. Классы BGL
- 215 14.1. Классы графов
  - 215 14.1.1. adjacency_list
  - 235 14.1.2. adjacency_matrix
- 243 14.2. Вспомогательные классы
  - 243 14.2.1. graph_traits
  - 246 14.2.2. adjacency_list_traits
  - 247 14.2.3. adjacency_matrix_traits
  - 248 14.2.4. property_map
  - 249 14.2.5. property
- 250 14.3. Графовые адаптеры
  - 250 14.3.1. edge_list
  - 252 14.3.2. reverse_graph
  - 256 14.3.3. fittered_graph
  - 261 14.3.4. Указатель на SGB Graph
  - 265 14.3.5. GRAPH<V,E> из библиотеки LEDA
  - 271 14.3.6. std::vector<EdgeList>
274 Глава 15. Библиотека отображений свойств
- 275 15.1. Концепции отображений свойств
  - 276 15.1.1. ReadablePropertyMap
  - 277 15.1.2. WritablePropertyMap
  - 277 15.1.3. ReadWritePropertyMap
  - 278 15.1.4. LvaluePropertyMap
- 278 15.2. Классы отображений свойств
  - 278 15.2.1. property_traits
  - 280 15.2.2. iterator_property_map
  - 281 15.2.3. Теги свойств
- 282 15.3. Создание пользовательских отображений свойств
  - 282 15.3.1. Отображения свойств для Stanford GraphSase
  - 283 15.3.2. Отображение свойств из std::map
284 Глава 16. Вспомогательные концепции, классы и функции
- 284 16.1. Buffer
- 285 16.2. ColorValue
- 285 16.3. MultiPassInputIterator
- 286 16.4. Monoid
- 286 16.5. mutable_queue
- 288 16.6. Непересекающиеся множества
  - 288 16.6.1. disjoint_sets
  - 290 16.6.2. find_with_path_halving
  - 290 16.6.3. find_with_full_path_compression
- 290 16.7. tie
- 291 16.8. graph_property_iter_range
294 Библиография
297 Дополнение к библиографии
- 297 Теория графов
- 297 C++ и STL
299 Алфавитный указатель

Инструкция как скачать книгу Джереми Сик, Лай-Кван Ли, Эндрю Ламсдэйн: C++ Boost Graph Library. Библиотека программиста в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.