Графики — это математические абстракции, которые полезны для решения многих типов задач в информатике. Следовательно, эти абстракции должны быть представлены в компьютерных программах. Стандартизированный общий интерфейс для пересечения графов имеет первостепенное значение для поощрения повторного использования алгоритмов графов и структур данных. Часть библиотеки Boost Graph Library представляет собой общий интерфейс, который позволяет получить доступ к структуре графа, но скрывает детали реализации. Это интерфейс в том смысле, что любая графовая библиотека, которая реализует этот интерфейс, будет совместима с общими алгоритмами BGL и с другими алгоритмами, которые также используют этот интерфейс. BGL предоставляет некоторые классы графов общего назначения, которые соответствуют этому интерфейсу, но они не предназначены для классов графов “only ”; безусловно, будут другие классы графов, которые лучше для определенных ситуаций. Мы считаем, что основной вклад BGL заключается в разработке этого интерфейса.
Интерфейс графа BGL и компоненты графа обычны, в том же смысле, что и Стандартная библиотека шаблонов (STL) [2]. В следующих разделах мы рассмотрим роль, которую играет общее программирование в STL, и сравним это с тем, как мы применяли общее программирование в контексте графов.
Конечно, если вы уже знакомы с общим программированием, пожалуйста, ныряйте прямо в него! Вот таблица содержимого . Для распределённого параллелизма памяти можно также посмотреть на Параллельный BGL.
Источник для BGL доступен как часть дистрибутива Boost, который вы можете загрузить отсюда .
Как создать BGL
Не надо! Библиотека с расширенным графиком - это библиотека только для заголовков, и ее не нужно строить для использования. Исключение составляют только парсер ввода GraphViz и парсер GraphML.
При составлении программ, использующих BGL, обязательно компилируйте с оптимизацией. Например, выберите режим “Release” с Microsoft Visual C++ или подайте флаг. -O2 или -O3 в 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<T>. 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 dstructures (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<T> 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
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.
The adjacency_matrix class stores edges in a |V| x |V|
matrix (where |V| is the number of vertices). The elements of
this matrix represent edges in the graph. Adjacency matrix
representations are especially suitable for very dense graphs, i.e.,
those where the number of edges approaches |V|2.
The edge_list class is an adaptor that takes any kind of edge
iterator and implements an Edge List Graph.
