graph_tool - efficient graph analysis and manipulation

Summary

Graph Generic multigraph class.
GraphView A view of selected vertices or edges of another graph.
Vertex Vertex descriptor.
Edge Edge descriptor.
PropertyMap This class provides a mapping from vertices, edges or whole graphs to arbitrary properties.
PropertyArray This is a ndarray subclass which keeps a reference of its PropertyMap owner, and detects if the underlying data has been invalidated.
load_graph Load a graph from file_name (which can be either a string or a file-like object).
group_vector_property Group list of properties props into a vector property map of the same type.
ungroup_vector_property Ungroup vector property map vprop into a list of individual property maps.
infect_vertex_property Propagate the prop values of vertices with value val to all their out-neighbours.
edge_difference Return an edge property map corresponding to the difference between the values of prop of target and source vertices of each edge.
value_types Return a list of possible properties value types.
show_config Show graph_tool build configuration.

This module provides:

  1. A Graph class for graph representation and manipulation
  2. Property maps for Vertex, Edge or Graph.
  3. Fast algorithms implemented in C++.

How to use the documentation

Documentation is available in two forms: docstrings provided with the code, and the full documentation available in the graph-tool homepage.

We recommend exploring the docstrings using IPython, an advanced Python shell with TAB-completion and introspection capabilities.

The docstring examples assume that graph_tool.all has been imported as gt:

>>> import graph_tool.all as gt

Code snippets are indicated by three greater-than signs:

>>> x = x + 1

Use the built-in help function to view a function’s docstring:

>>> help(gt.Graph)

Contents

class graph_tool.Graph(g=None, directed=True, prune=False, vorder=None)

Generic multigraph class.

This class encapsulates either a directed multigraph (default or if directed=True) or an undirected multigraph (if directed=False), with optional internal edge, vertex or graph properties.

If g is specified, the graph (and its internal properties) will be copied.

If prune is set to True, and g is specified, only the filtered graph will be copied, and the new graph object will not be filtered. Optionally, a tuple of three booleans can be passed as value to prune, to specify a different behavior to vertex, edge, and reversal filters, respectively.

If vorder is specified, it should correspond to a vertex PropertyMap specifying the ordering of the vertices in the copied graph.

The graph is implemented as an adjacency list, where both vertex and edge lists are C++ STL vectors.

copy()

Return a deep copy of self. All internal property maps are also copied.

Iterating over vertices and edges

See Iterating over vertices and edges for more documentation and examples.

vertices()

Return an iterator over the vertices.

Note

The order of the vertices traversed by the iterator always corresponds to the vertex index ordering, as given by the vertex_index property map.

Examples

>>> g = gt.Graph()
>>> vlist = list(g.add_vertex(5))
>>> vlist2 = []
>>> for v in g.vertices():
...     vlist2.append(v)
...
>>> assert(vlist == vlist2)
edges()

Return an iterator over the edges.

Note

The order of the edges traversed by the iterator does not necessarily correspond to the edge index ordering, as given by the edge_index property map. This will only happen after reindex_edges() is called, or in certain situations such as just after a graph is loaded from a file. However, further manipulation of the graph may destroy the ordering.

Obtaining vertex and edge descriptors
vertex(i, use_index=True)

Return the vertex with index i. If use_index=False, the i-th vertex is returned (which can differ from the vertex with index i in case of filtered graphs).

edge(s, t, all_edges=False)

Return the edge from vertex s to t, if it exists. If all_edges=True then a list is returned with all the parallel edges from s to t, otherwise only one edge is returned.

This operation will take \(O(k(s))\) time, where \(k(s)\) is the out-degree of vertex \(s\).

Number of vertices and edges
num_vertices()

Get the number of vertices.

Note

If the vertices are being filtered, this operation is \(O(N)\). Otherwise it is \(O(1)\).

num_edges()

Get the number of edges.

Note

If the edges are being filtered, this operation is \(O(E)\). Otherwise it is \(O(1)\).

Modifying vertices and edges

The following functions allow for addition and removal of vertices in the graph.

add_vertex(n=1)

Add a vertex to the graph, and return it. If n != 1, n vertices are inserted and an iterator over the new vertices is returned. This operation is \(O(n)\).

remove_vertex(vertex, fast=False)

Remove a vertex from the graph.

Note

If the option fast == False is given, this operation is \(O(N + E)\) (this is the default). Otherwise it is \(O(k + k_{\text{last}})\), where \(k\) is the (total) degree of the vertex being deleted, and \(k_{\text{last}}\) is the (total) degree of the vertex with the largest index.

Warning

If fast == True, the vertex being deleted is ‘swapped’ with the last vertex (i.e. with the largest index), which will in turn inherit the index of the vertex being deleted. All property maps associated with the graph will be properly updated, but the index ordering of the graph will no longer be the same.

The following functions allow for addition and removal of edges in the graph.

add_edge(source, target)

Add a new edge from source to target to the graph, and return it. This operation is \(O(1)\).

remove_edge(edge)

Remove an edge from the graph.

Note

This operation is normally \(O(k_s + k_t)\), where \(k_s\) and \(k_s\) are the total degrees of the source and target vertices, respectively. However, if set_fast_edge_removal() is set to True, this operation becomes \(O(1)\).

Warning

The relative ordering of the remaining edges in the graph is kept unchanged, unless set_fast_edge_removal() is set to True, in which case it can change.

add_edge_list(edge_list)

Add a list of edges to the graph, given by edge_list, which can be a list of (source, target) pairs where both source and target are vertex indexes, or a ndarray of shape (E,2), where E is the number of edges, and each line specifies a (source, target) pair. If the list references vertices which do not exist in the graph, they will be created.

set_fast_edge_removal(fast=True)

If fast == True the fast \(O(1)\) removal of edges will be enabled. This requires an additional data structure of size \(O(E)\) to be kept at all times. If fast == False, this data structure is destroyed.

get_fast_edge_removal()

Return whether the fast \(O(1)\) removal of edges is currently enabled.

The following functions allow for easy removal of vertices and edges from the graph.

clear()

Remove all vertices and edges from the graph.

clear_vertex(vertex)

Remove all in and out-edges from the given vertex.

clear_edges()

Remove all edges from the graph.

Directedness and reversal of edges

Note

These functions do not actually modify the graph, and are fully reversible. They are also very cheap, and have an \(O(1)\) complexity.

set_directed(is_directed)

Set the directedness of the graph.

is_directed()

Get the directedness of the graph.

set_reversed(is_reversed)

Reverse the direction of the edges, if is_reversed is True, or maintain the original direction otherwise.

is_reversed()

Return True if the edges are reversed, and False otherwise.

Creation of new property maps
new_property(key_type, value_type)

Create a new (uninitialized) vertex property map of key type key_type (v, e or g), value type value_type, and return it.

new_vertex_property(value_type)

Create a new (uninitialized) vertex property map of type value_type, and return it.

new_edge_property(value_type)

Create a new (uninitialized) edge property map of type value_type, and return it.

new_graph_property(value_type, val=None)

Create a new graph property map of type value_type, and return it. If val is not None, the property is initialized to its value.

New property maps can be created by copying already existing ones.

copy_property(src, tgt=None, value_type=None, g=None)

Copy contents of src property to tgt property. If tgt is None, then a new property map of the same type (or with the type given by the optional value_type parameter) is created, and returned. The optional parameter g specifies the (identical) source graph to copy properties from (defaults to self).

degree_property_map(deg, weight=None)

Create and return a vertex property map containing the degree type given by deg. If provided, weight should be an edge PropertyMap containing the edge weights which should be summed.

Index property maps
vertex_index

Vertex index map.

It maps for each vertex in the graph an unique integer in the range [0, num_vertices() - 1].

Note

Like edge_index, this is a special instance of a PropertyMap class, which is immutable, and cannot be accessed as an array.

edge_index

Edge index map.

It maps for each edge in the graph an unique integer.

Note

Like vertex_index, this is a special instance of a PropertyMap class, which is immutable, and cannot be accessed as an array.

Additionally, the indexes may not necessarily lie in the range [0, num_edges() - 1]. However this will always happen whenever no edges are deleted from the graph.

max_edge_index

The maximum value of the edge index map.

reindex_edges()

Reset the edge indexes so that they lie in the [0, num_edges() - 1] range. The index ordering will be compatible with the sequence returned by the edges() function.

Warning

Calling this function will invalidate all existing edge property maps, if the index ordering is modified! The property maps will still be usable, but their contents will still be tied to the old indexes, and thus may become scrambled.

Internal property maps

Internal property maps are just like regular property maps, with the only exception that they are saved and loaded to/from files together with the graph itself. See internal property maps for more details.

Note

All dictionaries below are mutable. However, any dictionary returned below is only an one-way proxy to the internally-kept properties. If you modify this object, the change will be propagated to the internal dictionary, but not vice-versa. Keep this in mind if you intend to keep a copy of the returned object.

properties

Dictionary of internal properties. Keys must always be a tuple, where the first element if a string from the set {‘v’, ‘e’, ‘g’}, representing a vertex, edge or graph property, respectively, and the second element is the name of the property map.

Examples

>>> g = gt.Graph()
>>> g.properties[("e", "foo")] = g.new_edge_property("vector<double>")
>>> del g.properties[("e", "foo")]
vertex_properties

Dictionary of internal vertex properties. The keys are the property names.

vp

Alias to vertex_properties.

edge_properties

Dictionary of internal edge properties. The keys are the property names.

ep

Alias to edge_properties.

graph_properties

Dictionary of internal graph properties. The keys are the property names.

gp

Alias to graph_properties.

list_properties()

Print a list of all internal properties.

Examples

>>> g = gt.Graph()
>>> g.properties[("e", "foo")] = g.new_edge_property("vector<double>")
>>> g.vertex_properties["foo"] = g.new_vertex_property("double")
>>> g.vertex_properties["bar"] = g.new_vertex_property("python::object")
>>> g.graph_properties["gnat"] = g.new_graph_property("string", "hi there!")
>>> g.list_properties()
gnat           (graph)   (type: string, val: hi there!)
bar            (vertex)  (type: python::object)
foo            (vertex)  (type: double)
foo            (edge)    (type: vector<double>)
Filtering of vertices and edges.

See Graph filtering for more details.

Note

These functions do not actually modify the graph, and are fully reversible. They are also very cheap, and have an \(O(1)\) complexity.

set_vertex_filter(prop, inverted=False)

Choose vertex boolean filter property. Only the vertices with value different than zero are kept in the filtered graph. If the inverted option is supplied with value True, only the vertices with value zero are kept. If the supplied property is None, any previous filtering is removed.

get_vertex_filter()

Return a tuple with the vertex filter property and bool value indicating whether or not it is inverted.

set_edge_filter(prop, inverted=False)

Choose edge boolean filter property. Only the edges with value different than zero are kept in the filtered graph. If the inverted option is supplied with value True, only the edges with value zero are kept. If the supplied property is None, any previous filtering is removed.

get_edge_filter()

Return a tuple with the edge filter property and bool value indicating whether or not it is inverted.

Warning

The purge functions below irreversibly remove the filtered vertices or edges from the graph, and return it to an unfiltered state. Note that, contrary to the functions above, these are \(O(V)\) and \(O(E)\) operations, respectively.

purge_vertices(in_place=False)

Remove all vertices of the graph which are currently being filtered out, and return it to the unfiltered state. This operation is not reversible.

If the option in_place == True is given, the algorithm will remove the filtered vertices and re-index all property maps which are tied with the graph. This is a slow operation which has an \(O(N^2)\) complexity.

If in_place == False, the graph and its vertex and edge property maps are temporarily copied to a new unfiltered graph, which will replace the contents of the original graph. This is a fast operation with an \(O(N + E)\) complexity. This is the default behaviour if no option is given.

purge_edges()

Remove all edges of the graph which are currently being filtered out, and return it to the unfiltered state. This operation is not reversible.

I/O operations

See Graph I/O for more details.

load(file_name, fmt='auto', ignore_vp=None, ignore_ep=None, ignore_gp=None)

Load graph from file_name (which can be either a string or a file-like object). The format is guessed from file_name, or can be specified by fmt, which can be either “xml”, “dot” or “gml”.

If provided, the parameters ignore_vp, ignore_ep and ignore_gp, should contain a list of property names (vertex, edge or graph, respectively) which should be ignored when reading the file.

save(file_name, fmt='auto')

Save graph to file_name (which can be either a string or a file-like object). The format is guessed from the file_name, or can be specified by fmt, which can be either “xml”, “dot” or “gml”.

class graph_tool.GraphView(g, vfilt=None, efilt=None, directed=None, reversed=False, skip_properties=False, skip_vfilt=False, skip_efilt=False)

Bases: graph_tool.Graph

A view of selected vertices or edges of another graph.

This class uses shared data from another Graph instance, but allows for local filtering of vertices and/or edges, edge directionality or reversal. See Graph views for more details and examples.

The existence of a GraphView object does not affect the original graph, except if the graph view is modified (addition or removal of vertices or edges), in which case the modification is directly reflected in the original graph (and vice-versa), since they both point to the same underlying data. Because of this, instances of PropertyMap can be used interchangeably with a graph and its views.

The argument g must be an instance of a Graph class. If specified, vfilt and efilt select which vertices and edges are filtered, respectively. These parameters can either be a boolean-valued PropertyMap or a ndarray, which specify which vertices/edges are selected, or an unary function which returns True if a given vertex/edge is to be selected, or False otherwise.

The boolean parameter directed can be used to set the directionality of the graph view. If directed = None, the directionality is inherited from g.

If reversed = True, the direction of the edges is reversed.

If vfilt or efilt is anything other than a PropertyMap instance, the instantiation running time is \(O(V)\) and \(O(E)\), respectively. Otherwise, the running time is \(O(1)\).

If either skip_properties, skip_vfilt or skip_efilt is True, then the internal properties, vertex filter or edge filter of the original graph are ignored, respectively.

base

Base graph.

class graph_tool.Vertex

Vertex descriptor.

This class represents a vertex in a Graph instance.

Vertex instances are hashable, and are convertible to integers, corresponding to its index (see vertex_index).

all_edges()

Return an iterator over all edges (both in or out).

all_neighbours()

Return an iterator over all neighbours (both in or out).

get_graph()

Return the graph to which the vertex belongs.

in_degree()

Return the in-degree.

in_edges()

Return an iterator over the in-edges.

in_neighbours()

Return an iterator over the in-neighbours.

is_valid()

Return whether the vertex is valid.

out_degree()

Return the out-degree.

out_edges()

Return an iterator over the out-edges.

out_neighbours()

Return an iterator over the out-neighbours.

class graph_tool.Edge

Edge descriptor.

This class represents an edge in a Graph.

Edge instances are hashable, and are convertible to a tuple, which contains the source and target vertices.

get_graph()

Return the graph to which the edge belongs.

is_valid()

Return whether the edge is valid.

source()

Return the source vertex.

target()

Return the target vertex.

class graph_tool.PropertyMap(pmap, g, key_type)

This class provides a mapping from vertices, edges or whole graphs to arbitrary properties.

See Property maps for more details.

The possible property value types are listed below.

Type name Alias
bool uint8_t
int16_t short
int32_t int
int64_t long, long long
double float
long double  
string  
vector<bool> vector<uint8_t>
vector<int16_t> short
vector<int32_t> vector<int>
vector<int64_t> vector<long>, vector<long long>
vector<double> vector<float>
vector<long double>  
vector<string>  
python::object object
copy(value_type=None)

Return a copy of the property map. If value_type is specified, the value type is converted to the chosen type.

get_graph()

Get the graph class to which the map refers.

key_type()

Return the key type of the map. Either ‘g’, ‘v’ or ‘e’.

value_type()

Return the value type of the map.

python_value_type()

Return the python-compatible value type of the map.

get_array()

Get a PropertyArray with the property values.

Note

An array is returned only if the value type of the property map is a scalar. For vector, string or object types, None is returned instead. For vector and string objects, indirect array access is provided via the get_2d_array() and set_2d_array() member functions.

Warning

The returned array does not own the data, which belongs to the property map. Therefore, if the graph changes, the array may become invalid and any operation on it will fail with a ValueError exception. Do not store the array if the graph is to be modified; store a copy instead.

a

Shortcut to the get_array() method as an attribute. This makes assignments more convenient, e.g.:

>>> g = gt.Graph()
>>> g.add_vertex(10)
<...>
>>> prop = g.new_vertex_property("double")
>>> prop.a = np.random.random(10)           # Assignment from array
fa

The same as the a attribute, but instead an indexed array is returned, which contains only entries for vertices/edges which are not filtered out. If there are no filters in place, the array is not indexed, and is identical to the a attribute.

Note that because advanced indexing is triggered, a copy of the array is returned, not a view, as for the a attribute. Nevertheless, the assignment of values to the whole array at once works as expected.

ma

The same as the a attribute, but instead a MaskedArray object is returned, which contains only entries for vertices/edges which are not filtered out. If there are no filters in place, a regular PropertyArray is returned, which is identical to the a attribute.

get_2d_array(pos)

Return a two-dimensional array with a copy of the entries of the vector-valued property map. The parameter pos must be a sequence of integers which specifies the indexes of the property values which will be used.

set_2d_array(a, pos=None)

Set the entries of the vector-valued property map from a two-dimensional array a. If given, the parameter pos must be a sequence of integers which specifies the indexes of the property values which will be set.

is_writable()

Return True if the property is writable.

class graph_tool.PropertyArray

Bases: numpy.ndarray

This is a ndarray subclass which keeps a reference of its PropertyMap owner, and detects if the underlying data has been invalidated.

prop_map

PropertyMap owner instance.

graph_tool.load_graph(file_name, fmt='auto', ignore_vp=None, ignore_ep=None, ignore_gp=None)

Load a graph from file_name (which can be either a string or a file-like object).

The format is guessed from file_name, or can be specified by fmt, which can be either “xml”, “dot” or “gml”.

If provided, the parameters ignore_vp, ignore_ep and ignore_gp, should contain a list of property names (vertex, edge or graph, respectively) which should be ignored when reading the file.

graph_tool.group_vector_property(props, value_type=None, vprop=None, pos=None)

Group list of properties props into a vector property map of the same type.

Parameters:

props : list of PropertyMap

Properties to be grouped.

value_type : string (optional, default: None)

If supplied, defines the value type of the grouped property.

vprop : PropertyMap (optional, default: None)

If supplied, the properties are grouped into this property map.

pos : list of ints (optional, default: None)

If supplied, should contain a list of indexes where each corresponding element of props should be inserted.

Returns:

vprop : PropertyMap

A vector property map with the grouped values of each property map in props.

Examples

>>> from numpy.random import seed, randint
>>> from numpy import array
>>> seed(42)
>>> gt.seed_rng(42)
>>> g = gt.random_graph(100, lambda: (3, 3))
>>> props = [g.new_vertex_property("int") for i in range(3)]
>>> for i in range(3):
...    props[i].a = randint(0, 100, g.num_vertices())
>>> gprop = gt.group_vector_property(props)
>>> print(gprop[g.vertex(0)].a)
[51 25  8]
>>> print(array([p[g.vertex(0)] for p in props]))
[51 25  8]
graph_tool.ungroup_vector_property(vprop, pos, props=None)

Ungroup vector property map vprop into a list of individual property maps.

Parameters:

vprop : PropertyMap

Vector property map to be ungrouped.

pos : list of ints

A list of indexes corresponding to where each element of vprop should be inserted into the ungrouped list.

props : list of PropertyMap (optional, default: None)

If supplied, should contain a list of property maps to which vprop should be ungroupped.

Returns:

props : list of PropertyMap

A list of property maps with the ungrouped values of vprop.

Examples

>>> from numpy.random import seed, randint
>>> from numpy import array
>>> seed(42)
>>> gt.seed_rng(42)
>>> g = gt.random_graph(100, lambda: (3, 3))
>>> prop = g.new_vertex_property("vector<int>")
>>> for v in g.vertices():
...    prop[v] = randint(0, 100, 3)
>>> uprops = gt.ungroup_vector_property(prop, [0, 1, 2])
>>> print(prop[g.vertex(0)].a)
[51 92 14]
>>> print(array([p[g.vertex(0)] for p in uprops]))
[51 92 14]
graph_tool.infect_vertex_property(g, prop, vals=None)

Propagate the prop values of vertices with value val to all their out-neighbours.

Parameters:

prop : PropertyMap

Property map to be modified.

vals : list (optional, default: None)

List of values to be propagated. If not provided, all values will be propagated.

Returns:

None : None

Examples

>>> from numpy.random import seed
>>> seed(42)
>>> gt.seed_rng(42)
>>> g = gt.random_graph(100, lambda: (3, 3))
>>> prop = g.vertex_index.copy("int32_t")
>>> gt.infect_vertex_property(g, prop, [10])
>>> print(sum(prop.a == 10))
4
graph_tool.edge_difference(g, prop, ediff=None)

Return an edge property map corresponding to the difference between the values of prop of target and source vertices of each edge.

Parameters:

prop : PropertyMap

Vertex property map to be used to compute the difference..

ediff : PropertyMap (optional, default: None)

If provided, the difference values will be stored in this property map.

Returns:

ediff : PropertyMap

Edge differences.

Examples

>>> gt.seed_rng(42)
>>> g = gt.random_graph(100, lambda: (3, 3))
>>> ediff = gt.edge_difference(g, g.vertex_index)
>>> print(ediff.a)
[ 63  74  70 -19   1 -41 -54 -38 -68 -87 -85 -40 -41  -6  -3   4  12 -40
  -1   1 -47 -31 -49 -39  28 -37 -50 -32 -34 -12  -1  -4   5  10   8 -51
 -27  18  -3  45 -13  42   3 -31  25 -21  44 -28 -34  53  -5  -7  47 -26
  67   7  28 -24  30  50  24  39  43  45  64  78  74  84  -7  32  73  47
  34  70   2  -2 -78 -92  81  22  80  37  66  -2   1  26  95  26  62  66
  30   7  56  79  69  80  74  84   8  47  73  54  11  79  71  60  72  57
  41 -15  33 -15 -28  -4 -29 -13  -8 -40  -6   6 -19 -22  15  10  -7 -13
 -29 -10  32  -9 -30 -14 -63 -60  -2 -13 -39  10  12  14 -37 -29 -16 -65
   1 -52 -21 -49 -43 -57  54  31  62 -40 -66 -53 -12 -71 -92 -18 -49 -65
 -83 -80 -33 -67 -70 -58 -40 -53 -44 -71 -46 -75 -37 -44 -57  -3 -15 -76
   4  16 -55 -10   1 -33  16  -6  -7 -66 -49 -57 -58 -35 -32  20 -28 -58
   9  28   7 -67  29   6 -17 -54  -8 -31  24 -37 -29 -19  -5 -13  17 -39
 -25  17  25  62  65 -17  34  -7  12   3  17 -13  -5  40  74  80  36  73
  75  52   4  75  67  43  17  33  57  44  40  34 -26 -15  -5  31  30  51
 -17  21   5 -19  34  -1  12  -1  62 -27  33 -22  43 -22 -39  33 -24  41
 -37  17 -31  45 -40 -39 -36  49  16  36 -19  44  36 -51 -35 -13   4  14
 -44 -16  -8 -13   9 -29  10 -62 -26 -47 -44   3]
graph_tool.value_types()

Return a list of possible properties value types.

graph_tool.show_config()

Show graph_tool build configuration.

Table Of Contents

Previous topic

Module documentation

Next topic

graph_tool.centrality - Centrality measures

This Page

Latest development version docs are also available.