| shortest_distance (g[, source, weights, ...]) | Calculate the distance of all vertices from a given source, or the all pairs shortest paths, if the source is not specified. |
| shortest_path (g, source, target[, weights, pred_map]) | Return the shortest path from source to target. |
| isomorphism (g1, g2[, isomap]) | Check whether two graphs are isomorphic. |
| subgraph_isomorphism (sub, g) | Obtain all subgraph isomorphisms of sub in g. |
| mark_subgraph (g, sub, vmap, emap[, vmask, emask]) | Mark a given subgraph sub on the graph g. |
| min_spanning_tree (g[, weights, root, tree_map]) | Return the minimum spanning tree of a given graph. |
| dominator_tree (g, root[, dom_map]) | Return a vertex property map the dominator vertices for each vertex. |
| topological_sort (g) | Return the topological sort of the given graph. It is returned as an array of vertex indexes, in the sort order. |
| transitive_closure (g) | Return the transitive closure graph of g. |
| label_components (g[, vprop, directed]) | Label the components to which each vertex in the graph belongs. If the graph is directed, it finds the strongly connected components. |
| label_biconnected_components (g[, eprop, vprop]) | Label the edges of biconnected components, and the vertices which are articulation points. |
| is_planar (g[, embedding, kuratowski]) | Test if the graph is planar. |
Check whether two graphs are isomorphic.
If isomap is True, a vertex PropertyMap with the isomorphism mapping is returned as well.
Examples
>>> from numpy.random import seed
>>> seed(42)
>>> g = gt.random_graph(100, lambda: (3,3))
>>> g2 = gt.Graph(g)
>>> gt.isomorphism(g, g2)
True
>>> g.add_edge(g.vertex(0), g.vertex(1))
<...>
>>> gt.isomorphism(g, g2)
False
Obtain all subgraph isomorphisms of sub in g.
It returns two lists, containing the vertex and edge property maps for sub with the isomorphism mappings. The value of the properties are the vertex/edge index of the corresponding vertex/edge in g.
Notes
The algorithm used is described in [ullmann-algorithm-1976]. It has worse-case complexity of O(N_g^{N_{sub}}), but for random graphs it typically has a complexity of O(N_g^\gamma) with \gamma depending sub-linearly on the size of sub.
References
| [ullmann-algorithm-1976] | Ullmann, J. R., “An algorithm for subgraph isomorphism”, Journal of the ACM 23 (1): 31–42, 1976, doi:10.1145/321921.321925 |
| [subgraph-isormophism-wikipedia] | http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem |
Examples
>>> from numpy.random import seed, poisson
>>> seed(42)
>>> g = gt.random_graph(30, lambda: (poisson(6),poisson(6)))
>>> sub = gt.random_graph(10, lambda: (poisson(1.8), poisson(1.9)))
>>> vm, em = gt.subgraph_isomorphism(sub, g)
>>> print len(vm)
175
>>> for i in xrange(len(vm)):
... g.set_vertex_filter(None)
... g.set_edge_filter(None)
... vmask, emask = gt.mark_subgraph(g, sub, vm[i], em[i])
... g.set_vertex_filter(vmask)
... g.set_edge_filter(emask)
... assert(gt.isomorphism(g, sub))
>>> g.set_vertex_filter(None)
>>> g.set_edge_filter(None)
>>> ewidth = g.copy_property(emask, value_type="double")
>>> ewidth.a *= 1.5
>>> ewidth.a += 0.5
>>> gt.graph_draw(g, vcolor=vmask, ecolor=emask, penwidth=ewidth,
... output="subgraph-iso-embed.png")
<...>
>>> gt.graph_draw(sub, output="subgraph-iso.png")
<...>
Mark a given subgraph sub on the graph g.
The mapping must be provided by the vmap and emap parameters, which map vertices/edges of sub to indexes of the corresponding vertices/edges in g.
This returns a vertex and an edge property map, with value type ‘bool’, indicating whether or not a vertex/edge in g corresponds to the subgraph sub.
Return the minimum spanning tree of a given graph.
| Parameters: | g : Graph
weights : PropertyMap (optional, default: None)
root : Vertex (optional, default: None)
tree_map : PropertyMap (optional, default: None)
|
|---|---|
| Returns: | tree_map : PropertyMap
|
Notes
The algorithm runs with O(E\log E) complexity, or O(E\log V) if root is specified.
References
| [kruskal-shortest-1956] | J. B. Kruskal. “On the shortest spanning subtree of a graph and the traveling salesman problem”, In Proceedings of the American Mathematical Sofiety, volume 7, pages 48-50, 1956. |
| [prim-shortest-1957] | R. Prim. “Shortest connection networks and some generalizations”, Bell System Technical Journal, 36:1389-1401, 1957. |
| [boost-mst] | http://www.boost.org/libs/graph/doc/graph_theory_review.html#sec:minimum-spanning-tree |
| [mst-wiki] | http://en.wikipedia.org/wiki/Minimum_spanning_tree |
Examples
>>> from numpy.random import seed
>>> seed(42)
>>> g = gt.random_graph(100, lambda: (5, 5))
>>> tree = gt.min_spanning_tree(g)
>>> print tree.a
[0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1
0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1
0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0
1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0]
Return a vertex property map the dominator vertices for each vertex.
| Parameters: | g : Graph
root : Vertex
dom_map : PropertyMap (optional, default: None)
|
|---|---|
| Returns: | dom_map : PropertyMap
|
Notes
A vertex u dominates a vertex v, if every path of directed graph from the entry to v must go through u.
The algorithm runs with O((V+E)\log (V+E)) complexity.
References
| [dominator-bgl] | http://www.boost.org/libs/graph/doc/lengauer_tarjan_dominator.htm |
Examples
>>> from numpy.random import seed
>>> seed(42)
>>> g = gt.random_graph(100, lambda: (2, 2))
>>> tree = gt.min_spanning_tree(g)
>>> g.set_edge_filter(tree)
>>> root = [v for v in g.vertices() if v.in_degree() == 0]
>>> dom = gt.dominator_tree(g, root[0])
>>> print dom.a
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0 0 0
78 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 26 0 0
0 0 0 20 0 0 0 0 0 0 0 50 0 0 0 0 0 0 0 0 0 0 0 0 0]
Return the topological sort of the given graph. It is returned as an array of vertex indexes, in the sort order.
Notes
The topological sort algorithm creates a linear ordering of the vertices such that if edge (u,v) appears in the graph, then v comes before u in the ordering. The graph must be a directed acyclic graph (DAG).
The time complexity is O(V + E).
References
| [topological-boost] | http://www.boost.org/libs/graph/doc/topological_sort.html |
| [topological-wiki] | http://en.wikipedia.org/wiki/Topological_sorting |
Examples
>>> from numpy.random import seed
>>> seed(42)
>>> g = gt.random_graph(30, lambda: (3, 3))
>>> tree = gt.min_spanning_tree(g)
>>> g.set_edge_filter(tree)
>>> sort = gt.topological_sort(g)
>>> print sort
[25 24 0 15 5 14 4 7 19 9 20 3 12 28 22 16 1 13 8 2 6 27 10 29 21
11 17 18 23 26]
Return the transitive closure graph of g.
Notes
The transitive closure of a graph G = (V,E) is a graph G* = (V,E*) such that E* contains an edge (u,v) if and only if G contains a path (of at least one edge) from u to v. The transitive_closure() function transforms the input graph g into the transitive closure graph tc.
The time complexity (worst-case) is O(VE).
References
| [transitive-boost] | http://www.boost.org/libs/graph/doc/transitive_closure.html |
| [transitive-wiki] | http://en.wikipedia.org/wiki/Transitive_closure |
Examples
>>> from numpy.random import seed
>>> seed(42)
>>> g = gt.random_graph(30, lambda: (3, 3))
>>> tc = gt.transitive_closure(g)
Label the components to which each vertex in the graph belongs. If the graph is directed, it finds the strongly connected components.
| Parameters: | g : Graph
vprop : PropertyMap (optional, default: None)
directed : bool (optional, default:None)
|
|---|---|
| Returns: | comp : PropertyMap
|
Notes
The components are arbitrarily labeled from 0 to N-1, where N is the total number of components.
The algorithm runs in O(V + E) time.
Examples
>>> from numpy.random import seed
>>> seed(43)
>>> g = gt.random_graph(100, lambda: (1, 1))
>>> comp = gt.label_components(g)
>>> print comp.get_array()
[0 0 0 0 1 0 2 1 0 1 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 2 0 1 0 0 1 0 0 2 0 0 0
2 2 0 0 0 2 0 0 0 0 0 2 0 0 0 0 2 0 0 0 0 1 0 0 2 2 0 1 0 1 0 0 0 0 0 1 1
0 2 1 0 0 2 0 0 2 0 3 2 0 0 3 2 0 0 0 0 0 0 1 1 1 0]
Label the edges of biconnected components, and the vertices which are articulation points.
| Parameters: | g : Graph
eprop : PropertyMap (optional, default: None)
vprop : PropertyMap (optional, default: None)
|
|---|---|
| Returns: | bicomp : PropertyMap
articulation : PropertyMap
nc : int
|
Notes
A connected graph is biconnected if the removal of any single vertex (and all edges incident on that vertex) can not disconnect the graph. More generally, the biconnected components of a graph are the maximal subsets of vertices such that the removal of a vertex from a particular component will not disconnect the component. Unlike connected components, vertices may belong to multiple biconnected components: those vertices that belong to more than one biconnected component are called “articulation points” or, equivalently, “cut vertices”. Articulation points are vertices whose removal would increase the number of connected components in the graph. Thus, a graph without articulation points is biconnected. Vertices can be present in multiple biconnected components, but each edge can only be contained in a single biconnected component.
The algorithm runs in O(V + E) time.
Examples
>>> from numpy.random import seed
>>> seed(42)
>>> g = gt.random_graph(100, lambda: 2, directed=False)
>>> comp, art, nc = gt.label_biconnected_components(g)
>>> print comp.a
[0 0 3 2 0 3 1 0 2 0 0 0 1 3 2 0 1 0 1 0 1 1 2 1 0 3 1 0 1 0 0 0 2 0 0 0 1
0 0 0 0 1 3 0 0 2 2 0 2 0 0 1 3 2 0 1 3 2 2 1 0 0 0 0 1 0 2 0 2 0 1 0 2 2
0 2 0 2 1 0 1 0 0 0 1 0 2 0 1 1 0 1 0 1 2 0 0 2 2 2]
>>> print art.a
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
>>> print nc
4
Calculate the distance of all vertices from a given source, or the all pairs shortest paths, if the source is not specified.
| Parameters: | g : Graph
source : Vertex (optional, default: None)
weights : PropertyMap (optional, default: None)
max_dist : scalar value (optional, default: None)
directed : bool (optional, default:None)
dense : bool (optional, default: False)
dist_map : PropertyMap (optional, default: None)
pred_map : bool (optional, default: False)
|
|---|---|
| Returns: | dist_map : PropertyMap
|
Notes
If a source is given, the distances are calculated with a breadth-first search (BFS) or Dijkstra’s algorithm [dijkstra], if weights are given. If source is not given, the distances are calculated with Johnson’s algorithm [johnson-apsp]. If dense=True, the Floyd-Warshall algorithm [floyd-warshall-apsp] is used instead.
If source is specified, the algorithm runs in O(V + E) time, or O(V \log V) if weights are given. If source is not specified, it runs in O(VE\log V) time, or O(V^3) if dense == True.
References
| [bfs] | Edward Moore, “The shortest path through a maze”, International Symposium on the Theory of Switching (1959), Harvard University Press;http://www.boost.org/libs/graph/doc/breadth_first_search.html |
| [dijkstra] | E. Dijkstra, “A note on two problems in connexion with graphs.” Numerische Mathematik, 1:269-271, 1959. http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html |
| [johnson-apsp] | http://www.boost.org/libs/graph/doc/johnson_all_pairs_shortest.html |
| [floyd-warshall-apsp] | http://www.boost.org/libs/graph/doc/floyd_warshall_shortest.html |
Examples
>>> from numpy.random import seed, poisson
>>> seed(42)
>>> g = gt.random_graph(100, lambda: (poisson(3), poisson(3)))
>>> dist = gt.shortest_distance(g, source=g.vertex(0))
>>> print dist.get_array()
[ 0 4 4 4 2147483647 3
3 2 2 3 4 4
5 2 3 1 4 2
4 4 6 2 2147483647 5
2 4 4 5 4 5
3 3 2 2 1 4
2 4 5 4 2147483647 4
3 3 3 3 3 3
6 4 4 1 5 3
3 2 2 5 2 4
3 4 5 4 3 2147483647
5 4 3 2 2 2147483647
4 4 5 2 3 5
4 5 4 4 3 2147483647
5 3 2147483647 3 3 4
3 3 3 1 5 5
2 3 4 3]
>>> dist = gt.shortest_distance(g)
>>> print array(dist[g.vertex(0)])
[ 0 4 4 4 2147483647 3
3 2 2 3 4 4
5 2 3 1 4 2
4 4 6 2 2147483647 5
2 4 4 5 4 5
3 3 2 2 1 4
2 4 5 4 2147483647 4
3 3 3 3 3 3
6 4 4 1 5 3
3 2 2 5 2 4
3 4 5 4 3 2147483647
5 4 3 2 2 2147483647
4 4 5 2 3 5
4 5 4 4 3 2147483647
5 3 2147483647 3 3 4
3 3 3 1 5 5
2 3 4 3]
Return the shortest path from source to target.
| Parameters: | g : Graph
source : Vertex
source : Vertex
weights : PropertyMap (optional, default: None)
pred_map : PropertyMap (optional, default: None)
|
|---|---|
| Returns: | vertex_list : list of Vertex
edge_list : list of Edge
|
Notes
The paths are computed with a breadth-first search (BFS) or Dijkstra’s algorithm [dijkstra], if weights are given.
The algorithm runs in O(V + E) time, or O(V \log V) if weights are given.
References
| [bfs] | Edward Moore, “The shortest path through a maze”, International Symposium on the Theory of Switching (1959), Harvard University Press;http://www.boost.org/libs/graph/doc/breadth_first_search.html |
| [dijkstra] | E. Dijkstra, “A note on two problems in connexion with graphs.” Numerische Mathematik, 1:269-271, 1959. http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html |
Examples
>>> from numpy.random import seed, poisson
>>> seed(42)
>>> g = gt.random_graph(300, lambda: (poisson(3), poisson(3)))
>>> vlist, elist = gt.shortest_path(g, g.vertex(10), g.vertex(11))
>>> print [str(v) for v in vlist]
['10', '283', '20', '158', '104', '25', '275', '75', '11']
>>> print [str(e) for e in elist]
['(10,283)', '(283,20)', '(20,158)', '(158,104)', '(104,25)', '(25,275)', '(275,75)', '(75,11)']
Test if the graph is planar.
| Parameters: | g : Graph
embedding : bool (optional, default: False)
kuratowski : bool (optional, default: False)
|
|---|---|
| Returns: | is_planar : bool
embedding : PropertyMap (only if embedding=True)
kuratowski : PropertyMap (only if kuratowski=True)
|
Notes
A graph is planar if it can be drawn in two-dimensional space without any of its edges crossing. This algorithm performs the Boyer-Myrvold planarity testing [boyer-myrvold]. See [boost-planarity] for more details.
This algorithm runs in O(V) time.
References
| [boyer-myrvold] | John M. Boyer and Wendy J. Myrvold, “On the Cutting Edge: Simplified O(n) Planarity by Edge Addition Journal of Graph Algorithms and Applications”, 8(2): 241-273, 2004. |
| [boost-planarity] | http://www.boost.org/libs/graph/doc/boyer_myrvold.html |
Examples
>>> from numpy.random import seed, random
>>> seed(42)
>>> g = gt.triangulation(random((100,2)))[0]
>>> p, embed_order = gt.is_planar(g, embedding=True)
>>> print p
True
>>> print list(embed_order[g.vertex(0)])
[0, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
>>> g = gt.random_graph(100, lambda: 4, directed=False)
>>> p, kur = gt.is_planar(g, kuratowski=True)
>>> print p
False
>>> g.set_edge_filter(kur, True)
>>> gt.graph_draw(g, layout="arf", size=(7,7), output="kuratowski.png")
<...>
Obstructing Kuratowski subgraph of a random graph.
graph_tool.generation - Random graph generation
graph_tool.flow - Maximum flow algorithms
Enter search terms or a module, class or function name.