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 filelike 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 outneighbours. 
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:
 A Graph class for graph representation and manipulation
 Property maps for Vertex, Edge or Graph.
 Fast algorithms implemented in C++.
Documentation is available in two forms: docstrings provided with the code, and the full documentation available in the graphtool homepage.
We recommend exploring the docstrings using IPython, an advanced Python shell with TABcompletion 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 greaterthan signs:
>>> x = x + 1
Use the builtin help function to view a function’s docstring:
>>> help(gt.Graph)
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.
Return a deep copy of self. All internal property maps are also copied.
See Iterating over vertices and edges for more documentation and examples.
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)
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.
Return the vertex with index i. If use_index=False, the ith vertex is returned (which can differ from the vertex with index i in case of filtered graphs).
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 outdegree of vertex \(s\).
Get the number of vertices.
Note
If the vertices are being filtered, this operation is \(O(N)\). Otherwise it is \(O(1)\).
Get the number of edges.
Note
If the edges are being filtered, this operation is \(O(E)\). Otherwise it is \(O(1)\).
The following functions allow for addition and removal of vertices in the graph.
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 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 a new edge from source to target to the graph, and return it. This operation is \(O(1)\).
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 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.
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.
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.
Remove all vertices and edges from the graph.
Remove all in and outedges from the given vertex.
Remove all edges from the graph.
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 the directedness of the graph.
Get the directedness of the graph.
Reverse the direction of the edges, if is_reversed is True, or maintain the original direction otherwise.
Return True if the edges are reversed, and False otherwise.
Create a new (uninitialized) vertex property map of key type key_type (v, e or g), value type value_type, and return it.
Create a new (uninitialized) vertex property map of type value_type, and return it.
Create a new (uninitialized) edge property map of type value_type, and return it.
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 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).
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.
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 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.
The maximum value of the edge index map.
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 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 oneway proxy to the internallykept properties. If you modify this object, the change will be propagated to the internal dictionary, but not viceversa. Keep this in mind if you intend to keep a copy of the returned object.
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")]
Dictionary of internal vertex properties. The keys are the property names.
Alias to vertex_properties.
Dictionary of internal edge properties. The keys are the property names.
Alias to edge_properties.
Dictionary of internal graph properties. The keys are the property names.
Alias to graph_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>)
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.
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.
Return a tuple with the vertex filter property and bool value indicating whether or not it is inverted.
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.
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.
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 reindex 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.
Remove all edges of the graph which are currently being filtered out, and return it to the unfiltered state. This operation is not reversible.
See Graph I/O for more details.
Load graph from file_name (which can be either a string or a filelike 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 graph to file_name (which can be either a string or a filelike object). The format is guessed from the file_name, or can be specified by fmt, which can be either “xml”, “dot” or “gml”.
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 viceversa), 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 booleanvalued 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 graph.
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).
Return an iterator over all edges (both in or out).
Return an iterator over all neighbours (both in or out).
Return the graph to which the vertex belongs.
Return the indegree.
Return an iterator over the inedges.
Return an iterator over the inneighbours.
Return whether the vertex is valid.
Return the outdegree.
Return an iterator over the outedges.
Return an iterator over the outneighbours.
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.
Return the graph to which the edge belongs.
Return whether the edge is valid.
Return the source vertex.
Return the target vertex.
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 
Return a copy of the property map. If value_type is specified, the value type is converted to the chosen type.
Get the graph class to which the map refers.
Return the key type of the map. Either ‘g’, ‘v’ or ‘e’.
Return the value type of the map.
Return the pythoncompatible value type of the map.
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.
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
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.
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.
Return a twodimensional array with a copy of the entries of the vectorvalued property map. The parameter pos must be a sequence of integers which specifies the indexes of the property values which will be used.
Set the entries of the vectorvalued property map from a twodimensional 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.
Return True if the property is writable.
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.
PropertyMap owner instance.
Load a graph from file_name (which can be either a string or a filelike 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.
Group list of properties props into a vector property map of the same type.
Parameters:  props : list of PropertyMap
value_type : string (optional, default: None)
vprop : PropertyMap (optional, default: None)
pos : list of ints (optional, default: None)


Returns:  vprop : PropertyMap

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]
Ungroup vector property map vprop into a list of individual property maps.
Parameters:  vprop : PropertyMap
pos : list of ints
props : list of PropertyMap (optional, default: None)


Returns:  props : list of PropertyMap

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]
Propagate the prop values of vertices with value val to all their outneighbours.
Parameters:  prop : PropertyMap
vals : list (optional, default: None)


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
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
ediff : PropertyMap (optional, default: None)


Returns:  ediff : PropertyMap

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]
Return a list of possible properties value types.
Show graph_tool build configuration.