# Clone the repository
git clone https://github.com/alibaba/AliSQL.git
cd AliSQL

# Build (release mode)
sh build.sh -t release -d ~/alisql

# Install
make install

# Initialize data directory
~/alisql/bin/mysqld --initialize-insecure --datadir=~/alisql/data

# Start the server with DuckDB enabled for the example below
~/alisql/bin/mysqld --datadir=~/alisql/data --duckdb_mode=ON

-- Create an analytical table with DuckDB engine
CREATE TABLE sales_analytics (
    sale_date DATE,
    product_id INT,
    revenue DECIMAL(10,2),
    quantity INT
) ENGINE=DuckDB;

-- Run an analytical aggregation through DuckDB
SELECT
    DATE_FORMAT(sale_date, '%Y-%m') as month,
    SUM(revenue) as total_revenue,
    COUNT(*) as transactions
FROM sales_analytics
GROUP BY month
ORDER BY total_revenue DESC;

-- Vector features are disabled by default and vector indexes require RC.
SET GLOBAL vidx_disabled = OFF;
SET SESSION transaction_isolation = 'READ-COMMITTED';

-- Create a table with a vector column
CREATE TABLE embeddings (
    id INT PRIMARY KEY,
    content TEXT,
    embedding VECTOR(3)
) ENGINE=InnoDB;

INSERT INTO embeddings VALUES
    (1, 'first document', VEC_FROMTEXT('[0.1,0.2,0.3]')),
    (2, 'second document', VEC_FROMTEXT('[0.2,0.1,0.4]'));

-- Create HNSW index for fast ANN search
CREATE VECTOR INDEX idx_embedding ON embeddings(embedding) DISTANCE=COSINE;

-- Find similar items using cosine distance
SELECT id, content,
       VEC_DISTANCE_COSINE(
           embedding, VEC_FROMTEXT('[0.1,0.2,0.3]')
       ) AS distance
FROM embeddings
ORDER BY distance
LIMIT 10;

Q4 2025  ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
         [x] DuckDB Storage Engine  [x] Vector Index (VIDX)   [x] 8.0.44 Release

2026     ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
         [x] Native Flashback       [x] Transaction & Binlog   [ ] DDL / RTO
             - AS OF TIMESTAMP          - Binlog in Redo V2       - Instant DDL
             - Undo snapshots           - Free Flush               - Fast Crash Recovery
                                        - Realtime Replication

# Install
curl -LsSf https://raw.githubusercontent.com/aliyun/rdsai-cli/main/install.sh | sh

# Connect and ask in natural language
rdsai --host localhost -u root -p secret -D mydb
mysql> analyze index usage on users table
mysql> show me slow queries from the last hour
mysql> why this query is slow: SELECT * FROM users WHERE name LIKE '%john%'

$ python3 -m venv .venv
$ source ~/.venv/bin/activate

(.venv)$ cd boost-root
(.venv)$ pip install -r libs/gil/doc/requirements.txt

$ echo "using doxygen ;" > ~/user-config.jam
$ cd boost-root
$ b2 libs/gil/doc

Implementation specification for Stored Procedures
          ==================================================

(BOOST_LIKELY(!!(expr))? ((void)0): ::boost::assertion_failed(#expr,
    BOOST_CURRENT_FUNCTION, __FILE__, __LINE__))

namespace boost
{
    void assertion_failed(char const * expr, char const * function,
        char const * file, long line);
}

(BOOST_LIKELY(!!(expr))? ((void)0): ::boost::assertion_failed_msg(#expr,
    msg, BOOST_CURRENT_FUNCTION, __FILE__, __LINE__))

namespace boost
{
    void assertion_failed_msg(char const * expr, char const * msg,
        char const * function, char const * file, long line);
}

void MyContainer::erase(iterator i)
{
// Some sanity checks, data must be ordered
#ifndef BOOST_ASSERT_IS_VOID

    if(i != c.begin()) {
        iterator prev = i;
        --prev;
        BOOST_ASSERT(*prev < *i);
    }
    else if(i != c.end()) {
        iterator next = i;
        ++next;
        BOOST_ASSERT(*i < *next);
    }

#endif

    this->erase_impl(i);
}

namespace boost
{

struct source_location
{
  constexpr source_location() noexcept;
  constexpr source_location(char const* file, uint_least32_t line,
    char const* function, uint_least32_t column = 0) noexcept;

  constexpr char const* file_name() const noexcept;
  constexpr char const* function_name() const noexcept;
  constexpr uint_least32_t line() const noexcept;
  constexpr uint_least32_t column() const noexcept;
};

template<class E, class T>
  std::basic_ostream<E, T> &
  operator<<( std::basic_ostream<E, T> & os, source_location const & loc );

} // namespace boost

#define BOOST_CURRENT_LOCATION \
  ::boost::source_location(__FILE__, __LINE__, BOOST_CURRENT_FUNCTION)

constexpr source_location() noexcept;

constexpr source_location(char const* file, uint_least32_t line,
  char const* function, uint_least32_t column = 0) noexcept;

template<class E, class T>
  std::basic_ostream<E, T> &
  operator<<( std::basic_ostream<E, T> & os, source_location const & loc );

#define BOOST_CURRENT_LOCATION \
  ::boost::source_location(__FILE__, __LINE__, BOOST_CURRENT_FUNCTION)

#define BOOST_CURRENT_LOCATION ::boost::source_location()

Probably the most common case to read a tiff image can be done as follows::

    std::string filename( "image.tif" );
    rgb8_image_t img;
    read_image( filename, img, tiff_tag() );

The code would be same for all other image formats. The only thing that needs
to change is the tag type ( tiff_tag ) in the read_image call.
The read_image() expects the supplied image type to be compatible with the
image stored in the file. If the user doesn't know what format an image has she
can use read_and_convert_image().
Another important fact is that read_image() will allocate the appropriate
memory needed for the read operation. There are ``read_view`` or
``read_and_convert_view`` counterparts, if the memory is already allocated.

Sometimes the user only wants to read a sub-part of an image,
then the above call would look as follows::

    read_image( filename
              , img
              , image_read_settings< tiff_tag >( point_t( 0, 0 ), point_t( 50, 50 ) )
              );

The image_read_settings class will provide the user with image format
independent reading setting but can also serves as a pointer for format
dependent settings.
Please see the specific image format sections
[link gil.io.using_io.supported_image_formats Supported Image Formats]
for more details.

Writing An Image

std::string filename( "image.tif" );
rgb8_image_t img( 640, 480 );

// write data into image

write_view( filename
          , view( img )
          , tiff_tag()
          );

std::string filename( "image.jpg" );
rgb8_image_t img( 640, 480 );

// write data into image

write_view( filename
          , view( img )
          , image_write_info< jpeg_tag >( 95 )
          );

Reading and writing in-memory buffers are supported as well. See as follows::

    // 1. Read an image.
    ifstream in( "test.tif", ios::binary );

    rgb8_image_t img;
    read_image( in, img, tiff_tag() );

    // 2. Write image to in-memory buffer.
    stringstream out_buffer( ios_base::out | ios_base::binary );

    rgb8_image_t src;
    write_view( out_buffer, view( src ), tiff_tag() );

    // 3. Copy in-memory buffer to another.
    stringstream in_buffer( ios_base::in | ios_base::binary );
    in_buffer << out_buffer.rdbuf();

    // 4. Read in-memory buffer to gil image
    rgb8_image_t dst;
    read_image( in_buffer, dst, tag_t() );

    // 5. Write out image.
    string filename( "out.tif" );
    ofstream out( filename.c_str(), ios_base::binary );
    write_view( out, view( dst ), tiff_tag() );

In case the user is using his own stream classes he has to make sure it
has the common interface read, write, seek, close, etc. Interface.

Using IO
--------

General Overview
~~~~~~~~~~~~~~~~

The tutorial pointed out some use cases for reading and writing images in
various image formats. This section will provide a more thorough overview.

The next sections will introduce the Read and Write interface. But it might be
worth pointing out that by using some advanced metaprogramming techniques the
interface is rather small and hopefully easy to understand.

Besides the general interface the user also has the ability to interface
directly with the underlying image format. For that each reader or writer
provides access to the so-called backend.

For instance::

    typedef get_reader_backend< const std::string
                              , tag_t
                              >::type backend_t;

    backend_t backend = read_image_info( bmp_filename
                                       , tag_t()
                                       );

    BOOST_CHECK_EQUAL( backend._info._width , 127 );
    BOOST_CHECK_EQUAL( backend._info._height, 64 );

Of course, the typedef can be removed when using c++11's auto feature.

Read Interface
~~~~~~~~~~~~~~

As the Tutorial demonstrated there are a few ways to read images.
Here is an enumeration of all read functions with a short description:

* ``read_image`` - read into a gil image with no conversion.
  Memory is allocated.
* ``read_view`` - read into a gil view with no conversion.
* ``read_and_convert_image`` - read and convert into a gil image.
  Memory is allocated.
* ``read_and_convert_view`` - read and convert into a gil view.
* ``read_image_info`` - read the image header.

Conversion in this context is necessary if the source (file) has an
incompatible color space with the destination (gil image type).
If that's the case the user has to use the xxx_and_convert_xxx variants.

All functions take the filename or a device as the first parameter.
The filename can be anything from a C-string, ``std::string``,
``std::wstring`` and ``boost::filesystem`` path. When using the path
object the user needs to define the ADD_FS_PATH_SUPPORT compiler symbol to
include the boost::filesystem dependency.
Devices could be a ``FILE*``, ``std::ifstream``, and ``TIFF*`` for TIFF images.

The second parameter is either an image or view type depending on the
``read_xxx`` function.
The third and last parameter is either an instance of the
``image_read_settings<FormatTag>`` or just the ``FormatTag``.
The settings can be various depending on the format which is being read.
But the all share settings for reading a partial image area.
The first point describes the top left image coordinate whereas the second
are the dimensions in x and y directions.

Here an example of setting up partial read::

    read_image( filename
              , img
              , image_read_settings< tiff_tag >( point_t( 0, 0 ), point_t( 50, 50 ) )
              );

Each format supports reading just the header information,
using ``read_image_info``. Please refer to the format specific sections
under 3.3. A basic example follows::

    image_read_info< tiff_t > info = read_image_info( filename
                                                    , tiff_t()
                                                    );

GIL also comes with a dynamic image extension.
In the context of GIL.IO a user can define an ``any_image`` type based on
several image types. The IO extension would then pick the matching image type
to the current image file.
The following example shows this feature::

    typedef mpl::vector< gray8_image_t
                       , gray16_image_t
                       , rgb8_image_t
                       , rgba_image_t
                       > my_img_types;

    any_image< my_img_types > runtime_image;

    read_image( filename
              , runtime_image
              , tiff_tag()
              );

During the review it became clear that there is a need to read big images
scanline by scanline. To support such use case a ``scanline_reader`` is
implemented for all supported image formats.
The ``scanline_read_iterators`` will then allow to traverse through the image.
The following code sample shows the usage::

    typedef tiff_tag tag_t;

    typedef scanline_reader< typename get_read_device< const char*
                                                     , tag_t
                                                     >::type
                            , tag_t
                            > reader_t;

    reader_t reader = make_scanline_reader( "C:/boost/libs/gil/test/extension/io/images/tiff/test.tif", tag_t() );

    typedef rgba8_image_t image_t;

    image_t dst( reader._info._width, reader._info._height );
    fill_pixels( view(dst), image_t::value_type() );

    typedef reader_t::iterator_t iterator_t;

    iterator_t it  = reader.begin();
    iterator_t end = reader.end();

    for( int row = 0; it != end; ++it, ++row )
    {
        copy_pixels( interleaved_view( reader._info._width
                                        , 1
                                        , ( image_t::view_t::x_iterator ) *it
                                        , reader._scanline_length
                                        )
                    , subimage_view( view( dst )
                                    , 0
                                    , row
                                    , reader._info._width
                                    , 1
                                    )
                    );
    }

There are many ways to traverse an image but for as of now only by
scanline is supported.


Write Interface
~~~~~~~~~~~~~~~

There is only one function for writing out images, write_view.
Similar to reading the first parameter is either a filename or a device.
The filename can be anything from a C-string, ``std::string``,
``std::wstring``, and ``boost::filesystem`` path. When using the path object
the user needs to define the ``ADD_FS_PATH_SUPPORT`` compiler symbol to
include the ``boost::filesystem`` dependency.
Devices could be ``FILE*``, ``std::ifstream``, and ``TIFF*`` for TIFF images.

The second parameter is an view object to image being written.
The third and last parameter is either a tag or an
``image_write_info<FormatTag>`` object containing more settings.
One example for instance is the JPEG quality.
Refer to the format specific sections under 3.3. to have a list of all
the possible settings.

Writing an any_image<...> is supported. See the following example::

    typedef mpl::vector< gray8_image_t
                       , gray16_image_t
                       , rgb8_image_t
                       , rgba_image_t
                       > my_img_types;


    any_image< my_img_types > runtime_image;

    // fill any_image

    write_view( filename
              , view( runtime_image )
              , tiff_tag()
              );

Compiler Symbols
~~~~~~~~~~~~~~~~

The following table gives an overview of all supported compiler symbols
that can be set by the user:

.. comment [table Compiler Symbols

======================================================== ========================================================
   Symbol                                                   Description
======================================================== ========================================================
BOOST_GIL_IO_ENABLE_GRAY_ALPHA                           Enable the color space "gray_alpha".
BOOST_GIL_IO_ADD_FS_PATH_SUPPORT                         Enable boost::filesystem 3.0 library.
BOOST_GIL_IO_PNG_FLOATING_POINT_SUPPORTED                Use libpng in floating point mode. This symbol is incompatible with BOOST_GIL_IO_PNG_FIXED_POINT_SUPPORTED.
BOOST_GIL_IO_PNG_FIXED_POINT_SUPPORTED                   Use libpng in integer mode. This symbol is incompatible with BOOST_GIL_IO_PNG_FLOATING_POINT_SUPPORTED.
BOOST_GIL_IO_PNG_DITHERING_SUPPORTED                     Look up "dithering" in libpng manual for explanation.
BOOST_GIL_IO_PNG_1_4_OR_LOWER                            Allow compiling with libpng 1.4 or lower.
BOOST_GIL_EXTENSION_IO_JPEG_C_LIB_COMPILED_AS_CPLUSPLUS  libjpeg is compiled as c++ lib.
BOOST_GIL_EXTENSION_IO_PNG_C_LIB_COMPILED_AS_CPLUSPLUS   libpng is compiled as c++ lib.
BOOST_GIL_EXTENSION_IO_TIFF_C_LIB_COMPILED_AS_CPLUSPLUS  libtiff is compiled as c++ lib.
BOOST_GIL_EXTENSION_IO_ZLIB_C_LIB_COMPILED_AS_CPLUSPLUS  zlib is compiled as c++ lib.
BOOST_GIL_IO_TEST_ALLOW_READING_IMAGES                   Allow basic test images to be read from local hard drive. The paths can be set in paths.hpp
BOOST_GIL_IO_TEST_ALLOW_WRITING_IMAGES                   Allow images to be written to the local hard drive. The paths can be set in paths.hpp
BOOST_GIL_IO_USE_BMP_TEST_SUITE_IMAGES                   Run tests using the bmp test images suite. See _BMP_TEST_FILES
BOOST_GIL_IO_USE_PNG_TEST_SUITE_IMAGES                   Run tests using the png test images suite. See _PNG_TEST_FILES
BOOST_GIL_IO_USE_PNM_TEST_SUITE_IMAGES                   Run tests using the pnm test images suite. Send me an email for accessing the files.
BOOST_GIL_IO_USE_TIFF_LIBTIFF_TEST_SUITE_IMAGES          Run tests using the targa file format test images suite. See _TIFF_LIB_TIFF_TEST_FILES
BOOST_GIL_IO_USE_TIFF_GRAPHICSMAGICK_TEST_SUITE_IMAGES   Run tests using the targa file format test images suite. See _TIFF_GRAPHICSMAGICK_TEST_FILES
======================================================== ========================================================

Supported Image Formats
~~~~~~~~~~~~~~~~~~~~~~~

BMP
+++

For a general overview of the BMP image file format go to the
following BMP_Wiki_.

Please note, the code has not been tested on X Windows System variations
of the BMP format which are usually referred to XBM and XPM formats.

Here, only the MS Windows and OS/2 format is relevant.

Currently the code is able to read and write the following image types:

:Read: ``gray1_image_t``, ``gray4_image_t``, ``gray8_image_t``, ``rgb8_image_t`` and, ``rgba8_image_t``
:Write: ``rgb8_image_t`` and, ``rgba8_image_t``

The lack of having an indexed image type in gil restricts the current
interface to only write out non-indexed images.
This is subject to change soon.

JPEG
++++

For a general overview of the JPEG image file format go to the
following JPEG_Wiki_.

This jpeg extension is based on the libjpeg library which can be
found here, JPEG_Lib_.

All versions starting from 8x are supported.

The user has to make sure this library is properly installed.
I strongly recommend the user to build the library yourself.
It could potentially save you a lot of trouble.

Currently the code is able to read and write the following image types:

:Read: ``gray8_image_t``, ``rgb8_image_t``, ``cmyk8_image_t``
:Write: ``gray8_image_t``, ``rgb8_image_t``, ``cmyk8_image_t``

Reading YCbCr or YCCK images is possible but might result in inaccuracies since
both color spaces aren't available yet for gil.
For now these color space are read as rgb images.
This is subject to change soon.

PNG
+++

For a general overview of the PNG image file format go to the
following PNG_Wiki_.

This png extension is based on the libpng, which can be found
here, PNG_Lib_.

All versions starting from 1.5.x are supported.

The user has to make sure this library is properly installed.
I strongly recommend the user to build the library yourself.
It could potentially save you a lot of trouble.

Currently the code is able to read and write the following image types:

:Read: gray1, gray2, gray4, gray8, gray16, gray_alpha_8, gray_alpha_16, rgb8, rgb16, rgba8, rgba16
:Write: gray1, gray2, gray4, gray8, gray16, gray_alpha_8, gray_alpha_16, rgb8, rgb16, rgba8, rgba16

For reading gray_alpha images the user has to compile application with ``BOOST_GIL_IO_ENABLE_GRAY_ALPHA``
macro  defined. This color space is defined in the toolbox by using ``gray_alpha.hpp``.

PNM
+++

For a general overview of the PNM image file format go to the
following PNM_Wiki_. No external library is needed for the pnm format.

The extension can read images in both flavours of the formats, ASCII and binary,
that is types from P1 through P6; can write only binary formats.

Currently the code is able to read and write the following image types:

:Read: gray1, gray8, rgb8
:Write: gray1, gray8, rgb8

When reading a mono text image the data is read as a gray8 image.

RAW
+++

For a general overview see RAW_Wiki_.

Currently the extension is only able to read rgb8 images.

TARGA
+++++

For a general overview of the BMP image file format go to the
following TARGA_Wiki_.

Currently the code is able to read and write the following image types:

:Read: rgb8_image_t and rgba8_image_t
:Write: rgb8_image_t and rgba8_image_t

The lack of having an indexed image type in gil restricts the current
interface to only write out non-indexed images.
This is subject to change soon.

TIFF
++++

For a general overview of the TIFF image file format go to the
following TIFF_Wiki_.

This tiff extension is based on the libtiff, which can be found, TIFF_Lib_.

All versions starting from 3.9.x are supported.

The user has to make sure this library is properly installed. I strongly
recommend the user to build the library yourself. It could potentially
save you a lot of trouble.

TIFF images can virtually encode all kinds of channel sizes representing
various color spaces. Even planar images are possible.
For instance, ``rbg323`` or ``gray7``. The channels also can have specific
formats, like integer values or floating point values.

For a complete set of options please consult the following websites:

* TIFF_Base_Tags_
* TIFF_Extension_Tags_

The author of this extension is not claiming all tiff formats are supported.
This extension is likely to be a moving target adding new features with each
new milestone. Here is an incomplete lists:

* Multi-page TIFF - read only
* Strip TIFF - read and write support
* Tiled TIFF - read and write support with user defined tiled sizes
* Bit images TIFF - fully supported, like ``gray1_image_t`` (minisblack)
* Planar TIFF - fully supported
* Floating-point TIFF - fully supported
* Palette TIFF - supported but no indexed image type is available as of now

This gil extension uses two different test image suites to test read and
write capabilities. See ``test_image`` folder.
It's advisable to use ImageMagick test viewer to display images.


Extending GIL::IO with new Formats
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Extending the gil::io with new formats is meant to be simple and
straightforward. Before adding I would recommend to have a look at existing
implementations and then trying to follow a couple of guidelines:

* Create the following files for your new xxx format
    * ``xxx_read.hpp`` - Only includes read code
    * ``xxx_write.hpp`` - Only includes write code
    * ``xxx_all.hpp`` - includes xxx_read.hpp and xxx_write.hpp
* Add the code to the ``boost::gil::detail`` namespace
* Create a tag type for the new format. Like this::

    struct xxx_tag : format_tag {};

* Create the image_read_info for the new format. It contains all the
  information that are necessary to read an image. It should be filled
  and returned by the ``get_info`` member of the reader class. See below::

    template<> struct image_read_info< xxx_tag > {};

* Create the image_write_info for the new format. It contains all the
  information that are necessary to write an image::

    template<> struct image_write_info< xxx_tag > {};

* Use the following reader skeleton as a start::

    template< typename Device
            , typename ConversionPolicy
            >
    class reader< Device
                , xxx_tag
                , ConversionPolicy
                >
                : public reader_base< xxx_tag
                                    , ConversionPolicy
                                    >
    {
    private:

        typedef typename ConversionPolicy::color_converter_type cc_t;

    public:

        reader( Device& device )
        : _io_dev( device )
        {}

        reader( Device&     device
              , const cc_t& cc
              )
        : _io_dev( device )
        , reader_base< xxx_tag
                     , ConversionPolicy
                     >( cc )
        {}

        image_read_info< xxx_tag > get_info()
        {
            // your implementation here
        }

        template< typename View >
        void apply( const View& dst_view )
        {
            // your implementation here
        }
    };

* The writer skeleton::

    template< typename Device >
    class writer< Device
                , xxx_tag
                >
    {
    public:

        writer( Device & file )
        : out(file)
        {}

        template<typename View>
        void apply( const View& view )
        {
            // your implementation here
        }

        template<typename View>
        void apply( const View&                        view
                  , const image_write_info< xxx_tag >& info )
        {
            // your implementation here
        }
    };

Running gil::io tests
---------------------

gil::io comes with a large suite of test cases which reads and writes various
file formats. It uses some test image suites which can be found online or
which can be demanded from me by sending me an email.

There are some test images created by me in the test folder.
To enable unit tests which make use of them set the following compiler options
``BOOST_GIL_IO_TEST_ALLOW_READING_IMAGES`` and
``BOOST_GIL_IO_TEST_ALLOW_WRITING_IMAGES``.

The following list provides all links to the image suites the compiler symbol
to enable the tests:

:BMP:   BMP_TEST_FILES_                 -- BOOST_GIL_IO_USE_BMP_TEST_SUITE_IMAGES
:PNG:   PNG_TEST_FILES_                 -- BOOST_GIL_IO_USE_PNG_TEST_SUITE_IMAGES
:PNM:   request files from me           -- BOOST_GIL_IO_USE_PNM_TEST_SUITE_IMAGES
:TIFF:  TIFF_LIB_TIFF_TEST_FILES_       -- BOOST_GIL_IO_USE_TIFF_LIBTIFF_TEST_SUITE_IMAGES
:TIFF:  TIFF_GRAPHICSMAGICK_TEST_FILES_ -- BOOST_GIL_IO_USE_TIFF_GRAPHICSMAGICK_TEST_SUITE_IMAGES


.. _BMP_Wiki: http://en.wikipedia.org/wiki/BMP_file_format
.. _JPEG_Wiki: http://en.wikipedia.org/wiki/JPEG
.. _JPEG_lib: http://www.ijg.org/
.. _PNG_Wiki: http://en.wikipedia.org/wiki/Portable_Network_Graphics
.. _PNG_Lib: http://libpng.org/pub/png/libpng.html
.. _PNM_Wiki: http://en.wikipedia.org/wiki/Portable_anymap
.. _RAW_Wiki: http://en.wikipedia.org/wiki/Raw_image_format
.. _TARGA_Wiki: http://en.wikipedia.org/wiki/Truevision_TGA
.. _RAW_lib: http://www.libraw.org/
.. _RAW_Wiki: http://en.wikipedia.org/wiki/Raw_image_format
.. _TIFF_Wiki: http://en.wikipedia.org/wiki/Tagged_Image_File_Format
.. _TIFF_Lib: http://www.remotesensing.org/libtiff/
.. _TIFF_Base_Tags: http://www.awaresystems.be/imaging/tiff/tifftags/baseline.html
.. _TIFF_Extension_Tags: http://www.awaresystems.be/imaging/tiff/tifftags/extension.html
.. _BMP_TEST_FILES: http://entropymine.com/jason/bmpsuite/
.. _PNG_TEST_FILES: http://www.schaik.com/pngsuite/pngsuite.html
.. _TARGA_TEST_FILES: http://www.fileformat.info/format/tga/sample/index.htm
.. _TIFF_LIB_TIFF_TEST_FILES: http://www.remotesensing.org/libtiff/images.html
.. _TIFF_GRAPHICSMAGICK_TEST_FILES: ftp://ftp.graphicsmagick.org/pub/tiff-samples/tiff-sample-images-be.tar.gz

---

### Extra Boost Boost 1 77 0 Libs Gil Doc Naming (`extra/boost/boost_1_77_0/libs/gil/doc/naming.rst`)

Naming Conventions
==================

Description of established naming conventions used in source code of GIL,
tests and examples.

Concrete Types
--------------

Concrete (non-generic) GIL types follow this naming convention::

  ColorSpace + BitDepth + [f | s]+ [c] + [_planar] + [_step] + ClassType + _t

where:

- ``ColorSpace`` indicates layout and ordering of components.
  For example, ``rgb``, ``bgr``, ``cmyk``, ``rgba``.

- ``BitDepth`` indicates the bit depth of the color channel.
  For example, ``8``,``16``,``32``.

- By default, type of channel is unsigned integral.
  The ``s`` tag indicates signed integral.
  The ``f`` tag indicates a floating point type, which is always signed.

- By default, objects operate on mutable pixels.
  The ``c`` tag indicates object operating over immutable pixels.

- ``_planar`` indicates planar organization (as opposed to interleaved).

- ``_step`` indicates special image views, locators and iterators which
  traverse the data in non-trivial way. For example, backwards or every other
  pixel.

- ``ClassType`` is ``_image`` (image), ``_view`` (image view), ``_loc`` (pixel
  2D locator) ``_ptr`` (pixel iterator), ``_ref`` (pixel reference),
  ``_pixel`` (pixel value).

- ``_t`` suffix indicaes it is a name of a type.

For example:

.. code-block:: cpp

  bgr8_image_t             a;    // 8-bit interleaved BGR image
  cmyk16_pixel_t           b;    // 16-bit CMYK pixel value;
  cmyk16c_planar_ref_t     c(b); // const reference to a 16-bit planar CMYK pixel.
  rgb32f_planar_step_ptr_t d;    // step pointer to a 32-bit planar RGB pixel.

---

### Extra Boost Boost 1 77 0 Libs Gil Doc Toolbox (`extra/boost/boost_1_77_0/libs/gil/doc/toolbox.rst`)

ToolBox extension
=================

.. _Reference: reference.html

Overview
--------

ToolBox provides collection of Boost.GIL extensions which are too
small to be maintained as standalone extensions.

Content:

* Color converters: Gray to  RGBA

* Color spaces: CMYKA, Gray with Alpha, HSL, HSV, Lab, XYZ

* Metafunctions:

  * ``channel_type``
  * ``channel_type_to_index``
  * ``get_num_bits``
  * ``get_pixel_type``
  * ``is_bit_aligned``
  * ``is_homogeneous``
  * ``is_similar``
  * ``pixel_bit_size``

* Image types:

  * ``indexed_image``

This extension will hopefully be added on by the community.

Since the extension is header-only, user just needs to include
its main header ``#include <boost/gil/extension/toolbox.hpp>``.

All definitions of the toolbox belong to the ``boost::gil`` namespace.

Folder Structure
----------------

The toolbox structured in the following sub-directories:

* color_converters
* color_spaces
* metafunctions
* image_types

Acknowledgements
----------------

Thanks to all the people who have reviewed this library and
made suggestions for improvements.

Reference
---------

The Reference_ section.

---

### Extra Boost Boost 1 77 0 Libs Gil Doc Warnings (`extra/boost/boost_1_77_0/libs/gil/doc/warnings.txt`)

/root/project/libs/gil/include/boost/gil/channel.hpp:34: warning: preprocessing issue while doing constant expression evaluation: syntax error
/root/project/libs/gil/include/boost/gil/image_processing/harris.hpp:16: warning: missing title after \defgroup CornerDetectionAlgorithms
/root/project/libs/gil/include/boost/gil/image_processing/numeric.hpp:22: warning: missing title after \defgroup ImageProcessingMath
/root/project/libs/gil/include/boost/gil/image_processing/scaling.hpp:18: warning: missing title after \defgroup ScalingAlgorithms
/root/project/libs/gil/include/boost/gil/image_processing/scaling.hpp:23: warning: missing title after \defgroup DownScalingAlgorithms
/root/project/libs/gil/include/boost/gil/bit_aligned_pixel_reference.hpp:85: warning: Refusing to add group PixelModelNonAlignedPixel to itself
/root/project/libs/gil/include/boost/gil/image_processing/numeric.hpp:22: warning: Refusing to add group ImageProcessingMath to itself
/root/project/libs/gil/include/boost/gil/image_processing/scaling.hpp:23: warning: Refusing to add group DownScalingAlgorithms to itself
/root/project/libs/gil/include/boost/gil/image_processing/threshold.hpp:97: warning: argument 'threshold_direction' of command @param is not found in the argument list of boost::gil::threshold_binary(SrcView const &src_view, DstView const &dst_view, typename channel_type< DstView >::type threshold_value, typename channel_type< DstView >::type max_value, threshold_direction direction=threshold_direction::regular)
/root/project/libs/gil/include/boost/gil/image_processing/threshold.hpp:108: warning: The following parameters of boost::gil::threshold_binary(SrcView const &src_view, DstView const &dst_view, typename channel_type< DstView >::type threshold_value, typename channel_type< DstView >::type max_value, threshold_direction direction=threshold_direction::regular) are not documented:
  parameter 'direction'
/root/project/libs/gil/include/boost/gil/io/read_and_convert_image.hpp:24: warning: argument 'settings' of command @param is not found in the argument list of boost::gil::read_and_convert_image(Reader &reader, Image &img, typename std::enable_if< mp11::mp_and< detail::is_reader< Reader >, is_format_tag< typename Reader::format_tag_t > >::value >::type *=nullptr)
/root/project/libs/gil/include/boost/gil/io/read_and_convert_image.hpp:24: warning: argument 'cc' of command @param is not found in the argument list of boost::gil::read_and_convert_image(Reader &reader, Image &img, typename std::enable_if< mp11::mp_and< detail::is_reader< Reader >, is_format_tag< typename Reader::format_tag_t > >::value >::type *=nullptr)
/root/project/libs/gil/include/boost/gil/io/read_and_convert_view.hpp:24: warning: argument 'img' of command @param is not found in the argument list of boost::gil::read_and_convert_view(Reader &reader, View const &view, typename std::enable_if< mp11::mp_and< detail::is_reader< Reader >, is_format_tag< typename Reader::format_tag_t > >::value >::type *=nullptr)
/root/project/libs/gil/include/boost/gil/io/read_and_convert_view.hpp:24: warning: argument 'settings' of command @param is not found in the argument list of boost::gil::read_and_convert_view(Reader &reader, View const &view, typename std::enable_if< mp11::mp_and< detail::is_reader< Reader >, is_format_tag< typename Reader::format_tag_t > >::value >::type *=nullptr)
/root/project/libs/gil/include/boost/gil/io/read_and_convert_view.hpp:24: warning: argument 'cc' of command @param is not found in the argument list of boost::gil::read_and_convert_view(Reader &reader, View const &view, typename std::enable_if< mp11::mp_and< detail::is_reader< Reader >, is_format_tag< typename Reader::format_tag_t > >::value >::type *=nullptr)
/root/project/libs/gil/include/boost/gil/io/read_and_convert_view.hpp:32: warning: The following parameters of boost::gil::read_and_convert_view(Reader &reader, View const &view, typename std::enable_if< mp11::mp_and< detail::is_reader< Reader >, is_format_tag< typename Reader::format_tag_t > >::value >::type *=nullptr) are not documented:
  parameter 'view'
/root/project/libs/gil/include/boost/gil/io/read_view.hpp:24: warning: argument 'settings' of command @param is not found in the argument list of boost::gil::read_view(Reader reader, View const &view, typename std::enable_if< mp11::mp_and< detail::is_reader< Reader >, typename is_format_tag< typename Reader::format_tag_t >::type, typename is_read_supported< typename get_pixel_type< View >::type, typename Reader::format_tag_t >::type >::value >::type *=nullptr)
/root/project/libs/gil/include/boost/gil/concepts/channel.hpp:188: warning: unexpected command endcode
/root/project/libs/gil/include/boost/gil/io/reader_base.hpp:46: warning: argument 'info' of command @param is not found in the argument list of reader_base< FormatTag, ConversionPolicy >::init_image(Image &img, const image_read_settings< FormatTag > &settings)
/root/project/libs/gil/include/boost/gil/io/reader_base.hpp:53: warning: The following parameters of boost::gil::reader_base::init_image(Image &img, const image_read_settings< FormatTag > &settings) are not documented:
  parameter 'settings'

---

### Extra Boost Boost 1 77 0 Libs Graph Doc Read Graphml (`extra/boost/boost_1_77_0/libs/graph/doc/read_graphml.rst`)

============================
|(logo)|__ ``read_graphml``
============================

.. Copyright (C) 2006  Tiago de Paula Peixoto <[email protected]>

   Distributed under the Boost Software License, Version 1.0. (See
   accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

   Authors: Tiago de Paula Peixoto

.. |(logo)| image:: ../../../boost.png
   :align: middle
   :alt: Boost

__ ../../../index.htm

::

  void read_graphml(std::istream& in, MutableGraph& graph,
                    dynamic_properties& dp, size_t graph_index = 0);


The ``read_graphml`` function interprets a graph described using the
GraphML_ format and builds a BGL graph that captures that
description.  Using this function, you can initialize a graph using
data stored as text.

The GraphML format can specify both directed and undirected graphs, and
``read_graphml`` differentiates between the two. One must pass
``read_graphml`` an undirected graph when reading an undirected graph;
the same is true for directed graphs. Furthermore, ``read_graphml``
will throw an exception if it encounters parallel edges and cannot add
them to the graph.

To handle attributes expressed in the GraphML format, ``read_graphml``
takes a dynamic_properties_ object and operates on its collection of
property maps.  The reader passes all the properties encountered to
this object, using the GraphML attribute names as the property names,
and with the appropriate C++ value type based on the GraphML attribute type
definition. Graph properties are also set with the same
dynamic_properties_ object, where the key type is the type of the graph itself.

If the file contains multiple graphs, the ``graph_index`` parameter controls
which graph will be loaded.  It defaults to ``0``, meaning that the first graph
in the file will be loaded.  If ``graph_index`` is greater than or equal to the
number of graphs in the file, an empty graph will be returned.

Requirements:
 - The type of the graph must model the `Mutable Graph`_ concept.
 - The type of the iterator must model the `Multi-Pass Iterator`_
   concept.
 - The property map value types must be default-constructible.


.. contents::

Where Defined
-------------
``<boost/graph/graphml.hpp>``

Exceptions
----------

::

  struct graph_exception : public std::exception {
    virtual ~graph_exception() throw();
    virtual const char* what() const throw() = 0;
  };

  struct bad_parallel_edge : public graph_exception {
    std::string from;
    std::string to;

    bad_parallel_edge(const std::string&, const std::string&);
    virtual ~bad_parallel_edge() throw();
    const char* what() const throw();
  };

  struct directed_graph_error : public graph_exception {
    virtual ~directed_graph_error() throw();
    virtual const char* what() const throw();
  };

  struct undirected_graph_error : public graph_exception {
    virtual ~undirected_graph_error() throw();
    virtual const char* what() const throw();
  };

  struct parse_error : public graph_exception {
    parse_error(const std::string&);
    virtual ~parse_error() throw() {}
    virtual const char* what() const throw();
    std::string statement;
    std::string error;
  };

Under certain circumstances, ``read_graphml`` will throw one of the
above exceptions.  The three concrete exceptions can all be caught
using the general ``graph_exception`` moniker when greater precision
is not needed.  In addition, all of the above exceptions derive from
the standard ``std::exception`` for even more generalized error
handling.

The ``bad_parallel_edge`` exception is thrown when an attempt to add a
parallel edge to the supplied MutableGraph fails.  The GraphML format
supports parallel edges, but some BGL-compatible graph types do not.
One example of such a graph is ``boost::adjacency_list<setS,vecS>``,
which allows at most one edge can between any two vertices.


The ``directed_graph_error`` exception occurs when an undirected graph
type is passed to ``read_graph``, but the graph defined in the GraphML
file contains at least one directed edge.

The ``undirected_graph_error`` exception occurs when a directed graph
type is passed to ``read_graph``,  but the graph defined in the GraphML
file contains at least one undirected edge.

The ``parse_error`` exception occurs when a syntax error is
encountered in the GraphML file. The error string will contain the
line and column where the error was encountered.


Building the GraphML reader
-----------------------------
To use the GraphML reader, you will need to build and link against
the "boost_graph" library. The library can be built by following the
`Boost Jam Build Instructions`_ for the subdirectory ``libs/graph/build``.


Notes
-----

 - On successful reading of a graph, every vertex and edge will have
   an associated value for every respective edge and vertex property
   encountered while interpreting the graph.  These values will be set
   using the ``dynamic_properties`` object.  Some properties may be
   ``put`` multiple times during the course of reading in order to
   ensure the GraphML semantics.  Those edges and vertices that are
   not explicitly given a value for a property (and that property has
   no default) will be given the default constructed value of the
   value type.  **Be sure that property map value types are default
   constructible.**

 - Nested graphs are supported as long as they are exactly of the same
   type as the root graph, i.e., are also directed or undirected. Note
   that since nested graphs are not directly supported by BGL, they
   are in fact completely ignored when building the graph, and the
   internal vertices or edges are interpreted as belonging to the root
   graph.

 - Hyperedges and Ports are not supported.

See Also
--------

write_graphml_


.. _GraphML: http://graphml.graphdrawing.org/
.. _`Mutable Graph`: MutableGraph.html
.. _`Multi-Pass Iterator`: ../../iterator/index.html
.. _dynamic_properties: ../../property_map/doc/dynamic_property_map.html
.. _write_graphml: write_graphml.html
.. _Boost Jam Build Instructions: ../../../more/getting_started.html#Build_Install

---

### Extra Boost Boost 1 77 0 Libs Graph Doc Read Graphviz (`extra/boost/boost_1_77_0/libs/graph/doc/read_graphviz.rst`)

============================
|(logo)|__ ``read_graphviz``
============================

.. |(logo)| image:: ../../../boost.png
   :align: middle
   :alt: Boost

.. Copyright (c) 2005-2009 Trustees of Indiana University
    Distributed under the Boost Software License, Version 1.0.
    (See accompanying file LICENSE_1_0.txt or copy at
     http://www.boost.org/LICENSE_1_0.txt)
__ ../../../index.htm

::

  namespace boost {

    template <typename MutableGraph>
    bool read_graphviz(std::istream& in, MutableGraph& graph,
                       dynamic_properties& dp,
                       const std::string& node_id = "node_id");

    template <typename MutableGraph>
    bool read_graphviz(std::string& str, MutableGraph& graph,
                       dynamic_properties& dp,
                       const std::string& node_id = "node_id");

    template <typename InputIterator, typename MutableGraph>
    bool read_graphviz(InputIterator begin, InputIterator end,
                       MutableGraph& graph, dynamic_properties& dp,
                       const std::string& node_id = "node_id");

  }


The ``read_graphviz`` function interprets a graph described using the
GraphViz_ DOT language and builds a BGL graph that captures that
description.  Using these functions, you can initialize a graph using
data stored as text.

The DOT language can specify both directed and undirected graphs, and
``read_graphviz`` differentiates between the two. One must pass
``read_graphviz`` an undirected graph when reading an undirected graph;
the same is true for directed graphs. Furthermore, ``read_graphviz``
will throw an exception if it encounters parallel edges and cannot add
them to the graph.

To handle properties expressed in the DOT language, ``read_graphviz``
takes a dynamic_properties_ object and operates on its collection of
property maps.  The reader passes all the properties encountered to
this object, using the GraphViz string keys as the property keys.
Furthermore, ``read_graphviz`` stores node identifier names under the
vertex property map named ``node_id``.

Requirements:
 - The type of the graph must model the `Mutable Graph`_ concept.
 - The type of the iterator must model the `Input Iterator`_
   concept.
 - The property map value types must be default-constructible.


.. contents::

Where Defined
-------------
``<boost/graph/graphviz.hpp>``

Exceptions
----------

::

  struct graph_exception : public std::exception {
    virtual ~graph_exception() throw();
    virtual const char* what() const throw() = 0;
  };

  struct bad_parallel_edge : public graph_exception {
    std::string from;
    std::string to;

    bad_parallel_edge(const std::string&, const std::string&);
    virtual ~bad_parallel_edge() throw();
    const char* what() const throw();
  };

  struct directed_graph_error : public graph_exception {
    virtual ~directed_graph_error() throw();
    virtual const char* what() const throw();
  };

  struct undirected_graph_error : public graph_exception {
    virtual ~undirected_graph_error() throw();
    virtual const char* what() const throw();
  };

  struct bad_graphviz_syntax: public graph_exception {
    std::string errmsg;

    bad_graphviz_syntax(const std::string&);
    virtual ~bad_graphviz_syntax() throw();
    virtual const char* what() const throw();
  };

Under certain circumstances, ``read_graphviz`` will throw one of the
above exceptions.  The three concrete exceptions can all be caught
using the general ``graph_exception`` moniker when greater precision
is not needed.  In addition, all of the above exceptions derive from
the standard ``std::exception`` for even more generalized error
handling.

The ``bad_parallel_edge`` exception is thrown when an attempt to add a
parallel edge to the supplied MutableGraph fails.  The DOT language
supports parallel edges, but some BGL-compatible graph types do not.
One example of such a graph is ``boost::adjacency_list<setS,vecS>``,
which allows at most one edge can between any two vertices.


The ``directed_graph_error`` exception occurs when an undirected graph
type is passed to ``read_graph`` but the textual representation of the
graph is directed, as indicated by the ``digraph`` keyword in the DOT
language.

The ``undirected_graph_error`` exception occurs when a directed graph
type is passed to ``read_graph`` but the textual representation of the
graph is undirected, as indicated by the ``graph`` keyword in the DOT
language.

The ``bad_graphviz_syntax`` exception occurs when the graph input is not a
valid GraphViz graph.


Example
-------
The following example illustrates a relatively simple use of the
GraphViz reader to populate an ``adjacency_list`` graph

::

  // Vertex properties
  typedef property < vertex_name_t, std::string,
            property < vertex_color_t, float > > vertex_p;
  // Edge properties
  typedef property < edge_weight_t, double > edge_p;
  // Graph properties
  typedef property < graph_name_t, std::string > graph_p;
  // adjacency_list-based type
  typedef adjacency_list < vecS, vecS, directedS,
    vertex_p, edge_p, graph_p > graph_t;

  // Construct an empty graph and prepare the dynamic_property_maps.
  graph_t graph(0);
  dynamic_properties dp;

  property_map<graph_t, vertex_name_t>::type name =
    get(vertex_name, graph);
  dp.property("node_id",name);

  property_map<graph_t, vertex_color_t>::type mass =
    get(vertex_color, graph);
  dp.property("mass",mass);

  property_map<graph_t, edge_weight_t>::type weight =
    get(edge_weight, graph);
  dp.property("weight",weight);

  // Use ref_property_map to turn a graph property into a property map
  boost::ref_property_map<graph_t*,std::string>
    gname(get_property(graph,graph_name));
  dp.property("name",gname);

  // Sample graph as an std::istream;
  std::istringstream
    gvgraph("digraph { graph [name=\"graphname\"]  a  c e [mass = 6.66] }");

  bool status = read_graphviz(gvgraph,graph,dp,"node_id");




Building the GraphViz Readers
-----------------------------
To use the GraphViz readers, you will need to build and link against
the "boost_graph" and "boost_regex" libraries. These libraries can be built by following the
`Boost Jam Build Instructions`_ for the subdirectories ``libs/graph/build`` and ``libs/regex/build``.


Notes
-----

 - The ``read_graphviz`` function does not use any code from the
   GraphViz distribution to interpret the DOT Language.  Rather, the
   implementation was based on documentation found on the GraphViz web
   site, as well as experiments run using the dot application.  The
   resulting interpretation may be subtly different from dot for some
   corner cases that are not well specified.

 - On successful reading of a graph, every vertex and edge will have
   an associated value for every respective edge and vertex property
   encountered while interpreting the graph.  These values will be set
   using the ``dynamic_properties`` object.  Those edges and
   vertices that are not explicitly given a value for a property (and that
   property has no default) will be
   given the default constructed value of the value type.  **Be sure
   that property map value types are default constructible.**

 - ``read_graphviz`` treats subgraphs as syntactic sugar.  It does not
   reflect subgraphs as actual entities in the BGL.  Rather, they are
   used to shorten some edge definitions as well as to give a subset
   of all nodes or edges certain properties. For example, the
   DOT graphs ``digraph { a -> subgraph {b -> c} -> e }`` and
   ``digraph { a -> b -> e ; a -> c -> e ; b -> c}`` are equivalent.

 - Subgraph IDs refer to subgraphs defined earlier in the graph
   description.  Undefined subgraphs behave as empty subgraphs
   (``{}``).  This is the same behavior as GraphViz.

See Also
--------

write_graphviz_


Future Work
-----------

 - Passing port information to BGL.

 - Expanding escape codes in the same way GraphViz does.

 - Support for optional recognition of subgraphs as distinct entities.


.. _GraphViz: http://graphviz.org/
.. _`Mutable Graph`: MutableGraph.html
.. _`Input Iterator`: http://www.boost.org/sgi/stl/InputIterator.html
.. _dynamic_properties: ../../property_map/doc/dynamic_property_map.html
.. _write_graphviz: write-graphviz.html
.. _Boost Jam Build Instructions: ../../../more/getting_started.html#Build_Install

---

### Extra Boost Boost 1 77 0 Libs Graph Doc Write Graphml (`extra/boost/boost_1_77_0/libs/graph/doc/write_graphml.rst`)

============================
|(logo)|__ ``write_graphml``
============================

.. Copyright (C) 2006  Tiago de Paula Peixoto <[email protected]>

   Distributed under the Boost Software License, Version 1.0. (See
   accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

   Authors: Tiago de Paula Peixoto

.. |(logo)| image:: ../../../boost.png
   :align: middle
   :alt: Boost

__ ../../../index.htm

::

  template<typename Graph>
  void
  write_graphml(std::ostream& out, const Graph& g, const dynamic_properties& dp,
	        bool ordered_vertices=false);

  template<typename Graph, typename VertexIndexMap>
  void
  write_graphml(std::ostream& out, const Graph& g, VertexIndexMap vertex_index,
                const dynamic_properties& dp, bool ordered_vertices=false);

This is to write a BGL graph object into an output stream in the
GraphML_ format.  Both overloads of ``write_graphml`` will emit all of
the properties stored in the dynamic_properties_ object, thereby
retaining the properties that have been read in through the dual
function read_graphml_. The second overload must be used when the
graph doesn't have an internal vertex index map, which must then be
supplied with the appropriate parameter.

.. contents::

Where Defined
-------------
``<boost/graph/graphml.hpp>``

Parameters
----------

OUT: ``std::ostream& out``
  A standard ``std::ostream`` object.

IN: ``VertexListGraph& g``
  A directed or undirected graph.  The
  graph's type must be a model of VertexListGraph_. If the graph
  doesn't have an internal ``vertex_index`` property map, one
  must be supplied with the vertex_index parameter.

IN: ``VertexIndexMap vertex_index``
  A vertex property map containing the indexes in the range
  [0,num_vertices(g)].


IN: ``dynamic_properties& dp``
  Contains all of the vertex, edge, and graph properties that should be
  emitted by the GraphML writer.

IN: ``bool ordered_vertices``
  This tells whether or not the order of the vertices from vertices(g)
  matches the order of the indexes. If ``true``, the ``parse.nodeids``
  graph attribute will be set to ``canonical``. Otherwise it will be
  set to ``free``.



Example
-------

This example demonstrates using BGL-GraphML interface to write
a BGL graph into a GraphML format file.

::

  enum files_e { dax_h, yow_h, boz_h, zow_h, foo_cpp,
                 foo_o, bar_cpp, bar_o, libfoobar_a,
                 zig_cpp, zig_o, zag_cpp, zag_o,
                 libzigzag_a, killerapp, N };
  const char* name[] = { "dax.h", "yow.h", "boz.h", "zow.h", "foo.cpp",
                         "foo.o", "bar.cpp", "bar.o", "libfoobar.a",
                         "zig.cpp", "zig.o", "zag.cpp", "zag.o",
                         "libzigzag.a", "killerapp" };

  int main(int,char*[])
  {
      typedef pair<int,int> Edge;
      Edge used_by[] = {
          Edge(dax_h, foo_cpp), Edge(dax_h, bar_cpp), Edge(dax_h, yow_h),
          Edge(yow_h, bar_cpp), Edge(yow_h, zag_cpp),
          Edge(boz_h, bar_cpp), Edge(boz_h, zig_cpp), Edge(boz_h, zag_cpp),
          Edge(zow_h, foo_cpp),
          Edge(foo_cpp, foo_o),
          Edge(foo_o, libfoobar_a),
          Edge(bar_cpp, bar_o),
          Edge(bar_o, libfoobar_a),
          Edge(libfoobar_a, libzigzag_a),
          Edge(zig_cpp, zig_o),
          Edge(zig_o, libzigzag_a),
          Edge(zag_cpp, zag_o),
          Edge(zag_o, libzigzag_a),
          Edge(libzigzag_a, killerapp)
       };

      const int nedges = sizeof(used_by)/sizeof(Edge);

      typedef adjacency_list< vecS, vecS, directedS,
          property< vertex_color_t, string >,
          property< edge_weight_t, int >
          > Graph;
      Graph g(used_by, used_by + nedges, N);

      graph_traits<Graph>::vertex_iterator v, v_end;
      for (tie(v,v_end) = vertices(g); v != v_end; ++v)
          put(vertex_color_t(), g, *v, name[*v]);

      graph_traits<Graph>::edge_iterator e, e_end;
      for (tie(e,e_end) = edges(g); e != e_end; ++e)
          put(edge_weight_t(), g, *e, 3);

      dynamic_properties dp;
      dp.property("name", get(vertex_color_t(), g));
      dp.property("weight", get(edge_weight_t(), g));

      write_graphml(std::cout, g, dp, true);
   }


The output will be:

::

  <?xml version="1.0" encoding="UTF-8"?>
  <graphml xmlns="http://graphml.graphdrawing.org/xmlns/graphml"  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns/graphml http://graphml.graphdrawing.org/xmlns/graphml/graphml-attributes-1.0rc.xsd">
    <key id="key0" for="node" attr.name="name" attr.type="string" />
    <key id="key1" for="edge" attr.name="weight" attr.type="int" />
    <graph id="G" edgedefault="directed" parse.nodeids="canonical" parse.edgeids="canonical" parse.order="nodesfirst">
      <node id="n0">
        <data key="key0">dax.h</data>
      </node>
      <node id="n1">
        <data key="key0">yow.h</data>
      </node>
      <node id="n2">
        <data key="key0">boz.h</data>
      </node>
      <node id="n3">
        <data key="key0">zow.h</data>
      </node>
      <node id="n4">
        <data key="key0">foo.cpp</data>
      </node>
      <node id="n5">
        <data key="key0">foo.o</data>
      </node>
      <node id="n6">
        <data key="key0">bar.cpp</data>
      </node>
      <node id="n7">
        <data key="key0">bar.o</data>
      </node>
      <node id="n8">
        <data key="key0">libfoobar.a</data>
      </node>
      <node id="n9">
        <data key="key0">zig.cpp</data>
      </node>
      <node id="n10">
        <data key="key0">zig.o</data>
      </node>
      <node id="n11">
        <data key="key0">zag.cpp</data>
      </node>
      <node id="n12">
        <data key="key0">zag.o</data>
      </node>
      <node id="n13">
        <data key="key0">libzigzag.a</data>
      </node>
      <node id="n14">
        <data key="key0">killerapp</data>
      </node>
      <edge id="e0" source="n0" target="n4">
        <data key="key1">3</data>
      </edge>
      <edge id="e1" source="n0" target="n6">
        <data key="key1">3</data>
      </edge>
      <edge id="e2" source="n0" target="n1">
        <data key="key1">3</data>
      </edge>
      <edge id="e3" source="n1" target="n6">
        <data key="key1">3</data>
      </edge>
      <edge id="e4" source="n1" target="n11">
        <data key="key1">3</data>
      </edge>
      <edge id="e5" source="n2" target="n6">
        <data key="key1">3</data>
      </edge>
      <edge id="e6" source="n2" target="n9">
	 <data key="key1">3</data>
      </edge>
      <edge id="e7" source="n2" target="n11">
	<data key="key1">3</data>
      </edge>
      <edge id="e8" source="n3" target="n4">
	<data key="key1">3</data>
      </edge>
      <edge id="e9" source="n4" target="n5">
	<data key="key1">3</data>
      </edge>
      <edge id="e10" source="n5" target="n8">
	<data key="key1">3</data>
      </edge>
      <edge id="e11" source="n6" target="n7">
	<data key="key1">3</data>
      </edge>
      <edge id="e12" source="n7" target="n8">
	<data key="key1">3</data>
      </edge>
      <edge id="e13" source="n8" target="n13">
	<data key="key1">3</data>
      </edge>
      <edge id="e14" source="n9" target="n10">
	<data key="key1">3</data>
      </edge>
      <edge id="e15" source="n10" target="n13">
	<data key="key1">3</data>
      </edge>
      <edge id="e16" source="n11" target="n12">
	<data key="key1">3</data>
      </edge>
      <edge id="e17" source="n12" target="n13">
	<data key="key1">3</data>
      </edge>
      <edge id="e18" source="n13" target="n14">
	<data key="key1">3</data>
      </edge>
    </graph>
  </graphml>

See Also
--------

_read_graphml

Notes
-----

 - Note that you can use GraphML file write facilities without linking
   against the ``boost_graph`` library.

.. _GraphML: http://graphml.graphdrawing.org/
.. _dynamic_properties: ../../property_map/doc/dynamic_property_map.html
.. _read_graphml: read_graphml.html
.. _VertexListGraph: VertexListGraph.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc DistributedEdgeListGraph (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/DistributedEdgeListGraph.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

==========================================
|Logo| Concept Distributed Edge List Graph
==========================================

.. contents::

Description
-----------

A Distributed Edge List Graph is a graph whose vertices are
distributed across multiple processes or address spaces. The
``vertices`` and ``num_vertices`` functions retain the same
signatures as in the `Edge List Graph`_ concept, but return only
the local set (and size of the local set) of vertices. 

Notation
--------

G
  A type that models the Distributed Edge List Graph concept.

g
  An object of type ``G``.

Refinement of
-------------

  - `Graph`_

Associated types
----------------

+----------------+---------------------------------------+---------------------------------+
|Edge            |``graph_traits<G>::edge_descriptor``   |Must model the                   |
|descriptor type |                                       |`Global Descriptor`_ concept.    |
+----------------+---------------------------------------+---------------------------------+
|Edge iterator   |``graph_traits<G>::edge_iterator``     |Iterates over edges stored       |
|type            |                                       |locally. The value type must be  |
|                |                                       |``edge_descriptor``.             |
+----------------+---------------------------------------+---------------------------------+
|Edges size      |``graph_traits<G>::edges_size_type``   |The unsigned integral type used  |
|type            |                                       |to store the number of edges     |
|                |                                       |in the local subgraph.           |
+----------------+---------------------------------------+---------------------------------+

Valid Expressions
-----------------

+----------------+---------------------+----------------------+-------------------------------------+
|Name            |Expression           |Type                  |Semantics                            |
+================+=====================+======================+=====================================+
|Local edge set  |``edges(g)``         |``std::pair<``        |Returns an iterator range            |
|                |                     |``edge_iterator,``    |providing access to the local        |
|                |                     |``edge_iterator>``    |edges in the graph.                  |
+----------------+---------------------+----------------------+-------------------------------------+
|Number of local |``num_edges(g)``     |``edges_size_type``   |Returns the number of edges          |
|edges.          |                     |                      |stored locally in the graph.         |
+----------------+---------------------+----------------------+-------------------------------------+


Models
------

  - `Distributed adjacency list`_

-----------------------------------------------------------------------------

Copyright (C) 2005 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Graph: http://www.boost.org/libs/graph/doc/Graph.html
.. _Edge List Graph: http://www.boost.org/libs/graph/doc/EdgeListGraph.html
.. _Distributed Graph: DistributedGraph.html
.. _Global descriptor: GlobalDescriptor.html
.. _Distributed adjacency list: distributed_adjacency_list.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc DistributedGraph (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/DistributedGraph.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

================================
|Logo| Concept Distributed Graph
================================

.. contents::

Description
-----------

A Distributed Graph is a graph whose vertices or edges are
distributed across multiple processes or address spaces. The
descriptors of a Distributed Graph must model the `Global
Descriptor`_ concept. 

Notation
--------

G
  A type that models the Distributed Graph concept.


Refinement of
-------------

  - Graph_

Associated types
----------------

+----------------+---------------------------------------+---------------------------------+
|Vertex          |``graph_traits<G>::vertex_descriptor`` |Must model the                   |
|descriptor type |                                       |`Global Descriptor`_ concept.    |
+----------------+---------------------------------------+---------------------------------+
|Edge            |``graph_traits<G>::edge_descriptor``   |Must model the                   |
|descriptor type |                                       |`Global Descriptor`_ concept.    |
+----------------+---------------------------------------+---------------------------------+


Models
------

  - `Distributed adjacency list`_

-----------------------------------------------------------------------------

Copyright (C) 2005 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Graph: http://www.boost.org/libs/graph/doc/Graph.html
.. _Global descriptor: GlobalDescriptor.html
.. _Distributed adjacency list: distributed_adjacency_list.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc DistributedVertexListGraph (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/DistributedVertexListGraph.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

============================================
|Logo| Concept Distributed Vertex List Graph
============================================

.. contents::

Description
-----------

A Distributed Vertex List Graph is a graph whose vertices are
distributed across multiple processes or address spaces. The
``vertices`` and ``num_vertices`` functions retain the same
signatures as in the `Vertex List Graph`_ concept, but return only
the local set (and size of the local set) of vertices. 

Notation
--------

G
  A type that models the Distributed Vertex List Graph concept.

g
  An object of type ``G``.

Refinement of
-------------

  - `Graph`_

Associated types
----------------

+----------------+---------------------------------------+---------------------------------+
|Vertex          |``graph_traits<G>::vertex_descriptor`` |Must model the                   |
|descriptor type |                                       |`Global Descriptor`_ concept.    |
+----------------+---------------------------------------+---------------------------------+
|Vertex iterator |``graph_traits<G>::vertex_iterator``   |Iterates over vertices stored    |
|type            |                                       |locally. The value type must be  |
|                |                                       |``vertex_descriptor``.           |
+----------------+---------------------------------------+---------------------------------+
|Vertices size   |``graph_traits<G>::vertices_size_type``|The unsigned integral type used  |
|type            |                                       |to store the number of vertices  |
|                |                                       |in the local subgraph.           |
+----------------+---------------------------------------+---------------------------------+

Valid Expressions
-----------------

+----------------+---------------------+----------------------+-------------------------------------+
|Name            |Expression           |Type                  |Semantics                            |
+================+=====================+======================+=====================================+
|Local vertex set|``vertices(g)``      |``std::pair<``        |Returns an iterator range            |
|                |                     |``vertex_iterator,``  |providing access to the local        |
|                |                     |``vertex_iterator>``  |vertices in the graph.               |
+----------------+---------------------+----------------------+-------------------------------------+
|Number of local |``num_vertices(g)``  |``vertices_size_type``|Returns the number of vertices       |
|vertices.       |                     |                      |stored locally in the graph.         |
+----------------+---------------------+----------------------+-------------------------------------+


Models
------

  - `Distributed adjacency list`_

-----------------------------------------------------------------------------

Copyright (C) 2005 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Graph: http://www.boost.org/libs/graph/doc/Graph.html
.. _Vertex List Graph: http://www.boost.org/libs/graph/doc/VertexListGraph.html
.. _Distributed Graph: DistributedGraph.html
.. _Global descriptor: GlobalDescriptor.html
.. _Distributed adjacency list: distributed_adjacency_list.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc GlobalDescriptor (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/GlobalDescriptor.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

================================
|Logo| Concept Global Descriptor
================================

.. contents::

Description
-----------

A global descriptor is an object that represents an entity that is
owned by some process and may reside in an address space not
accessible to the currently-executing process. The global descriptor
consists of two parts: the *owner* of the entity, which is the
identifier of that process in which the entity resides, and a *local
descriptor*, that uniquely identifies the entity with the address
space of the owner. 

Refinement of
-------------

  - `Default Constructible`_
  - Assignable_

Notation
--------
X
  A type that models the Global Descriptor concept.

x
  Object of type X


Associated types
----------------

+----------------+--------------------+---------------------------------+
|Process ID type |``process_id_type`` |Determined by the process group  |
|                |                    |associated with type X.          |
+----------------+--------------------+---------------------------------+
|Local descriptor|``local_type``      |Determined by the data structure |
|type            |                    |the descriptor accesses.         |
|                |                    |Must model `Equality Comparable`_|
|                |                    |and `Copy Constructible`_.       |
+----------------+--------------------+---------------------------------+

Valid Expressions
-----------------

+----------------+---------------------+---------------------+-------------------------------------+
|Name            |Expression           |Type                 |Semantics                            |
+================+=====================+=====================+=====================================+
|Owner           |``owner(x)``         |``process_id_type``  |Returns the owner of ``x``.          |
+----------------+---------------------+---------------------+-------------------------------------+
|Local descriptor|``local(x)``         |``local_type``       |Returns the local descriptor         |
|                |                     |                     |uniquely identifying ``x``.          |
+----------------+---------------------+---------------------+-------------------------------------+


-----------------------------------------------------------------------------

Copyright (C) 2005 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Assignable: http://www.sgi.com/tech/stl/Assignable.html
.. _Copy constructible: http://www.sgi.com/tech/stl/CopyConstructible.html
.. _Default constructible: http://www.sgi.com/tech/stl/DefaultConstructible.html
.. _Equality comparable: http://www.sgi.com/tech/stl/EqualityComparable.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Betweenness Centrality (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/betweenness_centrality.rst`)

.. Copyright (C) 2004-2009 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

=============================
|Logo| Betweenness Centrality
=============================

::

  // named parameter versions
  template<typename Graph, typename Param, typename Tag, typename Rest>
  void 
  brandes_betweenness_centrality(const Graph& g, 
                                 const bgl_named_params<Param,Tag,Rest>& params);

  template<typename Graph, typename CentralityMap>
  void 
  brandes_betweenness_centrality(const Graph& g, CentralityMap centrality);

  template<typename Graph, typename CentralityMap, typename EdgeCentralityMap>
  void 
  brandes_betweenness_centrality(const Graph& g, CentralityMap centrality,
                                 EdgeCentralityMap edge_centrality_map);

  // non-named parameter versions
  template<typename Graph, typename CentralityMap, typename EdgeCentralityMap,
           typename IncomingMap, typename DistanceMap, typename DependencyMap, 
           typename PathCountMap, typename VertexIndexMap, typename Buffer>
  void  
  brandes_betweenness_centrality(const Graph& g, 
                                 CentralityMap centrality,
                                 EdgeCentralityMap edge_centrality_map,
                                 IncomingMap incoming, 
                                 DistanceMap distance, 
                                 DependencyMap dependency,     
                                 PathCountMap path_count,   
                                 VertexIndexMap vertex_index,
                                 Buffer sources,
                                 typename property_traits<DistanceMap>::value_type delta);

  template<typename Graph, typename CentralityMap, typename EdgeCentralityMap, 
           typename IncomingMap, typename DistanceMap, typename DependencyMap, 
           typename PathCountMap, typename VertexIndexMap, typename WeightMap, 
           typename Buffer>    
  void 
  brandes_betweenness_centrality(const Graph& g, 
                                 CentralityMap centrality,
                                 EdgeCentralityMap edge_centrality_map,
                                 IncomingMap incoming, 
                                 DistanceMap distance, 
                                 DependencyMap dependency,
                                 PathCountMap path_count, 
                                 VertexIndexMap vertex_index,
                                 Buffer sources,
                                 typename property_traits<WeightMap>::value_type delta,
                                 WeightMap weight_map);

  // helper functions
  template<typename Graph, typename CentralityMap>
  typename property_traits<CentralityMap>::value_type
  central_point_dominance(const Graph& g, CentralityMap centrality);

The ``brandes_betweenness_centrality()`` function computes the
betweenness centrality of the vertices and edges in a graph.  The
method of calculating betweenness centrality in *O(V)* space is due to
Brandes [Brandes01]_.  The algorithm itself is a modification of
Brandes algorithm by Edmonds [Edmonds09]_.

.. contents::

Where Defined
-------------
<``boost/graph/distributed/betweenness_centrality.hpp``>

also accessible from

<``boost/graph/betweenness_centrality.hpp``>

Parameters
----------

IN:  ``const Graph& g``
  The graph type must be a model of `Distributed Graph`_.  The graph
  type must also model the `Incidence Graph`_ concept.  0-weighted
  edges in ``g`` will result in undefined behavior.

IN: ``CentralityMap centrality`` 
  A centrality map may be supplied to the algorithm, if not supplied a
  ``dummy_property_map`` will be used and no vertex centrality
  information will be recorded.  The ``CentralityMap`` type must be a
  `Distributed Property Map`_.  The key type must be the graph's
  vertex descriptor type.

  **Default**: A ``dummy_property_map``.

IN:  ``EdgeCentralityMap edge_centrality_map``
  An edge centrality map may be supplied to the algorithm, if not
  supplied a ``dummy_property_map`` will be used and no edge
  centrality information will be recorded.  The ``EdgeCentralityMap``
  type must be a `Distributed Property Map`_.  The key type must be
  the graph's vertex descriptor type.

  **Default**: A ``dummy_property_map``.

IN:  ``IncomingMap incoming``
  The incoming map contains the incoming edges to a vertex that are
  part of shortest paths to that vertex.  The ``IncomingMap`` type
  must be a `Distributed Property Map`_.  Its key type and value type
  must both be the graph's vertex descriptor type.

  **Default**: An ``iterator_property_map`` created from a
    ``std::vector`` of ``std::vector`` of the graph's vertex
    descriptor type.

IN:  ``DistanceMap distance``
  The distance map records the distance to vertices during the
  shortest paths portion of the algorithm.  The ``DistanceMap`` type
  must be a `Distributed Property Map`_.  Its key type must be the
  graph's vertex descriptor type.

  **Default**: An ``iterator_property_map`` created from a
    ``std::vector`` of the value type of the ``CentralityMap``.

IN: ``DependencyMap dependency`` 
  The dependency map records the dependency of each vertex during the
  centrality calculation portion of the algorithm.  The
  ``DependencyMap`` type must be a `Distributed Property Map`_.  Its
  key type must be the graph's vertex descriptor type.

  **Default**: An ``iterator_property_map`` created from a
    ``std::vector`` of the value type of the ``CentralityMap``.

IN:  ``PathCountMap path_count``

  The path count map records the number of shortest paths each vertex
  is on during the centrality calculation portion of the algorithm.
  The ``PathCountMap`` type must be a `Distributed Property Map`_.
  Its key type must be the graph's vertex descriptor type.

  **Default**: An ``iterator_property_map`` created from a
    ``std::vector`` of the graph's degree size type.

IN:  ``VertexIndexMap vertex_index``
  A model of `Readable Property Map`_ whose key type is the vertex
  descriptor type of the graph ``g`` and whose value type is an
  integral type. The property map should map from vertices to their
  (local) indices in the range *[0, num_vertices(g))*.

  **Default**: ``get(vertex_index, g)``

IN:  ``WeightMap weight_map``
  A model of `Readable Property Map`_ whose key type is the edge
  descriptor type of the graph ``g``.  If not supplied the betweenness
  centrality calculation will be unweighted.

IN: ``Buffer sources`` 
  A model of Buffer_ containing the starting vertices for the
  algorithm.  If ``sources`` is empty a complete betweenness
  centrality calculation using all vertices in ``g`` will be
  performed.  The value type of the Buffer must be the graph's vertex
  descriptor type.

  **Default**: An empty ``boost::queue`` of int.

Complexity
----------

Computing the shortest paths, counting them, and computing the
contribution to the centrality map is *O(V log V)*.  Calculating exact
betweenness centrality requires counting the shortest paths from all
vertices in ``g``, thus exact betweenness centrality is *O(V^2 log
V)*.

Algorithm Description
---------------------

For the vertices in ``sources`` (or all vertices in ``g`` when
``sources`` is empty) the algorithm first calls a customized
implementation of delta_stepping_shortest_paths_ which maintains a
shortest path tree using an ``IncomingMap``.  The ``IncomingMap``
contains the source of all incoming edges on shortest paths.

The ``IncomingMap`` defines the shortest path DAG at the target of the
edges in the shortest paths tree.  In the bidirectional case edge
flags could be used to translate the shortest paths information to the
source of the edges.  Setting edge flags during the shortest path
computation rather than using an ``IncomingMap`` would result in
adding an *O(V)* factor to the inner loop of the shortest paths
computation to account for having to clear edge flags when a new
shortest path is found.  This would increase the complexity of the
algorithm.  Asymptotically, the current implementation is better,
however using edge flags in the bidirectional case would reduce the
number of supersteps required by the depth of the shortest paths DAG
for each vertex.  Currently an ``outgoing`` map is explicitly
constructed by simply reversing the edges in the incoming map.  Once
the ``outgoing`` map is constructed it is traversed in dependency
order from the source of the shortest paths calculation in order to
compute path counts.  Once path counts are computed the shortest paths
DAG is again traversed in dependency order from the source to
calculate the dependency and centrality of each vertex.

The algorithm is complete when the centrality has been computed from
all vertices in ``g``.

Bibliography
------------

.. [Brandes01] Ulrik Brandes.  A Faster Algorithm for Betweenness
  Centrality. In the Journal of Mathematical Sociology, volume 25
  number 2, pages 163--177, 2001.

.. [Edmonds09] Nick Edmonds, Torsten Hoefler, and Andrew Lumsdaine.
  A Space-Efficient Parallel Algorithm for Computing Betweenness
  Centrality in Sparse Networks.  Indiana University tech report.
  2009.

-----------------------------------------------------------------------------

Copyright (C) 2009 The Trustees of Indiana University.

Authors: Nick Edmonds and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _delta_stepping_shortest_paths: dijkstra_shortest_paths.html
.. _Distributed Graph: DistributedGraph.html
.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html
.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
.. _Buffer: http://www.boost.org/libs/graph/doc/Buffer.html
.. _Process Group: process_group.html
.. _Distributed Property Map: distributed_property_map.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Boman Et Al Graph Coloring (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/boman_et_al_graph_coloring.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

=================================
|Logo| Boman et al graph coloring
=================================

::
  
  namespace graph { 
    template<typename DistributedGraph, typename ColorMap>
    typename property_traits<ColorMap>::value_type
    boman_et_al_graph_coloring
      (const DistributedGraph& g,
       ColorMap color,
       typename graph_traits<DistributedGraph>::vertices_size_type s = 100);

    template<typename DistributedGraph, typename ColorMap, typename ChooseColor>
    typename property_traits<ColorMap>::value_type
    boman_et_al_graph_coloring
      (const DistributedGraph& g,
       ColorMap color,
       typename graph_traits<DistributedGraph>::vertices_size_type s,
       ChooseColor choose_color);

    template<typename DistributedGraph, typename ColorMap, typename ChooseColor, 
             typename VertexOrdering>
    typename property_traits<ColorMap>::value_type
    boman_et_al_graph_coloring
      (const DistributedGraph& g, ColorMap color,
       typename graph_traits<DistributedGraph>::vertices_size_type s,
       ChooseColor choose_color, VertexOrdering ordering);

    template<typename DistributedGraph, typename ColorMap, typename ChooseColor,
             typename VertexOrdering, typename VertexIndexMap>
    typename property_traits<ColorMap>::value_type
    boman_et_al_graph_coloring
      (const DistributedGraph& g,
       ColorMap color,
       typename graph_traits<DistributedGraph>::vertices_size_type s,
       ChooseColor choose_color,
       VertexOrdering ordering, VertexIndexMap vertex_index);
  } 
  
The ``boman_et_al_graph_coloring`` function colors the vertices of an
undirected, distributed graph such that no two adjacent vertices have
the same color. All of the vertices of a given color form an
independent set in the graph. Graph coloring has been used to solve
various problems, including register allocation in compilers,
optimization problems, and scheduling problems.

.. image:: ../vertex_coloring.png
  :width: 462
  :height: 269
  :alt: Vertex coloring example
  :align: right

The problem of coloring a graph with the fewest possible number of
colors is NP-complete, so many algorithms (including the one
implemented here) are heuristic algorithms that try to minimize the
number of colors but are not guaranteed to provide an optimal
solution. This algorithm [BBC05]_ is similar to the
``sequential_vertex_coloring`` algorithm, that iterates through the
vertices once and selects the lowest-numbered color that the current
vertex can have. The coloring and the number of colors is therefore
related to the ordering of the vertices in the sequential case.

The distributed ``boman_et_al_graph_coloring`` algorithm will produce
different colorings depending on the ordering and distribution of the
vertices and the number of parallel processes cooperating to perform
the coloring. 

The algorithm returns the number of colors ``num_colors`` used to
color the graph.

.. contents::

Where Defined
~~~~~~~~~~~~~
<``boost/graph/distributed/boman_et_al_graph_coloring.hpp``>

Parameters
~~~~~~~~~~

IN: ``Graph& g``
  The graph type must be a model of `Distributed Vertex List Graph`_ and
  `Distributed Edge List Graph`_. 



UTIL/OUT: ``ColorMap color``
  Stores the color of each vertex, which will be a value in the range
  [0, ``num_colors``). The type ``ColorMap`` must model the
  `Read/Write Property Map`_ concept and must be a `distributed
  property map`_.



IN: ``vertices_size_type s``
  The number of vertices to color within each superstep. After
  ``s`` vertices have been colored, the colors of boundary vertices
  will be sent to their out-of-process neighbors. Smaller values
  communicate more often but may reduce the risk of conflicts,
  whereas larger values do more work in between communication steps
  but may create many conflicts.

  **Default**: 100

IN: ``ChooseColor choose_color``
  A function object that chooses the color for a vertex given the
  colors of its neighbors. The function object will be passed a vector
  of values (``marked``) and a ``marked_true`` value, and should
  return a ``color`` value such that ``color >= marked.size()`` or
  ``marked[color] != marked_true``. 

  **Default**:
  ``boost::graph::distributed::first_fit_color<color_type>()``, where
  ``color_type`` is the value type of the ``ColorMap`` property map.

IN: ``VertexOrdering ordering``
  A binary predicate function object that provides total ordering on
  the vertices in the graph. Whenever a conflict arises, only one of
  the processes involved will recolor the vertex in the next round,
  and this ordering determines which vertex should be considered
  conflicting (its owning process will then handle the
  conflict). Ideally, this predicate should order vertices so that
  conflicting vertices will be spread uniformly across
  processes. However, this predicate *must* resolve the same way on
  both processors. 

  **Default**: *unspecified*

IN: ``VertexIndexMap index``
  A mapping from vertex descriptors to indices in the range *[0,
  num_vertices(g))*. This must be a `Readable Property Map`_ whose
  key type is a vertex descriptor and whose value type is an integral
  type, typically the ``vertices_size_type`` of the graph.

  **Default:** ``get(vertex_index, g)``

Complexity
~~~~~~~~~~
The complexity of this algorithm is hard to characterize,
because it depends greatly on the number of *conflicts* that occur
during the algorithm. A conflict occurs when a *boundary vertex*
(i.e., a vertex that is adjacent to a vertex stored on a different
processor) is given the same color is a boundary vertex adjacency to
it (but on another processor). Conflicting vertices must be assigned
new colors, requiring additional work and communication. The work
involved in reassigning a color for a conflicting vertex is *O(d)*,
where *d* is the degree of the vertex and *O(1)* messages of *O(1)*
size are needed to resolve the conflict. Note that the number of
conflicts grows with (1) the number of processes and (2) the number
of inter-process edges.

Performance 
~~~~~~~~~~~

The performance of this implementation of Bomen et al's graph coloring
algorithm is illustrated by the following charts. Scaling and
performance is reasonable for all of the graphs we have tried.

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&cluster=Odin&columns=11
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&cluster=Odin&columns=11&speedup=1

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&cluster=Odin&columns=11
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&cluster=Odin&columns=11&speedup=1

-----------------------------------------------------------------------------

Copyright (C) 2005 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Distributed Vertex List Graph: DistributedVertexListGraph.html
.. _Distributed Edge List Graph: DistributedEdgeListGraph.html
.. _Distributed property map: distributed_property_map.html
.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
.. _Read/Write Property Map: http://www.boost.org/libs/property_map/ReadWritePropertyMap.html
.. [BBC05] Erik G. Boman, Doruk Bozdag, Umit Catalyurek, Assefaw
   H. Gebremedhin, and Fredrik Manne. A Scalable Parallel Graph Coloring
   Algorithm for Distributed Memory Computers. [preprint]

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Breadth First Search (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/breadth_first_search.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===========================
|Logo| Breadth-First Search
===========================

::

  // named parameter version
  template <class Graph, class P, class T, class R>
  void breadth_first_search(Graph& G, 
    typename graph_traits<Graph>::vertex_descriptor s, 
    const bgl_named_params& params);

  // non-named parameter version
  template <class Graph, class Buffer, class BFSVisitor, 
            class ColorMap>
  void breadth_first_search(const Graph& g, 
     typename graph_traits<Graph>::vertex_descriptor s, 
     Buffer& Q, BFSVisitor vis, ColorMap color);

The ``breadth_first_search()`` function performs a distributed breadth-first
traversal of a directed or undirected graph. The distributed BFS is
syntactically equivalent to its `sequential counterpart`_, which
provides additional background and discussion. Differences in
semantics are highlighted here, and we refer the reader to the
documentation of the `sequential breadth-first search`_ for the
remainder of the details.

This distributed breadth-first search algorithm implements a
*level-synchronized* breadth-first search, meaning that all vertices
in a given level of the BFS tree will be processed (potentially in
parallel) before any vertices from a successive level in the tree are
processed. Distributed breadth-first search visitors should account
for this behavior, a topic discussed further in `Visitor Event
Points`_. 

.. contents::

Where Defined
-------------
<``boost/graph/breadth_first_search.hpp``>

Parameter Defaults
------------------
All parameters of the `sequential breadth-first search`_ are supported
and have essentially the same meaning. Only differences are documented
here.

IN: ``Graph& g``
  The graph type must be a model of `Distributed Graph`_. 


IN: ``vertex_descriptor s``
  The start vertex must be the same in every process.


IN: ``visitor(BFSVisitor vis)``
  The visitor must be a distributed BFS visitor. The suble differences
  between sequential and distributed BFS visitors are discussed in the
  section `Visitor Event Points`_.

UTIL/OUT: ``color_map(ColorMap color)``
  The color map must be a `Distributed Property Map`_ with the same
  process group as the graph ``g`` whose colors must monotonically
  darken (white -> gray -> black). The default value is a distributed
  ``iterator_property_map`` created from a ``std::vector`` of
  ``default_color_type``. 


UTIL: ``buffer(Buffer& Q)``
  The queue must be a distributed queue that passes vertices to their
  owning process. If already-visited vertices should not be visited
  again (as is typical for BFS), the queue must filter duplicates
  itself. The queue controls synchronization within the algorithm: its
  ``empty()`` method must not return ``true`` until all local queues
  are empty. 
  
  **Default:** A ``distributed_queue`` of a ``filtered_queue`` over a
    standard ``boost::queue``. This queue filters out duplicate
    vertices and distributes vertices appropriately.

Complexity
----------
This algorithm performs *O(V + E)* work in *d + 1* BSP supersteps,
where *d* is the diameter of the connected component being
searched. Over all supersteps, *O(E)* messages of constant size will
be transmitted.

Visitor Event Points
--------------------
The `BFS Visitor`_ concept defines 9 event points that will be
triggered by the `sequential breadth-first search`_. The distributed
BFS retains these nine event points, but the sequence of events
triggered and the process in which each event occurs will change
depending on the distribution of the graph. 

``initialize_vertex(s, g)``
  This will be invoked by every process for each local vertex.


``discover_vertex(u, g)``
  This will be invoked each time a process discovers a new vertex
  ``u``. Due to incomplete information in distributed property maps,
  this event may be triggered many times for the same vertex ``u``.


``examine_vertex(u, g)``
  This will be invoked by the process owning the vertex ``u``. If the
  distributed queue prevents duplicates, it will be invoked only
  once for a particular vertex ``u``.


``examine_edge(e, g)``
  This will be invoked by the process owning the source vertex of
  ``e``. If the distributed queue prevents duplicates, it will be
  invoked only once for a particular edge ``e``.


``tree_edge(e, g)``
  Similar to ``examine_edge``, this will be invoked by the process
  owning the source vertex and may be invoked only once. Unlike the
  sequential BFS, this event may be triggered even when the target has
  already been discovered (but by a different process). Thus, some
  ``non_tree_edge`` events in a sequential BFS may become
  ``tree_edge`` in a distributed BFS.


``non_tree_edge(e, g)``
  Some ``non_tree_edge`` events in a sequential BFS may become
  ``tree_edge`` events in a distributed BFS. See the description of
  ``tree_edge`` for additional details.


``gray_target(e, g)``
  As with ``tree_edge`` not knowing when another process has already
  discovered a vertex, ``gray_target`` events may occur in a
  distributed BFS when ``black_target`` events may occur in a
  sequential BFS, due to a lack of information on a given
  processor. The source of edge ``e`` will be local to the process
  executing this event.


``black_target(e, g)``
  See documentation for ``gray_target``


``finish_vertex(e, g)``
  See documentation for ``examine_vertex``.

Making Visitors Safe for Distributed BFS

To illustrate the differences between sequential and distributed BFS
visitors, we consider a BFS visitor that places the distance from the
source vertex to every other vertex in a property map. The sequential
visitor is very simple::

  template<typename DistanceMap>
  struct bfs_discovery_visitor : bfs_visitor<> 
  {
    bfs_discovery_visitor(DistanceMap distance) : distance(distance) {}

    template<typename Edge, typename Graph>
    void tree_edge(Edge e, const Graph& g)
    {
      std::size_t new_distance = get(distance, source(e, g)) + 1;
      put(distance, target(e, g), new_distance);
    }
    
   private:
    DistanceMap distance;
  };

To revisit this code for distributed BFS, we consider the three points
in the section `Making Visitors Safe for Distributed BFS`_:

1. The distance map will need to become distributed, because the
   distance to each vertex should be stored in the process owning the
   vertex. This is actually a requirement on the user to provide such
   a distributed property map, although in many cases the property map
   will automatically be distributed and no syntactic changes will be
   required. 

2. This visitor *does* require a precise sequence of events that may
   change with a distributed BFS. The extraneous ``tree_edge`` events
   that may occur could result in attempts to put distances into the
   distance map multiple times for a single vertex. We therefore need
   to consider bullet #3.

3. Since multiple distance values may be written for each vertex, we
   must always choose the best value we can find to update the
   distance map. The distributed property map ``distance`` needs to
   resolve distances to the smallest distance it has seen. For
   instance, process 0 may find vertex ``u`` at level 3 but process 1
   finds it at level 5: the distance must remain at 3. To do this, we
   state that the property map's *role* is as a distance map, which
   introduces an appropriate reduction operation::

          set_property_map_role(vertex_distance, distance);

The resulting distributed BFS visitor (which also applies, with no
changes, in the sequential BFS) is very similar to our original
sequential BFS visitor. Note the single-line difference in the
constructor::

  template<typename DistanceMap>
  struct bfs_discovery_visitor : bfs_visitor<> 
  {
    bfs_discovery_visitor(DistanceMap distance) : distance(distance) 
    {
      set_property_map_role(vertex_distance, distance);
    }

    template<typename Edge, typename Graph>
    void tree_edge(Edge e, const Graph& g)
    {
      std::size_t new_distance = get(distance, source(e, g)) + 1;
      put(distance, target(e, g), new_distance);
    }
    
   private:
    DistanceMap distance;
  };


Performance
-----------
The performance of Breadth-First Search is illustrated by the
following charts. Scaling and performance is reasonable for all of the
graphs we have tried. 

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=4
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=4&speedup=1

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=4
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=4&speedup=1

-----------------------------------------------------------------------------

Copyright (C) 2004 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _sequential counterpart: http://www.boost.org/libs/graph/doc/breadth_first_search.html
.. _sequential breadth-first search: http://www.boost.org/libs/graph/doc/breadth_first_search.html
.. _Distributed Graph: DistributedGraph.html
.. _Distributed Property Map: distributed_property_map.html
.. _BFS Visitor: http://www.boost.org/libs/graph/doc/BFSVisitor.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Connected Components (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/connected_components.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===========================
|Logo| Connected Components
===========================

::
 
  namespace graph {
    // Default constructed ParentMap
    template<typename Graph, typename ComponentMap, typename ParentMap>
    typename property_traits<ComponentMap>::value_type
    connected_components( const Graph& g, ComponentMap c);

    // User supplied ParentMap
    template<typename Graph, typename ComponentMap, typename ParentMap>
    typename property_traits<ComponentMap>::value_type
    connected_components( const Graph& g, ComponentMap c, ParentMap p);
  }

The ``connected_components()`` function computes the connected
components of an undirected graph.  The distributed connected
components algorithm uses the sequential version of the connected
components algorithm to compute the connected components of the local
subgraph, then executes the parallel phase of the algorithm.  The
parallel portion of the connected components algorithm is loosely
based on the work of Goddard, Kumar, and Prins. The interface is a
superset of the interface to the BGL `sequential connected
components`_ algorithm.

Prior to executing the sequential phase of the algorithm, each process
identifies the roots of its local components.  An adjacency list of
all vertices adjacent to members of the component is then constructed
at the root vertex of each component.

The parallel phase of the distributed connected components algorithm
consists of a series of supersteps.  In each superstep, each root
attempts to hook to a member of it's adjacency list by assigning it's
parent pointer to that vertex.  Hooking is restricted to vertices
which are logically less than the current vertex to prevent looping.
Vertices which hook successfully are removed from the list of roots
and placed on another list of completed vertices.  All completed
vertices now execute a pointer jumping step until every completed
vertex has as its parent the root of a component.  This pointer
jumping step may be further optimized by the addition of Cycle
Reduction (CR) rules developed by Johnson and Metaxas, however current
performance evaluations indicate that this would have a negligible
impact on the overall performance of the algorithm.  These CR rules
reduce the number of pointer jumping steps from *O(n)* to *O(log n)*.
Following this pointer jumping step, roots which have hooked in this
phase transmit their adjacency list to their new parent.  The
remaining roots receive these edges and execute a pruning step on
their adjacency lists to remove vertices that are now members of their
component.  The parallel phase of the algorithm is complete when no
root successfully hooks.  Once the parallel phase is complete a final
pointer jumping step is performed on all vertices to assign the parent
pointers of the leaves of the initial local subgraph components to
their final parent which has now been determined.

The single largest performance bottleneck in the distributed connected
components algorithm is the effect of poor vertex distribution on the
algorithm.  For sparse graphs with a single large component, many
roots may hook to the same component, resulting in severe load
imbalance at the process owning this component.  Several methods of
modifying the hooking strategy to avoid this behavior have been
implemented but none has been successful as of yet.

.. contents::

Where Defined
-------------
<``boost/graph/connected_components.hpp``>

Parameters
----------

IN:  ``Graph& g``
  The graph typed must be a model of `Distributed Graph`_.

OUT:  ``ComponentMap c``
  The algorithm computes how many connected components are in the
  graph, and assigns each component an integer label.  The algorithm
  then records to which component each vertex in the graph belongs by
  recording the component number in the component property map.  The
  ``ComponentMap`` type must be a `Distributed Property Map`_.  The
  value type must be the ``vertices_size_type`` of the graph.  The key
  type must be the graph's vertex descriptor type. If you do not wish
  to compute component numbers, pass ``dummy_property_map`` as the
  component map and parent information will be provided in the parent
  map. 

UTIL:  ``ParentMap p``
  A parent map may be supplied to the algorithm, if not supplied the
  parent map will be constructed automatically.  The ``ParentMap`` type
  must be a `Distributed Property Map`_.  The value type and key type
  must be the graph's vertex descriptor type.

OUT:  ``property_traits<ComponentMap>::value_type``
  The number of components found will be returned as the value type of
  the component map.

Complexity
----------

The local phase of the algorithm is *O(V + E)*.  The parallel phase of
the algorithm requires at most *O(d)* supersteps where *d* is the
number of initial roots.  *d* is at most *O(V)* but becomes
significantly smaller as *E* increases.  The pointer jumping phase
within each superstep requires at most *O(c)* steps on each of the
completed roots where *c* is the length of the longest cycle.
Application of CR rules can reduce this to *O(log c)*.

Performance
-----------
The following charts illustrate the performance of the Parallel BGL
connected components algorithm. It performs well on very sparse and
very dense graphs. However, for cases where the graph has a medium
density with a giant connected component, the algorithm will perform
poorly. This is a known problem with the algorithm and as far as we
know all implemented algorithms have this degenerate behavior.

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=9
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=9&speedup=1

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=9
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=9&speedup=1


-----------------------------------------------------------------------------

Copyright (C) 2004 The Trustees of Indiana University.

Authors: Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Sequential connected components: http://www.boost.org/libs/graph/doc/connected_components.html
.. _Distributed Graph: DistributedGraph.html
.. _Distributed Property Map: distributed_property_map.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Connected Components Parallel Search (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/connected_components_parallel_search.rst`)

.. Copyright (C) 2004-2009 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===========================================
|Logo| Connected Components Parallel Search
===========================================

::

   namespace graph { namespace distributed {
     template<typename Graph, typename ComponentMap>
     typename property_traits<ComponentMap>::value_type
     connected_components_ps(const Graph& g, ComponentMap c)
   } }

The ``connected_components_ps()`` function computes the connected
components of a graph by performing a breadth-first search from
several sources in parallel while recording and eventually resolving
the collisions.

.. contents::

Where Defined
-------------
<``boost/graph/distributed/connected_components_parallel_search.hpp``>

Parameters
----------

IN:  ``const Graph& g``
  The graph type must be a model of `Distributed Graph`_.  The graph
  type must also model the `Incidence Graph`_ and be directed.

OUT:  ``ComponentMap c``
  The algorithm computes how many connected components are in the
  graph, and assigns each component an integer label.  The algorithm
  then records to which component each vertex in the graph belongs by
  recording the component number in the component property map.  The
  ``ComponentMap`` type must be a `Distributed Property Map`_.  The
  value type must be the ``vertices_size_type`` of the graph.  The key
  type must be the graph's vertex descriptor type.

Complexity
----------

*O(PN^2 + VNP)* work, in *O(N + V)* time, where N is the
number of mappings and V is the number of local vertices.

Algorithm Description
---------------------

Every *N* th nodes starts a parallel search from the first vertex in
their local vertex list during the first superstep (the other nodes
remain idle during the first superstep to reduce the number of
conflicts in numbering the components).  At each superstep, all new
component mappings from remote nodes are handled.  If there is no work
from remote updates, a new vertex is removed from the local list and
added to the work queue.

Components are allocated from the ``component_value_allocator``
object, which ensures that a given component number is unique in the
system, currently by using the rank and number of processes to stride
allocations.

When two components are discovered to actually be the same component,
a collision is recorded.  The lower component number is prefered in
the resolution, so component numbering resolution is consistent.
After the search has exhausted all vertices in the graph, the mapping
is shared with all processes and they independently resolve the
comonent mapping.  This phase can likely be significantly sped up if a
clever algorithm for the reduction can be found.

-----------------------------------------------------------------------------

Copyright (C) 2009 The Trustees of Indiana University.

Authors: Brian Barrett, Douglas Gregor, and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Distributed Graph: DistributedGraph.html
.. _Distributed Property Map: distributed_property_map.html
.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Dehne Gotz Min Spanning Tree (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/dehne_gotz_min_spanning_tree.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

============================
|Logo| Minimum Spanning Tree
============================

The Parallel BGL contains four `minimum spanning tree`_ (MST)
algorithms [DG98]_ for use on undirected, weighted, distributed
graphs. The graphs need not be connected: each algorithm will compute
a minimum spanning forest (MSF) when provided with a disconnected
graph.

The interface to each of the four algorithms is similar to the
implementation of 'Kruskal's algorithm'_ in the sequential BGL. Each
accepts, at a minimum, a graph, a weight map, and an output
iterator. The edges of the MST (or MSF) will be output via the output
iterator on process 0: other processes may receive edges on their
output iterators, but the set may not be complete, depending on the
algorithm. The algorithm parameters are documented together, because
they do not vary greatly. See the section `Selecting an MST
algorithm`_ for advice on algorithm selection.

The graph itself must model the `Vertex List Graph`_ concept and the
Distributed Edge List Graph concept. Since the most common
distributed graph structure, the `distributed adjacency list`_, only
models the Distributed Vertex List Graph concept, it may only be used
with these algorithms when wrapped in a suitable adaptor, such as the
`vertex_list_adaptor`_. 

.. contents::

Where Defined
-------------
<``boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp``>

Parameters
----------

IN: ``Graph& g``
  The graph type must be a model of `Vertex List Graph`_ and
  `Distributed Edge List Graph`_. 



IN/OUT: ``WeightMap weight``
  The weight map must be a `Distributed Property Map`_ and a `Readable
  Property Map`_ whose key type is the edge descriptor of the graph
  and whose value type is numerical.


  
IN/OUT: ``OutputIterator out``
  The output iterator through which the edges of the MSF will be
  written. Must be capable of accepting edge descriptors for output. 




IN: ``VertexIndexMap index``
  A mapping from vertex descriptors to indices in the range *[0,
  num_vertices(g))*. This must be a `Readable Property Map`_ whose
  key type is a vertex descriptor and whose value type is an integral
  type, typically the ``vertices_size_type`` of the graph.

  **Default:** ``get(vertex_index, g)``


IN/UTIL: ``RankMap rank_map``
  Stores the rank of each vertex, which is used for maintaining
  union-find data structures. This must be a `Read/Write Property Map`_
  whose key type is a vertex descriptor and whose value type is an
  integral type. 

  **Default:** An ``iterator_property_map`` built from an STL vector
  of the ``vertices_size_type`` of the graph and the vertex index map.


IN/UTIL: ``ParentMap parent_map``
  Stores the parent (representative) of each vertex, which is used for
  maintaining union-find data structures. This must be a `Read/Write
  Property Map`_ whose key type is a vertex descriptor and whose value
  type is also a vertex descriptor.

  **Default:** An ``iterator_property_map`` built from an STL vector
  of the ``vertex_descriptor`` of the graph and the vertex index map.


IN/UTIL: ``SupervertexMap supervertex_map``
  Stores the supervertex index of each vertex, which is used for
  maintaining the supervertex list data structures. This must be a
  `Read/Write Property Map`_ whose key type is a vertex descriptor and
  whose value type is an integral type.

  **Default:** An ``iterator_property_map`` built from an STL vector
  of the ``vertices_size_type`` of the graph and the vertex index map.



``dense_boruvka_minimum_spanning_tree``
---------------------------------------

:: 

  namespace graph {
    template<typename Graph, typename WeightMap, typename OutputIterator, 
             typename VertexIndexMap, typename RankMap, typename ParentMap, 
             typename SupervertexMap>
    OutputIterator
    dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map,
                                      OutputIterator out, 
                                      VertexIndexMap index,
                                      RankMap rank_map, ParentMap parent_map,
                                      SupervertexMap supervertex_map);

    template<typename Graph, typename WeightMap, typename OutputIterator, 
             typename VertexIndex>
    OutputIterator
    dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map,
                                      OutputIterator out, VertexIndex index);

    template<typename Graph, typename WeightMap, typename OutputIterator>
    OutputIterator
    dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map,
                                      OutputIterator out);
  }

Description
~~~~~~~~~~~

The dense Boruvka distributed minimum spanning tree algorithm is a
direct parallelization of the sequential MST algorithm by
Boruvka. The algorithm first creates a *supervertex* out of each
vertex. Then, in each iteration, it finds the smallest-weight edge
incident to each vertex, collapses supervertices along these edges,
and removals all self loops. The only difference between the
sequential and parallel algorithms is that the parallel algorithm
performs an all-reduce operation so that all processes have the
global minimum set of edges.

Unlike the other three algorithms, this algorithm emits the complete
list of edges in the minimum spanning forest via the output iterator
on all processes. It may therefore be more useful than the others
when parallelizing sequential BGL programs.

Complexity
~~~~~~~~~~

The distributed algorithm requires *O(log n)* BSP supersteps, each of
which requires *O(m/p + n)* time and *O(n)* communication per
process. 

Performance
~~~~~~~~~~~

The following charts illustrate the performance of this algorithm on
various random graphs. We see that the algorithm scales well up to 64
or 128 processors, depending on the type of graph, for dense
graphs. However, for sparse graphs performance tapers off as the
number of processors surpases *m/n*, i.e., the average degree (which
is 30 for this graph). This behavior is expected from the algorithm.

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=5
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=5&speedup=1

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=5
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=5&speedup=1

``merge_local_minimum_spanning_trees``
--------------------------------------

::

  namespace graph {
    template<typename Graph, typename WeightMap, typename OutputIterator,
             typename VertexIndexMap>
    OutputIterator
    merge_local_minimum_spanning_trees(const Graph& g, WeightMap weight,
                                       OutputIterator out, 
                                       VertexIndexMap index);

    template<typename Graph, typename WeightMap, typename OutputIterator>
    inline OutputIterator
    merge_local_minimum_spanning_trees(const Graph& g, WeightMap weight,
                                       OutputIterator out);
  }

Description
~~~~~~~~~~~

The merging local MSTs algorithm operates by computing minimum
spanning forests from the edges stored on each process. Then the
processes merge their edge lists along a tree. The child nodes cease
participating in the computation, but the parent nodes recompute MSFs
from the newly acquired edges. In the final round, the root of the
tree computes the global MSFs, having received candidate edges from
every other process via the tree.

Complexity
~~~~~~~~~~

This algorithm requires *O(log_D p)* BSP supersteps (where *D* is the
number of children in the tree, and is currently fixed at 3). Each
superstep requires *O((m/p) log (m/p) + n)* time and *O(m/p)*
communication per process.

Performance
~~~~~~~~~~~

The following charts illustrate the performance of this algorithm on
various random graphs. The algorithm only scales well for very dense
graphs, where most of the work is performed in the initial stage and
there is very little work in the later stages. 

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=6
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=6&speedup=1

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=6
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=6&speedup=1


``boruvka_then_merge``
----------------------

::

  namespace graph {
    template<typename Graph, typename WeightMap, typename OutputIterator,
             typename VertexIndexMap, typename RankMap, typename ParentMap,
             typename SupervertexMap>
    OutputIterator
    boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out,
                       VertexIndexMap index, RankMap rank_map, 
                       ParentMap parent_map, SupervertexMap
                       supervertex_map);

    template<typename Graph, typename WeightMap, typename OutputIterator,
             typename VertexIndexMap>
    inline OutputIterator
    boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out,
                        VertexIndexMap index);

    template<typename Graph, typename WeightMap, typename OutputIterator>
    inline OutputIterator
    boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out);
  }

Description
~~~~~~~~~~~

This algorithm applies both Boruvka steps and local MSF merging steps
together to achieve better asymptotic performance than either
algorithm alone. It first executes Boruvka steps until only *n/(log_d
p)^2* supervertices remain, then completes the MSF computation by
performing local MSF merging on the remaining edges and
supervertices. 

Complexity
~~~~~~~~~~

This algorithm requires *log_D p* + *log log_D p* BSP supersteps. The
time required by each superstep depends on the type of superstep
being performed; see the distributed Boruvka or merging local MSFS
algorithms for details.

Performance
~~~~~~~~~~~

The following charts illustrate the performance of this algorithm on
various random graphs. We see that the algorithm scales well up to 64
or 128 processors, depending on the type of graph, for dense
graphs. However, for sparse graphs performance tapers off as the
number of processors surpases *m/n*, i.e., the average degree (which
is 30 for this graph). This behavior is expected from the algorithm.

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=7
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=7&speedup=1

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=7
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=7&speedup=1

``boruvka_mixed_merge``
-----------------------

::

  namespace {
    template<typename Graph, typename WeightMap, typename OutputIterator,
             typename VertexIndexMap, typename RankMap, typename ParentMap,
             typename SupervertexMap>
    OutputIterator
    boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out,
                        VertexIndexMap index, RankMap rank_map, 
                        ParentMap parent_map, SupervertexMap
                        supervertex_map);

    template<typename Graph, typename WeightMap, typename OutputIterator,
             typename VertexIndexMap>
    inline OutputIterator
    boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out,
                        VertexIndexMap index);

    template<typename Graph, typename WeightMap, typename OutputIterator>
    inline OutputIterator
    boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out);
  }

Description
~~~~~~~~~~~

This algorithm applies both Boruvka steps and local MSF merging steps
together to achieve better asymptotic performance than either method
alone. In each iteration, the algorithm first performs a Boruvka step
and then merges the local MSFs computed based on the supervertex
graph. 

Complexity
~~~~~~~~~~

This algorithm requires *log_D p* BSP supersteps. The
time required by each superstep depends on the type of superstep
being performed; see the distributed Boruvka or merging local MSFS
algorithms for details. However, the algorithm is
communication-optional (requiring *O(n)* communication overall) when
the graph is sufficiently dense, i.e., *m/n >= p*.

Performance
~~~~~~~~~~~

The following charts illustrate the performance of this algorithm on
various random graphs. We see that the algorithm scales well up to 64
or 128 processors, depending on the type of graph, for dense
graphs. However, for sparse graphs performance tapers off as the
number of processors surpases *m/n*, i.e., the average degree (which
is 30 for this graph). This behavior is expected from the algorithm.

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=8
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeSparse&columns=8&speedup=1

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=8
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER,SF,SW&dataset=TimeDense&columns=8&speedup=1


Selecting an MST algorithm
--------------------------

Dehne and Gotz reported [DG98]_ mixed results when evaluating these
four algorithms. No particular algorithm was clearly better than the
others in all cases. However, the asymptotically best algorithm
(``boruvka_mixed_merge``) seemed to perform more poorly in their tests
than the other merging-based algorithms. The following performance
charts illustrate the performance of these four minimum spanning tree
implementations. 

Overall, ``dense_boruvka_minimum_spanning_tree`` gives the most
consistent performance and scalability for the graphs we
tested. Additionally, it may be more suitable for sequential programs
that are being parallelized, because it emits complete MSF edge lists
via the output iterators in every process.

Performance on Sparse Graphs
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER&dataset=TimeSparse&columns=5,6,7,8
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER&dataset=TimeSparse&columns=5,6,7,8&speedup=1

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SF&dataset=TimeSparse&columns=5,6,7,8
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SF&dataset=TimeSparse&columns=5,6,7,8&speedup=1

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SW&dataset=TimeSparse&columns=5,6,7,8
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SW&dataset=TimeSparse&columns=5,6,7,8&speedup=1

Performance on Dense Graphs
~~~~~~~~~~~~~~~~~~~~~~~~~~~
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER&dataset=TimeDense&columns=5,6,7,8
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=ER&dataset=TimeDense&columns=5,6,7,8&speedup=1

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SF&dataset=TimeDense&columns=5,6,7,8
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SF&dataset=TimeDense&columns=5,6,7,8&speedup=1

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SW&dataset=TimeDense&columns=5,6,7,8
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?generator=SW&dataset=TimeDense&columns=5,6,7,8&speedup=1

-----------------------------------------------------------------------------

Copyright (C) 2004 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _minimum spanning tree: http://www.boost.org/libs/graph/doc/graph_theory_review.html#sec:minimum-spanning-tree
.. _Kruskal's algorithm: http://www.boost.org/libs/graph/doc/kruskal_min_spanning_tree.html
.. _Vertex list graph: http://www.boost.org/libs/graph/doc/VertexListGraph.html
.. _distributed adjacency list: distributed_adjacency_list.html
.. _vertex_list_adaptor: vertex_list_adaptor.html
.. _Distributed Edge List Graph: DistributedEdgeListGraph.html
.. _Distributed property map: distributed_property_map.html
.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
.. _Read/Write Property Map: http://www.boost.org/libs/property_map/ReadWritePropertyMap.html

.. [DG98] Frank Dehne and Silvia Gotz. *Practical Parallel Algorithms
    for Minimum Spanning Trees*. In Symposium on Reliable Distributed Systems, 
    pages 366--371, 1998.

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Dijkstra Example (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/dijkstra_example.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

=======================
Parallel Shortest Paths
=======================
To illustrate the use of the Parallel Boost Graph Library, we
illustrate the use of both the sequential and parallel BGL to find
the shortest paths from vertex A to every other vertex in the
following simple graph:

.. image:: ../dijkstra_seq_graph.png

With the sequential BGL_, the program to calculate shortest paths has
three stages. Readers familiar with the BGL may wish to skip ahead to
the section `Distributing the graph`_.


  - `Define the graph type`_
  - `Construct the graph`_
  - `Invoke Dijkstra's algorithm`_

Define the graph type
~~~~~~~~~~~~~~~~~~~~~

For this problem we use an adjacency list representation of the graph,
using the BGL ``adjacency_list``_ class template. It will be a directed
graph (``directedS`` parameter ) whose vertices are stored in an
``std::vector`` (``vecS`` parameter) where the outgoing edges of each
vertex are stored in an ``std::list`` (``listS`` parameter). To each
of the edges we attach an integral weight.

::

  typedef adjacency_list<listS, vecS, directedS,
                         no_property,                 // Vertex properties 
                         property<edge_weight_t, int> // Edge properties
                         > graph_t;
  typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
  typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;

Construct the graph
~~~~~~~~~~~~~~~~~~~
To build the graph, we declare an enumeration containing the node
names (for our own use) and create two arrays: the first,
``edge_array``, contains the source and target of each edge, whereas
the second, ``weights``, contains the integral weight of each
edge. We pass the contents of the arrays via pointers (used here as
iterators) to the graph constructor to build our graph:

::

  typedef std::pair Edge;
  const int num_nodes = 5;
  enum nodes { A, B, C, D, E };
  char name[] = "ABCDE";
  Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
    Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)
  };
  int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
  int num_arcs = sizeof(edge_array) / sizeof(Edge);

  graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);


Invoke Dijkstra's algorithm
~~~~~~~~~~~~~~~~~~~~~~~~~~~
To invoke Dijkstra's algorithm, we need to first decide how we want
to receive the results of the algorithm, namely the distance to each
vertex and the predecessor of each vertex (allowing reconstruction of
the shortest paths themselves). In our case, we will create two
vectors, ``p`` for predecessors and ``d`` for distances. 

Next, we determine our starting vertex ``s`` using the ``vertex``
operation on the ``adjacency_list``_ and call
``dijkstra_shortest_paths``_ with the graph ``g``, starting vertex
``s``, and two ``property maps``_ that instruct the algorithm to
store predecessors in the ``p`` vector and distances in the ``d``
vector. The algorithm automatically uses the edge weights stored
within the graph, although this capability can be overridden.

::

  // Keeps track of the predecessor of each vertex
  std::vector<vertex_descriptor> p(num_vertices(g));
  // Keeps track of the distance to each vertex
  std::vector<int> d(num_vertices(g));

  vertex_descriptor s = vertex(A, g);
  dijkstra_shortest_paths
    (g, s, 
     predecessor_map(
       make_iterator_property_map(p.begin(), get(vertex_index, g))).
     distance_map(
       make_iterator_property_map(d.begin(), get(vertex_index, g)))
     );

Distributing the graph
~~~~~~~~~~~~~~~~~~~~~~
The prior computation is entirely sequential, with the graph stored
within a single address space. To distribute the graph across several
processors without a shared address space, we need to represent the
processors and communication among them and alter the graph type. 

Processors and their interactions are abstracted via a *process
group*. In our case, we will use MPI_ for communication with
inter-processor messages sent immediately:
  
::

  typedef mpi::process_group<mpi::immediateS> process_group_type;

Next, we instruct the ``adjacency_list`` template
to distribute the vertices of the graph across our process group,
storing the local vertices in an ``std::vector``::

  typedef adjacency_list<listS, 
                         distributedS, 
                         directedS,
                         no_property,                 // Vertex properties 
                         property<edge_weight_t, int> // Edge properties
                         > graph_t;
  typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
  typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;

Note that the only difference from the sequential BGL is the use of
the ``distributedS`` selector, which identifies a distributed
graph. The vertices of the graph will be distributed among the
various processors, and the processor that owns a vertex also stores
the edges outgoing from that vertex and any properties associated
with that vertex or its edges. With three processors and the default
block distribution, the graph would be distributed in this manner:

.. image:: ../dijkstra_dist3_graph.png

Processor 0 (red) owns vertices A and B, including all edges outoing
from those vertices, processor 1 (green) owns vertices C and D (and
their edges), and processor 2 (blue) owns vertex E. Constructing this
graph uses the same syntax is the sequential graph, as in the section
`Construct the graph`_. 

The call to ``dijkstra_shortest_paths`` is syntactically equivalent to
the sequential call, but the mechanisms used are very different. The
property maps passed to ``dijkstra_shortest_paths`` are actually
*distributed* property maps, which store properties for local edges
or vertices and perform implicit communication to access properties
of remote edges or vertices when needed. The formulation of Dijkstra's
algorithm is also slightly different, because each processor can
only attempt to relax edges outgoing from local vertices: as shorter
paths to a vertex are discovered, messages to the processor owning
that vertex indicate that the vertex may require reprocessing. 

----------------------------------------------------------------------

Return to the `Parallel BGL home page`_

.. _Parallel BGL home page: index.html
.. _dijkstra_shortest_paths: http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
.. _property maps: http://www.boost.org/libs/graph/doc/using_property_maps.html
.. _adjacency_list: http://www.boost.org/libs/graph/doc/adjacency_list.html
.. _MPI: http://www-unix.mcs.anl.gov/mpi/
.. _BGL: http://www.boost.org/libs/graph/doc

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Dijkstra Shortest Paths (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/dijkstra_shortest_paths.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

==============================================
|Logo| Dijkstra's Single-Source Shortest Paths
==============================================

::

  // named parameter version
  template <typename Graph, typename P, typename T, typename R>
  void
  dijkstra_shortest_paths(Graph& g,
    typename graph_traits<Graph>::vertex_descriptor s,
    const bgl_named_params& params);

  // non-named parameter version
  template <typename Graph, typename DijkstraVisitor, 
            typename PredecessorMap, typename DistanceMap,
            typename WeightMap, typename VertexIndexMap, typename CompareFunction, typename CombineFunction, 
            typename DistInf, typename DistZero>
  void dijkstra_shortest_paths
    (const Graph& g,
     typename graph_traits<Graph>::vertex_descriptor s, 
     PredecessorMap predecessor, DistanceMap distance, WeightMap weight, 
     VertexIndexMap index_map,
     CompareFunction compare, CombineFunction combine, DistInf inf, DistZero zero,
     DijkstraVisitor vis);

The ``dijkstra_shortest_paths()`` function solves the single-source
shortest paths problem on a weighted, undirected or directed
distributed graph. There are two implementations of distributed
Dijkstra's algorithm, which offer different performance
tradeoffs. Both are accessible via the ``dijkstra_shortest_paths()``
function (for compatibility with sequential BGL programs). The
distributed Dijkstra algorithms are very similar to their sequential
counterparts. Only the differences are highlighted here; please refer
to the `sequential Dijkstra implementation`_ for additional
details. The best-performing implementation for most cases is the
`Delta-Stepping algorithm`_; however, one can also employ the more
conservative `Crauser et al.'s algorithm`_ or the simlistic  `Eager
Dijkstra's algorithm`_. 

.. contents::

Where Defined
-------------
<``boost/graph/dijkstra_shortest_paths.hpp``>

Parameters 
----------

All parameters of the `sequential Dijkstra implementation`_ are
supported and have essentially the same meaning. The distributed
Dijkstra implementations introduce a new parameter that allows one to
select `Eager Dijkstra's algorithm`_ and control the amount of work it
performs. Only differences and new parameters are documented here.

IN: ``Graph& g``
  The graph type must be a model of `Distributed Graph`_. 


IN: ``vertex_descriptor s``
  The start vertex must be the same in every process.


OUT: ``predecessor_map(PredecessorMap p_map)``
  The predecessor map must be a `Distributed Property Map`_ or 
  ``dummy_property_map``, although only the local portions of the map
  will be written. 

  **Default:** ``dummy_property_map``


UTIL/OUT: ``distance_map(DistanceMap d_map)``
  The distance map must be either a `Distributed Property Map`_ or
  ``dummy_property_map``. It will be given the ``vertex_distance``
  role. 


IN: ``visitor(DijkstraVisitor vis)``
  The visitor must be a distributed Dijkstra visitor. The suble differences
  between sequential and distributed Dijkstra visitors are discussed in the
  section `Visitor Event Points`_.


UTIL/OUT: ``color_map(ColorMap color)``
  The color map must be a `Distributed Property Map`_ with the same
  process group as the graph ``g`` whose colors must monotonically
  darken (white -> gray -> black). The default value is a distributed
  ``iterator_property_map`` created from a ``std::vector`` of
  ``default_color_type``. 


IN: ``lookahead(distance_type look)``

  When this parameter is supplied, the implementation will use the
  `Eager Dijkstra's algorithm`_ with the given lookahead value.
  Lookahead permits distributed Dijkstra's algorithm to speculatively
  process vertices whose shortest distance from the source may not
  have been found yet. When the distance found is the shortest
  distance, parallelism is improved and the algorithm may terminate
  more quickly. However, if the distance is not the shortest distance,
  the vertex will need to be reprocessed later, resulting in more
  work.

  The type ``distance_type`` is the value type of the ``DistanceMap``
  property map. It is a nonnegative value specifying how far ahead
  Dijkstra's algorithm may process values.

  **Default:** no value (lookahead is not employed; uses `Crauser et
  al.'s algorithm`_).

Visitor Event Points
--------------------
The `Dijkstra Visitor`_ concept defines 7 event points that will be
triggered by the `sequential Dijkstra implementation`_. The distributed
Dijkstra retains these event points, but the sequence of events
triggered and the process in which each event occurs will change
depending on the distribution of the graph, lookahead, and edge
weights. 

``initialize_vertex(s, g)``
  This will be invoked by every process for each local vertex.


``discover_vertex(u, g)``
  This will be invoked each type a process discovers a new vertex
  ``u``. Due to incomplete information in distributed property maps,
  this event may be triggered many times for the same vertex ``u``.


``examine_vertex(u, g)``
  This will be invoked by the process owning the vertex ``u``. This
  event may be invoked multiple times for the same vertex when the
  graph contains negative edges or lookahead is employed. 


``examine_edge(e, g)``
  This will be invoked by the process owning the source vertex of
  ``e``. As with ``examine_vertex``, this event may be invoked
  multiple times for the same edge.


``edge_relaxed(e, g)``
  Similar to ``examine_edge``, this will be invoked by the process
  owning the source vertex and may be invoked multiple times (even
  without lookahead or negative edges).


``edge_not_relaxed(e, g)``
  Similar to ``edge_relaxed``. Some ``edge_not_relaxed`` events that
  would be triggered by sequential Dijkstra's will become
  ``edge_relaxed`` events in distributed Dijkstra's algorithm. 


``finish_vertex(e, g)``
  See documentation for ``examine_vertex``. Note that a "finished"
  vertex is not necessarily finished if lookahead is permitted or
  negative edges exist in the graph.


Crauser et al.'s algorithm
--------------------------

::

  namespace graph {
    template<typename DistributedGraph, typename DijkstraVisitor,
             typename PredecessorMap, typename DistanceMap, typename WeightMap,
             typename IndexMap, typename ColorMap, typename Compare,
             typename Combine, typename DistInf, typename DistZero>
    void
    crauser_et_al_shortest_paths
      (const DistributedGraph& g,
       typename graph_traits<DistributedGraph>::vertex_descriptor s,
       PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
       IndexMap index_map, ColorMap color_map,
       Compare compare, Combine combine, DistInf inf, DistZero zero,
       DijkstraVisitor vis);

    template<typename DistributedGraph, typename DijkstraVisitor,
             typename PredecessorMap, typename DistanceMap, typename WeightMap>
    void
    crauser_et_al_shortest_paths
      (const DistributedGraph& g,
       typename graph_traits<DistributedGraph>::vertex_descriptor s,
       PredecessorMap predecessor, DistanceMap distance, WeightMap weight);

    template<typename DistributedGraph, typename DijkstraVisitor,
             typename PredecessorMap, typename DistanceMap>
    void
    crauser_et_al_shortest_paths
      (const DistributedGraph& g,
       typename graph_traits<DistributedGraph>::vertex_descriptor s,
       PredecessorMap predecessor, DistanceMap distance);
  }

The formulation of Dijkstra's algorithm by Crauser, Mehlhorn, Meyer,
and Sanders [CMMS98a]_ improves the scalability of parallel Dijkstra's
algorithm by increasing the number of vertices that can be processed
in a given superstep. This algorithm adapts well to various graph
types, and is a simple algorithm to use, requiring no additional user
input to achieve reasonable performance. The disadvantage of this
algorithm is that the implementation is required to manage three
priority queues, which creates a large amount of work at each node.

This algorithm is used by default in distributed
``dijkstra_shortest_paths()``. 

Where Defined
~~~~~~~~~~~~~
<``boost/graph/distributed/crauser_et_al_shortest_paths.hpp``>

Complexity
~~~~~~~~~~
This algorithm performs *O(V log V)* work in *d + 1* BSP supersteps,
where *d* is at most *O(V)* but is generally much smaller. On directed
Erdos-Renyi graphs with edge weights in [0, 1), the expected number of
supersteps *d* is *O(n^(1/3))* with high probability.

Performance
~~~~~~~~~~~
The following charts illustrate the performance of the Parallel BGL implementation of Crauser et al.'s
algorithm on graphs with edge weights uniformly selected from the
range *[0, 1)*.

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=4
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=4&speedup=1

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=4
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=4&speedup=1


Eager Dijkstra's algorithm
--------------------------

::

  namespace graph {
    template<typename DistributedGraph, typename DijkstraVisitor,
             typename PredecessorMap, typename DistanceMap, typename WeightMap,
             typename IndexMap, typename ColorMap, typename Compare,
             typename Combine, typename DistInf, typename DistZero>
    void
    eager_dijkstra_shortest_paths
      (const DistributedGraph& g,
       typename graph_traits<DistributedGraph>::vertex_descriptor s,
       PredecessorMap predecessor, DistanceMap distance, 
       typename property_traits<DistanceMap>::value_type lookahead,
       WeightMap weight, IndexMap index_map, ColorMap color_map,
       Compare compare, Combine combine, DistInf inf, DistZero zero,
       DijkstraVisitor vis);

    template<typename DistributedGraph, typename DijkstraVisitor,
             typename PredecessorMap, typename DistanceMap, typename WeightMap>
    void
    eager_dijkstra_shortest_paths
      (const DistributedGraph& g,
       typename graph_traits<DistributedGraph>::vertex_descriptor s,
       PredecessorMap predecessor, DistanceMap distance, 
       typename property_traits<DistanceMap>::value_type lookahead,
       WeightMap weight);

    template<typename DistributedGraph, typename DijkstraVisitor,
             typename PredecessorMap, typename DistanceMap>
    void
    eager_dijkstra_shortest_paths
      (const DistributedGraph& g,
       typename graph_traits<DistributedGraph>::vertex_descriptor s,
       PredecessorMap predecessor, DistanceMap distance,
       typename property_traits<DistanceMap>::value_type lookahead);
  }

In each superstep, parallel Dijkstra's algorithm typically only
processes nodes whose distances equivalent to the global minimum
distance, because these distances are guaranteed to be correct. This
variation on the algorithm allows the algorithm to process all
vertices whose distances are within some constant value of the
minimum distance. The value is called the "lookahead" value and is
provided by the user as the fifth parameter to the function. Small
values of the lookahead parameter will likely result in limited
parallelization opportunities, whereas large values will expose more
parallelism but may introduce (non-infinite) looping and result in
extra work. The optimal value for the lookahead parameter depends on
the input graph; see [CMMS98b]_ and [MS98]_.

This algorithm will be used by ``dijkstra_shortest_paths()`` when it
is provided with a lookahead value.

Where Defined
~~~~~~~~~~~~~
<``boost/graph/distributed/eager_dijkstra_shortest_paths.hpp``>

Complexity
~~~~~~~~~~
This algorithm performs *O(V log V)* work in *d
+ 1* BSP supersteps, where *d* is at most *O(V)* but may be smaller
depending on the lookahead value. the algorithm may perform more work
when a large lookahead is provided, because vertices will be
reprocessed. 

Performance
~~~~~~~~~~~
The performance of the eager Dijkstra's algorithm varies greatly
depending on the lookahead value. The following charts illustrate the
performance of the Parallel BGL on graphs with edge weights uniformly
selected from the range *[0, 1)* and a constant lookahead of 0.1.

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=5
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeSparse&columns=5&speedup=1

.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=5
  :align: left
.. image:: http://www.osl.iu.edu/research/pbgl/performance/chart.php?cluster=Odin&generator=ER,SF,SW&dataset=TimeDense&columns=5&speedup=1

Delta-Stepping algorithm
--------------------------

::

  namespace boost { namespace graph { namespace distributed {

    template <typename Graph, typename PredecessorMap, 
              typename DistanceMap, typename WeightMap>
    void delta_stepping_shortest_paths
      (const Graph& g,
       typename graph_traits<Graph>::vertex_descriptor s, 
       PredecessorMap predecessor, DistanceMap distance, WeightMap weight, 
       typename property_traits<WeightMap>::value_type delta)


    template <typename Graph, typename PredecessorMap, 
              typename DistanceMap, typename WeightMap>
    void delta_stepping_shortest_paths
      (const Graph& g,
       typename graph_traits<Graph>::vertex_descriptor s, 
       PredecessorMap predecessor, DistanceMap distance, WeightMap weight)
    }

  } } } 


The delta-stepping algorithm [MS98]_ is another variant of the parallel
Dijkstra algorithm. Like the eager Dijkstra algorithm, it employs a
lookahead (``delta``) value that allows processors to process vertices
before we are guaranteed to find their minimum distances, permitting
more parallelism than a conservative strategy. Delta-stepping also
introduces a multi-level bucket data structure that provides more
relaxed ordering constraints than the priority queues employed by the
other Dijkstra variants, reducing the complexity of insertions,
relaxations, and removals from the central data structure. The
delta-stepping algorithm is the best-performing of the Dijkstra
variants.

The lookahead value ``delta`` determines how large each of the
"buckets" within the delta-stepping queue will be, where the ith
bucket contains edges within tentative distances between ``delta``*i
and ``delta``*(i+1). ``delta`` must be a positive value. When omitted,
``delta`` will be set to the maximum edge weight divided by the
maximum degree.

Where Defined
~~~~~~~~~~~~~
<``boost/graph/distributed/delta_stepping_shortest_paths.hpp``>

Example
-------
See the separate `Dijkstra example`_.


Bibliography
------------

.. [CMMS98a] Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter Sanders. A
  Parallelization of Dijkstra's Shortest Path Algorithm. In
  *Mathematical Foundations of Computer Science (MFCS)*, volume 1450 of
  Lecture Notes in Computer Science, pages 722--731, 1998. Springer.

.. [CMMS98b] Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer, and Peter
  Sanders. Parallelizing Dijkstra's shortest path algorithm. Technical
  report, MPI-Informatik, 1998. 

.. [MS98] Ulrich Meyer and Peter Sanders. Delta-stepping: A parallel
  shortest path algorithm. In *6th ESA*, LNCS. Springer, 1998.

-----------------------------------------------------------------------------

Copyright (C) 2004, 2005, 2006, 2007, 2008 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _sequential Dijkstra implementation: http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
.. _distributed breadth-first search: breadth_first_search.html
.. _Distributed Graph: DistributedGraph.html
.. _Distributed Property Map: distributed_property_map.html
.. _Dijkstra Visitor: http://www.boost.org/libs/graph/doc/DijkstraVisitor.html
.. _Dijkstra example: dijkstra_example.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc DistributedS (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/distributedS.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

======================================
``distributedS`` Distribution Selector
======================================

The Boost Graph Library's class template adjacency_list_ supports
several selectors that indicate what data structure should be used for
the storage of edges or vertices. The selector ``vecS``, for instance,
indicates storage in a ``std::vector`` whereas ``listS`` indicates
storage in a ``std::list``. The Parallel BGL's `distributed
adjacency list`_ supports an additional selector, ``distributedS``,
that indicates that the storage should be distributed across multiple
processes. This selector can transform a sequential adjacency list
into a distributed adjacency list.

::

  template<typename ProcessGroup, typename LocalSelector = vecS>
  struct distributedS;


Template parameters
~~~~~~~~~~~~~~~~~~~

**ProcessGroup**:
  The type of the process group over which the property map is
  distributed and also the medium for communication. This type must
  model the `Process Group`_ concept, but certain data structures may
  place additional requirements on this parameter.

**LocalSelector**:
  A selector type (e.g., ``vecS``) that indicates how vertices or
  edges should be stored in each process. 

-----------------------------------------------------------------------------

Copyright (C) 2005 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine


.. _adjacency_list: http://www.boost.org/libs/graph/doc/adjacency_list.html
.. _Distributed adjacency list: distributed_adjacency_list.html
.. _Process group: process_group.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Distributed Adjacency List (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/distributed_adjacency_list.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

=================================
|Logo| Distributed Adjacency List
=================================

.. contents::

Introduction
------------

The distributed adjacency list implements a graph data structure using
an adjacency list representation. Its interface and behavior are
roughly equivalent to the Boost Graph Library's adjacency_list_
class template. However, the distributed adjacency list partitions the
vertices of the graph across several processes (which need not share
an address space). Edges outgoing from any vertex stored by a process
are also stored on that process, except in the case of undirected
graphs, where either the source or the target may store the edge.

::

  template<typename OutEdgeListS, typename ProcessGroup, typename VertexListS,
           typename DirectedS, typename VertexProperty, typename EdgeProperty, 
           typename GraphProperty, typename EdgeListS>
  class adjacency_list<OutEdgeListS, 
                       distributedS,
                       DirectedS, VertexProperty,
                       EdgeProperty, GraphProperty, EdgeListS>;

Defining a Distributed Adjacency List

Vertex and edge properties for distributed graphs mirror their
counterparts for non-distributed graphs. With a distributed graph,
however, vertex and edge properties are stored only in the process
that owns the vertex or edge. 

The most direct way to attach properties to a distributed graph is to
create a structure that will be attached to each of the vertices and
edges of the graph. For example, if we wish to model a simplistic map
of the United States interstate highway system, we might state that
the vertices of the graph are cities and the edges are highways, then
define the information that we maintain for each city and highway:

::

  struct City {
    City() { }
    City(const std::string& name, const std::string& mayor = "Unknown", int population = 0)
      : name(name), mayor(mayor), population(population) { }

    std::string name;
    std::string mayor;
    int population;

    // Serialization support is required!
    template<typename Archiver>
    void serialize(Archiver& ar, const unsigned int /*version*/) {
      ar & name & mayor & population;
    }
  };

  struct Highway {
    Highway() { }
    Highway(const std::string& name, int lanes, int miles_per_hour, int length) 
      : name(name), lanes(lanes), miles_per_hour(miles_per_hour), length(length) { }

    std::string name;
    int lanes;
    int miles_per_hour;
    int length;

    // Serialization support is required!
    template<typename Archiver>
    void serialize(Archiver& ar, const unsigned int /*version*/) {
      ar & name & lanes & miles_per_hour & length;
    }
  };


To create a distributed graph for a road map, we supply ``City`` and
``Highway`` as the fourth and fifth parameters to ``adjacency_list``,
respectively:

::

  typedef adjacency_list<vecS, 
                         distributedS,
                         directedS,
                         City, Highway> 
    RoadMap;


Property maps for internal properties retain their behavior with
distributed graphs via `distributed property maps`_, which automate
communication among processes so that ``put`` and ``get`` operations
may be applied to non-local vertices and edges. However, for
distributed adjacency lists that store vertices in a vector
(``VertexListS`` is ``vecS``), the automatic ``vertex_index``
property map restricts the domain of ``put`` and ``get`` operations
to vertices local to the process executing the operation. For example,
we can create a property map that accesses the length of each highway
as follows:

::

  RoadMap map; // distributed graph instance

  typedef property_map<RoadMap, int Highway::*>::type 
    road_length = get(&Highway::length, map);


Now, one can access the length of any given road based on its edge
descriptor ``e`` with the expression ``get(road_length, e)``,
regardless of which process stores the edge ``e``. 

Named Vertices
~~~~~~~~~~~~~~

The vertices of a graph typically correspond to named entities within
the application domain. In the road map example from the previous
section, the vertices in the graph represent cities. The distributed
adjacency list supports named vertices, which provides an implicit
mapping from the names of the vertices in the application domain
(e.g., the name of a city, such as "Bloomington") to the actual vertex
descriptor stored within the distributed graph (e.g., the third vertex
on processor 1). By enabling support for named vertices, one can refer
to vertices by name when manipulating the graph. For example, one can
add a highway from Indianapolis to Chicago:

::
  
  add_edge("Indianapolis", "Chicago", Highway("I-65", 4, 65, 151), map);

The distributed adjacency list will find vertices associated with the
names "Indianapolis" and "Chicago", then add an edge between these
vertices that represents I-65. The vertices may be stored on any
processor, local or remote. 

To enable named vertices, specialize the ``internal_vertex_name``
property for the structure attached to the vertices in your
graph. ``internal_vertex_name`` contains a single member, ``type``,
which is the type of a function object that accepts a vertex property
and returns the name stored within that vertex property. In the case
of our road map, the ``name`` field contains the name of each city, so
we use the ``member`` function object from the `Boost.MultiIndex`_
library to extract the name, e.g.,

::

  namespace boost { namespace graph { 

  template<>
  struct internal_vertex_name<City>
  {
    typedef multi_index::member<City, std::string, &City::name> type;
  };
  
  } }


That's it! One can now refer to vertices by name when interacting with
the distributed adjacency list.

What happens when one uses the name of a vertex that does not exist?
For example, in our ``add_edge`` call above, what happens if the
vertex named "Indianapolis" has not yet been added to the graph? By
default, the distributed adjacency list will throw an exception if a
named vertex does not yet exist. However, one can customize this
behavior by specifying a function object that constructs an instance
of the vertex property (e.g., ``City``) from just the name of the
vertex. This customization occurs via the
``internal_vertex_constructor`` trait. For example, using the
``vertex_from_name`` template (provided with the Parallel BGL), we can
state that a ``City`` can be constructed directly from the name of the
city using its second constructor:

::

  namespace boost { namespace graph {

  template<>
  struct internal_vertex_constructor<City>
  {
    typedef vertex_from_name<City> type;
  };

  } }

Now, one can add edges by vertex name freely, without worrying about
the explicit addition of vertices. The ``mayor`` and ``population``
fields will have default values, but the graph structure will be
correct. 

Building a Distributed Graph
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Once you have determined the layout of your graph type, including the
specific data structures and properties, it is time to construct an
instance of the graph by adding the appropriate vertices and
edges. Construction of distributed graphs can be slightly more
complicated than construction of normal, non-distributed graph data
structures, because one must account for both the distribution of the
vertices and edges and the multiple processes executing
concurrently. There are three main ways to construct distributed
graphs:

1. *Sequence constructors*: if your data can easily be generated by a
pair of iterators that produce (source, target) pairs, you can use the
sequence constructors to build the distributed graph in parallel. This
method is often preferred when creating benchmarks, because random
graph generators like the sorted_erdos_renyi_iterator_ create the
appropriate input sequence. Note that one must provide the same input
iterator sequence on all processes. This method has the advantage that
the sequential graph-building code is identical to the parallel
graph-building code. An example constructing a random graph this way:

  ::

    typedef boost::sorted_erdos_renyi_iterator<boost::minstd_rand, Graph> ERIter;
    boost::minstd_rand gen;
    unsigned long n = 1000000; // 1M vertices
    Graph g(ERIter(gen, n, 0.00005), ERIter(), n);

2. *Adding edges by vertex number*: if you are able to map your
vertices into values in the random [0, *n*), where *n* is the number
of vertices in the distributed graph. Use this method rather than the
sequence constructors when your algorithm cannot easily be moved into
input iterators, or if you can't replicate the input sequence. For
example, you might be reading the graph from an input file:

  ::

    Graph g(n); // initialize with the total number of vertices, n
    if (process_id(g.process_group()) == 0) {
      // Only process 0 loads the graph, which is distributed automatically
      int source, target;
      for (std::cin >> source >> target)
        add_edge(vertex(source, g), vertex(target, g), g);
    }

    // All processes synchronize at this point, then the graph is complete
    synchronize(g.process_group());

3. *Adding edges by name*: if you are using named vertices, you can
construct your graph just by calling ``add_edge`` with the names of
the source and target vertices. Be careful to make sure that each edge
is added by only one process (it doesn't matter which process it is),
otherwise you will end up with multiple edges. For example, in the
following program we read edges from the standard input of process 0,
adding those edges by name. Vertices and edges will be created and
distributed automatically.

  ::

    Graph g;
    if (process_id(g.process_group()) == 0) {
      // Only process 0 loads the graph, which is distributed automatically
      std:string source, target;
      for(std::cin >> source >> target)
        add_edge(source, target, g);
    }

    // All processes synchronize at this point, then the graph is complete
    synchronize(g.process_group());


Graph Concepts
~~~~~~~~~~~~~~

The distributed adjacency list models the Graph_ concept, and in
particular the `Distributed Graph`_ concept. It also models the
`Incidence Graph`_ and `Adjacency Graph`_ concept, but restricts the
input domain of the operations to correspond to local vertices
only. For instance, a process may only access the outgoing edges of a
vertex if that vertex is stored in that process. Undirected and
bidirectional distributed adjacency lists model the `Bidirectional
Graph`_ concept, with the same domain restrictions. Distributed
adjacency lists also model the `Mutable Graph`_ concept (with domain
restrictions; see the Reference_ section), `Property Graph`_ concept,
and `Mutable Property Graph`_ concept.

Unlike its non-distributed counterpart, the distributed adjacency
list does **not** model the `Vertex List Graph`_ or `Edge List
Graph`_ concepts, because one cannot enumerate all vertices or edges
within a distributed graph. Instead, it models the weaker
`Distributed Vertex List Graph`_ and `Distributed Edge List Graph`_
concepts, which permit access to the local edges and vertices on each
processor. Note that if all processes within the process group over
which the graph is distributed iterator over their respective vertex
or edge lists, all vertices and edges will be covered once. 

Reference
---------
Since the distributed adjacency list closely follows the
non-distributed adjacency_list_, this reference documentation
only describes where the two implementations differ.

Where Defined
~~~~~~~~~~~~~

<boost/graph/distributed/adjacency_list.hpp>

Associated Types
~~~~~~~~~~~~~~~~

::

  adjacency_list::process_group_type

The type of the process group over which the graph will be
distributed.

-----------------------------------------------------------------------------

  adjacency_list::distribution_type

The type of distribution used to partition vertices in the graph.

-----------------------------------------------------------------------------

  adjacency_list::vertex_name_type

If the graph supports named vertices, this is the type used to name
vertices. Otherwise, this type is not present within the distributed
adjacency list. 


Member Functions
~~~~~~~~~~~~~~~~

::

    adjacency_list(const ProcessGroup& pg = ProcessGroup());

    adjacency_list(const GraphProperty& g, 
                   const ProcessGroup& pg = ProcessGroup());

Construct an empty distributed adjacency list with the given process
group (or default) and graph property (or default).

-----------------------------------------------------------------------------

::

    adjacency_list(vertices_size_type n, const GraphProperty& p,
                   const ProcessGroup& pg, const Distribution& distribution);

    adjacency_list(vertices_size_type n, const ProcessGroup& pg,
                   const Distribution& distribution);

    adjacency_list(vertices_size_type n, const GraphProperty& p,
                   const ProcessGroup& pg = ProcessGroup());
      
    adjacency_list(vertices_size_type n, 
                   const ProcessGroup& pg = ProcessGroup());

Construct a distributed adjacency list with ``n`` vertices,
optionally providing the graph property, process group, or
distribution. The ``n`` vertices will be distributed via the given
(or default-constructed) distribution. This operation is collective,
requiring all processes with the process group to execute it
concurrently.

-----------------------------------------------------------------------------

::

    template <class EdgeIterator>
    adjacency_list(EdgeIterator first, EdgeIterator last,
                   vertices_size_type n, 
                   const ProcessGroup& pg = ProcessGroup(),
                   const GraphProperty& p = GraphProperty());

    template <class EdgeIterator, class EdgePropertyIterator>
    adjacency_list(EdgeIterator first, EdgeIterator last,
                   EdgePropertyIterator ep_iter,
                   vertices_size_type n,
                   const ProcessGroup& pg = ProcessGroup(),
                   const GraphProperty& p = GraphProperty());

    template <class EdgeIterator>
    adjacency_list(EdgeIterator first, EdgeIterator last,
                   vertices_size_type n, 
                   const ProcessGroup& process_group,
                   const Distribution& distribution,
                   const GraphProperty& p = GraphProperty());

    template <class EdgeIterator, class EdgePropertyIterator>
    adjacency_list(EdgeIterator first, EdgeIterator last,
                   EdgePropertyIterator ep_iter,
                   vertices_size_type n,
                   const ProcessGroup& process_group,
                   const Distribution& distribution,
                   const GraphProperty& p = GraphProperty());

Construct a distributed adjacency list with ``n`` vertices and with
edges specified in the edge list given by the range ``[first, last)``. The
``EdgeIterator`` must be a model of InputIterator_. The value type of the
``EdgeIterator`` must be a ``std::pair``, where the type in the pair is an
integer type. The integers will correspond to vertices, and they must
all fall in the range of ``[0, n)``. When provided, ``ep_iter``
refers to an edge property list ``[ep_iter, ep_iter + m)`` contains
properties for each of the edges.

This constructor is a collective operation and must be executed
concurrently by each process with the same argument list. Most
importantly, the edge lists provided to the constructor in each process
should be equivalent. The vertices will be partitioned among the
processes according to the ``distribution``, with edges placed on the
process owning the source of the edge. Note that this behavior
permits sequential graph construction code to be parallelized
automatically, regardless of the underlying distribution. 

-----------------------------------------------------------------------------

::

  void clear()

Removes all of the edges and vertices from the local graph. To
eliminate all vertices and edges from the graph, this routine must be
executed in all processes.

-----------------------------------------------------------------------------

::

  process_group_type& process_group();
  const process_group_type& process_group() const;

Returns the process group over which this graph is distributed.

-----------------------------------------------------------------------------

::

  distribution_type&       distribution();
  const distribution_type& distribution() const;

Returns the distribution used for initial placement of vertices.

-----------------------------------------------------------------------------

::

  template<typename VertexProcessorMap>
    void redistribute(VertexProcessorMap vertex_to_processor);

Redistributes the vertices (and, therefore, the edges) of the
graph. The property map ``vertex_to_processor`` provides, for each
vertex, the process identifier indicating where the vertex should be
moved. Once this collective routine has completed, the distributed
graph will reflect the new distribution. All vertex and edge
descsriptors and internal and external property maps are invalidated
by this operation.

-----------------------------------------------------------------------------

::

  template<typename OStreamConstructibleArchive>
    void save(std::string const& filename) const;

  template<typename IStreamConstructibleArchive>
    void load(std::string const& filename);

Serializes the graph to a Boost.Serialization archive. 
``OStreamConstructibleArchive`` and ``IStreamConstructibleArchive``
are models of Boost.Serialization *Archive* with the extra
requirement that they can be constructed from a ``std::ostream`` 
and ``std::istream``.
``filename`` names a directory that will hold files for
the different processes.


Non-Member Functions
~~~~~~~~~~~~~~~~~~~~

::

  std::pair<vertex_iterator, vertex_iterator>
  vertices(const adjacency_list& g);

Returns an iterator-range providing access to the vertex set of graph
``g`` stored in this process. Each of the processes that contain ``g``
will get disjoint sets of vertices.

-----------------------------------------------------------------------------

::

  std::pair<edge_iterator, edge_iterator>
  edges(const adjacency_list& g);

Returns an iterator-range providing access to the edge set of graph
``g`` stored in this process.

-----------------------------------------------------------------------------

::

  std::pair<adjacency_iterator, adjacency_iterator>
  adjacent_vertices(vertex_descriptor u, const adjacency_list& g);

Returns an iterator-range providing access to the vertices adjacent to
vertex ``u`` in graph ``g``. The vertex ``u`` must be local to this process.

-----------------------------------------------------------------------------

::

  std::pair<out_edge_iterator, out_edge_iterator>
  out_edges(vertex_descriptor u, const adjacency_list& g);

Returns an iterator-range providing access to the out-edges of vertex
``u`` in graph ``g``. If the graph is undirected, this iterator-range
provides access to all edges incident on vertex ``u``. For both
directed and undirected graphs, for an out-edge ``e``, ``source(e, g)
== u`` and ``target(e, g) == v`` where ``v`` is a vertex adjacent to
``u``. The vertex ``u`` must be local to this process.

-----------------------------------------------------------------------------

::

  std::pair<in_edge_iterator, in_edge_iterator>
  in_edges(vertex_descriptor v, const adjacency_list& g);

Returns an iterator-range providing access to the in-edges of vertex
``v`` in graph ``g``. This operation is only available if
``bidirectionalS`` was specified for the ``Directed`` template
parameter. For an in-edge ``e``, ``target(e, g) == v`` and ``source(e,
g) == u`` for some vertex ``u`` that is adjacent to ``v``, whether the
graph is directed or undirected. The vertex ``v`` must be local to
this process.

-----------------------------------------------------------------------------

::

  degree_size_type
  out_degree(vertex_descriptor u, const adjacency_list& g);

Returns the number of edges leaving vertex ``u``. Vertex ``u`` must
be local to the executing process.

-----------------------------------------------------------------------------

::

  degree_size_type
  in_degree(vertex_descriptor u, const adjacency_list& g);

Returns the number of edges entering vertex ``u``. This operation is
only available if ``bidirectionalS`` was specified for the
``Directed`` template parameter. Vertex ``u`` must be local to the
executing process.

-----------------------------------------------------------------------------

::

  vertices_size_type
  num_vertices(const adjacency_list& g);

Returns the number of vertices in the graph ``g`` that are stored in
the executing process.

-----------------------------------------------------------------------------

::

  edges_size_type
  num_edges(const adjacency_list& g);

Returns the number of edges in the graph ``g`` that are stored in the
executing process.

-----------------------------------------------------------------------------

::

  vertex_descriptor
  vertex(vertices_size_type n, const adjacency_list& g);

Returns the ``n``th vertex in the graph's vertex list, according to the
distribution used to partition the graph. ``n`` must be a value
between zero and the sum of ``num_vertices(g)`` in each process (minus
one). Note that it is not necessarily the case that ``vertex(0, g) ==
*num_vertices(g).first``. This function is only guaranteed to be
accurate when no vertices have been added to or removed from the
graph after its initial construction.

-----------------------------------------------------------------------------

::

  std::pair<edge_descriptor, bool>
  edge(vertex_descriptor u, vertex_descriptor v,
       const adjacency_list& g);

Returns an edge connecting vertex ``u`` to vertex ``v`` in graph
``g``. For bidirectional and undirected graphs, either vertex ``u`` or
vertex ``v`` must be local; for directed graphs, vertex ``u`` must be
local.

-----------------------------------------------------------------------------

::

  std::pair<out_edge_iterator, out_edge_iterator>
  edge_range(vertex_descriptor u, vertex_descriptor v,
             const adjacency_list& g);

TODO: Not implemented.  Returns a pair of out-edge iterators that give
the range for all the parallel edges from ``u`` to ``v``. This function only
works when the ``OutEdgeList`` for the ``adjacency_list`` is a container that
sorts the out edges according to target vertex, and allows for
parallel edges. The ``multisetS`` selector chooses such a
container. Vertex ``u`` must be stored in the executing process.

Structure Modification
~~~~~~~~~~~~~~~~~~~~~~

::

  unspecified add_edge(vertex_descriptor u, vertex_descriptor v, adjacency_list& g);
  unspecified add_edge(vertex_name_type u, vertex_descriptor v, adjacency_list& g);
  unspecified add_edge(vertex_descriptor u, vertex_name_type v, adjacency_list& g);
  unspecified add_edge(vertex_name_type u, vertex_name_type v, adjacency_list& g);

Adds edge ``(u,v)`` to the graph. The return type itself is
unspecified, but the type can be copy-constructed and implicitly
converted into a ``std::pair<edge_descriptor,bool>``. The edge
descriptor describes the added (or found) edge. For graphs that do not
allow parallel edges, if the edge 
is already in the graph then a duplicate will not be added and the
``bool`` flag will be ``false``. Also, if u and v are descriptors for
the same vertex (creating a self loop) and the graph is undirected,
then the edge will not be added and the flag will be ``false``. When
the flag is ``false``, the returned edge descriptor points to the
already existing edge. 

The parameters ``u`` and ``v`` can be either vertex descriptors or, if
the graph uses named vertices, the names of vertices. If no vertex
with the given name exists, the internal vertex constructor will be
invoked to create a new vertex property and a vertex with that
property will be added to the graph implicitly. The default internal
vertex constructor throws an exception.

-----------------------------------------------------------------------------

::

  unspecified add_edge(vertex_descriptor u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g);
  unspecified add_edge(vertex_name_type u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g);
  unspecified add_edge(vertex_descriptor u, vertex_name_type v, const EdgeProperties& p, adjacency_list& g);
  unspecified add_edge(vertex_name_type u, vertex_name_type v, const EdgeProperties& p, adjacency_list& g);


Adds edge ``(u,v)`` to the graph and attaches ``p`` as the value of the edge's
internal property storage. See the previous ``add_edge()`` member
function for more details.  

-----------------------------------------------------------------------------

::

  void 
  remove_edge(vertex_descriptor u, vertex_descriptor v, 
              adjacency_list& g);

Removes the edge ``(u,v)`` from the graph. If the directed selector is
``bidirectionalS`` or ``undirectedS``, either the source or target
vertex of the graph must be local. If the directed selector is
``directedS``, then the source vertex must be local.

-----------------------------------------------------------------------------

::

  void 
  remove_edge(edge_descriptor e, adjacency_list& g);

Removes the edge ``e`` from the graph. If the directed selector is
``bidirectionalS`` or ``undirectedS``, either the source or target
vertex of the graph must be local. If the directed selector is
``directedS``, then the source vertex must be local.

-----------------------------------------------------------------------------

::

  void remove_edge(out_edge_iterator iter, adjacency_list& g);

This has the same effect as ``remove_edge(*iter, g)``. For directed
(but not bidirectional) graphs, this will be more efficient than
``remove_edge(*iter, g)``.

-----------------------------------------------------------------------------

::

  template <class Predicate >
  void remove_out_edge_if(vertex_descriptor u, Predicate predicate,
                          adjacency_list& g);

Removes all out-edges of vertex ``u`` from the graph that satisfy the
predicate. That is, if the predicate returns ``true`` when applied to an
edge descriptor, then the edge is removed. The vertex ``u`` must be local.

The affect on descriptor and iterator stability is the same as that of
invoking remove_edge() on each of the removed edges.

-----------------------------------------------------------------------------

::

  template <class Predicate >
  void remove_in_edge_if(vertex_descriptor v, Predicate predicate,
                         adjacency_list& g);

Removes all in-edges of vertex ``v`` from the graph that satisfy the
predicate. That is, if the predicate returns true when applied to an
edge descriptor, then the edge is removed. The vertex ``v`` must be local.

The affect on descriptor and iterator stability is the same as that of
invoking ``remove_edge()`` on each of the removed edges.

This operation is available for undirected and bidirectional
adjacency_list graphs, but not for directed.  

-----------------------------------------------------------------------------

::

  template <class Predicate> 
  void remove_edge_if(Predicate predicate, adjacency_list& g);

Removes all edges from the graph that satisfy the predicate. That is,
if the predicate returns true when applied to an edge descriptor, then
the edge is removed. 

The affect on descriptor and iterator stability is the same as that
of invoking ``remove_edge()`` on each of the removed edges.

-----------------------------------------------------------------------------

::

  vertex_descriptor add_vertex(adjacency_list& g);

Adds a vertex to the graph and returns the vertex descriptor for the
new vertex. The vertex will be stored in the local process. This
function is not available when using named vertices.

-----------------------------------------------------------------------------

::

  unspecified add_vertex(const VertexProperties& p, adjacency_list& g);
  unspecified add_vertex(const vertex_name_type& p, adjacency_list& g);

Adds a vertex to the graph with the specified properties. If the graph
is using vertex names, the vertex will be added on whichever process
"owns" that name. Otherwise, the vertex will be stored in the local
process. Note that the second constructor will invoke the
user-customizable internal vertex constructor, which (by default)
throws an exception when it sees an unknown vertex. 

The return type is of unspecified type, but can be copy-constructed
and can be implicitly converted into a vertex descriptor.

-----------------------------------------------------------------------------

::

  void clear_vertex(vertex_descriptor u, adjacency_list& g);

Removes all edges to and from vertex ``u``. The vertex still appears
in the vertex set of the graph.

The affect on descriptor and iterator stability is the same as that of
invoking ``remove_edge()`` for all of the edges that have ``u`` as the source
or target.

This operation is not applicable to directed graphs, because the
incoming edges to vertex ``u`` are not known.

-----------------------------------------------------------------------------

::

  void clear_out_edges(vertex_descriptor u, adjacency_list& g);

Removes all out-edges from vertex ``u``. The vertex still appears in
the vertex set of the graph. 

The affect on descriptor and iterator stability is the same as that of
invoking ``remove_edge()`` for all of the edges that have ``u`` as the
source. 

This operation is not applicable to undirected graphs (use
``clear_vertex()`` instead).

-----------------------------------------------------------------------------

::

  void clear_in_edges(vertex_descriptor u, adjacency_list& g);

Removes all in-edges from vertex ``u``. The vertex still appears in
the vertex set of the graph.

The affect on descriptor and iterator stability is the same as that of
invoking ``remove_edge()`` for all of the edges that have ``u`` as the
target. 

This operation is only applicable to bidirectional graphs.

-----------------------------------------------------------------------------

::

  void remove_vertex(vertex_descriptor u, adjacency_list& g);

Remove vertex ``u`` from the vertex set of the graph. It is assumed
that there are no edges to or from vertex ``u`` when it is
removed. One way to make sure of this is to invoke ``clear_vertex()``
beforehand. The vertex ``u`` must be stored locally.

Property Map Accessors
~~~~~~~~~~~~~~~~~~~~~~

::

  template <class PropertyTag>
  property_map<adjacency_list, PropertyTag>::type
  get(PropertyTag, adjacency_list& g);

  template <class PropertyTag>
  property_map<adjacency_list, Tag>::const_type
  get(PropertyTag, const adjacency_list& g);

Returns the property map object for the vertex property specified by
``PropertyTag``. The ``PropertyTag`` must match one of the properties
specified in the graph's ``VertexProperty`` template argument. The
returned property map will be a `distributed property map`_.

-----------------------------------------------------------------------------

::

  template <class PropertyTag , class X>
  typename property_traits<property_map<adjacency_list, PropertyTag>::const_type>::value_type
  get(PropertyTag, const adjacency_list& g, X x);

This returns the property value for ``x``, where ``x`` is either a vertex or
edge descriptor.  The entity referred to by descriptor ``x`` must be
stored in the local process.

-----------------------------------------------------------------------------

::

  template <class PropertyTag , class X, class Value>
  void put(PropertyTag, const adjacency_list& g, X x, const Value& value);

This sets the property value for ``x`` to value. ``x`` is either a
vertex or edge descriptor. ``Value`` must be convertible to ``typename
property_traits<property_map<adjacency_list,
PropertyTag>::type>::value_type``. 

-----------------------------------------------------------------------------

::

  template <class GraphProperties, class GraphPropertyTag>
  typename graph_property<adjacency_list, GraphPropertyTag>::type&
  get_property(adjacency_list& g, GraphPropertyTag);

  template <class GraphProperties, class GraphPropertyTag >
  const typename graph_property<adjacency_list, GraphPropertyTag>::type&
  get_property(const adjacency_list& g, GraphPropertyTag);

TODO: not implemented.

Return the property specified by ``GraphPropertyTag`` that is attached
to the graph object ``g``. The ``graph_property`` traits class is
defined in ``boost/graph/adjacency_list.hpp``.

-----------------------------------------------------------------------------

Copyright (C) 2004 The Trustees of Indiana University.

Copyright (C) 2007 Douglas Gregor

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _adjacency_list: http://www.boost.org/libs/graph/doc/adjacency_list.html
.. _guidelines: http://www.boost.org/libs/graph/doc/using_adjacency_list.html
.. _process group: process_group.html
.. _mpi process group: process_group.html
.. _distributedS: distributedS.html
.. _Graph: http://www.boost.org/libs/graph/doc/Graph.html
.. _Distributed graph: DistributedGraph.html
.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html
.. _Adjacency Graph: http://www.boost.org/libs/graph/doc/AdjacencyGraph.html
.. _Bidirectional Graph: http://www.boost.org/libs/graph/doc/BidirectionalGraph.html
.. _Mutable Graph: http://www.boost.org/libs/graph/doc/MutableGraph.html
.. _Property Graph: http://www.boost.org/libs/graph/doc/PropertyGraph.html
.. _Mutable Property Graph: http://www.boost.org/libs/graph/doc/MutablePropertyGraph.html
.. _Vertex List Graph: http://www.boost.org/libs/graph/doc/VertexListGraph.html
.. _Edge List Graph: http://www.boost.org/libs/graph/doc/EdgeListGraph.html
.. _Distribution: concepts/Distribution.html
.. _distributed property map: distributed_property_map.html
.. _distributed property maps: distributed_property_map.html
.. _Distributed Vertex List Graph: DistributedVertexListGraph.html
.. _Distributed Edge List Graph: DistributedEdgeListGraph.html
.. _InputIterator: http://www.boost.org/doc/html/InputIterator.html
.. _member: http://www.boost.org/libs/multi_index/doc/reference/key_extraction.html#member_synopsis
.. _Boost.MultiIndex: http://www.boost.org/libs/multi_index/doc/index.html
.. _sorted_erdos_renyi_iterator: http://www.boost.org/libs/graph/doc/sorted_erdos_renyi_gen.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Distributed Property Map (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/distributed_property_map.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===============================
|Logo| Distributed Property Map
===============================

A distributed property map adaptor is a property map whose stored
values are distributed across multiple non-overlapping memory spaces
on different processes. Values local to the current process are stored
within a local property map and may be immediately accessed via
``get`` and ``put``. Values stored on remote processes may also be
accessed via ``get`` and ``put``, but the behavior differs slightly:

 - ``put`` operations update a local ghost cell and send a "put"
   message to the process that owns the value. The owner is free to
   update its own "official" value or may ignore the put request.

 - ``get`` operations returns the contents of the local ghost
   cell. If no ghost cell is available, one is created using a
   (customizable) default value. 

Using distributed property maps requires a bit more care than using
local, sequential property maps. While the syntax and semantics are
similar, distributed property maps may contain out-of-date
information that can only be guaranteed to be synchronized by
calling the ``synchronize`` function in all processes.

To address the issue of out-of-date values, distributed property
maps support multiple `consistency models`_ and may be supplied with a
`reduction operation`_.

Distributed property maps meet the requirements of the `Readable
Property Map`_ and, potentially, the `Writable Property Map`_ and
`Read/Write Property Map`_ concepts. Distributed property maps do
*not*, however, meet the requirements of the `Lvalue Property Map`_
concept, because elements residing in another process are not
directly addressible. There are several forms of distributed property
maps:

  - `Distributed property map adaptor`_
  - `Distributed iterator property map`_
  - `Distributed safe iterator property map`_
  - `Local property map`_

------------------
Consistency models
------------------

Distributed property maps offer many consistency models, which affect
how the values read from and written to remote keys relate to the
"official" value for that key stored in the owning process. The
consistency model of a distributed property map can be set with the
member function ``set_consistency_model`` to a bitwise-OR of the
flags in the ``boost::parallel::consistency_model`` enumeration. The
individual flags are:

  - ``cm_forward``: The default consistency model, which propagates
    values forward from ``put`` operations on remote processors to
    the owner of the value being changed. 
  
  - ``cm_backward``: After all values have been forwarded or flushed
    to the owning processes, each process receives updates values for
    each of its ghost cells. After synchronization, the values in
    ghost cells are guaranteed to match the values stored on the
    owning processor.

  - ``cm_bidirectional``: A combination of both ``cm_forward`` and
    ``cm_backward``. 

  - ``cm_flush``: At the beginning of synchronization, all of the
    values stored locally in ghost cells are sent to their owning
    processors. 

  - ``cm_reset``: Executes a ``reset()`` operation after
    synchronization, setting the values in each ghost cell to their
    default value.

  - ``cm_clear``: Executes a ``clear()`` operation after
    synchronizing, eliminating all ghost cells.


There are several common combinations of flags that result in
interesting consistency models. Some of these combinations are:

  - ``cm_forward``: By itself, the forward consistency model enables
    algorithms such as `Dijkstra's shortest paths`_ and
    `Breadth-First Search`_ to operate correctly.

  - ``cm_flush & cm_reset``: All updates values are queued locally,
    then flushed during the synchronization step. Once the flush has
    occurred, the ghost cells are restored to their default
    values. This consistency model is used by the PageRank_
    implementation to locally accumulate rank for each node.


-------------------
Reduction operation
-------------------

The reduction operation maintains consistency by determining how
multiple writes to a property map are resolved and what the property
map should do if unknown values are requested. More specifically, a
reduction operation is used in two cases:

  1. When a value is needed for a remote key but no value is
     immediately available, the reduction operation provides a
     suitable default. For instance, a distributed property map
     storing distances may have a reduction operation that returns
     an infinite value as the default, whereas a distributed
     property map for vertex colors may return white as the
     default.

  2. When a value is received from a remote process, the process
     owning the key associated with that value must determine which
     value---the locally stored value, the value received from a
     remote process, or some combination of the two---will be
     stored as the "official" value in the property map. The
     reduction operation transforms the local and remote values
     into the "official" value to be stored.

The reduction operation of a distributed property map can be set with
the ``set_reduce`` method of ``distributed_property_map``. The reduce
operation is a function object with two signatures. The first
signature takes a (remote) key and returns a default value for it,
whereas the second signatures takes a key and two values (local first,
then remote) and will return the combined value that will be stored in
the local property map.  Reduction operations must also contain a
static constant ``non_default_resolver", which states whether the
reduction operation's default value actually acts like a default
value. It should be ``true`` when the default is meaningful (e.g.,
infinity for a distance) and ``false`` when the default should not be
used. 

The following reduction operation is used by the distributed PageRank
algorithm. The default rank for a remote node is 0. Rank is
accumulated locally, and then the reduction operation combines local
and remote values by adding them. Combined with a consistency model
that flushes all values to the owner and then resets the values
locally in each step, the resulting property map will compute partial 
sums on each processor and then accumulate the results on the owning
processor. The PageRank reduction operation is defined as follows.
 
::

  template<typename T>
  struct rank_accumulate_reducer {
    static const bool non_default_resolver = true;

    // The default rank of an unknown node 
    template<typename K>
    T operator()(const K&) const { return T(0); }

    template<typename K>
    T operator()(const K&, const T& x, const T& y) const { return x + y; }
  };


--------------------------------
Distributed property map adaptor
--------------------------------

The distributed property map adaptor creates a distributed property
map from a local property map, a `process group`_ over which
distribution should occur, and a `global descriptor`_ type that
indexes the distributed property map. 
  

Synopsis
~~~~~~~~

::

  template<typename ProcessGroup, typename LocalPropertyMap, typename Key,
           typename GhostCellS = gc_mapS>
  class distributed_property_map
  {
  public:
    typedef ... ghost_regions_type;
 
    distributed_property_map();

    distributed_property_map(const ProcessGroup& pg, 
                             const LocalPropertyMap& pm);

    template<typename Reduce>
    distributed_property_map(const ProcessGroup& pg, 
                             const LocalPropertyMap& pm,
                             const Reduce& reduce);

    template<typename Reduce> void set_reduce(const Reduce& reduce);
    void set_consistency_model(int model);

    void flush();
    void reset();
    void clear();
  };

  reference get(distributed_property_map pm, const key_type& key);

  void
  put(distributed_property_map pm, const key_type& key, const value_type& value);
  local_put(distributed_property_map pm, const key_type& key, const value_type& value);

  void request(distributed_property_map pm, const key_type& key);

  void synchronize(distributed_property_map& pm);

  template<typename Key, typename ProcessGroup, typename LocalPropertyMap>
  distributed_property_map<ProcessGroup, LocalPropertyMap, Key>
  make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap);

  template<typename Key, typename ProcessGroup, typename LocalPropertyMap,
           typename Reduce>
  distributed_property_map<ProcessGroup, LocalPropertyMap, Key>
  make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap,
                                Reduce reduce);

Template parameters
~~~~~~~~~~~~~~~~~~~

**ProcessGroup**:
  The type of the process group over which the
  property map is distributed and is also the medium for
  communication.


**LocalPropertyMap**:
  The type of the property map that will store values
  for keys local to this processor. The ``value_type`` of this
  property map will become the ``value_type`` of the distributed
  property map. The distributed property map models the same property
  map concepts as the ``LocalPropertyMap``, with one exception: a
  distributed property map cannot be an `Lvalue Property Map`_
  (because remote values are not addressable), and is therefore
  limited to `Read/Write Property Map`_.


**Key**:
  The ``key_type`` of the distributed property map, which
  must model the `Global Descriptor`_ concept. The process ID type of
  the ``Key`` parameter must match the process ID type of the
  ``ProcessGroup``, and the local descriptor type of the ``Key`` must
  be convertible to the ``key_type`` of the ``LocalPropertyMap``.


**GhostCellS**:
  A selector type that indicates how ghost cells should be stored in
  the distributed property map. There are either two or three
  options, depending on your compiler:

    - ``boost::parallel::gc_mapS`` (default): Uses an STL ``map`` to
      store the ghost cells for each process. 
    
    - ``boost::parallel::gc_vector_mapS``: Uses a sorted STL
      ``vector`` to store the ghost cells for each process. This
      option works well when there are likely to be few insertions
      into the ghost cells; for instance, if the only ghost cells used
      are for neighboring vertices, the property map can be
      initialized with cells for each neighboring vertex, providing
      faster lookups than a ``map`` and using less space.

    - ``boost::parallel::gc_hash_mapS``: Uses the GCC ``hash_map`` to
      store ghost cells. This option may improve performance over
      ``map`` for large problems sizes, where the set of ghost cells
      cannot be predetermined.


Member functions
~~~~~~~~~~~~~~~~

::

  distributed_property_map();

Default-construct a distributed property map. The property map is in
an invalid state, and may only be used if it is reassigned to a valid
property map. 

------------------------------------------------------------------------------

::

    distributed_property_map(const ProcessGroup& pg, 
                             const LocalPropertyMap& pm);

    template<typename Reduce>
    distributed_property_map(const ProcessGroup& pg, 
                             const LocalPropertyMap& pm,
                             const Reduce& reduce);

Construct a property map from a process group and a local property
map. If a ``reduce`` operation is not supplied, a default of
``basic_reduce<value_type>`` will be used. 

------------------------------------------------------------------------------

::

  template<typename Reduce> void set_reduce(const Reduce& reduce);

Replace the current reduction operation with the new operation
``reduce``.

------------------------------------------------------------------------------

::

  void set_consistency_model(int model);

Sets the consistency model of the distributed property map, which will
take effect on the next synchronization step. See the section
`Consistency models`_ for a description of the effect of various
consistency model flags.

------------------------------------------------------------------------------

::
  
  void flush();

Emits a message sending the contents of all local ghost cells to the
owners of those cells. 

------------------------------------------------------------------------------

::
  
  void reset();

Replaces the values stored in each of the ghost cells with the default
value generated by the reduction operation. 

------------------------------------------------------------------------------

::
  
  void clear();

Removes all ghost cells from the property map.


Free functions
~~~~~~~~~~~~~~

::

  reference get(distributed_property_map pm, const key_type& key);

Retrieves the element in ``pm`` associated with the given ``key``. If
the key refers to data stored locally, returns the actual value
associated with the key. If the key refers to nonlocal data, returns
the value of the ghost cell. If no ghost cell exists, the behavior
depends on the current reduction operation: if a reduction operation
has been set and has ``non_default_resolver`` set ``true``, then a
ghost cell will be created according to the default value provided by
the reduction operation. Otherwise, the call to ``get`` will abort
because no value exists for this remote cell. To avoid this problem,
either set a reduction operation that generates default values,
``request()`` the value and then perform a synchronization step, or
``put`` a value into the cell before reading it.

------------------------------------------------------------------------------

::

  void
  put(distributed_property_map pm, const key_type& key, const value_type& value);

Places the given ``value`` associated with ``key`` into property map
``pm``. If the key refers to data stored locally, the value is
immediately updates. If the key refers to data stored in a remote
process, updates (or creates) a local ghost cell containing this
value for the key and sends the new value to the owning process. Note
that the owning process may reject this value based on the reduction
operation, but this will not be detected until the next
synchronization step.

------------------------------------------------------------------------------

::

  void
  local_put(distributed_property_map pm, const key_type& key, const value_type& value);

Equivalent to ``put(pm, key, value)``, except that no message is sent
to the owning process when the value is changed for a nonlocal key.

------------------------------------------------------------------------------

::

  void synchronize(distributed_property_map& pm);

Synchronize the values stored in the distributed property maps. Each
process much execute ``synchronize`` at the same time, after which
the ghost cells in every process will reflect the actual value stored
in the owning process.

------------------------------------------------------------------------------

::

 void request(distributed_property_map pm, const key_type& key);

Request that the element "key" be available after the next
synchronization step. For a non-local key, this means establishing a
ghost cell and requesting.

------------------------------------------------------------------------------

::

  template<typename Key, typename ProcessGroup, typename LocalPropertyMap>
  distributed_property_map
  make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap);

  template<typename Key, typename ProcessGroup, typename LocalPropertyMap,
           typename Reduce>
  distributed_property_map
  make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap,
                                Reduce reduce);

Create a distributed property map over process group ``pg`` and local
property map ``pmap``. A default reduction operation will be generated
if it is not provided.

---------------------------------
Distributed iterator property map
---------------------------------

The distributed iterator property map adaptor permits the creation of
distributed property maps from random access iterators using the same
syntax as non-distributed iterator property maps. The specialization
is based on a `local property map`_, which contains the
indices for local descriptors and is typically returned to describe
the vertex indices of a distributed graph.

Synopsis
~~~~~~~~

::

  template<typename RandomAccessIterator, typename ProcessGroup,
           typename GlobalKey, typename LocalMap, typename ValueType,
           typename Reference>
  class iterator_property_map<RandomAccessIterator, 
                              local_property_map,
                              ValueType, Reference>
  {
  public:
    typedef local_property_map index_map_type;

    iterator_property_map();
    iterator_property_map(RandomAccessIterator iter, const index_map_type& id);
  };

  reference get(iterator_property_map pm, const key_type& key);
  void put(iterator_property_map pm, const key_type& key, const value_type& value);

  template<typename RandomAccessIterator, typename ProcessGroup,
           typename GlobalKey, typename LocalMap>
  iterator_property_map<RandomAccessIterator, 
                        local_property_map >
  make_iterator_property_map(RandomAccessIterator iter, 
                             local_property_map id);


Member functions
~~~~~~~~~~~~~~~~

::

    iterator_property_map();

Default-constructs a distributed iterator property map. The property
map is in an invalid state, and must be reassigned before it may be
used. 

------------------------------------------------------------------------------

::

    iterator_property_map(RandomAccessIterator iter, const index_map_type& id);

Constructs a distributed iterator property map using the property map
``id`` to map global descriptors to local indices. The random access
iterator sequence ``[iter, iter + n)`` must be a valid range, where
``[0, n)`` is the range of local indices. 

Free functions
~~~~~~~~~~~~~~

::

  reference get(iterator_property_map pm, const key_type& key);

Returns the value associated with the given ``key`` from the
distributed property map.

------------------------------------------------------------------------------

::
 
  void put(iterator_property_map pm, const key_type& key, const value_type& value);

Associates the value with the given key in the distributed property map.

------------------------------------------------------------------------------

::

  template<typename RandomAccessIterator, typename ProcessGroup,
           typename GlobalKey, typename LocalMap, typename ValueType,
           typename Reference>
  iterator_property_map<RandomAccessIterator, 
                        local_property_map<ProcessGroup, GlobalKey, LocalMap>,
                                           ValueType, Reference>
  make_iterator_property_map(RandomAccessIterator iter, 
                             local_property_map<ProcessGroup, GlobalKey, LocalMap>,
                                                ValueType, Reference> id);

Creates a distributed iterator property map using the given iterator
``iter`` and local index property map ``id``.

--------------------------------------
Distributed safe iterator property map
--------------------------------------

The distributed safe iterator property map adaptor permits the
creation of distributed property maps from random access iterators
using the same syntax as non-distributed safe iterator property
maps. The specialization is based on a `local property map`_, which
contains the indices for local descriptors and is typically returned
to describe the vertex indices of a distributed graph. Safe iterator
property maps check the indices of accesses to ensure that they are
not out-of-bounds before attempting to access an value.

Synopsis
~~~~~~~~

::

  template<typename RandomAccessIterator, typename ProcessGroup,
           typename GlobalKey, typename LocalMap, typename ValueType,
           typename Reference>
  class safe_iterator_property_map<RandomAccessIterator, 
                                   local_property_map<ProcessGroup, GlobalKey, LocalMap>,
                                   ValueType, Reference>
  {
  public:
    typedef local_property_map<ProcessGroup, GlobalKey, LocalMap> index_map_type;

    safe_iterator_property_map();
    safe_iterator_property_map(RandomAccessIterator iter, std::size_t n, 
                               const index_map_type& id);
  };

  reference get(safe_iterator_property_map pm, const key_type& key);
  void put(safe_iterator_property_map pm, const key_type& key, const value_type& value);

  template<typename RandomAccessIterator, typename ProcessGroup,
           typename GlobalKey, typename LocalMap, typename ValueType,
           typename Reference>
  safe_iterator_property_map<RandomAccessIterator, 
                             local_property_map<ProcessGroup, GlobalKey, LocalMap>,
                                                ValueType, Reference>
  make_safe_iterator_property_map(RandomAccessIterator iter, 
                                  std::size_t n,
                                  local_property_map<ProcessGroup, GlobalKey, LocalMap>,
                                                     ValueType, Reference> id);

Member functions
~~~~~~~~~~~~~~~~

::

    safe_iterator_property_map();

Default-constructs a distributed safe iterator property map. The property
map is in an invalid state, and must be reassigned before it may be
used. 

------------------------------------------------------------------------------

::

    safe_iterator_property_map(RandomAccessIterator iter, std::size_t n,
                               const index_map_type& id);

Constructs a distributed safe iterator property map using the property map
``id`` to map global descriptors to local indices. The random access
iterator sequence ``[iter, iter + n)``. 

Free functions
~~~~~~~~~~~~~~

::

  reference get(safe_iterator_property_map pm, const key_type& key);

Returns the value associated with the given ``key`` from the
distributed property map.

------------------------------------------------------------------------------

::
 
  void put(safe_iterator_property_map pm, const key_type& key, const value_type& value);

Associates the value with the given key in the distributed property map.

------------------------------------------------------------------------------

::

  template<typename RandomAccessIterator, typename ProcessGroup,
           typename GlobalKey, typename LocalMap, typename ValueType,
           typename Reference>
  safe_iterator_property_map<RandomAccessIterator, 
                             local_property_map,
                                                ValueType, Reference>
  make_safe_iterator_property_map(RandomAccessIterator iter, 
                                  std::size_t n,
                                  local_property_map,
                                                     ValueType, Reference> id);

Creates a distributed safe iterator property map using the given iterator
``iter`` and local index property map ``id``. The indices in ``id`` must

------------------
Local property map
------------------

A property map adaptor that accesses an underlying property map whose
key type is the local part of the ``Key`` type for the local subset
of keys. Local property maps are typically used by distributed graph
types for vertex index properties.

Synopsis
~~~~~~~~

::

  template<typename ProcessGroup, typename GlobalKey, typename LocalMap>
    class local_property_map
    {
    public:
    typedef typename property_traits<LocalMap>::value_type value_type;
    typedef GlobalKey                                      key_type;
    typedef typename property_traits<LocalMap>::reference  reference;
    typedef typename property_traits<LocalMap>::category   category;

    explicit 
    local_property_map(const ProcessGroup& process_group = ProcessGroup(),
                       const LocalMap& local_map = LocalMap());

    reference operator[](const key_type& key);
  };

  reference get(const local_property_map& pm, key_type key);
  void put(local_property_map pm, const key_type& key, const value_type& value);

Template parameters
~~~~~~~~~~~~~~~~~~~

:ProcessGroup: the type of the process group over which the global
  keys are distributed.

:GlobalKey: The ``key_type`` of the local property map, which
  must model the `Global Descriptor`_ concept. The process ID type of
  the ``GlobalKey`` parameter must match the process ID type of the
  ``ProcessGroup``, and the local descriptor type of the ``GlobalKey``
  must be convertible to the ``key_type`` of the ``LocalMap``.

:LocalMap: the type of the property map that will store values
  for keys local to this processor. The ``value_type`` of this
  property map will become the ``value_type`` of the local
  property map. The local property map models the same property
  map concepts as the ``LocalMap``.

Member functions
~~~~~~~~~~~~~~~~

::

  explicit 
  local_property_map(const ProcessGroup& process_group = ProcessGroup(),
                     const LocalMap& local_map = LocalMap());

Constructs a local property map whose keys are distributed across the
given process group and which accesses the given local map.

------------------------------------------------------------------------------

::

  reference operator[](const key_type& key);

Access the value associated with the given key, which must be local
to this process.

Free functions
~~~~~~~~~~~~~~

::

  reference get(const local_property_map& pm, key_type key);

Return the value associated with the given key, which must be local
to this process.

------------------------------------------------------------------------------

::

  void put(local_property_map pm, const key_type& key, const value_type& value);

Set the value associated with the given key, which must be local to
this process.

-----------------------------------------------------------------------------

Copyright (C) 2004, 2005 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
.. _Writable Property Map: http://www.boost.org/libs/property_map/WritablePropertyMap.html
.. _Read/Write Property Map: http://www.boost.org/libs/property_map/ReadWritePropertyMap.html
.. _Lvalue Property Map: http://www.boost.org/libs/property_map/LvaluePropertyMap.html
.. _Process Group: process_group.html
.. _Global Descriptor: GlobalDescriptor.html
.. _Dijkstra's shortest paths: dijkstra_shortest_paths.html
.. _Breadth-First Search: breadth_first_search.html
.. _PageRank: page_rank.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Distributed Queue (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/distributed_queue.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

================================
|Logo| Distributed queue adaptor
================================

::

  template<typename ProcessGroup, typename Buffer>
  class distributed_queue
  {
  public:
    typedef ProcessGroup                     process_group_type;
    typedef Buffer                           buffer_type;
    typedef typename buffer_type::value_type value_type;
    typedef typename buffer_type::size_type  size_type;

    explicit 
    distributed_queue(const ProcessGroup& process_group = ProcessGroup(), 
                      const Buffer& buffer = Buffer(),
                      bool polling = false);

    distributed_queue(const ProcessGroup& process_group, bool polling);

    void push(const value_type& x);
    void pop(); 
    value_type& top();
    const value_type& top() const;
    bool empty() const;
    size_type size() const;
  };

  template<typename ProcessGroup, typename Buffer>
  inline distributed_queue<ProcessGroup, Buffer>
  make_distributed_queue(const ProcessGroup& process_group, const Buffer& buffer,
                         bool polling = false);
  
Class template ``distributed_queue`` implements a distributed queue
across a process group. The distributed queue is an adaptor over an
existing (local) queue, which must model the Buffer_ concept. Each
process stores a distinct copy of the local queue, from which it draws
or removes elements via the ``pop`` and ``top`` members.

The value type of the local queue must be a model of the 
`Global Descriptor`_ concept. The ``push`` operation of the
distributed queue passes (via a message) the value to its owning
processor. Thus, the elements within a particular local queue are
guaranteed to have the process owning that local queue as an owner.

Synchronization of distributed queues occurs in the ``empty`` and
``size`` functions, which will only return "empty" values (true or 0,
respectively) when the entire distributed queue is empty. If the local
queue is empty but the distributed queue is not, the operation will
block until either condition changes. When the ``size`` function of a
nonempty queue returns, it returns the size of the local queue. These
semantics were selected so that sequential code that processes
elements in the queue via the following idiom can be parallelized via
introduction of a distributed queue:

::

  distributed_queue<...> Q;
  Q.push(x);
  while (!Q.empty()) {
    // do something, that may push a value onto Q
  }

In the parallel version, the initial ``push`` operation will place
the value ``x`` onto its owner's queue. All processes will
synchronize at the call to empty, and only the process owning ``x``
will be allowed to execute the loop (``Q.empty()`` returns
false). This iteration may in turn push values onto other remote
queues, so when that process finishes execution of the loop body
and all processes synchronize again in ``empty``, more processes
may have nonempty local queues to execute. Once all local queues
are empty, ``Q.empty()`` returns ``false`` for all processes.

The distributed queue can receive messages at two different times:
during synchronization and when polling ``empty``. Messages are
always received during synchronization, to ensure that accurate
local queue sizes can be determines. However, whether ``empty``
should poll for messages is specified as an option to the
constructor. Polling may be desired when the order in which
elements in the queue are processed is not important, because it
permits fewer synchronization steps and less communication
overhead. However, when more strict ordering guarantees are
required, polling may be semantically incorrect. By disabling
polling, one ensures that parallel execution using the idiom above
will not process an element at a later "level" before an earlier
"level". 

The distributed queue nearly models the Buffer_
concept. However, the ``push`` routine does not necessarily
increase the result of ``size()`` by one (although the size of the
global queue does increase by one).

Member Functions
----------------

::

  explicit 
  distributed_queue(const ProcessGroup& process_group = ProcessGroup(), 
                    const Buffer& buffer = Buffer(),
                    bool polling = false);

Build a new distributed queue that communicates over the given
``process_group``, whose local queue is initialized via ``buffer`` and
which may or may not poll for messages.

-----------------------------------------------------------------------------

::

  distributed_queue(const ProcessGroup& process_group, bool polling);

Build a new distributed queue that communicates over the given 
``process_group``, whose local queue is default-initalized and which
may or may not poll for messages.

-----------------------------------------------------------------------------

::

  void push(const value_type& x);

Push an element onto the distributed queue.

The element will be sent to its owner process to be added to that
process's local queue. If polling is enabled for this queue and
the owner process is the current process, the value will be
immediately pushed onto the local queue.

Complexity: O(1) messages of size O(``sizeof(value_type)``) will be
transmitted.


-----------------------------------------------------------------------------

::

  void pop();

Pop an element off the local queue. The queue must not be ``empty()``.

-----------------------------------------------------------------------------

::

  value_type& top();
  const value_type& top();

Returns the top element in the local queue. The queue must not be
``empty()``.

-----------------------------------------------------------------------------

::

  bool empty() const;

Determines if the queue is empty.

When the local queue is nonempty, returns true. If the local queue is
empty, synchronizes with all other processes in the process group
until either (1) the local queue is nonempty (returns true) (2) the
entire distributed queue is empty (returns false).

-----------------------------------------------------------------------------

::

  size_type size() const;


Determines the size of the local queue.

The behavior of this routine is equivalent to the behavior of
``empty``, except that when ``empty`` returns true this
function returns the size of the local queue and when ``empty``
returns false this function returns zero.

Free Functions
--------------

::

  template<typename ProcessGroup, typename Buffer>
  inline distributed_queue<ProcessGroup, Buffer>
  make_distributed_queue(const ProcessGroup& process_group, const Buffer& buffer,
                         bool polling = false);

Constructs a distributed queue.

-----------------------------------------------------------------------------

Copyright (C) 2004, 2005 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Global descriptor: GlobalDescriptor.html
.. _Buffer: http://www.boost.org/libs/graph/doc/Buffer.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Fruchterman Reingold (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/fruchterman_reingold.rst`)

.. Copyright (C) 2004-2009 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===========================
|Logo| Fruchterman Reingold
===========================

::

    namespace graph { namespace distributed {

      template<typename Graph, typename PositionMap, 
               typename AttractiveForce, typename RepulsiveForce,
               typename ForcePairs, typename Cooling, typename DisplacementMap>
      void
      fruchterman_reingold_force_directed_layout
      (const Graph&    g,
       PositionMap     position,
       typename property_traits<PositionMap>::value_type const& origin,
       typename property_traits<PositionMap>::value_type const& extent,
       AttractiveForce attractive_force,
       RepulsiveForce  repulsive_force,
       ForcePairs      force_pairs,
       Cooling         cool,
       DisplacementMap displacement)

      template<typename Graph, typename PositionMap, 
               typename AttractiveForce, typename RepulsiveForce,
               typename ForcePairs, typename Cooling, typename DisplacementMap>
      void
      fruchterman_reingold_force_directed_layout
      (const Graph&    g,
       PositionMap     position,
       typename property_traits<PositionMap>::value_type const& origin,
       typename property_traits<PositionMap>::value_type const& extent,
       AttractiveForce attractive_force,
       RepulsiveForce  repulsive_force,
       ForcePairs      force_pairs,
       Cooling         cool,
       DisplacementMap displacement,
       simple_tiling   tiling)
    } }

.. contents::

Where Defined
-------------
<``boost/graph/distributed/fruchterman_reingold.hpp``>

also accessible from

<``boost/graph/fruchterman_reingold.hpp``>

Parameters
----------

IN:  ``const Graph& g``
  The graph type must be a model of `Distributed Graph`_.  The graph
  type must also model the `Incidence Graph`_.

OUT:  ``PositionMap position``

IN:  ``property_traits<PositionMap>::value_type origin``

IN:  ``property_traits<PositionMap>::value_type extent``

IN:  ``AttractiveForce attractive_force``

IN:  ``RepulsiveForce repulsive_force``

IN:  ``ForcePairs force_pairs``

IN:  ``Cooling cool``

IN:  ``DisplacementMap displacement``

..
 Complexity
 ----------

..
 Algorithm Description
 ---------------------

-----------------------------------------------------------------------------

Copyright (C) 2009 The Trustees of Indiana University.

Authors: Nick Edmonds and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Distributed Graph: DistributedGraph.html
.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html
.. _Distributed Property Map: distributed_property_map.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Index (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/index.rst`)

.. Copyright (C) 2004-2009 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===================================
|Logo| Parallel Boost Graph Library
===================================

Overview
--------

The Parallel Boost Graph Library is an extension to the `Boost Graph
Library`_ (BGL) for parallel and distributed computing. It offers
distributed graphs and graph algorithms to exploit coarse-grained
parallelism along with parallel algorithms that exploit fine-grained
parallelism, while retaining the same interfaces as the (sequential)
BGL. Code written using the sequential BGL should be easy to
parallelize with the parallel BGL. Visitors new to the Parallel BGL
should read our `architectural overview`_.

1. `Process groups`_

  - `MPI process group`_
  - `Simple trigger interface`_

2. Auxiliary data structures

  - `Distributed queue`_
  - `Distributed property map`_
 
3. Distributed graph concepts

  - `Distributed Graph`_
  - `Distributed Vertex List Graph`_
  - `Distributed Edge List Graph`_
  - `Global Descriptor`_

4. Graph data structures

  - `Distributed adjacency list`_

5. Graph adaptors

  - `Local subgraph adaptor`_
  - `Vertex list graph adaptor`_

6. Graph input/output

  - Graphviz output
  - `METIS input`_

7. Synthetic data generators

  - `R-MAT generator`_
  - `Sorted R-MAT generator`_
  - `Sorted unique R-MAT generator`_
  - `Unique R-MAT generator`_
  - `Scalable R-MAT generator`_
  - `Erdos-Renyi generator`_
  - `Sorted Erdos-Renyi generator`_
  - `Small world generator`_
  - `SSCA generator`_
  - `Mesh generator`_

8. Algorithms

  - Distributed algorithms 

    - `Breadth-first search`_
    - `Dijkstra's single-source shortest paths`_

      - `Eager Dijkstra shortest paths`_
      - `Crauser et al. Dijkstra shortest paths`_
      - `Delta-Stepping shortest paths`_

    - `Depth-first search`_
    - `Minimum spanning tree`_

      - `Boruvka's minimum spanning tree`_
      - `Merging local minimum spanning forests`_
      - `Boruvka-then-merge`_
      - `Boruvka-mixed-merge`_

    - Connected components

      - `Connected components`_
      - `Connected components parallel search`_
      - `Strongly-connected components`_
    
    - PageRank_
    - `Boman et al. Graph coloring`_
    - `Fruchterman Reingold force-directed layout`_
    - `s-t connectivity`_
    - `Betweenness centrality`_
    - `Non-distributed betweenness centrality`_

----------------------------------------------------------------------------

Copyright (C) 2005-2009 The Trustees of Indiana University.

Authors: Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Parallel Dijkstra example: dijkstra_example.html
.. _Boost Graph Library: http://www.boost.org/libs/graph/doc
.. _adjacency_list: http://www.boost.org/libs/graph/doc/adjacency_list.html
.. _local subgraph adaptor: local_subgraph.html
.. _vertex list graph adaptor: vertex_list_adaptor.html
.. _MPI: http://www-unix.mcs.anl.gov/mpi/
.. _generic programming: http://www.cs.rpi.edu/~musser/gp/
.. _development page: design/index.html
.. _process groups: process_group.html
.. _MPI process group: process_group.html
.. _Simple trigger interface: simple_trigger.html
.. _Open Systems Laboratory: http://www.osl.iu.edu
.. _Indiana University: http://www.indiana.edu
.. _Distributed adjacency list: distributed_adjacency_list.html
.. _Distributed queue: distributed_queue.html
.. _Distributed property map: distributed_property_map.html
.. _R-MAT generator: rmat_generator.html
.. _Sorted R-MAT generator: sorted_rmat_generator.html
.. _Sorted Unique R-MAT generator: sorted_unique_rmat_generator.html
.. _Unique R-MAT generator: unique_rmat_generator.html
.. _Scalable R-MAT generator: scalable_rmat_generator.html
.. _Erdos-Renyi generator: http://www.boost.org/libs/graph/doc/erdos_renyi_generator.html
.. _Sorted Erdos-Renyi generator: http://www.boost.org/libs/graph/doc/sorted_erdos_renyi_gen.html
.. _Small world generator: http://www.boost.org/libs/graph/doc/small_world_generator.html
.. _SSCA generator: ssca_generator.html
.. _Mesh generator: mesh_generator.html
.. _Breadth-first search: breadth_first_search.html
.. _Depth-first search: tsin_depth_first_visit.html
.. _Dijkstra's single-source shortest paths: dijkstra_shortest_paths.html
.. _Eager Dijkstra shortest paths: dijkstra_shortest_paths.html#eager-dijkstra-s-algorithm
.. _Crauser et al. Dijkstra shortest paths: dijkstra_shortest_paths.html#crauser-et-al-s-algorithm
.. _Delta-Stepping shortest paths: dijkstra_shortest_paths.html#delta-stepping-algorithm
.. _Minimum spanning tree: dehne_gotz_min_spanning_tree.html
.. _Boruvka's minimum spanning tree: dehne_gotz_min_spanning_tree.html#dense-boruvka-minimum-spanning-tree
.. _Merging local minimum spanning forests: dehne_gotz_min_spanning_tree.html#merge-local-minimum-spanning-trees
.. _Boruvka-then-merge: dehne_gotz_min_spanning_tree.html#boruvka-then-merge
.. _Boruvka-mixed-merge: dehne_gotz_min_spanning_tree.html#boruvka-mixed-merge
.. _PageRank: page_rank.html
.. _Boman et al. Graph coloring: boman_et_al_graph_coloring.html
.. _Connected components: connected_components.html
.. _Connected components parallel search: connected_components_parallel_search.html
.. _Strongly-connected components: strong_components.html
.. _Distributed Graph: DistributedGraph.html
.. _Distributed Vertex List Graph: DistributedVertexListGraph.html
.. _Distributed Edge List Graph: DistributedEdgeListGraph.html
.. _Global Descriptor: GlobalDescriptor.html
.. _METIS Input: metis.html
.. _architectural overview: overview.html
.. _Fruchterman Reingold force-directed layout: fruchterman_reingold.html
.. _s-t connectivity: st_connected.html
.. _Betweenness centrality: betweenness_centrality.html
.. _Non-distributed betweenness centrality: non_distributed_betweenness_centrality.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Local Subgraph (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/local_subgraph.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

=============================
|Logo| Local Subgraph Adaptor
=============================

The local subgraph adaptor takes an existing `Distributed Graph` and
filters out all of the nonlocal edges and vertices, presenting only
the local portion of the distributed graph to the user. The behavior
is equivalent to (and implemented with) a `filtered graph`_, and is a
noncopying view into the graph itself. Changes made through the
filtered graph will be reflected in the original graph and vice-versa.

::

  template<typename DistributedGraph> class local_subgraph;

  template<typename DistributedGraph>
  local_subgraph<DistributedGraph> make_local_subgraph(DistributedGraph& g);

Where Defined
-------------
<boost/graph/distributed/local_subgraph.hpp>

Reference
---------
The local subgraph adaptor adapts and forwards all operations of
distributed graphs, the signatures of which will be omitted. Only
operations unique to the local subgraph adaptor are presented.

Member Functions
~~~~~~~~~~~~~~~~

::

  local_subgraph(DistributedGraph& g);

Constructs a local subgraph presenting the local portion of the
distributed graph ``g``.

--------------------------------------------------------------------------

::
 
  DistributedGraph&         base()               { return g; }
  const DistributedGraph&   base() const         { return g; }

Returns the underlying distributed graph.

Free Functions
~~~~~~~~~~~~~~

::

  template<typename DistributedGraph>
  local_subgraph<DistributedGraph> make_local_subgraph(DistributedGraph& g);

Constructs a local subgraph presenting the local portion of the
distributed graph ``g``.

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _filtered graph: http://www.boost.org/libs/graph/doc/filtered_graph.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Mesh Generator (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/mesh_generator.rst`)

.. Copyright (C) 2004-2009 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===========================
|Logo| Mesh Generator
===========================


-----------------------------------------------------------------------------

Copyright (C) 2009 The Trustees of Indiana University.

Authors: Nick Edmonds and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Metis (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/metis.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

=========================================
|Logo| METIS Input Routines
=========================================

:: 

  namespace boost { 
    namespace graph {
      class metis_reader;
      class metis_exception;
      class metis_input_exception;
      class metis_distribution;
    }
  }


METIS_ is a set of programs for partitioning graphs (among other
things). The Parallel BGL can read the METIS graph format and
partition format, allowing one to easily load METIS-partitioned
graphs into the Parallel BGL's data structures.

.. contents::

Where Defined
~~~~~~~~~~~~~
<``boost/graph/metis.hpp``>


Graph Reader
------------------

::

  class metis_reader
  {
   public:
    typedef std::size_t vertices_size_type;
    typedef std::size_t edges_size_type;
    typedef double vertex_weight_type;
    typedef double edge_weight_type;

    class edge_iterator;
    class edge_weight_iterator;
    
    metis_reader(std::istream& in);

    edge_iterator begin();
    edge_iterator end();
    edge_weight_iterator weight_begin();

    vertices_size_type num_vertices() const;
    edges_size_type num_edges() const;

    std::size_t num_vertex_weights() const;

    vertex_weight_type vertex_weight(vertices_size_type v, std::size_t n);

    bool has_edge_weights() const;
  };


Usage
~~~~~

The METIS reader provides an iterator interface to the METIS graph
file. The iterator interface is most useful when constructing Parallel
BGL graphs on-the-fly. For instance, the following code builds a graph
``g`` from a METIS graph stored in ``argv[1]``. 

::

  std::ifstream in_graph(argv[1]);
  metis_reader reader(in_graph);
  Graph g(reader.begin(), reader.end(),
          reader.weight_begin(),
          reader.num_vertices());


The calls to ``begin()`` and ``end()`` return an iterator range for
the edges in the graph; the call to ``weight_begin()`` returns an
iterator that will enumerate the weights of the edges in the
graph. For a distributed graph, the distribution will be determined
automatically by the graph; to use a METIS partitioning, see the
section `Partition Reader`_.

Associated Types 
~~~~~~~~~~~~~~~~

::

  metis_reader::edge_iterator

An `Input Iterator`_ that enumerates the edges in the METIS graph, and
is suitable for use as the ``EdgeIterator`` of an adjacency_list_.
The ``value_type`` of this iterator is a pair of vertex numbers.

-----------------------------------------------------------------------------

::

  metis_reader::edge_weight_iterator

An `Input Iterator`_ that enumerates the edge weights in the METIS
graph. The ``value_type`` of this iterator is ``edge_weight_type``. If
the edges in the METIS graph are unweighted, the result of
dereferencing this iterator will always be zero.

Member Functions
~~~~~~~~~~~~~~~~

::

  metis_reader(std::istream& in);

Constructs a new METIS reader that will retrieve edges from the input
stream ``in``. If any errors are encountered while initially parsing
``in``, ``metis_input_exception`` will be thrown.

-----------------------------------------------------------------------------

::

  edge_iterator begin();

Returns an iterator to the first edge in the METIS file. 

-----------------------------------------------------------------------------

::

  edge_iterator end();

Returns an iterator one past the last edge in the METIS file.

-----------------------------------------------------------------------------

::

  edge_weight_iterator weight_begin();

Returns an iterator to the first edge weight in the METIS file. The
weight iterator should be moved in concert with the edge iterator;
when the edge iterator moves, the edge weight changes. If the edges
in the graph are unweighted, the weight returned will always be zero.

-----------------------------------------------------------------------------

::

  vertices_size_type num_vertices() const;

Returns the number of vertices in the graph.


-----------------------------------------------------------------------------

::

    edges_size_type num_edges() const;

Returns the number of edges in the graph.

-----------------------------------------------------------------------------

::

    std::size_t num_vertex_weights() const;

Returns the number of weights attached to each vertex.

-----------------------------------------------------------------------------

::

    vertex_weight_type vertex_weight(vertices_size_type v, std::size_t n);

-----------------------------------------------------------------------------

::

    bool has_edge_weights() const;  

Returns ``true`` when the edges of the graph have weights, ``false``
otherwise. When ``false``, the edge weight iterator is still valid
but returns zero for the weight of each edge.


Partition Reader
----------------

::

  class metis_distribution
  {
   public:  
    typedef int process_id_type;
    typedef std::size_t size_type;

    metis_distribution(std::istream& in, process_id_type my_id);
    
    size_type block_size(process_id_type id, size_type) const;
    process_id_type operator()(size_type n);
    size_type local(size_type n) const;
    size_type global(size_type n) const;
    size_type global(process_id_type id, size_type n) const;

   private:
    std::istream& in;
    process_id_type my_id;
    std::vector<process_id_type> vertices;
  };


Usage
~~~~~

The class ``metis_distribution`` loads a METIS partition file and
makes it available as a Distribution suitable for use with the
`distributed adjacency list`_ graph type. To load a METIS graph using
a METIS partitioning, use a ``metis_reader`` object for the graph and
a ``metis_distribution`` object for the distribution, as in the
following example.

::

  std::ifstream in_graph(argv[1]);
  metis_reader reader(in_graph);

  std::ifstream in_partitions(argv[2]);
  metis_distribution dist(in_partitions, process_id(pg));
  Graph g(reader.begin(), reader.end(),
          reader.weight_begin(),
          reader.num_vertices(),
          pg,
          dist);

In this example, ``argv[1]`` is the graph and ``argv[2]`` is the
partition file generated by ``pmetis``. The ``dist`` object loads the
partitioning information from the input stream it is given and uses
that to distributed the adjacency list. Note that the input stream
must be in the METIS partition file format and must have been
partitioned for the same number of processes are there are in the
process group ``pg``.

Member Functions
~~~~~~~~~~~~~~~~

::

  metis_distribution(std::istream& in, process_id_type my_id);

Creates a new METIS distribution from the input stream
``in``. ``my_id`` is the process ID of the current process in the
process group over which the graph will be distributed.

-----------------------------------------------------------------------------

::

  size_type block_size(process_id_type id, size_type) const;

Returns the number of vertices to be stored in the process
``id``. The second parameter, ``size_type``, is unused and may be any
value. 

-----------------------------------------------------------------------------

::

  process_id_type operator()(size_type n);

Returns the ID for the process that will store vertex number ``n``.

-----------------------------------------------------------------------------

::

  size_type local(size_type n) const;

Returns the local index of vertex number ``n`` within its owning
process. 

-----------------------------------------------------------------------------

::

  size_type global(size_type n) const;

Returns the global index of the current processor's local vertex ``n``. 

-----------------------------------------------------------------------------


::

  size_type global(process_id_type id, size_type n) const;
  
Returns the global index of the process ``id``'s local vertex ``n``.

-----------------------------------------------------------------------------

Copyright (C) 2005 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. _METIS: http://www-users.cs.umn.edu/~karypis/metis/metis/
.. _distributed adjacency list: distributed_adjacency_list.html
.. _adjacency_list: http://www.boost.org/libs/graph/doc/adjacency_list.html
.. _input iterator: http://www.sgi.com/tech/stl/InputIterator.html

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Mpi Bsp Process Group (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/mpi_bsp_process_group.rst`)

.. Copyright (C) 2004-2009 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

============================
|Logo| MPI BSP Process Group
============================

.. contents::

Introduction
------------

The MPI ``mpi_process_group`` is an implementation of the `process
group`_ interface using the Message Passing Interface (MPI). It is the
primary process group used in the Parallel BGL at this time.

Where Defined
-------------

Header ``<boost/graph/distributed/mpi_process_group.hpp>``

Reference
---------

::

  namespace boost { namespace graph { namespace distributed {

  class mpi_process_group 
  {
  public:
    typedef boost::mpi::communicator communicator_type;
    
    // Process group constructors
    mpi_process_group(communicator_type comm = communicator_type());
    mpi_process_group(std::size_t num_headers, std::size_t buffer_size, 
                      communicator_type comm = communicator_type());
    
    mpi_process_group();
    mpi_process_group(const mpi_process_group&, boost::parallel::attach_distributed_object);

    // Triggers
    template<typename Type, typename Handler>
      void trigger(int tag, const Handler& handler);

    template<typename Type, typename Handler>
      void trigger_with_reply(int tag, const Handler& handler);

    trigger_receive_context trigger_context() const;

    // Helper operations
    void poll();
    mpi_process_group base() const;
  };

  // Process query
  int process_id(const mpi_process_group&);
  int num_processes(const mpi_process_group&);

  // Message transmission
  template<typename T>
    void send(const mpi_process_group& pg, int dest, int tag, const T& value);

  template<typename T>
    void receive(const mpi_process_group& pg, int source, int tag, T& value);

  optional<std::pair<int, int> > probe(const mpi_process_group& pg);

  // Synchronization
  void synchronize(const mpi_process_group& pg);

  // Out-of-band communication
  template<typename T>
    void send_oob(const mpi_process_group& pg, int dest, int tag, const T& value);

  template<typename T, typename U>
    void 
    send_oob_with_reply(const mpi_process_group& pg, int dest, int
                        tag, const T& send_value, U& receive_value);

  template<typename T>
    void receive_oob(const mpi_process_group& pg, int source, int tag, T& value);

  } } }

Since the ``mpi_process_group`` is an implementation of the `process
group`_ interface, we omit the description of most of the functions in
the prototype. Two constructors need special mentioning:

::
  
      mpi_process_group(communicator_type comm = communicator_type());

The constructor can take an optional MPI communicator. As default a communicator
constructed from MPI_COMM_WORLD is used.

::
  
    mpi_process_group(std::size_t num_headers, std::size_t buffer_size, 
                      communicator_type comm = communicator_type());


For performance fine tuning the maximum number of headers in a message batch
(num_headers) and the maximum combined size of batched messages (buffer_size) 
can be specified. The maximum message size of a batch is 
16*num_headers+buffer_size. Sensible default values have been found by optimizing
a typical application on a cluster with Ethernet network, and are num_header=64k
and buffer_size=1MB, for a total maximum batches message size of 2MB.



-----------------------------------------------------------------------------

Copyright (C) 2007 Douglas Gregor

Copyright (C) 2007 Matthias Troyer

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _process group: process_group.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Non Distributed Betweenness Centrality (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/non_distributed_betweenness_centrality.rst`)

.. Copyright (C) 2004-2009 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

=============================================
|Logo| Non-Distributed Betweenness Centrality
=============================================

::

  // named parameter versions
  template<typename ProcessGroup, typename Graph, typename Param, typename Tag, typename Rest>
  void 
  non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g, 
                                                 const bgl_named_params<Param,Tag,Rest>& params);

  template<typename ProcessGroup, typename Graph, typename CentralityMap, 
           typename Buffer>
  void 
  non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g, 
                                                 CentralityMap centrality, Buffer sources);

  template<typename ProcessGroup, typename Graph, typename CentralityMap, 
           typename EdgeCentralityMap, typename Buffer>
  void 
  non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg, const Graph& g, 
                                                 CentralityMap centrality,
                                                 EdgeCentralityMap edge_centrality_map, 
                                                 Buffer sources);

  // non-named parameter versions
  template<typename ProcessGroup, typename Graph, typename CentralityMap, 
           typename EdgeCentralityMap, typename IncomingMap, typename DistanceMap, 
           typename DependencyMap, typename PathCountMap, typename VertexIndexMap, 
           typename Buffer>
  void 
  non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg,
                                                 const Graph& g, 
                                                 CentralityMap centrality,
                                                 EdgeCentralityMap edge_centrality_map,
                                                 IncomingMap incoming, 
                                                 DistanceMap distance, 
                                                 DependencyMap dependency,     
                                                 PathCountMap path_count,      
                                                 VertexIndexMap vertex_index,
                                                 Buffer sources);

  template<typename ProcessGroup, typename Graph, typename CentralityMap, 
           typename EdgeCentralityMap, typename IncomingMap, typename DistanceMap, 
           typename DependencyMap, typename PathCountMap, typename VertexIndexMap, 
           typename WeightMap, typename Buffer>
  void 
  non_distributed_brandes_betweenness_centrality(const ProcessGroup& pg,
                                                 const Graph& g, 
                                                 CentralityMap centrality,
                                                 EdgeCentralityMap edge_centrality_map,
                                                 IncomingMap incoming, 
                                                 DistanceMap distance, 
                                                 DependencyMap dependency,
                                                 PathCountMap path_count, 
                                                 VertexIndexMap vertex_index,
                                                 WeightMap weight_map,
                                                 Buffer sources);

  // helper functions
  template<typename Graph, typename CentralityMap>
  typename property_traits<CentralityMap>::value_type
  central_point_dominance(const Graph& g, CentralityMap centrality);

The ``non_distributed_betweenness_centrality()`` function computes the
betweenness centrality of the vertices and edges in a graph.  The name
is somewhat confusing, the graph ``g`` is not a distributed graph,
however the algorithm does run in parallel.  Rather than parallelizing
the individual shortest paths calculations that are required by
betweenness centrality, this variant of the algorithm performs the
shortest paths calculations in parallel with each process in ``pg``
calculating the shortest path from a different set of source vertices
using the BGL's implementation of `Dijkstra shortest paths`_.  Each
process accumulates into it's local centrality map and once all the
shortest paths calculations are performed a reduction is performed to
combine the centrality from all the processes.

.. contents::

Where Defined
-------------
<``boost/graph/distributed/betweenness_centrality.hpp``>

Parameters
----------

IN: ``const ProcessGroup& pg`` 
  The process group over which the the processes involved in
  betweenness centrality communicate.  The process group type must
  model the `Process Group`_ concept.

IN: ``const Graph& g`` 
  The graph type must be a model of the `Incidence Graph`_ concept.

IN: ``CentralityMap centrality`` 
  A centrality map may be supplied to the algorithm, if one is not
  supplied a ``dummy_property_map`` will be used and no vertex
  centrality information will be recorded.  The key type of the
  ``CentralityMap`` must be the graph's vertex descriptor type.

  **Default**: A ``dummy_property_map``.

IN:  ``EdgeCentralityMap edge_centrality_map``
  An edge centrality map may be supplied to the algorithm, if one is
  not supplied a ``dummy_property_map`` will be used and no edge
  centrality information will be recorded.  The key type of the
  ``EdgeCentralityMap`` must be the graph's vertex descriptor type.

  **Default**: A ``dummy_property_map``.

IN:  ``IncomingMap incoming``
  The incoming map contains the incoming edges to a vertex that are
  part of shortest paths to that vertex.  Its key type must be the
  graph's vertex descriptor type and its value type must be the
  graph's edge descriptor type.

  **Default**: An ``iterator_property_map`` created from a
    ``std::vector`` of ``std::vector`` of the graph's edge descriptor
    type.

IN:  ``DistanceMap distance``
  The distance map records the distance to vertices during the
  shortest paths portion of the algorithm.  Its key type must be the
  graph's vertex descriptor type.

  **Default**: An ``iterator_property_map`` created from a
    ``std::vector`` of the value type of the ``CentralityMap``.

IN: ``DependencyMap dependency`` 
  The dependency map records the dependency of each vertex during the
  centrality calculation portion of the algorithm.  Its key type must
  be the graph's vertex descriptor type.

  **Default**: An ``iterator_property_map`` created from a
    ``std::vector`` of the value type of the ``CentralityMap``.

IN:  ``PathCountMap path_count``
  The path count map records the number of shortest paths each vertex
  is on during the centrality calculation portion of the algorithm.
  Its key type must be the graph's vertex descriptor type.

  **Default**: An ``iterator_property_map`` created from a
    ``std::vector`` of the graph's degree size type.

IN:  ``VertexIndexMap vertex_index``
  A model of `Readable Property Map`_ whose key type is the vertex
  descriptor type of the graph ``g`` and whose value type is an
  integral type. The property map should map from vertices to their
  (local) indices in the range *[0, num_vertices(g))*.

  **Default**: ``get(vertex_index, g)``

IN:  ``WeightMap weight_map``
  A model of `Readable Property Map`_ whose key type is the edge
  descriptor type of the graph ``g``.  If not supplied the betweenness
  centrality calculation will be unweighted.

IN: ``Buffer sources`` 
  A model of Buffer_ containing the starting vertices for the
  algorithm.  If ``sources`` is empty a complete betweenness
  centrality calculation using all vertices in ``g`` will be
  performed.  The value type of the Buffer must be the graph's vertex
  descriptor type.

  **Default**: An empty ``boost::queue`` of int.

Complexity
----------

Each of the shortest paths calculations is *O(V log V)* and each of
them may be run in parallel (one per process in ``pg``).  The
reduction phase to calculate the total centrality at the end of the
shortest paths phase is *O(V log V)*.

Algorithm Description
---------------------

The algorithm uses a non-distributed (sequential) graph, as well as
non-distributed property maps.  Each process contains a separate copy
of the sequential graph ``g``.  In order for the algorithm to be
correct, these copies of ``g`` must be identical.  The ``sources``
buffer contains the vertices to use as the source of single source
shortest paths calculations when approximating betweenness centrality
using a subset of the vertices in the graph.  If ``sources`` is empty
then a complete betweenness centrality calculation is performed using
all vertices.

In the sequential phase of the algorithm each process computes
shortest paths from a subset of the vertices in the graph using the
Brandes shortest paths methods from the BGL's betweenness centrality
implementation.  In the parallel phase of the algorithm a reduction is
performed to sum the values computed by each process for all vertices
in the graph.

Either weighted or unweighted betweenness centrality is calculated
depending on whether a ``WeightMap`` is passed.

-----------------------------------------------------------------------------

Copyright (C) 2009 The Trustees of Indiana University.

Authors: Nick Edmonds and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Process Group: process_group.html
.. _Buffer: http://www.boost.org/libs/graph/doc/Buffer.html
.. _Dijkstra shortest paths: http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html
.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Overview (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/overview.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===============================================
An Overview of the Parallel Boost Graph Library
===============================================

.. image:: ../graph.png
  :width: 206
  :height: 184
  :alt: An example graph
  :align: right

The Parallel Boost Graph Library (Parallel BGL) is a C++ library for
parallel, distributed computation on graphs. The Parallel BGL contains
distributed graph data structures, distributed graph algorithms,
abstractions over the communication medium (such as MPI), and
supporting data structures. A graph (also called a *network*) consists
of a set of *vertices* and a set of relationships between vertices,
called *edges*. The edges may be *undirected*, meaning that the
relationship between vertices is mutual, e.g., "X is related to Y", or
they can be *directed*, meaning that the relationship goes only one
way, e.g., "X is the child of Y". The following figure illustrates a
typical directed graph, where *a-i* are the vertices and the arrows
represent edges.

.. image:: ../distributed-graph.png
  :width: 229
  :height: 199
  :alt: A distributed graph
  :align: right

The Parallel BGL is primarily concerned with *distributed*
graphs. Distributed graphs are conceptually graphs, but their storage
is spread across multiple processors. The following figure
demonstrates a distributed version of the graph above, where the graph
has been divided among three processors (represented by the grey
rectangles). Edges in the graph may be either local (with both
endpoints stored on the same processor) or remote (the target of the
edge is stored on a different processor).

The Parallel BGL is a generic library. At its core are *generic*
distributed graph algorithms, which can operate on any distributed
graph data structure provided that data structure meets certain
requirements. For instance, the algorithm may need to enumerate the
set of vertices stored on the current processor, enumerate the set of
outgoing edges from a particular vertex, and determine on which
processor the target of each edge resides. The graph algorithms in the
Parallel BGL are also generic with respect to the *properties*
attached to edges and vertices in a graph; for instance, the weight of
each edge can be stored as part of the graph or allocated in a
completely separate data structure. 

The genericity available in the algorithms of the Parallel BGL allows
them to be applied to existing graph data structures. However, most
users will instead be writing new code that takes advantage of the
Parallel BGL. The Parallel BGL provides distributed graph data
structures that meet the requirements of the Parallel BGL
algorithms. The primary data structure is the `distributed adjacency
list`_, which allows storage and manipulation of a (distributed)
graph. The vertices in the graph are divided among the various
processors, and each of the edges outgoing from a vertex are stored on
the processor that "owns" (stores) that vertex. The following figure
illustrates the distributed adjacency list representation.

.. image:: ../dist-adjlist.png
  :width: 446
  :height: 154
  :alt: A distributed adjacency list
  :align: center

.. image:: ../dist-pmap.png
  :width: 271
  :height: 175
  :alt: A distributed property map
  :align: right

The `distributed adjacency list`_ distributes the structure of a graph
over multiple processors. While graph structure is in important part
of many graph problems, there are typically other properties attached
to the vertices and edges, such as edge weights or the position of
vertices within a grid. These properties are stored in *property
maps*, which associate a single piece of data with each edge or vertex
in a graph. Distributed property maps extend this notion to
distributed computing, where properties are stored on the same
processor as the vertex or edge. The following figure illustrates the
distribution of a property map storing colors (white, gray, black) for
each vertex. In addition to the storage for each vertex, the
processors store some "ghost cells" that cache values actually stored
on other processors, represented by the dashed boxes.

Tying together all of the distributed data structures of the Parallel
BGL are its process groups and distributed graph algorithms. Process
groups coordinate the interactions between multiple processes and
distributed data structures by abstracting the communication
mechanism. The algorithms are typically written using the SPMD model
(Single Program, Multiple Data) and interact with both the distributed
data structures and the process group itself. At various points in the
algorithm's execution, all processes execute a synchronization point,
which allows all of the distributed data structures to ensure an
appropriate degree of consistency across processes. The following
diagram illustrates the communication patterns within the the
execution of a distributed algorithm in the Parallel BGL. In
particular, the diagram illustrates the distributed data structures
used in a distributed breadth-first search, from the top-left and
proceeding clockwise:

   - a user-defined property map that tracks the distance from the
     source vertex to all other vertices,

   - an automatically-generated property map that tracks the "color"
     of vertices in the (distributed) graph, to determine which
     vertices have been seen before,

   - a distributed queue, which coordinates the breadth-first search
     and distributes new vertices to search, and

   - a distributed graph, on which the breadth-first search is
     operating.

.. image:: ../architecture.png
  :width: 485
  :height: 410
  :alt: Parallel Boost Graph Library architecture
  :align: center

----------------------------------------------------------------------------

Copyright (C) 2005 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. _Distributed adjacency list: distributed_adjacency_list.html
.. _Process groups:

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Page Rank (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/page_rank.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===============
|Logo| PageRank
===============

::
  
  namespace graph { 
    template<typename Graph, typename RankMap, typename Done>
    inline void
    page_rank(const Graph& g, RankMap rank_map, Done done, 
              typename property_traits<RankMap>::value_type damping = 0.85);

    template<typename Graph, typename RankMap>
    inline void
    page_rank(const Graph& g, RankMap rank_map);
  } 
  
The ``page_rank`` algorithm computes the ranking of vertices in a
graph, based on the connectivity of a directed graph [PBMW98]_. The
idea of PageRank is based on a random model of a Web surfer, who
starts a random web page and then either follows a link from that web
page (choosing from the links randomly) or jumps to a completely
different web page (not necessarily linked from the current
page). The PageRank of each page is the probability of the random web
surfer visiting that page.

.. contents::

Where Defined
~~~~~~~~~~~~~
<``boost/graph/distributed/page_rank.hpp``>

also accessible from

<``boost/graph/page_rank.hpp``>

Parameters
~~~~~~~~~~

IN: ``Graph& g``
  The graph type must be a model of `Distributed Vertex List Graph`_ and
  `Distributed Edge List Graph`_. The graph must be directed.

OUT: ``RankMap rank``
  Stores the rank of each vertex. The type ``RankMap`` must model the
  `Read/Write Property Map`_ concept and must be a `distributed
  property map`_. Its key type must be the vertex descriptor of the
  graph type and its value type must be a floating-point or rational
  type. 

IN: ``Done done``
  A function object that determines when the PageRank algorithm
  should complete. It will be passed two parameters, the rank map and
  a reference to the graph, and should return ``true`` when the
  algorithm should terminate.

  **Default**: ``graph::n_iterations(20)``

IN: ``typename property_traits<RankMap>::value_type damping``
  The damping factor is the probability that the Web surfer will
  select an outgoing link from the current page instead of jumping to
  a random page. 

  **Default**: 0.85

Complexity
~~~~~~~~~~
Each iteration of PageRank requires *O((V + E)/p)* time on *p*
processors and performs *O(V)* communication. The number of
iterations is dependent on the input to the algorithm.

Bibliography
------------

.. [PBMW98] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry
  Winograd. The PageRank Citation Ranking: Bringing Order to the
  Web. Technical report, Stanford Digital Library Technologies Project,
  November 1998.

-----------------------------------------------------------------------------

Copyright (C) 2005 The Trustees of Indiana University.

Authors: Douglas Gregor and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Distributed Vertex List Graph: DistributedVertexListGraph.html
.. _Distributed Edge List Graph: DistributedEdgeListGraph.html
.. _Distributed property map: distributed_property_map.html
.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
.. _Read/Write Property Map: http://www.boost.org/libs/property_map/ReadWritePropertyMap.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Process Group (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/process_group.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

==================================
|Logo| Parallel BGL Process Groups
==================================

.. contents::

Introduction
------------

Process groups are an abstraction of a set of communicating processes
that coordinate to solve the same problem. Process groups contain
facilities for identifying the processes within that group, sending
and receiving messages between the processes in that group, and
performing collective communications involving all processes in the
group simultaneously. 

Communication model
-------------------

Process groups are based on an extended version of the Bulk
Synchronous Parallel (BSP) model of computation. Parallel computations
in the BSP model are organized into *supersteps*, each of which
consists of a computation phase followed by a communication
phase. During the computation phase, all processes in the process
group work exclusively on local data, and there is no inter-process
communication. During the communication phase, all of the processes
exchange message with each other. Messages sent in the communication
phase of a superstep will be received in the next superstep.

The boundary between supersteps in the Parallel BGL corresponds to the
``synchronize`` operation. Whenever a process has completed its local
computation phase and sent all of the messages required for that
superstep, it invokes the ``synchronize`` operation on the process
group. Once all processes in the process group have entered
``synchronize``, they exchange messages and then continue with the
next superstep. 

The Parallel BGL loosens the BSP model significantly, to provide a
more natural programming model that also provides some performance
benefits over the strict BSP model. The primary extension is the
ability to receive messages sent within the same superstep
"asynchronously", either to free up message buffers or to respond to
an immediate request for information. For particularly unstructured
computations, the ability to send a message and get an immediate reply
can simplify many computations that would otherwise need to be split
into two separate supersteps. Additionally, the Parallel BGL augments
the BSP model with support for multiple distributed data structures,
each of which are provided with a different communication space but
whose messages will all be synchronized concurrently. 

Distributed data structures
~~~~~~~~~~~~~~~~~~~~~~~~~~~

A typical computation with the Parallel BGL involves several
distributed data structures working in concern. For example, a simple
breadth-first search involves the distributed graph data structure
containing the graph itself, a distributed queue that manages the
traversal through the graph, and a distributed property map that
tracks which vertices have already been visited as part of the
search. 

The Parallel BGL manages these distributed data structures by allowing
each of the data structures to attach themselves to the process group
itself. When a distributed data structure attaches to the process
group, it receives its own copy of the process group that allows the
distributed data structure to communicate without colliding with the
communications from other distributed data structures. When the
process group is synchronized, all of the distributed data structures
attached to that process group are automatically synchronized, so that
all of the distributed data structures in a computation remain
synchronized. 

A distributed data structure attaches itself to the process group by
creating a copy of the process group and passing an
``attach_distributed_object`` flag to the process group
constructor. So long as this copy of the process group persists, the
distributed data structure is attached the process group. For this
reason, most distributed data structures keep a copy of the process
group as member data, constructing the member with
``attach_distributed_object``, e.g.,

::

  template<typename ProcessGroup>
  struct distributed_data_structure 
  {
    explicit distributed_data_structure(const ProcessGroup& pg)
      : process_group(pg, boost::parallel::attach_distributed_object())
    { }

  private:
    ProcessGroup process_group;
  };


Asynchronous receives
~~~~~~~~~~~~~~~~~~~~~

Distributed data structures in the Parallel BGL can "asynchronously"
receive and process messages before the end of a BSP
superstep. Messages can be received any time that a process is inside
the process group operations, and the scheduling of message receives
is entirely managed by the process group. 

Distributed data structures receive messages through
"triggers". Triggers are function objects responsible for processing a
received message. Each trigger is registered with the ``trigger``
method of the process group using a specific message
tag (an integer) and the type of data that is expected to be
contained within that message. Whenever a message with that tag
becomes available, the progress group will call the trigger with the
source of the message, the message tag, the data contained in the
message, and the "context" of the message.

The majority of triggers have no return value, although it is common
that the triggers send messages back to the source process. In certain
cases where the trigger's purpose is to immediately reply with a
value, the trigger should be registered with the
``trigger_with_reply`` method and should return the value that will be
sent back to the caller. The ``trigger_with_reply`` facility is only
useful in conjunction with out-of-band messaging, discussed next.

Out-of-band messaging
~~~~~~~~~~~~~~~~~~~~~

The majority of messages sent by the Parallel BGL are sent through the
normal send operations, to be received in the next superstep or, in
some cases, received "early" by a trigger. These messages are not
time-sensitive, so they will be delivered whenever the process group
processes them. 

Some messages, however, require immediate responses. For example, if a
process needs to determine the current value associated with a vertex
owned by another process, the first process must send a request to the
second process and block while waiting for a response. For such
messages, the Parallel BGL's process groups provide an out-of-band
messaging mechanism. Out-of-band messages are transmitted immediately,
with a much higher priority than other messages. The sending of
out-of-band messages can be coupled with a receive operation that
waits until the remote process has received the message and sent its
reply. For example, in the following code the process sends a message
containing the string ``name`` to process ``owner`` with tag
``msg_get_descriptor_by_name`` via an out-of-band message. The
receiver of that message will immediately deliver the message via a
trigger, that returns the resulting value--a
``vertex_descriptor``--that will be passed back to the process that
initiated the communication. The full communication happens
immediately, within the current superstep.

::
 
  std::string name;
  vertex_descriptor descriptor;
  send_oob_with_reply(process_group, owner, msg_get_descriptor_by_name,
                      name, descriptor);

Reference
---------

The Parallel BGL process groups specify an interface that can be
implemented by various communication subsystems. In this reference
section, we use the placeholder type ``ProcessGroup`` to stand in for
the various process group implementations that exist. There is only
one implementation of the process group interface at this time:

  - `MPI BSP process group`_

::

  enum trigger_receive_context {
    trc_none,
    trc_in_synchronization,
    trc_early_receive,
    trc_out_of_band
  };
  
  class ProcessGroup 
  {
    // Process group constructors
    ProcessGroup();
    ProcessGroup(const ProcessGroup&, boost::parallel::attach_distributed_object);

    // Triggers
    template<typename Type, typename Handler>
      void trigger(int tag, const Handler& handler);

    template<typename Type, typename Handler>
      void trigger_with_reply(int tag, const Handler& handler);

    trigger_receive_context trigger_context() const;

    // Helper operations
    void poll();
    ProcessGroup base() const;
  };

  // Process query
  int process_id(const ProcessGroup&);
  int num_processes(const ProcessGroup&);

  // Message transmission
  template<typename T>
    void send(const ProcessGroup& pg, int dest, int tag, const T& value);

  template<typename T>
    void receive(const ProcessGroup& pg, int source, int tag, T& value);

  optional<std::pair > probe(const ProcessGroup& pg);

  // Synchronization
  void synchronize(const ProcessGroup& pg);

  // Out-of-band communication
  template<typename T>
    void send_oob(const ProcessGroup& pg, int dest, int tag, const T& value);

  template<typename T, typename U>
    void 
    send_oob_with_reply(const ProcessGroup& pg, int dest, int
                        tag, const T& send_value, U& receive_value);

  template<typename T>
    void receive_oob(const ProcessGroup& pg, int source, int tag, T& value);


Process group constructors
~~~~~~~~~~~~~~~~~~~~~~~~~~

::

    ProcessGroup();

Constructs a new process group with a different communication space
from any other process group.

-----------------------------------------------------------------------------

::

    ProcessGroup(const ProcessGroup& pg, boost::parallel::attach_distributed_object);

Attaches a new distributed data structure to the process group
``pg``. The resulting process group can be used for communication
within that new distributed data structure. When the newly-constructed
process group is eventually destroyed, the distributed data structure
is detached from the process group.

Triggers
~~~~~~~~

::

    template<typename Type, typename Handler>
      void trigger(int tag, const Handler& handler);

Registers a trigger with the given process group. The trigger will
watch for messages with the given ``tag``. When such a message is
available, it will be received into a value of type ``Type``, and the
function object ``handler`` will be invoked with four parameters: 

source
  The rank of the source process (an ``int``)

tag
  The tag used to send the message (also an ``int``)

data:
  The data transmitted with the message. The data will have the type
  specified when the trigger was registered.

context:
  The context in which the trigger is executed. This will be a value of
  type ``trigger_receive_context``, which stages whether the trigger
  is being executed during synchronization, asynchronously in response
  to an "early" receive (often to free up communication buffers), or
  in response to an "out-of-band" message.

Triggers can only be registered by process groups that result from
attaching a distributed data structure. A trigger can be invoked in
response to either a normal send operation or an out-of-band send
operation. There is also a `simple trigger interface`_ for defining
triggers in common cases.

-----------------------------------------------------------------------------

::

    template<typename Type, typename Handler>
      void trigger_with_reply(int tag, const Handler& handler);

Like the ``trigger`` method, registers a trigger with the given
process group. The trigger will watch for messages with the given
``tag``. When such a message is available, it will be received into a
value of type ``Type`` and ``handler`` will be invoked, just as with a
normal trigger. However, a trigger registered with
``trigger_with_reply`` must return a value, which will be immediately
sent back to the process that initiated the send resulting in this
trigger. Thus, ``trigger_with_reply`` should only be used for messages
that need immediate responses. These triggers can only be invoked via
the out-of-band sends that wait for the reply, via
``send_oob_with_reply``. There is also a `simple trigger interface`_
for defining triggers in common cases.

-----------------------------------------------------------------------------

::

    trigger_receive_context trigger_context() const;

Retrieves the current context of the process group with respect to the
invocation of triggers. When ``trc_none``, the process group is not
currently invoking any triggers. Otherwise, this value describes in
what context the currently executing trigger is being invoked.


Helper operations
~~~~~~~~~~~~~~~~~

::

  void poll();

Permits the process group to receive any incomining messages,
processing them via triggers. If you have a long-running computation
that does not invoke any of the process group's communication
routines, you should call ``poll`` occasionally to along incoming
messages to be processed. 

-----------------------------------------------------------------------------

::

    ProcessGroup base() const;

Retrieves the "base" process group for this process group, which is a
copy of the underlying process group that does not reference any
specific distributed data structure.

Process query
~~~~~~~~~~~~~

::

  int process_id(const ProcessGroup& pg);

Retrieves the ID (or "rank") of the calling process within the process
group. Process IDs are values in the range [0, ``num_processes(pg)``)
that uniquely identify the process. Process IDs can be used to
initiate communication with another process.

-----------------------------------------------------------------------------

::

  int num_processes(const ProcessGroup& pg);

Returns the number of processes within the process group.


Message transmission
~~~~~~~~~~~~~~~~~~~~

::

  template<typename T>
    void send(const ProcessGroup& pg, int dest, int tag, const T& value);

Sends a message with the given ``tag`` and carrying the given
``value`` to the process with ID ``dest`` in the given process
group. All message sends are non-blocking, meaning that this send
operation will not block while waiting for the communication to
complete. There is no guarantee when the message will be received,
except that it will become available to the destination process by the
end of the superstep, in the collective call to ``synchronize``.

Any type of value can be transmitted via ``send``, so long as it
provides the appropriate functionality to be serialized with the
Boost.Serialization library.

-----------------------------------------------------------------------------

::

  template<typename T>
    void receive(const ProcessGroup& pg, int source, int tag, T& value);

Receives a message with the given ``tag`` sent from the process
``source``, updating ``value`` with the payload of the message. This
receive operation can only receive messages sent within the previous
superstep via the ``send`` operation. If no such message is available
at the time ``receive`` is called, the program is ill-formed.

-----------------------------------------------------------------------------

::

  optional<std::pair<int, int> > probe(const ProcessGroup& pg);

Determines whether a message is available. The probe operation checks
for any messages that were sent in the previous superstep but have not
yet been received. If such a message exists, ``probe`` returns a
(source, tag) pair describing the message. Otherwise, ``probe`` will
return an empty ``boost::optional``. 

A typical use of ``probe`` is to continually probe for messages at the
beginning of the superstep, receiving and processing those messages
until no messages remain.


Synchronization
~~~~~~~~~~~~~~~

::

  void synchronize(const ProcessGroup& pg);

The ``synchronize`` function is a collective operation that must be
invoked by all of the processes within the process group. A call to
``synchronize`` marks the end of a superstep in the parallel
computation. All messages sent before the end of the superstep will be
received into message buffers, and can be processed by the program in
the next superstep. None of the processes will leave the
``synchronize`` function until all of the processes have entered the
function and exchanged messages, so that all processes are always on
the same superstep.

Out-of-band communication
~~~~~~~~~~~~~~~~~~~~~~~~~

::

  template<typename T>
    void send_oob(const ProcessGroup& pg, int dest, int tag, const T& value);

Sends and out-of-band message. This out-of-band send operation acts
like the normal ``send`` operation, except that out-of-band messages
are delivered immediately through a high-priority channel. 

-----------------------------------------------------------------------------

::

  template<typename T, typename U>
    void 
    send_oob_with_reply(const ProcessGroup& pg, int dest, int
                        tag, const T& send_value, U& receive_value);

Sends an out-of-band message and waits for a reply. The
``send_oob_with_reply`` function can only be invoked with message tags
that correspond to triggers registered with
``trigger_with_reply``. This operation will send the message
immediately (through the high-priority, out-of-band channel), then
wait until the remote process sends a reply. The data from the reply
is stored into ``receive_value``. 

-----------------------------------------------------------------------------

::

  template<typename T>
    void receive_oob(const ProcessGroup& pg, int source, int tag, T& value);

Receives an out-of-band message with the given ``source`` and
``tag``. As with the normal ``receive`` operation, it is an error to
call ``receive_oob`` if no message matching the source and tag is
available. This routine is used only rarely; for most circumstances,
use ``send_oob_with_reply`` to perform an immediate send with a
reply. 

-----------------------------------------------------------------------------

Copyright (C) 2007 Douglas Gregor

Copyright (C) 2007 Matthias Troyer

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _MPI BSP process group: mpi_bsp_process_group.html
.. _Simple trigger interface: simple_trigger.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Rmat Generator (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/rmat_generator.rst`)

.. Copyright (C) 2004-2009 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===================================
|Logo| R-MAT generator
===================================

::
 
  template<typename RandomGenerator, typename Graph>
  class rmat_iterator
  {
  public:
    typedef std::input_iterator_tag iterator_category;
    typedef std::pair<vertices_size_type, vertices_size_type> value_type;
    typedef const value_type& reference;
    typedef const value_type* pointer;
    typedef void difference_type;

    rmat_iterator();
    rmat_iterator(RandomGenerator& gen, vertices_size_type n, 
                  edges_size_type m, double a, double b, double c, 
                  double d, bool permute_vertices = true);
    // Iterator operations
    reference operator*() const;
    pointer operator->() const;
    rmat_iterator& operator++();
    rmat_iterator operator++(int);
    bool operator==(const rmat_iterator& other) const;
    bool operator!=(const rmat_iterator& other) const;
 };

This class template implements a generator for R-MAT graphs [CZF04]_,
suitable for initializing an adjacency_list or other graph structure
with iterator-based initialization. An R-MAT graph has a scale-free
distribution w.r.t. vertex degree and is implemented using
Recursive-MATrix partitioning.

Where Defined
-------------
<``boost/graph/rmat_graph_generator.hpp``>

Constructors
------------

::

  rmat_iterator();

Constructs a past-the-end iterator.

::

  rmat_iterator(RandomGenerator& gen, vertices_size_type n, 
                edges_size_type m, double a, double b, double c, 
                double d, bool permute_vertices = true);

Constructs an R-MAT generator iterator that creates a graph with ``n``
vertices and ``m`` edges.  ``a``, ``b``, ``c``, and ``d`` represent
the probability that a generated edge is placed of each of the 4
quadrants of the partitioned adjacency matrix.  Probabilities are
drawn from the random number generator gen.  Vertex indices are
permuted to eliminate locality when ``permute_vertices`` is true.

Example
-------

::

  #include 
  #include 
  #include 

  typedef boost::adjacency_list<> Graph;
  typedef boost::rmat_iterator RMATGen;

  int main()
  {
    boost::minstd_rand gen;
    // Create graph with 100 nodes and 400 edges 
    Graph g(RMATGen(gen, 100, 400, 0.57, 0.19, 0.19, 0.05), RMATGen(), 100);
    return 0;
  }


Bibliography
------------

.. [CZF04] D Chakrabarti, Y Zhan, and C Faloutsos.  R-MAT: A Recursive
  Model for Graph Mining. In Proceedings of 4th International Conference
  on Data Mining, pages 442--446, 2004.

-----------------------------------------------------------------------------

Copyright (C) 2009 The Trustees of Indiana University.

Authors: Nick Edmonds and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Scalable Rmat Generator (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/scalable_rmat_generator.rst`)

.. Copyright (C) 2004-2009 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===================================
|Logo| Scalable R-MAT generator
===================================

::
 
  template<typename ProcessGroup, typename Distribution, 
           typename RandomGenerator, typename Graph>
  class scalable_rmat_iterator
  {
  public:
    typedef std::input_iterator_tag iterator_category;
    typedef std::pair<vertices_size_type, vertices_size_type> value_type;
    typedef const value_type& reference;
    typedef const value_type* pointer;
    typedef void difference_type;

    scalable_rmat_iterator();
    scalable_rmat_iterator(ProcessGroup pg, Distribution distrib,
                           RandomGenerator& gen, vertices_size_type n, 
                           edges_size_type m, double a, double b, double c, 
                           double d, bool permute_vertices = true);

    // Iterator operations
    reference operator*() const;
    pointer operator->() const;
    scalable_rmat_iterator& operator++();
    scalable_rmat_iterator operator++(int);
    bool operator==(const scalable_rmat_iterator& other) const;
    bool operator!=(const scalable_rmat_iterator& other) const;
 };

This class template implements a generator for R-MAT graphs [CZF04]_,
suitable for initializing an adjacency_list or other graph structure
with iterator-based initialization. An R-MAT graph has a scale-free
distribution w.r.t. vertex degree and is implemented using
Recursive-MATrix partitioning.

Where Defined
-------------
<``boost/graph/rmat_graph_generator.hpp``>

Constructors
------------

::

  scalable_rmat_iterator();

Constructs a past-the-end iterator.

::

  scalable_rmat_iterator(ProcessGroup pg, Distribution distrib,
                         RandomGenerator& gen, vertices_size_type n, 
                         edges_size_type m, double a, double b, double c, 
                         double d, bool permute_vertices = true);

Constructs an R-MAT generator iterator that creates a graph with ``n``
vertices and ``m`` edges.  Inside the ``scalable_rmat_iterator``
processes communicate using ``pg`` to generate their local edges as
defined by ``distrib``.  ``a``, ``b``, ``c``, and ``d`` represent the
probability that a generated edge is placed of each of the 4 quadrants
of the partitioned adjacency matrix.  Probabilities are drawn from the
random number generator ``gen``.  Vertex indices are permuted to
eliminate locality when ``permute_vertices`` is true.

Example
-------

::

  #include 
  #include 
  #include 
  #include 

  using boost::graph::distributed::mpi_process_group;

  typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
                                      distributedS<mpi_process_group> > Graph;
  typedef boost::scalable_rmat_iterator RMATGen;

  int main()
  {
    boost::minstd_rand gen;
    mpi_process_group pg;

    int N = 100;

    boost::parallel::variant_distribution distrib 
      = boost::parallel::block(pg, N);

    // Create graph with 100 nodes and 400 edges 
    Graph g(RMATGen(pg, distrib, gen, N, 400, 0.57, 0.19, 0.19, 0.05), 
            RMATGen(), N, pg, distrib);
    return 0;
  }

Bibliography
------------

.. [CZF04] D Chakrabarti, Y Zhan, and C Faloutsos.  R-MAT: A Recursive
  Model for Graph Mining. In Proceedings of 4th International Conference
  on Data Mining, pages 442--446, 2004.

-----------------------------------------------------------------------------

Copyright (C) 2009 The Trustees of Indiana University.

Authors: Nick Edmonds, Brian Barrett, and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Sequential connected components: http://www.boost.org/libs/graph/doc/connected_components.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Simple Trigger (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/simple_trigger.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

============================
|Logo| Simple Triggers
============================

.. contents::

Introduction
------------

Triggers in the `process group`_ interface are used to asynchronously
receive and process messages destined for distributed data
structures. The trigger interface is relatively versatile, permitting
one to attach any function object to handle requests. The
``simple_trigger`` function simplifies a common case for triggers:
attaching a trigger that invokes a specific member function of the
distributed data structure.

Where Defined
-------------

Header ````

Reference
---------

  ::

    template<typename ProcessGroup, typename Class, typename T>
      void 
      simple_trigger(ProcessGroup& pg, int tag, Class* self, 
                     void (Class::*pmf)(int source, int tag, const T& data, 
                                        trigger_receive_context context))

    template<typename ProcessGroup, typename Class, typename T, typename Result>
      void 
      simple_trigger(ProcessGroup& pg, int tag, Class* self, 
                     Result (Class::*pmf)(int source, int tag, const T& data, 
                                          trigger_receive_context context))

The ``simple_trigger`` function registers a trigger that invokes the
given member function (``pmf``) on the object ``self`` whenever a
message is received. If the member function has a return value, then
the trigger has a reply, and can only be used via out-of-band sends
that expect a reply. Otherwise, the member function returns ``void``,
and the function is registered as a normal trigger.


-----------------------------------------------------------------------------

Copyright (C) 2007 Douglas Gregor

Copyright (C) 2007 Matthias Troyer

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _process group: process_group.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Sorted Rmat Generator (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/sorted_rmat_generator.rst`)

.. Copyright (C) 2004-2009 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===================================
|Logo| Sorted R-MAT generator
===================================

::
 
  template<typename RandomGenerator, typename Graph,
           typename EdgePredicate = keep_all_edges>
  class sorted_rmat_iterator
  {
  public:
    typedef std::input_iterator_tag iterator_category;
    typedef std::pair<vertices_size_type, vertices_size_type> value_type;
    typedef const value_type& reference;
    typedef const value_type* pointer;
    typedef void difference_type;

    sorted_rmat_iterator();
    sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n, 
                         edges_size_type m, double a, double b, double c, 
                         double d, bool permute_vertices = true);
    // Iterator operations
    reference operator*() const;
    pointer operator->() const;
    sorted_rmat_iterator& operator++();
    sorted_rmat_iterator operator++(int);
    bool operator==(const sorted_rmat_iterator& other) const;
    bool operator!=(const sorted_rmat_iterator& other) const;
 };

This class template implements a generator for R-MAT graphs [CZF04]_,
suitable for initializing an adjacency_list or other graph structure
with iterator-based initialization. An R-MAT graph has a scale-free
distribution w.r.t. vertex degree and is implemented using
Recursive-MATrix partitioning.  The output of this generator is sorted
for use with `compressed sparse row graph`_.

Where Defined
-------------
<``boost/graph/rmat_graph_generator.hpp``>

Constructors
------------

::

  sorted_rmat_iterator();

Constructs a past-the-end iterator.

::


  sorted_rmat_iterator(RandomGenerator& gen, vertices_size_type n, 
                       edges_size_type m, double a, double b, double c, 
                       double d, bool permute_vertices = true,
                       EdgePredicate ep = keep_all_edges());

Constructs an R-MAT generator iterator that creates a graph with ``n``
vertices and ``m`` edges.  ``a``, ``b``, ``c``, and ``d`` represent
the probability that a generated edge is placed of each of the 4
quadrants of the partitioned adjacency matrix.  Probabilities are
drawn from the random number generator ``gen``.  Vertex indices are
permuted to eliminate locality when ``permute_vertices`` is true.
``ep`` allows the user to specify which edges are retained, this is
useful in the case where the user wishes to refrain from storing
remote edges locally during generation to reduce memory consumption.

Example
-------

::

  #include 
  #include 
  #include 

  typedef boost::compressed_sparse_row_graph<> Graph;
  typedef boost::sorted_rmat_iterator 
    RMATGen;

  int main()
  {
    boost::minstd_rand gen;
    // Create graph with 100 nodes and 400 edges 
    Graph g(RMATGen(gen, 100, 400, 0.57, 0.19, 0.19, 0.05), 
            RMATGen(), 100);
    return 0;
  }

Bibliography
------------

.. [CZF04] D Chakrabarti, Y Zhan, and C Faloutsos.  R-MAT: A Recursive
  Model for Graph Mining. In Proceedings of 4th International Conference
  on Data Mining, pages 442--446, 2004.

-----------------------------------------------------------------------------

Copyright (C) 2009 The Trustees of Indiana University.

Authors: Nick Edmonds and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _compressed sparse row graph: http://www.boost.org/libs/graph/doc/compressed_sparse_row.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Sorted Unique Rmat Generator (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/sorted_unique_rmat_generator.rst`)

.. Copyright (C) 2004-2009 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

====================================
|Logo| Sorted unique R-MAT generator
====================================

::
 
  template<typename RandomGenerator, typename Graph,
           typename EdgePredicate = keep_all_edges>
  class sorted_unique_rmat_iterator
  {
  public:
    typedef std::input_iterator_tag iterator_category;
    typedef std::pair<vertices_size_type, vertices_size_type> value_type;
    typedef const value_type& reference;
    typedef const value_type* pointer;
    typedef void difference_type;

    sorted_unique_rmat_iterator();
    sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n, 
                                edges_size_type m, double a, double b, double c, 
                                double d, bool bidirectional = true,
                                bool permute_vertices = true,
                                EdgePredicate ep = keep_all_edges());
    // Iterator operations
    reference operator*() const;
    pointer operator->() const;
    sorted_unique_rmat_iterator& operator++();
    sorted_unique_rmat_iterator operator++(int);
    bool operator==(const sorted_unique_rmat_iterator& other) const;
    bool operator!=(const sorted_unique_rmat_iterator& other) const;
 };

This class template implements a generator for R-MAT graphs [CZF04]_,
suitable for initializing an adjacency_list or other graph structure
with iterator-based initialization. An R-MAT graph has a scale-free
distribution w.r.t. vertex degree and is implemented using
Recursive-MATrix partitioning.  The output of this generator is sorted
for use with a `compressed sparse row graph`_. The edge list produced by
this iterator is guaranteed not to contain parallel edges.

Where Defined
-------------
<``boost/graph/rmat_graph_generator.hpp``>

Constructors
------------

::

  sorted_unique_rmat_iterator();

Constructs a past-the-end iterator.

::

  sorted_unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n, 
                              edges_size_type m, double a, double b, double c, 
                              double d, bool bidirectional = false, 
                              bool permute_vertices = true,
                              EdgePredicate ep = keep_all_edges());

Constructs an R-MAT generator iterator that creates a graph with ``n``
vertices and ``m`` edges.  ``a``, ``b``, ``c``, and ``d`` represent
the probability that a generated edge is placed of each of the 4
quadrants of the partitioned adjacency matrix.  Probabilities are
drawn from the random number generator ``gen``.  Vertex indices are
permuted to eliminate locality when ``permute_vertices`` is true.
When ``bidirectional`` is ``true`` for every edge s-t, the
corresponding anti-edge t-s is added as well, these anti-edges are not
counted towards ``m``. ``ep`` allows the user to specify which edges
are retained, this is useful in the case where the user wishes to
refrain from storing remote edges locally during generation to reduce
memory consumption.

Example
-------

::

  #include 
  #include 
  #include 
  #include 

  using boost::graph::distributed::mpi_process_group;

  typedef compressed_sparse_row_graph<directedS, no_property, no_property, no_property,
                                      distributedS<mpi_process_group> > Graph;
  typedef keep_local_edges,
                           mpi_process_group::process_id_type> EdgeFilter; 
  typedef boost::sorted_unique_rmat_iterator RMATGen;

  int main()
  {
    boost::minstd_rand gen;
    mpi_process_group pg;

    int N = 100;

    boost::parallel::variant_distribution distrib 
      = boost::parallel::block(pg, N);

    mpi_process_group::process_id_type id = process_id(pg);

    // Create graph with 100 nodes and 400 edges 
    Graph g(RMATGen(gen, N, 400, 0.57, 0.19, 0.19, 0.05, true, 
                    true, EdgeFilter(distrib, id)), 
            RMATGen(), N, pg, distrib);
    return 0;
  }


Bibliography
------------

.. [CZF04] D Chakrabarti, Y Zhan, and C Faloutsos.  R-MAT: A Recursive
  Model for Graph Mining. In Proceedings of 4th International Conference
  on Data Mining, pages 442--446, 2004.

-----------------------------------------------------------------------------

Copyright (C) 2009 The Trustees of Indiana University.

Authors: Nick Edmonds and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _compressed sparse row graph: http://www.boost.org/libs/graph/doc/compressed_sparse_row.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Ssca Generator (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/ssca_generator.rst`)

.. Copyright (C) 2004-2009 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===========================
|Logo| SSCA Generator
===========================

Generator from the Scalable Synthetic Compact Application #2 Graph Analysis benchmark.


-----------------------------------------------------------------------------

Copyright (C) 2009 The Trustees of Indiana University.

Authors: Nick Edmonds and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc St Connected (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/st_connected.rst`)

.. Copyright (C) 2004-2009 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===========================
|Logo| s-t Connectivity
===========================

::

  namespace graph { namespace distributed {
    template<typename DistributedGraph, typename ColorMap>
    inline bool 
    st_connected(const DistributedGraph& g, 
                 typename graph_traits<DistributedGraph>::vertex_descriptor s,
                 typename graph_traits<DistributedGraph>::vertex_descriptor t,
                 ColorMap color)

    template<typename DistributedGraph>
    inline bool 
    st_connected(const DistributedGraph& g, 
                 typename graph_traits<DistributedGraph>::vertex_descriptor s,
                 typename graph_traits<DistributedGraph>::vertex_descriptor t)

    template<typename DistributedGraph, typename ColorMap, typename OwnerMap>
    bool 
    st_connected(const DistributedGraph& g, 
                 typename graph_traits<DistributedGraph>::vertex_descriptor s,
                 typename graph_traits<DistributedGraph>::vertex_descriptor t,
                 ColorMap color, OwnerMap owner)
  } }

The ``st_connected()`` function determines whether there exists a path
from ``s`` to ``t`` in a graph ``g``.  If a path exists the function
returns ``true``, otherwise it returns ``false``.

This algorithm is currently *level-synchronized*, meaning that all
vertices in a given level of the search tree will be processed
(potentially in parallel) before any vertices from a successive level
in the tree are processed.  This is not necessary for the correctness
of the algorithm but rather is an implementation detail.  This
algorithm could be rewritten fully-asynchronously using triggers which
would remove the level-synchronized behavior.

.. contents::

Where Defined
-------------
<``boost/graph/distributed/st_connected.hpp``>

Parameters
----------

IN:  ``const DistributedGraph& g``
  The graph type must be a model of `Distributed Graph`_.  The graph
  type must also model the `Incidence Graph`_.

IN:  ``vertex_descriptor s``

IN:  ``vertex_descriptor t``

UTIL/OUT: ``color_map(ColorMap color)``
  The color map must be a `Distributed Property Map`_ with the same
  process group as the graph ``g`` whose colors must monotonically
  darken (white -> gray/green -> black). The default value is a
  distributed ``two_bit_color_map``.

IN:  ``OwnerMap owner``
  The owner map must map from vertices to the process that owns them
  as described in the `GlobalDescriptor`_ concept.

OUT:  ``bool``
  The algorithm returns ``true`` if a path from ``s`` to ``t`` is
  found, and false otherwise.

Complexity
----------

This algorithm performs *O(V + E)* work in *d/2 + 1* BSP supersteps,
where *d* is the shortest distance from ``s`` to ``t``. Over all
supersteps, *O(E)* messages of constant size will be transmitted.

Algorithm Description
---------------------

The algorithm consists of two simultaneous breadth-first traversals
from ``s`` and ``t`` respectively.  The algorithm utilizes a single
queue for both traversals with the traversal from ``s`` being denoted
by a ``gray`` entry in the color map and the traversal from ``t``
being denoted by a ``green`` entry.  The traversal method is similar
to breadth-first search except that no visitor event points are
called.  When any process detects a collision in the two traversals
(by attempting to set a ``gray`` vertex to ``green`` or vice-versa),
it signals all processes to terminate on the next superstep and all
processes return ``true``.  If the queues on all processes are empty
and no collision is detected then all processes terminate and return
``false``.

-----------------------------------------------------------------------------

Copyright (C) 2009 The Trustees of Indiana University.

Authors: Nick Edmonds and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Distributed Graph: DistributedGraph.html
.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html
.. _Distributed Property Map: distributed_property_map.html
.. _GlobalDescriptor: GlobalDescriptor.html

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Strong Components (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/strong_components.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

===========================
|Logo| Connected Components
===========================

::
  
  template<typename Graph, typename ComponentMap>
  inline typename property_traits<ComponentMap>::value_type
  strong_components( const Graph& g, ComponentMap c);

  namespace graph {
    template<typename Graph, typename VertexComponentMap>
    void
    fleischer_hendrickson_pinar_strong_components(const Graph& g, VertexComponentMap r);

    template<typename Graph, typename ReverseGraph, 
             typename ComponentMap, typename IsoMapFR, typename IsoMapRF>
    inline typename property_traits<ComponentMap>::value_type
    fleischer_hendrickson_pinar_strong_components(const Graph& g, 
                                                  ComponentMap c,
                                                  const ReverseGraph& gr, 
                                                  IsoMapFR fr, IsoMapRF rf);
  }
    
The ``strong_components()`` function computes the strongly connected
components of a directed graph.  The distributed strong components
algorithm uses the `sequential strong components`_ algorithm to
identify components local to a processor.  The distributed portion of
the algorithm is built on the `distributed breadth first search`_
algorithm and is based on the work of Fleischer, Hendrickson, and
Pinar [FHP00]_. The interface is a superset of the interface to the
BGL `sequential strong components`_ algorithm. The number of
strongly-connected components in the graph is returned to all
processes. 

The distributed strong components algorithm works on both ``directed``
and ``bidirectional`` graphs.  In the bidirectional case, a reverse
graph adapter is used to produce the required reverse graph.  In 
the directed case, a separate graph is constructed in which all the
edges are reversed.

.. contents::

Where Defined
-------------
<``boost/graph/distributed/strong_components.hpp``>

also accessible from

<``boost/graph/strong_components.hpp``>

Parameters
----------

IN:  ``const Graph& g``
  The graph type must be a model of `Distributed Graph`_.  The graph
  type must also model the `Incidence Graph`_ and be directed.

OUT:  ``ComponentMap c``
  The algorithm computes how many strongly connected components are in the
  graph, and assigns each component an integer label.  The algorithm
  then records to which component each vertex in the graph belongs by
  recording the component number in the component property map.  The
  ``ComponentMap`` type must be a `Distributed Property Map`_.  The
  value type must be the ``vertices_size_type`` of the graph.  The key
  type must be the graph's vertex descriptor type.

UTIL:  ``VertexComponentMap r``
  The algorithm computes a mapping from each vertex to the
  representative of the strong component, stored in this property map.
  The ``VertexComponentMap`` type must be a `Distributed Property Map`_.
  The value and key types must be the vertex descriptor of the graph.

IN: ``const ReverseGraph& gr``
  The reverse (or transpose) graph of ``g``, such that for each
  directed edge *(u, v)* in ``g`` there exists a directed edge
  *(fr(v), fr(u))* in ``gr`` and for each edge *(v', u')* in *gr*
  there exists an edge *(rf(u'), rf(v'))* in ``g``. The functions
  *fr* and *rf* map from vertices in the graph to the reverse graph
  and vice-verse, and are represented as property map arguments. The
  concept requirements on this graph type are equivalent to those on
  the ``Graph`` type, but the types need not be the same.

  **Default**: Either a ``reverse_graph`` adaptor over the original
  graph (if the graph type is bidirectional, i.e., models the
  `Bidirectional Graph`_ concept) or a `distributed adjacency list`_
  constructed from the input graph.

IN: ``IsoMapFR fr``
  A property map that maps from vertices in the input graph ``g`` to
  vertices in the reversed graph ``gr``. The type ``IsoMapFR`` must
  model the `Readable Property Map`_ concept and have the graph's
  vertex descriptor as its key type and the reverse graph's vertex
  descriptor as its value type.

  **Default**: An identity property map (if the graph type is
  bidirectional) or a distributed ``iterator_property_map`` (if the
  graph type is directed).

IN: ``IsoMapRF rf``
  A property map that maps from vertices in the reversed graph ``gr``
  to vertices in the input graph ``g``. The type ``IsoMapRF`` must
  model the `Readable Property Map`_ concept and have the reverse
  graph's vertex descriptor as its key type and the graph's vertex
  descriptor as its value type.

  **Default**: An identity property map (if the graph type is
  bidirectional) or a distributed ``iterator_property_map`` (if the
  graph type is directed).

Complexity
----------

The local phase of the algorithm is *O(V + E)*.  The parallel phase of
the algorithm requires at most *O(V)* supersteps each containing two 
breadth first searches which are *O(V + E)* each. 


Algorithm Description
---------------------

Prior to executing the sequential phase of the algorithm, each process
identifies any completely local strong components which it labels and
removes from the vertex set considered in the parallel phase of the
algorithm.

The parallel phase of the distributed strong components algorithm
consists of series of supersteps.  Each superstep starts with one
or more vertex sets which are guaranteed to completely contain
any remaining strong components.  A `distributed breadth first search`_
is performed starting from the first vertex in each vertex set.
All of these breadth first searches are performed in parallel by having
each processor call ``breadth_first_search()`` with a different starting
vertex, and if necessary inserting additional vertices into the 
``distributed queue`` used for breadth first search before invoking
the algorithm.  A second `distributed breadth first search`_ is
performed on the reverse graph in the same fashion.  For each initial
vertex set, the successor set (the vertices reached in the forward 
breadth first search), and the predecessor set (the vertices reached
in the backward breadth first search) is computed.  The intersection
of the predecessor and successor sets form a strongly connected 
component which is labeled as such.  The remaining vertices in the 
initial vertex set are partitioned into three subsets each guaranteed
to completely contain any remaining strong components.  These three sets
are the vertices in the predecessor set not contained in the identified
strongly connected component, the vertices in the successor set not 
in the strongly connected component, and the remaing vertices in the 
initial vertex set not in the predecessor or successor sets.  Once
new vertex sets are identified, the algorithm begins a new superstep.
The algorithm halts when no vertices remain.

To boost performance in sparse graphs when identifying small components,
when less than a given portion of the initial number of vertices 
remain in active vertex sets, a filtered graph adapter is used
to limit the graph seen by the breadth first search algorithm to the
active vertices.

Bibliography
------------

.. [FHP00] Lisa Fleischer, Bruce Hendrickson, and Ali Pinar. On
  Identifying Strongly Connected Components in Parallel. In Parallel and
  Distributed Processing (IPDPS), volume 1800 of Lecture Notes in
  Computer Science, pages 505--511, 2000. Springer.

-----------------------------------------------------------------------------

Copyright (C) 2004, 2005 The Trustees of Indiana University.

Authors: Nick Edmonds, Douglas Gregor, and Andrew Lumsdaine

.. |Logo| image:: pbgl-logo.png
            :align: middle
            :alt: Parallel BGL
            :target: http://www.osl.iu.edu/research/pbgl

.. _Sequential strong components: http://www.boost.org/libs/graph/doc/strong_components.html
.. _Distributed breadth first search: breadth_first_search.html
.. _Distributed Graph: DistributedGraph.html
.. _Distributed Property Map: distributed_property_map.html
.. _Incidence Graph: http://www.boost.org/libs/graph/doc/IncidenceGraph.html
.. _Bidirectional Graph: http://www.boost.org/libs/graph/doc/BidirectionalGraph.html
.. _distributed adjacency list: distributed_adjacency_list.html
.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html
..

---

### Extra Boost Boost 1 77 0 Libs Graph Parallel Doc Tsin Depth First Visit (`extra/boost/boost_1_77_0/libs/graph_parallel/doc/tsin_depth_first_visit.rst`)

.. Copyright (C) 2004-2008 The Trustees of Indiana University.
   Use, modification and distribution is subject to the Boost Software
   License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

========================
|Logo| Depth-First Visit
========================

::

  template<typename DistributedGraph, typename DFSVisitor>
  void
  depth_first_visit(const DistributedGraph& g,
                    typename graph_traits<DistributedGraph>::vertex_descriptor s,
                    DFSVisitor vis);

  namespace graph {
    template<typename DistributedGraph, typename DFSVisitor, 
           typename VertexIndexMap>
    void
    tsin_depth_first_visit(const DistributedGraph& g,
                           typename graph_traits<DistributedGraph>::vertex_descriptor s,
                           DFSVisitor vis);

    template<typename DistributedGraph, typename DFSVisitor, 
             typename VertexIndexMap>
    void
    tsin_depth_first_visit(const DistributedGraph& g,
                           typename graph_traits<DistributedGraph>::vertex_descriptor s,
                           DFSVisitor vis, VertexIndexMap index_map);

    template<typename DistributedGraph, typename ColorMap, typename ParentMap,
             typename ExploreMap, typename NextOutEdgeMap, typename DFSVisitor>
    void
    tsin_depth_first_visit(const DistributedGraph& g,
                           typename graph_traits<DistributedGraph>::vertex_descriptor s,
                           DFSVisitor vis, ColorMap color, ParentMap parent, ExploreMap explore, 
                           NextOutEdgeMap next_out_edge);
  } 

The ``depth_first_visit()`` function performs a distributed
depth-first traversal of an undirected graph using Tsin's corrections
[Tsin02]_ to Cidon's algorithm [Cidon88]_. The distributed DFS is
syntactically similar to its `sequential counterpart`_, which provides
additional background and discussion. Differences in semantics are
highlighted here, and we refer the reader to the documentation of the
`sequential depth-first search`_ for the remainder of the
details. Visitors passed to depth-first search need to account for the
distribution of vertices across processes, because events will be
triggered on certain processes but not others. See the section
`Visitor Event Points`_ for details.

Where Defined
-------------
<``boost/graph/distributed/depth_first_search.hpp``>

also available in 

<``boost/graph/depth_first_search.hpp``>

Parameters
----------

IN: ``const Graph& g``
  The graph type must be a model of `Distributed Graph`_. The graph
  must be undirected.

IN: ``vertex_descriptor s``
  The start vertex must be the same in every process.

IN: ``DFSVisitor vis``
  The visitor must be a distributed DFS visitor. The suble differences
  between sequential and distributed DFS visitors are discussed in the
  section `Visitor Event Points`_.

IN: ``VertexIndexMap map``
  A model of `Readable Property Map`_ whose key type is the vertex
  descriptor type of the graph ``g`` and whose value type is an
  integral type. The property map should map from vertices to their
  (local) indices in the range *[0, num_vertices(g))*.

  **Default**: ``get(vertex_index, g)``

UTIL/OUT: ``ColorMap color``
  The color map must be a `Distributed Property Map`_ with the same
  process group as the graph ``g`` whose colors must monotonically
  darken (white -> gray -> black). 

  **Default**: A distributed ``iterator_property_map`` created from a
  ``std::vector`` of ``default_color_type``.

UTIL/OUT: ``ParentMap parent``
  The parent map must be a `Distributed Property Map`_ with the same
  process group as the graph ``g`` whose key and values types are the
  same as the vertex descriptor type of the graph ``g``. This
  property map holds the parent of each vertex in the depth-first
  search tree.

  **Default**: A distributed ``iterator_property_map`` created from a
  ``std::vector`` of the vertex descriptor type of the graph.

UTIL: ``ExploreMap explore``
  The explore map must be a `Distributed Property Map`_ with the same
  process group as the graph ``g`` whose key and values types are the
  same as the vertex descriptor type of the graph ``g``. 

  **Default**: A distributed ``iterator_property_map`` created from a
  ``std::vector`` of the vertex descriptor type of the graph.

UTIL: ``NextOutEdgeMap next_out_edge``
  The next out-edge map must be a `Distributed Property Map`_ with the
  same process group as the graph ``g`` whose key type is the vertex
  descriptor of the graph ``g`` and whose value type is the
  ``out_edge_iterator`` type of the graph. It is used internally to
  keep track of the next edge that should be traversed from each
  vertex.

  **Default**: A distributed ``iterator_property_map`` created from a
  ``std::vector`` of the ``out_edge_iterator`` type of the graph.

Complexity
----------
Depth-first search is inherently sequential, so parallel speedup is
very poor. Regardless of the number of processors, the algorithm will
not be faster than *O(V)*; see [Tsin02]_ for more details.

Visitor Event Points
--------------------
The `DFS Visitor`_ concept defines 8 event points that will be
triggered by the `sequential depth-first search`_. The distributed
DFS retains these event points, but the sequence of events
triggered and the process in which each event occurs will change
depending on the distribution of the graph. 

``initialize_vertex(s, g)``
  This will be invoked by every process for each local vertex.


``discover_vertex(u, g)``
  This will be invoked each time a process discovers a new vertex
  ``u``. 


``examine_vertex(u, g)``
  This will be invoked by the process owning the vertex ``u``. 

``examine_edge(e, g)``
  This will be invoked by the process owning the source vertex of
  ``e``. 


``tree_edge(e, g)``
  Similar to ``examine_edge``, this will be invoked by the process
  owning the source vertex and may be invoked only once. 


``back_edge(e, g)``
  Some edges that would be forward or cross edges in the sequential
  DFS may be detected as back edges by the distributed DFS, so extra
  ``back_edge`` events may be received.

``forward_or_cross_edge(e, g)``
  Some edges that would be forward or cross edges in the sequential
  DFS may be detected as back edges by the distributed DFS, so fewer
  ``forward_or_cross_edge`` events may be received in the distributed
  algorithm than in the sequential case.

``finish_vertex(e, g)``
  See documentation for ``examine_vertex``.

Making Visitors Safe for Distributed DFS

unique_rmat_iterator();
unique_rmat_iterator(RandomGenerator& gen, vertices_size_type n, 
              edges_size_type m, double a, double b, double c, 
              double d, bool permute_vertices = true);
// Iterator operations
reference operator*() const;
pointer operator->() const;
unique_rmat_iterator& operator++();
unique_rmat_iterator operator++(int);
bool operator==(const unique_rmat_iterator& other) const;
bool operator!=(const unique_rmat_iterator& other) const;

IN: ``Graph& g``
  The graph type must be a model of `Distributed Vertex List Graph`_.

IN: ``GlobalIndexMap index_map``
  A `Distributed property map`_ whose type must model `Readable
  property map`_ that maps from vertices to a global index. If
  provided, this map must be initialized prior to be passed to the
  vertex list adaptor.

  **Default:** A property map of unspecified type constructed from a
  distributed ``iterator_property_map`` that uses the
  ``vertex_index`` property map of the underlying graph and a vector
  of ``vertices_size_type``.

Complexity

src/intro
src/overview
src/reference

src/configurations
src/discussion
src/acknowledgements
src/license

#include <ostream>
#include <ios>

void hex_my_byte(std::ostream& os, char byte)
{
    os << std::hex << static_cast<unsigned>(byte);
}

/* Detailed source-code truncated for AI context efficiency. */

class saver {
public:
    typedef std::ios_base state_type;
    typedef `implementation_defined` aspect_type;

    explicit saver(state_type& s);
    saver(state_type& s, const aspect_type& new_value);
    ~saver();

    void restore();
};

template<class Ch, class Tr>
class saver {
public:
    typedef std::basic_ios<Ch, Tr> state_type;
    typedef `implementation-defined` aspect_type;

    explicit saver(state_type& s);
    saver(state_type& s, const aspect_type& new_value);
    ~saver();

    void restore();
};

#include <boost/io/ios_state.hpp>
#include <ios>
#include <iostream>
#include <ostream>

void new_hex_my_byte(std::ostream& os, char byte)
{
    boost::io::ios_flags_saver ifs(os);
    os << std::hex << static_cast<unsigned>(byte);
}

int main()
{
    // ...
    {
        boost::io::ios_all_saver ias(std::cout);
        new_hex_my_byte(std::cout, 'A');
    }
    // ...
    {
        boost::io::ios_all_saver ias(std::cerr);
        new_hex_my_byte(std::cerr, 'b');
        ias.restore();
        new_hex_my_byte(std::cerr, 'C');
    }
    // ...
}

#include <boost/io/ostream_joiner.hpp>
#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;
    v.push_back(2);
    v.push_back(4);
    v.push_back(6);
    v.push_back(8);
    std::copy(v.begin(), v.end(), boost::make_ostream_joiner(std::cout, ','));
}

namespace boost {
namespace io {

template<class Delim, class Char = char,
    class Traits = std::char_traits<Char> >
class ostream_joiner {
public:
    typedef Char char_type;
    typedef Traits traits_type;
    typedef std::basic_ostream<Char, Traits> ostream_type;
    typedef std::output_iterator_tag iterator_category;
    typedef void value_type;
    typedef void difference_type;
    typedef void pointer;
    typedef void reference;

    ostream_joiner(ostream_type& output, const Delim& delim);
    ostream_joiner(ostream_type& output, Delim&& delim);

    template<class T>
    ostream_joiner& operator=(const T& value);

    ostream_joiner& operator*() noexcept;
    ostream_joiner& operator++() noexcept;
    ostream_joiner& operator++(int) noexcept;
};

template<class Char, class Traits, class Delim>
ostream_joiner<std::decay_t<Delim>, Char, Traits>
make_ostream_joiner(std::basic_ostream<Char, Traits>& output, Delim&& delim);

} // io
} // boost

ostream_joiner(ostream_type& output, const Delim& delim);

ostream_joiner(ostream_type& output, Delim&& delim);

template<class T>
ostream_joiner& operator=(const T& value);

ostream_joiner& operator*() noexcept;

ostream_joiner& operator++() noexcept;

ostream_joiner& operator++(int) noexcept;

template<class Char, class Traits, class Delim>
ostream_joiner<decay_t<Delim>, Char, Traits>
make_ostream_joiner(std::basic_ostream<Char, Traits>& output, Delim&& delim);

template<class charT, class traits>
std::basic_ostream<charT, traits>&
operator<<(std::basic_ostream<charT, traits>& os,
    const basic_string_view<charT, traits>& str)
{
    return boost::io::ostream_put(os, str.data(), str.size());
}

namespace boost {
namespace io {

template<class charT, class traits>
std::basic_ostream<charT, traits>&
ostream_put(std::basic_ostream<charT, traits>& os,
    const charT* data, std::size_t size);

} // io
} // boost

template<class charT, class traits>
std::basic_ostream<charT, traits>&
ostream_put(std::basic_ostream<charT, traits>& os,
    const charT* data, std::size_t size);

std::stringstream ss;
std::string original = "fooled you";
std::string roundtrip;

ss << original;
ss >> roundtrip;

std::cout << original;   // outputs: fooled you
std::cout << roundtrip; // outputs: fooled

assert(original == roundtrip); // assert will fire

std::stringstream ss;
std::string original = "fooled you";
std::string roundtrip;

ss << quoted(original);
ss >> quoted(roundtrip);

std::cout << quoted(original); // outputs: "fooled you"
std::cout << roundtrip;       // outputs: fooled you

assert(original == roundtrip); // assert will not fire

std::cout << quoted("'Jack & Jill'", '&', '\''); // outputs: '&'Jack && Jill&''

namespace boost {
namespace io {

template<class Char, class Traits, class Alloc>
`unspecified-type1`
quoted(const std::basic_string<Char, Traits, Alloc>& string,
       Char escape='\\', Char delim='\"');

template<class Char>
`unspecified-type2`
quoted(const Char* string, Char escape='\\', Char delim='\"');

template<class Char, class Traits, class Alloc>
`unspecified-type3`
quoted(std::basic_string<Char, Traits, Alloc>& string,
       Char escape='\\', Char delim='\"');

} // io
} // boost

template<class Char, class Traits>
std::basic_ostream<Char, Traits>&
operator<<(std::basic_ostream<Char, Traits>& os,
           const `unspecified-typeN`& proxy);

template<class Char, class Traits>
std::basic_istream<Char, Traits>&
operator>>(std::basic_istream<Char, Traits>& is,
           const `unspecified-type3`& proxy);

Synopsis
--------

::

    template <typename Iterator, typename Distance>
    constexpr void advance(Iterator& it, Distance n);


Description
-----------

Moves ``it`` forward by ``n`` increments
(or backward by ``|n|`` decrements if ``n`` is negative).


Requirements
------------

``Iterator`` should model Incrementable Iterator.


Preconditions
-------------

Let ``it``\ :sub:`i` be the iterator obtained by incrementing
(or decrementing if ``n`` is negative) ``it`` by *i*. All the iterators
``it``\ :sub:`i` for *i* = 0, 1, 2, ..., ``|n|`` should be valid.

If ``Iterator`` does not model Bidirectional Traversal Iterator,
``n`` should be non-negative.


Complexity
----------

If ``Iterator`` models Random Access Traversal Iterator, it takes constant time;
otherwise it takes linear time.


Notes
-----

- This function is not a customization point and is protected against
  being found by argument-dependent lookup (ADL).
- This function is ``constexpr`` only in C++14 or later.


--------------------------------------------------------------------------------

| Author: Michel Morin
| Copyright |C| 2017 Michel Morin
| Distributed under the `Boost Software License, Version 1.0
  <http://www.boost.org/LICENSE_1_0.txt>`_.

.. |C| unicode:: U+00A9 .. COPYRIGHT SIGN

---

### Extra Boost Boost 1 77 0 Libs Iterator Doc Counting Iterator (`extra/boost/boost_1_77_0/libs/iterator/doc/counting_iterator.rst`)

.. Distributed under the Boost
.. Software License, Version 1.0. (See accompanying
.. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

+++++++++++++++++++
 Counting Iterator
+++++++++++++++++++

:Author: David Abrahams, Jeremy Siek, Thomas Witt
:Contact: [email protected], [email protected], [email protected]
:organization: `Boost Consulting`_, Indiana University `Open Systems
               Lab`_, University of Hanover `Institute for Transport
               Railway Operation and Construction`_
:date: $Date$
:copyright: Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003. 

.. _`Boost Consulting`: http://www.boost-consulting.com
.. _`Open Systems Lab`: http://www.osl.iu.edu
.. _`Institute for Transport Railway Operation and Construction`: http://www.ive.uni-hannover.de

:abstract: How would you fill up a vector with the numbers zero
  through one hundred using ``std::copy()``?  The only iterator
  operation missing from builtin integer types is an
  ``operator*()`` that returns the current value of the integer.
  The counting iterator adaptor adds this crucial piece of
  functionality to whatever type it wraps.  One can use the
  counting iterator adaptor not only with integer types, but with
  any incrementable type.

  .. include:: counting_iterator_abstract.rst

.. contents:: Table of Contents

``counting_iterator`` synopsis
..............................

.. include:: counting_iterator_ref.rst
.. include:: make_counting_iterator.rst

.. include:: counting_iterator_eg.rst

.. _iterator-category: iterator_facade.html#iterator-category
.. |iterator-category| replace:: *iterator-category*

---

### Extra Boost Boost 1 77 0 Libs Iterator Doc Counting Iterator Abstract (`extra/boost/boost_1_77_0/libs/iterator/doc/counting_iterator_abstract.rst`)

.. Copyright David Abrahams 2006. Distributed under the Boost
.. Software License, Version 1.0. (See accompanying
.. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

``counting_iterator`` adapts an object by adding an ``operator*`` that
returns the current value of the object. All other iterator operations
are forwarded to the adapted object.

---

### Extra Boost Boost 1 77 0 Libs Iterator Doc Counting Iterator Eg (`extra/boost/boost_1_77_0/libs/iterator/doc/counting_iterator_eg.rst`)

.. Copyright David Abrahams 2006. Distributed under the Boost
.. Software License, Version 1.0. (See accompanying
.. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

Example
.......

This example fills an array with numbers and a second array with
pointers into the first array, using ``counting_iterator`` for both
tasks. Finally ``indirect_iterator`` is used to print out the numbers
into the first array via indirection through the second array.

::

    int N = 7;
    std::vector numbers;
    typedef std::vector::iterator n_iter;
    std::copy(boost::counting_iterator(0),
             boost::counting_iterator(N),
             std::back_inserter(numbers));

    std::vector<std::vector::iterator> pointers;
    std::copy(boost::make_counting_iterator(numbers.begin()),
	      boost::make_counting_iterator(numbers.end()),
	      std::back_inserter(pointers));

    std::cout << "indirectly printing out the numbers from 0 to " 
	      << N << std::endl;
    std::copy(boost::make_indirect_iterator(pointers.begin()),
	      boost::make_indirect_iterator(pointers.end()),
	      std::ostream_iterator(std::cout, " "));
    std::cout << std::endl;


The output is::

    indirectly printing out the numbers from 0 to 7
    0 1 2 3 4 5 6 

The source code for this example can be found `here`__.

__ ../example/counting_iterator_example.cpp

---

### Extra Boost Boost 1 77 0 Libs Iterator Doc Counting Iterator Ref (`extra/boost/boost_1_77_0/libs/iterator/doc/counting_iterator_ref.rst`)

.. Copyright David Abrahams 2006. Distributed under the Boost
.. Software License, Version 1.0. (See accompanying
.. file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

::

  template <
      class Incrementable
    , class CategoryOrTraversal = use_default
    , class Difference = use_default
  >
  class counting_iterator
  {
  public:
      typedef Incrementable value_type;
      typedef const Incrementable& reference;
      typedef const Incrementable* pointer;
      typedef /* see below */ difference_type;
      typedef /* see below */ iterator_category;

      counting_iterator();
      counting_iterator(counting_iterator const& rhs);
      explicit counting_iterator(Incrementable x);
      Incrementable const& base() const;
      reference operator*() const;
      counting_iterator& operator++();
      counting_iterator& operator--();
  private:
      Incrementable m_inc; // exposition
  };


If the ``Difference`` argument is ``use_default`` then
``difference_type`` is an unspecified signed integral
type. Otherwise ``difference_type`` is ``Difference``.

``iterator_category`` is determined according to the following
algorithm:

.. parsed-literal::

   if (CategoryOrTraversal is not use_default)
       return CategoryOrTraversal
   else if (numeric_limits::is_specialized)
       return |iterator-category|_\ (
           random_access_traversal_tag, Incrementable, const Incrementable&)
   else
       return |iterator-category|_\ (
            iterator_traversal::type, 
            Incrementable, const Incrementable&)
        
[*Note:* implementers are encouraged to provide an implementation of
  ``operator-`` and a ``difference_type`` that avoids overflows in
  the cases where ``std::numeric_limits::is_specialized``
  is true.]

``counting_iterator`` requirements
..................................

The ``Incrementable`` argument shall be Copy Constructible and Assignable.

If ``iterator_category`` is convertible to ``forward_iterator_tag``
or ``forward_traversal_tag``, the following must be well-formed::

    Incrementable i, j;
    ++i;         // pre-increment
    i == j;      // operator equal


If ``iterator_category`` is convertible to
``bidirectional_iterator_tag`` or ``bidirectional_traversal_tag``,
the following expression must also be well-formed::

    --i

If ``iterator_category`` is convertible to
``random_access_iterator_tag`` or ``random_access_traversal_tag``,
the following must must also be valid::

    counting_iterator::difference_type n;
    i += n;
    n = i - j;
    i < j;

``counting_iterator`` models
............................

Specializations of ``counting_iterator`` model Readable Lvalue
Iterator. In addition, they model the concepts corresponding to the
iterator tags to which their ``iterator_category`` is convertible.
Also, if ``CategoryOrTraversal`` is not ``use_default`` then
``counting_iterator`` models the concept corresponding to the iterator
tag ``CategoryOrTraversal``.  Otherwise, if
``numeric_limits::is_specialized``, then
``counting_iterator`` models Random Access Traversal Iterator.
Otherwise, ``counting_iterator`` models the same iterator traversal
concepts modeled by ``Incrementable``.

``counting_iterator<X,C1,D1>`` is interoperable with
``counting_iterator<Y,C2,D2>`` if and only if ``X`` is
interoperable with ``Y``.



``counting_iterator`` operations
................................

In addition to the operations required by the concepts modeled by
``counting_iterator``, ``counting_iterator`` provides the following
operations.


``counting_iterator();``

:Requires: ``Incrementable`` is Default Constructible.
:Effects: Default construct the member ``m_inc``.


``counting_iterator(counting_iterator const& rhs);``

:Effects: Construct member ``m_inc`` from ``rhs.m_inc``.



``explicit counting_iterator(Incrementable x);``

:Effects: Construct member ``m_inc`` from ``x``.


``reference operator*() const;``

:Returns: ``m_inc``


``counting_iterator& operator++();``

:Effects: ``++m_inc``
:Returns: ``*this``


``counting_iterator& operator--();``

:Effects: ``--m_inc``
:Returns: ``*this``  


``Incrementable const& base() const;``

:Returns: ``m_inc``

---

### Extra Boost Boost 1 77 0 Libs Iterator Doc Distance (`extra/boost/boost_1_77_0/libs/iterator/doc/distance.rst`)

.. Copyright (C) 2017 Michel Morin.
   Distributed under the Boost Software License, Version 1.0.
   (See accompanying file LICENSE_1_0.txt or copy at
   http://www.boost.org/LICENSE_1_0.txt)

========
distance
========

``boost::iterators::distance`` is an adapted version of ``std::distance`` for 
the Boost iterator traversal concepts.


Header
------

template <typename Iterator>
constexpr typename iterator_difference::type
distance(Iterator first, Iterator last);