graph-tool is an efficient Python

Python (programming language)

Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...

 module for manipulation and statistical analysis of graphs

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 (a.k.a. networks

Network theory

Network theory is an area of computer science and network science and part of graph theory. It has application in many disciplines including statistical physics, particle physics, computer science, biology, economics, operations research, and sociology...

). Contrary to most other python modules with similar functionality, the core data structures and algorithms of graph-tool are implemented in C++

C++

C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...

, making extensive use of metaprogramming

Metaprogramming

Metaprogramming is the writing of computer programs that write or manipulate other programs as their data, or that do part of the work at compile time that would otherwise be done at runtime...

, based heavily on the Boost Graph Library. This confers a level of performance which is comparable (both in memory usage and computation time) to that of a pure C++

C++

C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...

 library.

Furthermore, many algorithms are implemented in parallel using OpenMP

OpenMP

OpenMP is an API that supports multi-platform shared memory multiprocessing programming in C, C++, and Fortran, on most processor architectures and operating systems, including Linux, Unix, AIX, Solaris, Mac OS X, and Microsoft Windows platforms...

, which provides excellent performance on multi-core architectures, without degrading the performance on single-core machines.

Features

• Creation and manipulation of directed
  Directed graph
  A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
  
   or undirected graphs
  Graph (mathematics)
  In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
  
  .
• Association of arbitrary information to the vertices, edges or even the graph itself, by means of property maps.
• Filter vertices and/or edges "on the fly", such that they appear to have been removed.
• Support for dot
  DOT language
  DOT is a plain text graph description language. It is a simple way of describing graphs that both humans and computer programs can use. DOT graphs are typically files that end with the .gv extension. The .gv extension is preferred, as .dot also is used by Microsoft Office 2003.Various programs...
  
   and GraphML
  GraphML
  GraphML is an XML-based file format for graphs. The GraphML file format results from the joint effort of the graph drawing community to define a common format for exchanging graph structure data...
  
   formats.
• Convenient and powerful graph drawing
  Graph drawing
  Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
  
   based on Graphviz
  Graphviz
  Graphviz is a package of open-source tools initiated by AT&T Labs Research for drawing graphs specified in DOT language scripts. It also provides libraries for software applications to use the tools...
  
  .
• Support for typical statistical measurements: degree/property histogram, combined degree/property histogram, vertex-vertex correlations, assortativity
  Assortativity
  Assortativity is a preference for a network's nodes to attach to others that are similar or different in some way. Though the specific measure of similarity may vary, network theorists often examine assortativity in terms of a node's degree...
  
  , average vertex-vertex shortest path, etc.
• Support for several graph-theoretical algorithms: such as graph isomorphism
  Graph isomorphism
  In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
  
  , subgraph isomormism
  Subgraph isomorphism problem
  In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs G and H are given as input, and one must determine whether G contains a subgraph that is isomorphic to H....
  
  , minimum spanning tree
  Minimum spanning tree
  Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
  
  , connected components, dominator
  Dominator
  In computer science, in control flow graphs, a node d dominates a node n if every path from the start node to n must go through d. Notationally, this is written as d dom n...
  
   tree, maximum flow, etc.
• Support for several centrality
  Centrality
  Within graph theory and network analysis, there are various measures of the centrality of a vertex within a graph that determine the relative importance of a vertex within the graph...
  
   measures.
• Support for clustering coefficients
  Clustering coefficient
  In graph theory, a clustering coefficient is a measure of degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties...
  
  , as well as network motif
  Network motif
  Network motifs are connectivity-patterns that occur much more often than they do in random networks. Most networks studied in biology, ecology and other fields have been found to show a small set of network motifs; surprisingly, in most cases the networks seem to be largely composed of these...
  
   statistics and community structure
  Community structure
  In the study of complex networks, a network is said to have community structure if the nodes of the network can be easily grouped into sets of nodes such that each set of nodes is densely connected internally...
  
   detection.
• Generation of random graphs, with arbitrary degree distribution and correlations.
• Support for well-established network models: Price
  Preferential attachment
  A preferential attachment process is any of a class of processes in which some quantity, typically some form of wealth or credit, is distributed among a number of individuals or objects according to how much they already have, so that those who are already wealthy receive more than those who are not...
  
  , Barabási-Albert, Geometric Networks, Multidimensional lattice graph
  Lattice graph
  The terms lattice graph, mesh graph, or grid graph refer to a number of categories of graphs whose drawing corresponds to some grid/mesh/lattice, i.e., its vertices correspond to the nodes of the mesh and its edges correspond to the ties between the nodes.-Square grid graph:A common type of a...
  
  , etc.