# Boost Graph Library: Python Bindings (Experimental)

The Boost Graph Library offers a wealth of graph algorithms and data types for C++. These algorithms are flexible and efficient, but the mechanisms employed to achieve this goal can result in long compile times that slow the development cycle.

The Python bindings are build using the Boost.Python library. The bindings are meant to strike a balance of usability, flexibility, and efficiency, making it possible to rapidly develop useful systems using the BGL in Python.

- Caveats and Warnings
- Building the Python Bindings
- Goals
- Documentation style
  - Graph types
  - Types
  - Constructors
  - General operations
  - Vertex List Graph operations
  - Edge List Graph operations
  - Mutable Graph operations
  - Incidence Graph operations
  - Vertex Property Maps
  - Edge Property Maps
  - Input/Output operations
- Algorithms
- Property Maps

- A simple visualization tool
- Request for comments

## Caveats and Warnings

The Python bindings for the Graph library are experimental at this time. The bindings may not work (but they probably do) and we will not attempt to provide backward compatibility if the interfaces change. If you have any ideas

## Building the Python Bindings

To build the Python bindings, change to the `libs/graph/build/python` subdirectory of Boost and then follow the Boost Build Instructions to build the Python extension module. The end result will be a dynamic library (DLL, .so, etc.) that can be loaded into Python via "`import bgl`". Note: For this build to succeed, the graph library must work flawlessly on the compile, including the new GraphViz parser, which tends to break many compilers. Visual C++ 7.1 and recent versions of the GCC and Intel compilers are known to work.

## Goals

The goal of the BGL-Python bindings is to create a set of bindings for the majority of the BGL in Python that:

- "Feel" like the BGL, but with Python syntax.
- Allow rapid prototyping of algorithms for the BGL.
- Allow easy porting from the BGL in Python to the BGL in C++.
- Permit the use of the BGL in applications for which C++ is not particularly well suited.
- Strike a balance between simplicity, usability, and efficiency.

Note that one goal we did not list is that the Python syntax be perfect for Python. For instance, one might implement a graph library in Python very differently from the way the BGL is implemented in C++, and the Python version may be syntactically superior. Nonetheless, having a strong syntactic correlation between the BGL in C++ and the BGL in Python is important for this project. It is strongly recommended that you build with release mode, e.g., `bjam -sBUILD=release`.

## A First Example

Our first example illustrates the use of BGL graphs, graph algorithms, and property maps from Python. The initial step is to load the BGL-Python bindings:

    from bgl import *

Next, we load a GraphViz file containing the description of a sample graph. The `Graph` type is an undirected graph; `file_kind` is an enumerator with only two potential values: `adjlist`, for an adjacency-list representation, or `graphviz`, for a GraphViz file.

    g = Graph("biconnected_components.dot", file_kind.graphviz)

Assuming no exceptions have been thrown, we will have an undirected graph loaded. We can immediately call `biconnected_components` to compute the biconnected components within the graph:

    art_points = biconnected_components(g, g.get_edge_int_map("label"))

There are several interesting parts of the preceeding line. We call the `biconnected_components` algorithm with two parameters. The first is just the graph itself. The second parameter is a property map from edges to an integer value, which will be stored in the graph under the name "label". Finally, the return value of `biconnected_components` is a Python list containing the articulation points of the graph.

Other kinds of property maps are available. In this case, we create two property maps attaching strings to the vertices of the graph. We then iterate over all vertices of the graph to set default values for each vertex property.

    v_color = g.get_vertex_string_map("fillcolor")
    v_style = g.get_vertex_string_map("style")
    for v in g.vertices:
      v_color[v] = "white"
      v_style[v] = "filled"

Lastly, we mark all of the articulation points red and write out the result in GraphViz format.

    for v in art_points:
      v_color[v] = "red"

    g.write_graphviz("biconnected_components_out.dot")

## Documentation style

The Python bindings for the Boost Graph Library retain essentially the same syntax. Because of this, there is no separate documentation for the BGL in Python: each BGL component (algorithms, data structures, etc.) available in Python will be marked with the Python symbol . Unless an explicit Python section (or field) is present, the Python versions have precisely the same semantics as the C++ version.

### Graph types

The C++ Boost Graph Library provides several graph types that permit the generation of a huge number of specific graph types. In Python, the BGL only exposes two general-purpose graph types: `Graph` and `Digraph`, for undirected and directed graphs, respectively. Both graph types are part of the `bgl` extension module for Python. These graph types are one-size-fits-most, offering stable vertex and edge descriptors and a core set of operations from the `adjacency_list` class template. The following sections briefly describe the operations that can be performed on both the `Graph` and `Digraph` Python graph types, although the documentation uses `Graph` in the description.

Unlike the C++ graph types in the BGL, the Python graph types use object-oriented syntax. For instance, `num_vertices(g)` retrieves the number of vertices in graph `g` in C++, whereas the Python equivalent is `g.num_vertices()`. All of the graph operations described in the following text are methods of the graph type.

#### Types

    Graph.Vertex

> The type of a vertex descriptor in the graph `Graph` that will be used to refer to vertices in the graph. Note that there may be several Python objects that refer to the same vertex, which can be compared with `==` and `!=` correctly.
> Bug: Vertex descriptors do not work properly when used in a Python `dict`.

    Graph.Edge

> The type of a edge descriptor in the graph `Graph` that will be used to refer to edges in the graph. Note that there may be several Python objects that refer to the same edge, which can be compared with `==` and `!=` correctly.
> Bug: Edge descriptors do not work properly when used in a Python `dict`.

#### Constructors

    Graph()

> Constructs an empty graph.

    Graph(edges, name_map = "")

> Constructs a graph from a list of edges. `edges` should be a Python sequence, the elements of which should be 2-tuples containing the source and target of the edge. The sources and targets can be of any type that has a less-than operator defined, e.g., strings or integers. If a non-empty string is provided for `name_map`, a `vertex_object_map` will be created that maps from the vertices that are created to the name used in the list of edges.

    Graph(filename, kind)

> Constructs a graph from an external file using one of the Boost Graph Library's graph parsers. `filename` is a string containing the file name. `kind` is an value of type `bgl.file_kind`, which has one of the following values:
> - `bgl.file_kind.adjlist`: Reads an adjacency-list representation into the graph. In the file, each line represents a single edge. On that line will be the source and target of the edge, separated by one or more spaces.
> - `bgl.file_kind.graphviz`: Reads a GraphViz DOT file into the graph. The DOT file must represent a graph that is directed (for a `Digraph`) or undirected (for a `Graph`). See `read_graphviz` for additional details.

    Graph(generator, seed)

> Constructs a graph using the random generator `generator` and random seed value `seed` (an integer). The `generator` parameter may be one of three things:
> - `bgl.ErdosRenyi(n, p)`: Generates a graph with `n` vertices and a probability 0 <= `p` >= 1 of having an edge between any two vertices `u` and `v`.
> - `bgl.SmallWorld(n, k, p)`: Generates a small-world graph with `n` vertices, each of which is connected to its `k` nearest neighbors (assuming one places the vertices in a circle). With probability `p`, each edge in the graph is randomly rewired.
> - `bgl.PowerLawOutDegree(n, alpha, beta)`: Generates a scale-free graph using the Power Law Out Degree model with `n` vertices. Each vertex has degree beta * x-alpha, where x is a random value between 0 and n-1. The value of beta controls the y-intercept of the curve, so that increasing beta increases the average degree of vertices. The value of alpha controls how steeply the curve drops off, with larger values indicating a steeper curve. The web graph, for instance, has alpha ~ 2.72.

#### General operations

    is_directed()

> Returns `True` if the edges in the graph are directed, `False` otherwise.

#### Vertex List Graph operations

    num_vertices()

> Returns the number of vertices in the graph.

    vertices

> Returns a sequence containing all vertices in the graph. This sequence has a Python iterator, such that the following Python code prints the names of all vertices in graph `g`:

>     for v in g.vertices:
>       print name[v]

#### Edge List Graph operations

    num_edges()

> Returns the number of edges in the graph.

    edges

> Returns a sequence containing all edges in the graph. This sequence has a Python iterator, such that the following Python code prints the weights of all edges in graph `g`:

>     for e in g.edges:
>       print weight[e]

#### Mutable Graph operations

    add_vertex()

> Adds a new vertex to the graph and returns the descriptor of the new vertex. Default values for all property maps attached to the graph will be provided for this vertex.

    clear_vertex(v)

> Removes all of the incoming and outgoing edges to the vertex `v`. The properties for each of the edges removed will be removed from the property maps attached to the graph.

    remove_vertex(v)

> Removes the vertex `v` from the graph. Before invoking this function, there must be no edges attached to this vertex (either incoming or outgoing), which can be ensured by a call to `clear_vertex(v)`. Properties associated with this vertex will be removed from the property maps attached to the graph. Once this call completes, the vertex descriptor `v` is considered invalid and cannot be used again.

    add_edge(u, v)

> Add an edge (u, v) to the graph and returns the descriptor for the new edge. Default values for all property maps attached to the graph will be provided for this edge.

    remove_edge(e)

> Remove the edge `e` from the graph. The properties for `e` will be be removed from the property maps attached to the graph. Once this operation completes, the edge descriptor `e` is considered invalid and cannot be used again.

#### Incidence Graph operations

    source(e)

> Returns the source of the edge `e`.

    target(e)

> Returns the target of the edge `e`.

    out_edges(u)

> Returns a sequence containing all edges outgoing from `u`. This sequence has an iterator, so that the following Python code prints the weights of all edges outgoing from vertex `u` in graph `g`:

>     for e in g.out_edges(u):
>       print weight[e]

> For each edge `e`, `g.source(e) == u`.

    out_degree(u)

> Returns the number of edges outgoing from vertex `u`.

    in_edges(v)

> Returns a sequence containing all edges incoming to `v`. This sequence has an iterator, so that the following Python code prints the weights of all edges incoming to vertex `v` in graph `g`:

>     for e in g.in_edges(u):
>       print weight[e]

> For each edge `e`, `g.target(e) == v`. For undirected graphs, the `in_edges` will be equivalent to the `out_edges`, except that the source and target will be swapped.

    in_degree(u)

> Returns the number of edges incoming to vertex `u`. For undirected graphs, `g.in_degree(u) == g.in_degree(v)`.

    adjacent_vertices(u)

> Returns a sequence containing all vertices adjacent to `u`. This sequence has an iterator, so that the following Python code prints the names of all vertices adjacent to vertex `u` in graph `g`:

>     for v in g.adjacent_vertices(u):
>       print name[v]

> The sequence of adjacent vertices for vertex `u` corresponds to the targets of the outgoing edges of `u`.

#### Vertex property maps

    has_vertex_map(name)

> Returns `True` if the graph contains a vertex property map with the name `name`.

    get_vertex_index_map()

> Returns a property map that maps vertex descriptors to indices in the range [0, `g.num_vertices()`).

    get_vertex_color_map()

> Returns a property map that maps vertex descriptors to values of the Python type `bgl.Color`, which is an enumeration containing the values `white`, `gray`, and `black`. If a property map of this name already exists, its values are converted to colors. Otherwise, a new map is created.

    get_vertex_double_map()

> Returns a property map that maps vertex descriptors to `double` values. If a property map of this name already exists, its values are converted to `double`s. Otherwise, a new map is created.

    get_vertex_int_map()

> Returns a property map that maps vertex descriptors to `int` values. If a property map of this name already exists, its values are converted to `int`s. Otherwise, a new map is created.

    get_vertex_string_map()

> Returns a property map that maps vertex descriptors to `string` values. If a property map of this name already exists, its values are converted to `string`s. Otherwise, a new map is created.

    get_vertex_object_map()

> Returns a property map that maps vertex descriptors to Python `object`s. If a property map of this name already exists, its values are converted to `object`s. Otherwise, a new map is created.

    get_vertex_point_map()

> Returns a property map that maps vertex descriptors to values of the Python type `bgl.Point2D`, which is an class containing `x` and `y` attributes storing `double` values. If a property map of this name already exists, its values are converted to 2-D points. Otherwise, a new map is created.
> Bug: Writing just the `x` or `y` attributes of a `bgl.Point2D` object does not work at this time. However, you can create a new `bgl.Point2D` object and assign it into the property map.

#### Edge property maps

    has_edge_map(name)

> Returns `True` if the graph contains a edge property map with the name `name`.

    get_edge_index_map()

> Returns a property map that maps edge descriptors to indices in the range [0, `g.num_edges()`).

    get_edge_color_map()

> Returns a property map that maps edge descriptors to values of the Python type `bgl.Color`, which is an enumeration containing the values `white`, `gray`, and `black`. If a property map of this name already exists, its values are converted to colors. Otherwise, a new map is created.

    get_edge_double_map()

> Returns a property map that maps edge descriptors to `double` values. If a property map of this name already exists, its values are converted to `double`s. Otherwise, a new map is created.

    get_edge_int_map()

> Returns a property map that maps edge descriptors to `int` values. If a property map of this name already exists, its values are converted to `int`s. Otherwise, a new map is created.

    get_edge_string_map()

> Returns a property map that maps edge descriptors to `string` values. If a property map of this name already exists, its values are converted to `string`s. Otherwise, a new map is created.

    get_edge_object_map()

> Returns a property map that maps edge descriptors to Python `object`s. If a property map of this name already exists, its values are converted to `object`s. Otherwise, a new map is created.

#### Input/Output operations

The BGL graph types can be pickled from Python. Additional file-based formats are also available for use.

    read_graphviz(filename, node_id = "node_id")

> Reads a GraphViz file named `filename`into the graph, which is assumed to be empty. The operation will create a `vertex_string_map` named `node_id` that maps from vertex descriptors to the node identifiers in the GraphViz file. All vertex and edge attributes stored in the file will be loaded into `vertex_string_map` and `edge_string_map` property maps, respectively. An exception will be thrown if parsing of the GraphViz file fails.

    write_graphviz(filename, node_id = None)

> Writes the graph into a file named `filename` in GraphViz format. All vertex and edge attributes stored in the graph's property maps will be written to the file. If `node_id` is provided, the vertex identifiers in the GraphViz output will correspond with the names provided in the vertex property map `node_id`. Otherwise, integer indices will be used to identify nodes in the output file.

### Algorithms

All algorithms available in Python operate only on the Python graph types supplied by the BGL-Python bindings and are not generic in the same sense as their C++ counterparts. However, unless marked otherwise, their parameters are still customizable from Python. See, for instance, `breadth_first_search`, which can still be provided with a customized queue and visitor from within Python.

All algorithms are in the `bgl` extension module, at the top level, and have the same names as in C++.

The parameters of BGL functions exposed to Python have the same general data types, order, and names as in C++. If the BGL function takes named parameters, then the names of the parameters can be used for keyword arguments in Python. For instance:

    // C++
    betweenness_centrality(g, weight_map(weight).centrality_map(centrality));

    # Python
    bgl.betweenness_centrality(g, weight_map = weight, centrality_map = centrality);

Unless otherwise specified, all parameters documented in C++ are available in Python. If there are any differences, the parameter documentation will contain a Python line describing those differences. If the default in Python differs from the C++ default, the parameter documentation will contain a Python default line. Finally, if the algorithm's behavior is radically different in Python, the algorithm will contain a "Python" section. Although not available now, we would like to rewrite the C++ examples in Python and add a "Python Example" for each algorithm with inline examples.

### Property Maps

Property maps in Python allow the same `[]` operator syntax as Python dictionaries. For instance, if we have a property map `rank` mapping vertices to integers, we can increment the rank of vertex `v` with the following Python code:

    rank[v] = rank[v] + 1

However, unlike Python dictionaries one cannot enumerate the keys or values in a property map. Instead, you must enumerate the vertex or edges in the graph to index into the Python property map. This restriction follows from the C++ formulation of property maps, which do not allow such iteration.

## A simple visualization tool

The program `vis.py`, in the `examples/python` subdirectory, is a simple Graph visualization tool written in Python using the BGL bindings. It can load graphs, perform graph layout, run a few graph algorithms on graphs, etc. At present, it is not a useful program per se but merely an example of what can be achieved (quickly!) using the BGL-Python bindings. To use this program you will need to install wxPython.

## Request for comments

We want YOU to send it comments, questions, bug reports, or suggestions for the BGL-Python bindings. They are experimental, used primarily in-house for rapid prototyping of graph systems. If you have any ideas, please post them to the Boost-Users or Boost Developers mailing lists, or e-mail me directly at
.

Copyright © 2005 | Doug Gregor, Indiana University ( ) Andrew Lumsdaine, Indiana University ( )