год издания — 2006, кол-во страниц — 304, ISBN — 5-469-00352-3, 0-201-72914-8, тираж — 2000, язык — русский, тип обложки — мягк., масса книги — 360 гр., издательство — Питер

серия — Библиотека программиста

КНИГА СНЯТА С ПРОДАЖИ

Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine
THE BOOST GRAPH LIBRARY
User Guide and Reference Manual

Addison-Wesley, 2002

Пер. с англ. Р. Сузи

Формат 70x100 1/16

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

Предисловие	11

Введение	15

Обобщённое программирование	16
Немного из истории BGL	17
Что такое Boost?	18
Получение и установка программного обеспечения BGL	18
Как пользоваться книгой	19
Грамотное программирование	20
Благодарности	21
Лицензия	22
От издательства	22

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

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

1.1. Немного терминологии из теории графов	24
1.2. Графовые концепции	26
1.2.1. Описатели вершин и рёбер	26
1.2.2. Отображение свойств	27
1.2.3. Обход графа	28
1.2.4. Создание и модификация графа	29
1.2.5. Посетители алгоритмов	30
1.3. Классы и адаптеры графов	32
1.3.1. Классы графов	32
1.3.2. Адаптеры графов	33
1.4. Обобщённые алгоритмы на графах	34
1.4.1. Обобщённый алгоритм топологической сортировки	34
1.4.2. Обобщённый алгоритм поиска в глубину	38

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

2.1. Введение	39
2.1.1. Полиморфизм в объектно-ориентированном программировании	40
2.1.2. Полиморфизм в обобщённом программировании	41
2.1.3. Сравнение ОП и ООП	41
2.2. Обобщённое программирование и STL	44
2.3. Концепции и модели	47
2.3.1. Наборы требований	47
2.3.2. Пример: Inputlterator	48
2.4. Ассоциированные типы и классы свойств	49
2.4.1. Ассоциированные типы в шаблонах функций	49
2.4.2. Определители типов, вложенные в классах	49
2.4.3. Определение класса свойств	50
2.4.4. Частичная специализация	51
2.4.5. Диспетчеризация тегов	52
2.5. Проверка концепции	53
2.5.1. Классы для проверки концепций	54
2.5.2. Прототипы концепций	55
2.6. Пространство имён	56
2.6.1. Классы	56
2.6.2. Поиск Кенига	56
2.7. Именованные параметры функций	58

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

3.1. Зависимости между файлами	59
3.2. Подготовка графа	60
3.2.1. Решаем, какой графовый класс использовать	61
3.2.2. Строим граф с помощью итераторов рёбер	61
3.3. Порядок компиляции	62
3.3.1. Топологическая сортировка через поиск в глубину	62
3.3.2. Маркировка вершин с использованием внешних свойств	64
3.3.3. Доступ к смежным вершинам	64
3.3.4. Обход всех вершин	65
3.4. Циклические зависимости	66
3.5. «На пути» к обобщённому поиску в глубину: посетители	67
3.6. Подготовка графа: внутренние свойства	69
3.7. Время компиляции	71
3.8. Обобщённая топологическая сортировка и поиск в глубину	72
3.9. Время параллельной компиляции	74
3.10. Итоги	76

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

4.1. Поиск в ширину	77
4.1.1. Определения	77
4.1.2. Шесть степеней Кевина Бэкона	78
4.2. Поиск в глубину	82
4.2.1. Определения	83
4.2.2. Нахождение циклов в графах потоков управления программы	84

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

5.1. Определения	89
5.2. Маршрутизация в Интернете	90
5.3. Алгоритм Беллмана-Форда и маршрутизация с помощью вектора
расстояний	91
5.4. Маршрутизация с учётом состояния линии и алгоритм Дейкстры	95

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

6.1. Определения	102
6.2. Планирование телефонной сети	102
6.3. Алгоритм Краскала	104
6.4. Алгоритм Прима	106

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

7.1. Определения	109
7.2. Связные компоненты и связность Интернета	110
7.3. Сильные компоненты связности и ссылки веб-страниц	114

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

8.1. Определения	117
8.2. Рёберная связность	118

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

9.1. Ходы конём как граф	125
9.2. Поиск с возвратом на графе	127
9.3. Эвристика Варнсдорфа	128

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

10.1. Использование топологической сортировки из BGL с графом из LEDA	131
10.2. Использование топологической сортировки из BGL с графом из SGB	132
10.3. Реализация адаптеров графов	134

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

11.1. Сравнения графовых классов	137
11.1.1. Результаты и обсуждение	138
11.2. Итоги главы	144

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

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

12.1. Концепции обхода графов	146
12.1.1. Неориентированные графы	148
12.1.2. Graph	151
12.1.3. IncidenceGraph	152
12.1.4. BidirectionalGraph	153
12.1.5. AdjacencyGraph	154
12.1.6. VertexListGraph	155
12.1.7. EdgeListGraph	156
12.1.8. AdjacencyMatrix	157
12.2. Концепции для изменения графов	157
12.2.1. VertexMutableGraph	159
12.2.2. EdgeMutableGraph	160
12.2.3. MutablelncidenceGraph	161
12.2.4. MutableBidirectionalGraph	161
12.2.5. MutableEdgeListGraph	162
12.2.6. PropertyGraph	162
12.2.7. VertexMutablePropertyGraph	163
12.2.8. EdgeMutablePropertyGraph	164
12.3. Концепции посетителей	164
12.3.1. BFSVisitor	165
12.3.2. DFSVisitor	166
12.3.3. DijkstraVisitor	167
12.3.4. BellmanFordVisitor	168

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

13.1. Обзор	170
13.1.1. Информация об алгоритме	171
13.2. Базовые алгоритмы	172
13.2.1. breadth_first_search	172
13.2.2. breadth_first_visit	176
13.2.3 depth_first_search	177
13.2.4. depth_first_visit	181
13.2.5. topological_sort	182
13.3. Алгоритмы кратчайших путей	183
13.3.1. dijkstra_shortest_paths	183
13.3.2. bellman_ford_shortest_paths	188
13.3.3. johnson_all_pairs_shortest_paths	191
13.4. Алгоритмы минимальных осговных деревьев	194
13.4.1. kruskal_minimum_spanning_tree	194
13.4.2. prim_minimum_spanning_tree	197
13.5. Статические компоненты связности	200
13.5.1. connected_components	200
13.5.2. strong_components	202
13.6. Растущие компоненты связности	205
13.6.1. initialize_incremental_components	207
13.6.2. incrementaLcomponents	207
13.6.3. same_component	207
13.6.4. component_index	208
13.7. Алгоритмы максимального потока	209
13.7.1. edmunds_karp_max_flow	209
13.7.2. push_relabel_max_flow	212

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

14.1. Классы графов	215
14.1.1. adjacency_list	215
14.1.2. adjacency_matrix	235
14.2. Вспомогательные классы	243
14.2.1. graph_traits	243
14.2.2. adjacency_list_traits	246
14.2.3. adjacency_matrix_traits	247
14.2.4. property_map	248
14.2.5. property	249
14.3. Графовые адаптеры	250
14.3.1. edge_list	250
14.3.2. reverse_graph	252
14.3.3. filtered_graph	256
14.3.4. Указатель на SGB Graph	261
14.3.5. GRAPH<V,E> из библиотеки LEDA	265
14.3.6. std::vector<EdgeList>	271

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

15.1. Концепции отображений свойств	275
15.1.1. ReadablePropertyMap	276
15.1.2. WritablePropertyMap	277
15.1.3. ReadWritePropertyMap	277
15.1.4. LvaluePropertyMap	278
15.2. Классы отображений свойств	278
15.2.1. property_traits	278
15.2.2. iterator_property_map	280
15.2.3. Теги свойств	281
15.3. Создание пользовательских отображений свойств	282
15.3.1. Отображения свойств для Stanford GraphBase	282
15.3.2. Отображение свойств из std::map	283

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

16.1. Buffer	284
16.2. ColorValue	285
16.3. MultiPassInputlterator	285
16.4. Monoid	286
16.5. mutable_queue	286
16.6. Непересекающиеся множества	288
16.6.1. disjoint_sets	288
16.6.2. find_with_path_halving	290
16.6.3. find_with_full_path_compression	290
16.7. tie	290
16.8. graph_property_iter_range	291

Библиография	294

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

Теория графов	297
C++ и STL	297

Алфавитный указатель	299

Книги на ту же тему

Стандарты программирования на C++: 101 правило и рекомендации, Саттер Г., Александреску А., 2015
Современное проектирование на C++: Обобщённое программирование и прикладные шаблоны проектирования, Александреску А., 2015
Моя первая программа на C/C++, Нейбауэр А. Р., 1995
Основы программирования на языках C и C++, Ашарина И. В., 2002
Справочник программиста по C/C++. — 2-е изд., Шилдт Г., 2001
Начальный курс C и C++, Березин Б. И., Березин С. Б., 2001
Язык программирования C. Лекции и упражнения. — 6-е изд., Прата С., 2015
UNIX. Профессиональное программирование. — 2-е изд., Стивенс Р., Раго С., 2007

elapsed time 0.020 sec

/ИТ-книги

ОГЛАВЛЕНИЕ

Книги на ту же тему