| 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:
- 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 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)
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.
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 i-th 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 out-degree 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.
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.
Remove an edge from the graph.
The following functions allow for easy removal of vertices of edges from the graph.
Remove all vertices and edges from the graph.
Remove all in and out-edges 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.
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 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.
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!)
foo (vertex) (type: double)
bar (vertex) (type: python::object)
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 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.
Remove all edges of the graph which are currently being filtered out, and return it to the unfiltered state. This operation is not reversible.
Stash current filter state and set the graph to its unfiltered state. The optional keyword arguments specify which type of filter should be stashed.
Pop last stashed filter state. The optional keyword arguments specify which type of filter should be recovered.
Return a copy of the filter state of the graph.
Set the filter state of the graph.
See Graph I/O for more details.
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 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”.
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)\).
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 in-degree.
Return an iterator over the in-edges.
Return an iterator over the in-neighbours.
Return whether the vertex is valid.
Return the out-degree.
Return an iterator over the out-edges.
Return an iterator over the out-neighbours.
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 python-compatible 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 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 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.
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 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.
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 out-neighbours.
| 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.