Class GraphBase

Generates a graph from its adjacency matrix.

Parameters:

• matrix - the adjacency matrix
• mode - the mode to be used. Possible values are:
  • ADJ_DIRECTED - the graph will be directed and a matrix element gives the number of edges between two vertex.
  • ADJ_UNDIRECTED - alias to ADJ_MAX for convenience.
  • ADJ_MAX - undirected graph will be created and the number of edges between vertex i and j is max(A(i,j), A(j,i))
  • ADJ_MIN - like ADJ_MAX, but with min(A(i,j), A(j,i))
  • ADJ_PLUS - like ADJ_MAX, but with A(i,j) + A(j,i)
  • ADJ_UPPER - undirected graph with the upper right triangle of the matrix (including the diagonal)
  • ADJ_LOWER - undirected graph with the lower left triangle of the matrix (including the diagonal)

  These values can also be given as strings without the ADJ prefix.

Generates a graph based on asymmetric vertex types and connection probabilities.

This is the asymmetric variant of Graph.Preference. A given number of vertices are generated. Every vertex is assigned to an "incoming" and an "outgoing" vertex type according to the given joint type probabilities. Finally, every vertex pair is evaluated and a directed edge is created between them with a probability depending on the "outgoing" type of the source vertex and the "incoming" type of the target vertex.

Parameters:

• n - the number of vertices in the graph
• type_dist_matrix - matrix giving the joint distribution of vertex types
• pref_matrix - matrix giving the connection probabilities for different vertex types.
• attribute - the vertex attribute name used to store the vertex types. If None, vertex types are not stored.
• loops - whether loop edges are allowed.

Generates a graph from the Graph Atlas.

Parameters:

• idx - The index of the graph to be generated. Indices start from zero, graphs are listed:
  1. in increasing order of number of nodes;
  2. for a fixed number of nodes, in increasing order of the number of edges;
  3. for fixed numbers of nodes and edges, in increasing order of the degree sequence, for example 111223 < 112222;
  4. for fixed degree sequence, in increasing number of automorphisms.

Generates a graph based on the Barabasi-Albert model.

Parameters:

• n - the number of vertices
• m - either the number of outgoing edges generated for each vertex or a list containing the number of outgoing edges for each vertex explicitly.
• outpref - True if the out-degree of a given vertex should also increase its citation probability (as well as its in-degree), but it defaults to False.
• directed - True if the generated graph should be directed (default: False).
• power - the power constant of the nonlinear model. It can be omitted, and in this case the usual linear model will be used.
• zero_appeal - the attractivity of vertices with degree zero.

Generates a de Bruijn graph with parameters (m, n)

A de Bruijn graph represents relationships between strings. An alphabet of m letters are used and strings of length n are considered. A vertex corresponds to every possible string and there is a directed edge from vertex v to vertex w if the string of v can be transformed into the string of w by removing its first letter and appending a letter to it.

Please note that the graph will have m^n vertices and even more edges, so probably you don't want to supply too big numbers for m and n.

Parameters:

• m - the size of the alphabet
• n - the length of the strings

Generates a graph with a given degree sequence.

Parameters:

• out - the out-degree sequence for a directed graph. If the in-degree sequence is omitted, the generated graph will be undirected, so this will be the in-degree sequence as well
• in - the in-degree sequence for a directed graph. If omitted, the generated graph will be undirected.
• method - the generation method to be used. One of the following:
  • "simple" -- simple generator that sometimes generates loop edges and multiple edges. The generated graph is not guaranteed to be connected.
  • "vl" -- a more sophisticated generator that can sample undirected, connected simple graphs uniformly. It uses Monte-Carlo methods to randomize the graphs. This generator should be favoured if undirected and connected graphs are to be generated. igraph uses the original implementation of Fabien Viger; see the following URL and the paper cited on it for the details of the algorithm: http://www-rp.lip6.fr/~latapy/FV/generation.html.

Generates a graph based on the Erdos-Renyi model.

Parameters:

• n - the number of vertices.
• p - the probability of edges. If given, m must be missing.
• m - the number of edges. If given, p must be missing.
• directed - whether to generate a directed graph.
• loops - whether self-loops are allowed.

Generates a graph based on a simple growing model with vertex types.

A single vertex is added at each time step. This new vertex tries to connect to k vertices in the graph. The probability that such a connection is realized depends on the types of the vertices involved.

Parameters:

• n - the number of vertices in the graph
• k - the number of connections tried in each step
• type_dist - list giving the distribution of vertex types
• pref_matrix - matrix (list of lists) giving the connection probabilities for different vertex types
• directed - whether to generate a directed graph.

Generates a famous graph based on its name.

Several famous graphs are known to igraph including (but not limited to) the Chvatal graph, the Petersen graph or the Tutte graph. This method generates one of them based on its name (case insensitive). See the documentation of the C interface of igraph for the names available: http://cneurocvs.rmki.kfki.hu/igraph/doc/html/igraph-Generators.html.

Parameters:

• name - the name of the graph to be generated.

Generates a graph based on the forest fire model

The forest fire model is a growin graph model. In every time step, a new vertex is added to the graph. The new vertex chooses an ambassador (or more than one if ambs>1) and starts a simulated forest fire at its ambassador(s). The fire spreads through the edges. The spreading probability along an edge is given by fw_prob. The fire may also spread backwards on an edge by probability fw_prob * bw_factor. When the fire ended, the newly added vertex connects to the vertices ``burned'' in the previous fire.

Parameters:

• n - the number of vertices in the graph
• fw_prob - forward burning probability
• bw_factor - ratio of backward and forward burning probability
• ambs - number of ambassadors chosen in each step
• directed - whether the graph will be directed

Generates a full graph (directed or undirected, with or without loops).

Parameters:

• n - the number of vertices.
• directed - whether to generate a directed graph.
• loops - whether self-loops are allowed.

Generates a full citation graph

A full citation graph is a graph where the vertices are indexed from 0 to n-1 and vertex i has a directed edge towards all vertices with an index less than i.

Parameters:

• n - the number of vertices.
• directed - whether to generate a directed graph.

Generates a random geometric graph.

The algorithm drops the vertices randomly on the 2D unit square and connects them if they are closer to each other than the given radius.

Parameters:

• n - The number of vertices in the graph
• radius - The given radius
• torus - This should be True if we want to use a torus instead of a square.
• return_coordinates - whether the X and Y coordinates of the vertices should be returned. If True, a list for each dimension will be returned along with the graph, packed in a tuple.

Generates a growing random graph.

Parameters:

• n - The number of vertices in the graph
• m - The number of edges to add in each step (after adding a new vertex)
• directed - whether the graph should be directed.
• citation - whether the new edges should originate from the most recently added vertex.

Generates a graph with a given isomorphy class.

Parameters:

• n - the number of vertices in the graph (3 or 4)
• class - the isomorphy class
• directed - whether the graph should be directed.

Generates a Kautz graph with parameters (m, n)

A Kautz graph is a labeled graph, vertices are labeled by strings of length n+1 above an alphabet with m+1 letters, with the restriction that every two consecutive letters in the string must be different. There is a directed edge from a vertex v to another vertex w if it is possible to transform the string of v into the string of w by removing the first letter and appending a letter to it.

Parameters:

• m - the size of the alphabet minus one
• n - the length of the strings minus one

Generates a graph from LCF notation.

LCF is short for Lederberg-Coxeter-Frucht, it is a concise notation for 3-regular Hamiltonian graphs. It consists of three parameters, the number of vertices in the graph, a list of shifts giving additional edges to a cycle backbone and another integer giving how many times the shifts should be performed. See http://mathworld.wolfram.com/LCFNotation.html for details.

Parameters:

• n - the number of vertices
• shifts - the shifts in a list or tuple
• repeats - the number of repeats

Generates a regular lattice.

Parameters:

• dim - list with the dimensions of the lattice
• nei - value giving the distance (number of steps) within which two vertices will be connected. Not implemented yet.
• directed - whether to create a directed graph.
• mutual - whether to create all connections as mutual in case of a directed graph.
• circular - whether the generated lattice is periodic.

Generates a graph based on vertex types and connection probabilities.

This is practically the nongrowing variant of Graph.Establishment. A given number of vertices are generated. Every vertex is assigned to a vertex type according to the given type probabilities. Finally, every vertex pair is evaluated and an edge is created between them with a probability depending on the types of the vertices involved.

Parameters:

• n - the number of vertices in the graph
• type_dist - list giving the distribution of vertex types
• pref_matrix - matrix giving the connection probabilities for different vertex types.
• attribute - the vertex attribute name used to store the vertex types. If None, vertex types are not stored.
• directed - whether to generate a directed graph.
• loops - whether loop edges are allowed.

Reads a graph from a file conforming to the DIMACS minimum-cost flow file format.

For the exact description of the format, see http://lpsolve.sourceforge.net/5.5/DIMACS.htm

Restrictions compared to the official description of the format:

• igraph's DIMACS reader requires only three fields in an arc definition, describing the edge's source and target node and its capacity.
• Source nodes are identified by 's' in the FLOW field, target nodes are identified by 't'.
• Node indices start from 1. Only a single source and target node is allowed.

Parameters:

• f - the name of the file or a Python file handle
• directed - whether the generated graph should be directed.

Returns:

the generated graph, the source and the target of the flow and the edge capacities in a tuple

Reads an edge list from a file and creates a graph based on it.

Please note that the vertex indices are zero-based.

Parameters:

• f - the name of the file or a Python file handle
• directed - whether the generated graph should be directed.

Reads a GML file and creates a graph based on it.

Parameters:

• f - the name of the file or a Python file handle

Reads a GraphML format file and creates a graph based on it.

Parameters:

• f - the name of the file or a Python file handle
• index - if the GraphML file contains multiple graphs, specifies the one that should be loaded. Graph indices start from zero, so if you want to load the first graph, specify 0 here.

Reads an .lgl file used by LGL.

It is also useful for creating graphs from "named" (and optionally weighted) edge lists.

This format is used by the Large Graph Layout program. See the documentation of LGL regarding the exact format description.

LGL originally cannot deal with graphs containing multiple or loop edges, but this condition is not checked here, as igraph is happy with these.

Parameters:

• f - the name of the file or a Python file handle
• names - If True, the vertex names are added as a vertex attribute called 'name'.
• weights - If True, the edge weights are added as an edge attribute called 'weight'.

Reads an .ncol file used by LGL.

It is also useful for creating graphs from "named" (and optionally weighted) edge lists.

This format is used by the Large Graph Layout program. See the documentation of LGL regarding the exact format description.

LGL originally cannot deal with graphs containing multiple or loop edges, but this condition is not checked here, as igraph is happy with these.

Parameters:

• f - the name of the file or a Python file handle
• names - If True, the vertex names are added as a vertex attribute called 'name'.
• weights - If True, the edge weights are added as an edge attribute called 'weight'.
• directed - whether the graph being created should be directed

Reads a Pajek format file and creates a graph based on it.

Parameters:

• f - the name of the file or a Python file handle

Generates a graph based on a stochastic model where the probability of an edge gaining a new node is proportional to the edges gained in a given time window.

Parameters:

• n - the number of vertices
• m - either the number of outgoing edges generated for each vertex or a list containing the number of outgoing edges for each vertex explicitly.
• window - size of the window in time steps
• outpref - True if the out-degree of a given vertex should also increase its citation probability (as well as its in-degree), but it defaults to False.
• directed - True if the generated graph should be directed (default: False).
• power - the power constant of the nonlinear model. It can be omitted, and in this case the usual linear model will be used.

Generates a ring graph.

Parameters:

• n - the number of vertices in the ring
• directed - whether to create a directed ring.
• mutual - whether to create mutual edges in a directed ring.
• circular - whether to create a closed ring.

Generates a star graph.

Parameters:

• n - the number of vertices in the graph
• mode - Gives the type of the star graph to create. Should be one of the constants STAR_OUT, STAR_IN and STAR_UNDIRECTED.
• center - Vertex ID for the central vertex in the star.

Generates a tree in which almost all vertices have the same number of children.

Parameters:

• n - the number of vertices in the graph
• children - the number of children of a vertex in the graph
• type - determines whether the tree should be directed, and if this is the case, also its orientation. Must be one of TREE_IN, TREE_OUT and TREE_UNDIRECTED.

Parameters:

• dim - the dimension of the lattice
• size - the size of the lattice along all dimensions
• nei - value giving the distance (number of steps) within which two vertices will be connected. Not implemented yet, should be 1.
• p - rewiring probability

Generates a graph from its adjacency matrix.

Parameters:

• matrix - the adjacency matrix
• mode - the mode to be used. Possible values are:
  • ADJ_DIRECTED - the graph will be directed and a matrix element gives the number of edges between two vertex.
  • ADJ_UNDIRECTED - alias to ADJ_MAX for convenience.
  • ADJ_MAX - undirected graph will be created and the number of edges between vertex i and j is max(A(i,j), A(j,i))
  • ADJ_MIN - like ADJ_MAX, but with min(A(i,j), A(j,i))
  • ADJ_PLUS - like ADJ_MAX, but with A(i,j) + A(j,i)
  • ADJ_UPPER - undirected graph with the upper right triangle of the matrix (including the diagonal)
  • ADJ_LOWER - undirected graph with the lower left triangle of the matrix (including the diagonal)

  These values can also be given as strings without the ADJ prefix.

• attr - the name of the edge attribute that stores the edge weights.

x.__init__(...) initializes x; see x.__class__.__doc__ for signature

Overrides: object.__init__

Returns: a new object with type S, a subtype of T

Overrides: object.__new__

str(x)

Overrides: object.__str__

Adds edges to the graph.

Parameters:

• es - the list of edges to be added. Every edge is represented with a tuple, containing the vertex IDs of the two endpoints. Vertices are enumerated from zero. It is allowed to provide a single pair instead of a list consisting of only one pair.

Returns:

the same graph object

Adds vertices to the graph.

Parameters:

• n - the number of vertices to be added

Returns:

the same graph object

Returns adjacent edges to a given vertex.

Parameters:

• vertex - a vertex ID
• type - whether to return only predecessors (OUT), successors (IN) or both (ALL). Ignored for undirected graphs.

Decides whether two given vertices are directly connected.

Parameters:

• v1 - the first vertex
• v2 - the second vertex

Returns:

True if there exists an edge from v1 to v2, False otherwise.

Returns the list of articulation points in the graph.

A vertex is an articulation point if its removal increases the number of connected components in the graph.

Returns:

the attribute name list of the graph

Calculates Kleinberg's authority score for the vertices of the graph

Parameters:

• scale - whether to normalize the scores so that the largest one is 1.
• arpack_options - an ARPACKOptions object used to fine-tune the ARPACK eigenvector calculation. If omitted, the module-level variable called arpack_options is used.
• return_eigenvalue - whether to return the largest eigenvalue

Returns:

the authority scores in a list and optionally the largest eigenvalue as a second member of a tuple

Calculates the average path length in a graph.

Parameters:

• directed - whether to consider directed paths in case of a directed graph. Ignored for undirected graphs.
• unconn - what to do when the graph is unconnected. If True, the average of the geodesic lengths in the components is calculated. Otherwise for all unconnected vertex pairs, a path length equal to the number of vertices is used.

Returns:

the average path length in the graph

Calculates or estimates the betweenness of nodes in a graph.

Keyword arguments:

Parameters:

• vertices - the vertices for which the betweennesses must be returned. If None, assumes all of the vertices in the graph.
• directed - whether to consider directed paths.
• cutoff - if it is an integer, only paths less than or equal to this length are considered, effectively resulting in an estimation of the betweenness for the given nodes. If None, the exact betweenness is returned.

Returns:

the (possibly estimated) betweenness of the given nodes in a list

Conducts a breadth first search (BFS) on the graph.

Parameters:

• vid - the root vertex ID
• mode - either IN or OUT or ALL, ignored for undirected graphs.

Returns:

a tuple with the following items:

• The vertex IDs visited (in order)
• The start indices of the layers in the vertex list
• The parent of every vertex in the BFS

Constructs a breadth first search (BFS) iterator of the graph.

Parameters:

• vid - the root vertex ID
• mode - either IN or OUT or ALL.
• advanced - if False, the iterator returns the next vertex in BFS order in every step. If True, the iterator returns the distance of the vertex from the root and the parent of the vertex in the BFS tree as well.

Returns:

the BFS iterator as an igraph.BFSIter object.

Calculates bibliographic coupling scores for given vertices in a graph.

Parameters:

• vertices - the vertices to be analysed. If None, all vertices will be considered.

Returns:

bibliographic coupling scores for all given vertices in a matrix.

Calculates the biconnected components of the graph.

Parameters:

• return_articulation_points - whether to return the articulation points as well

Returns:

a list of lists containing edge indices making up spanning trees of the biconnected components (one spanning tree for each component) and optionally the list of articulation points

Internal function, undocumented.

Internal function, undocumented.

Returns the clique number of the graph.

The clique number of the graph is the size of the largest clique.

Returns some or all cliques of the graph as a list of tuples.

A clique is a complete subgraph -- a set of vertices where an edge is present between any two of them (excluding loops)

Parameters:

• min - the minimum size of cliques to be returned. If zero or negative, no lower bound will be used.
• max - the maximum size of cliques to be returned. If zero or negative, no upper bound will be used.

Calculates the closeness centralities of given nodes in a graph.

The closeness centerality of a vertex measures how easily other vertices can be reached from it (or the other way: how easily it can be reached from the other vertices). It is defined as the number of the number of vertices minus one divided by the sum of the lengths of all geodesics from/to the given vertex.

If the graph is not connected, and there is no path between two vertices, the number of vertices is used instead the length of the geodesic. This is always longer than the longest possible geodesic.

Parameters:

• vertices - the vertices for which the closenesses must be returned. If None, uses all of the vertices in the graph.
• mode - must be one of IN, OUT and ALL. IN means that the length of the incoming paths, OUT means that the length of the outgoing paths must be calculated. ALL means that both of them must be calculated.
• cutoff - if it is an integer, only paths less than or equal to this length are considered, effectively resulting in an estimation of the closeness for the given nodes (which is always an underestimation of the real closeness, since some vertex pairs will appear as disconnected even though they are connected).. If None, the exact closeness is returned.

Returns:

the calculated closenesses in a list

Calculates the (strong or weak) clusters for a given graph.

Parameters:

• mode - must be either STRONG or WEAK, depending on the clusters being sought. Optional, defaults to STRONG.

Returns:

the component index for every node in the graph.

Calculates cocitation scores for given vertices in a graph.

Parameters:

• vertices - the vertices to be analysed. If None, all vertices will be considered.

Returns:

cocitation scores for all given vertices in a matrix.

Community structure detection based on the betweenness of the edges in the network. This algorithm was invented by M Girvan and MEJ Newman, see: M Girvan and MEJ Newman: Community structure in social and biological networks, Proc. Nat. Acad. Sci. USA 99, 7821-7826 (2002).

The idea is that the betweenness of the edges connecting two communities is typically high. So we gradually remove the edge with the highest betweenness from the network and recalculate edge betweenness after every removal, as long as all edges are removed.

Parameters:

• directed - whether to take into account the directedness of the edges when we calculate the betweenness values.
• return_removed_edges - whether to return the IDs of the edges in the order of removal.
• return_merges - if True, returns the order in which the individual vertices are merged into communities.
• return_ebs - if True, returns the edge betweenness of the removed edges at the time of the removal.
• return_bridges - if True, returns the IDs of the edges whose removal increased the number of connected components (these are the so-called bridges).

Returns:

a tuple with the removed edges IDs, the merge matrix, the edge betweennesses of the removed edges and the IDs of the bridges. Any of these elements can be equal to None based on the return_* arguments.

Finds the community structure of the graph according to the algorithm of Clauset et al based on the greedy optimization of modularity.

This is a bottom-up algorithm: initially every vertex belongs to a separate community, and communities are merged one by one. In every step, the two communities being merged are the ones which result in the maximal increase in modularity.

Parameters:

• weights - name of an edge attribute or a list containing edge weights
• return_q - if True, returns the modularity achieved before each merge during the algorithm, so the first element of the list returned will be the initial modularity (when every vertex belongs to a separate community), the second one is the modularity after the first join and so on.

Returns:

a tuple with the following elements:

1. The list of merges
2. The modularity scores before each merge if return_q is True, or None otherwise

Finds the community structure of the graph according to the label propagation method of Raghavan et al.

Initially, each vertex is assigned a different label. After that, each vertex chooses the dominant label in its neighbourhood in each iteration. Ties are broken randomly and the order in which the vertices are updated is randomized before every iteration. The algorithm ends when vertices reach a consensus.

Note that since ties are broken randomly, there is no guarantee that the algorithm returns the same community structure after each run. In fact, they frequently differ. See the paper of Raghavan et al on how to come up with an aggregated community structure.

Parameters:

• weights - name of an edge attribute or a list containing edge weights
• initial - name of a vertex attribute or a list containing the initial vertex labels. Labels are identified by integers from zero to n-1 where n is the number of vertices. Negative numbers may also be present in this vector, they represent unlabeled vertices.
• fixed - a list of booleans for each vertex. True corresponds to vertices whose labeling should not change during the algorithm. It only makes sense if initial labels are also given. Unlabeled vertices cannot be fixed. Note that vertex attribute names are not accepted here.

Returns:

the resulting membership vector

A proper implementation of Newman's eigenvector community structure detection. Each split is done by maximizing the modularity regarding the original network. See the reference for details.

Parameters:

• n - the desired number of communities. If negative, the algorithm tries to do as many splits as possible. Note that the algorithm won't split a community further if the signs of the leading eigenvector are all the same.
• return_merges - if True, returns the order in which the individual vertices are merged into communities.

Returns:

a tuple where the first element is the membership vector of the clustering and the second element is the merge matrix.

A naive implementation of Newman's eigenvector community structure detection. This function splits the network into two components according to the leading eigenvector of the modularity matrix and then recursively takes the given number of steps by splitting the communities as individual networks. This is not the correct way, however, see the reference for explanation. Consider using the correct community_leading_eigenvector method instead.

Parameters:

• n - the desired number of communities. If negative, the algorithm tries to do as many splits as possible. Note that the algorithm won't split a community further if the signs of the leading eigenvector are all the same.
• return_merges - if True, returns the order in which the individual vertices are merged into communities.

Returns:

a tuple where the first element is the membership vector of the clustering and the second element is the merge matrix.

Finds the community structure of the graph according to the random walk method of Latapy & Pons.

The basic idea of the algorithm is that short random walks tend to stay in the same community. The method provides a dendrogram.

Parameters:

• weights - name of an edge attribute or a list containing edge weights
• return_q - if True, returns the modularities achieved in each step of the algorithm as a list.

Returns:

a tuple with the following elements:

1. The list of merges
2. The modularity scores if return_q is True, or None otherwise

Returns the complementer of the graph

Parameters:

• loops - whether to include loop edges in the complementer.

Returns:

the complementer of the graph

Calculates Burt's constraint scores for given vertices in a graph.

Burt's constraint is higher if ego has less, or mutually stronger related (i.e. more redundant) contacts. Burt's measure of constraint, C[i], of vertex i's ego network V[i], is defined for directed and valued graphs as follows:

C[i] = sum( sum( (p[i,q] p[q,j])^2, q in V[i], q != i,j ), j in V[], j != i)

for a graph of order (ie. number od vertices) N, where proportional tie strengths are defined as follows:

p[i,j]=(a[i,j]+a[j,i]) / sum(a[i,k]+a[k,i], k in V[i], k != i), a[i,j] are elements of A and the latter being the graph adjacency matrix.

For isolated vertices, constraint is undefined.

Parameters:

• vertices - the vertices to be analysed or None for all vertices.
• weights - weights associated to the edges. Can be an attribute name as well. If None, every edge will have the same weight.

Returns:

constraint scores for all given vertices in a matrix.

Finds the coreness (shell index) of the vertices of the network.

The k-core of a graph is a maximal subgraph in which each vertex has at least degree k. (Degree here means the degree in the subgraph of course). The coreness of a vertex is k if it is a member of the k-core but not a member of the k+1-core.

Parameters:

• mode - whether to compute the in-corenesses (IN), the out-corenesses (OUT) or the undirected corenesses (ALL). Ignored and assumed to be ALL for undirected graphs.

Returns:

the corenesses for each vertex.

Determines the number of isomorphisms between the graph and another one

Parameters:

• other - the other graph. If None, the number of automorphisms will be returned.

Returns:

the number of isomorphisms between the two given graphs (or the number of automorphisms if other is None.

Counts the multiplicities of the given edges.

Parameters:

• edges - edge indices for which we want to count their multiplicity. If None, all edges are counted.

Returns:

the multiplicities of the given edges as a list.

Determines the number of subisomorphisms between the graph and another one

Parameters:

• other - the other graph.

Returns:

the number of subisomorphisms between the two given graphs

Decomposes the graph into subgraphs.

Parameters:

• mode - must be either STRONG or WEAK, depending on the clusters being sought.
• maxcompno - maximum number of components to return. None means all possible components.
• minelements - minimum number of vertices in a component. By setting this to 2, isolated vertices are not returned as separate components.

Returns:

a list of the subgraphs. Every returned subgraph is a copy of the original.

Returns some vertex degrees from the graph.

This method accepts a single vertex ID or a list of vertex IDs as a parameter, and returns the degree of the given vertices (in the form of a single integer or a list, depending on the input parameter).

Parameters:

• vertices - a single vertex ID or a list of vertex IDs
• type - the type of degree to be returned (OUT for out-degrees, IN IN for in-degrees or ALL for the sum of them).
• loops - whether self-loops should be counted.

Removes edges from the graph.

All vertices will be kept, even if they lose all their edges. Nonexistent edges will be silently ignored.

Parameters:

• es - the list of edges to be removed. Edges are identifed by edge IDs. EdgeSeq objects are also accepted here.

Returns:

the same graph object

Deletes vertices and all its edges from the graph.

Parameters:

• vs - a single vertex ID or the list of vertex IDs to be deleted.

Returns:

the same graph object

Calculates the density of the graph.

Parameters:

• loops - whether to take loops into consideration. If True, the algorithm assumes that there might be some loops in the graph and calculates the density accordingly. If False, the algorithm assumes that there can't be any loops.

Returns:

the reciprocity of the graph.

Calculates the diameter of the graph.

Parameters:

• directed - whether to consider directed paths.
• unconn - if True and the graph is unconnected, the longest geodesic within a component will be returned. If False and the graph is unconnected, the result is the number of vertices if there are no weights or infinity if there are weights.
• weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.

Returns:

the diameter

Creates the disjoint union of two (or more) graphs.

Parameters:

• graphs - the list of graphs to be united with the current one.

Dyad census, as defined by Holland and Leinhardt

Dyad census means classifying each pair of vertices of a directed graph into three categories: mutual, there is an edge from a to b and also from b to a; asymmetric, there is an edge either from a to b or from b to a but not the other way and null, no edges between a and b.

Returns:

the number of mutual, asymmetric and null connections in a 3-tuple.

Counts the number of edges.

Returns: integer

the number of edges in the graph.

Returns:

the attribute name list of the graph's edges

Calculates or estimates the edge betweennesses in a graph.

Parameters:

• directed - whether to consider directed paths.
• cutoff - if it is an integer, only paths less than or equal to this length are considered, effectively resulting in an estimation of the betweenness values. If None, the exact betweennesses are returned.

Returns:

a list with the (exact or estimated) edge betweennesses of all edges.

Calculates the edge connectivity of the graph or between some vertices.

The edge connectivity between two given vertices is the number of edges that have to be removed in order to disconnect the two vertices into two separate components. This is also the number of edge disjoint directed paths between the vertices. The edge connectivity of the graph is the minimal edge connectivity over all vertex pairs.

This method calculates the edge connectivity of a given vertex pair if both the source and target vertices are given. If none of them is given (or they are both negative), the overall edge connectivity is returned.

Parameters:

• source - the source vertex involved in the calculation.
• target - the target vertex involved in the calculation.
• checks - if the whole graph connectivity is calculated and this is True, igraph performs some basic checks before calculation. If the graph is not strongly connected, then the connectivity is obviously zero. If the minimum degree is one, then the connectivity is also one. These simple checks are much faster than checking the entire graph, therefore it is advised to set this to True. The parameter is ignored if the connectivity between two given vertices is computed.

Returns:

the edge connectivity

Calculates the eigenvector centralities of the vertices in a graph.

Parameters:

• scale - whether to normalize the centralities so the largest one will always be 1.
• weights - edge weights given as a list or an edge attribute. If None, all edges have equal weight.
• return_eigenvalue - whether to return the actual largest eigenvalue along with the centralities
• arpack_options - an ARPACKOptions object that can be used to fine-tune the calculation. If it is omitted, the module-level variable called arpack_options is used.

Returns:

the eigenvector centralities in a list and optionally the largest eigenvalue (as a second member of a tuple)

Returns two vertex IDs whose distance equals the actual diameter of the graph.

If there are many shortest paths with the length of the diameter, it returns the first one it found.

Parameters:

• directed - whether to consider directed paths.
• unconn - if True and the graph is unconnected, the longest geodesic within a component will be returned. If False and the graph is unconnected, the result contains the number of vertices if there are no weights or infinity if there are weights.
• weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.

Returns:

a triplet containing the two vertex IDs and their distance. The IDs are None if the graph is unconnected and unconn is False.

Returns the adjacency matrix of a graph.

Parameters:

• type - either GET_ADJACENCY_LOWER (uses the lower triangle of the matrix) or GET_ADJACENCY_UPPER (uses the upper triangle) or GET_ADJACENCY_BOTH (uses both parts). Ignored for directed graphs.

Returns:

the adjacency matrix.

Calculates all of the shortest paths from/to a given node in a graph.

Parameters:

• v - the source/destination for the calculated paths
• mode - the directionality of the paths. IN means to calculate incoming paths, OUT means to calculate outgoing paths, ALL means to calculate both ones.

Returns:

all of the shortest path from the given node to every other reachable node in the graph in a list. Note that in case of mode=IN, the nodes in a path are returned in reversed order!

Returns a path with the actual diameter of the graph.

If there are many shortest paths with the length of the diameter, it returns the first one it founds.

Parameters:

• directed - whether to consider directed paths.
• unconn - if True and the graph is unconnected, the longest geodesic within a component will be returned. If False and the graph is unconnected, the result is the number of vertices if there are no weights or infinity if there are weights.
• weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.

Returns:

the vertices in the path in order.

Returns the edge ID of an arbitrary edge between vertices v1 and v2

Parameters:

• v1 - the first vertex ID
• v2 - the second vertex ID
• directed - whether edge directions should be considered in directed graphs. The default is True. Ignored for undirected graphs.

Returns:

the edge ID of an arbitrary edge between vertices v1 and v2

Internal function, undocumented.

Returns all isomorphisms between the graph and another one

Parameters:

• other - the other graph. If None, the automorphisms will be returned.

Returns:

a list of lists, each item of the list containing the mapping from vertices of the second graph to the vertices of the first one

Calculates the shortest paths from/to a given node in a graph.

Parameters:

• v - the source/destination for the calculated paths
• weights - edge weights in a list or the name of an edge attribute holding edge weights. If None, all edges are assumed to have equal weight.
• mode - the directionality of the paths. IN means to calculate incoming paths, OUT means to calculate outgoing paths, ALL means to calculate both ones.

Returns:

at most one shortest path for every node in the graph in a list. For unconnected graphs, some of the list elements will be empty lists. Note that in case of mode=IN, the nodes in a path are returned in reversed order!

Returns all subisomorphisms between the graph and another one

Parameters:

• other - the other graph.

Returns:

a list of lists, each item of the list containing the mapping from vertices of the second graph to the vertices of the first one

Returns the girth of the graph.

The girth of a graph is the length of the shortest circle in it.

Parameters:

• return_shortest_circle - whether to return one of the shortest circles found in the graph.

Returns:

the length of the shortest circle or (if return_shortest_circle) is true, the shortest circle itself as a list

Calculates Kleinberg's hub score for the vertices of the graph

Parameters:

• scale - whether to normalize the scores so that the largest one is 1.
• arpack_options - an ARPACKOptions object used to fine-tune the ARPACK eigenvector calculation. If omitted, the module-level variable called arpack_options is used.
• return_eigenvalue - whether to return the largest eigenvalue

Returns:

the hub scores in a list and optionally the largest eigenvalue as a second member of a tuple

Returns the independence number of the graph.

The independence number of the graph is the size of the largest independent vertex set.

Returns some or all independent vertex sets of the graph as a list of tuples.

Two vertices are independent if there is no edge between them. Members of an independent vertex set are mutually independent.

Parameters:

• min - the minimum size of sets to be returned. If zero or negative, no lower bound will be used.
• max - the maximum size of sets to be returned. If zero or negative, no upper bound will be used.

Creates the intersection of two (or more) graphs.

Parameters:

• graphs - the list of graphs to be intersected with the current one.

Decides whether the graph is bipartite or not.

Vertices of a bipartite graph can be partitioned into two groups A and B in a way that all edges go between the two groups.

Parameters:

• return_types - if False, the method will simply return True or False depending on whether the graph is bipartite or not. If True, the actual group assignments are also returned as a list of boolean values. (Note that the group assignment is not unique, especially if the graph consists of multiple components, since the assignments of components are independent from each other).

Returns:

True if the graph is bipartite, False if not. If return_types is True, the group assignment is also returned.

Decides whether the graph is connected.

Parameters:

• mode - whether we should calculate strong or weak connectivity.

Returns:

True if the graph is connected, False otherwise.

Checks whether a specific set of edges contain loop edges

Parameters:

• edges - edge indices which we want to check. If None, all edges are checked.

Returns:

a list of booleans, one for every edge given

Checks whether an edge is a multiple edge.

Also works for a set of edges -- in this case, every edge is checked one by one. Note that if there are multiple edges going between a pair of vertices, there is always one of them that is not reported as multiple (only the others). This allows one to easily detect the edges that have to be deleted in order to make the graph free of multiple edges.

Parameters:

• edges - edge indices which we want to check. If None, all edges are checked.

Returns:

a list of booleans, one for every edge given

Checks whether an edge has an opposite pair.

Also works for a set of edges -- in this case, every edge is checked one by one. The result will be a list of booleans (or a single boolean if only an edge index is supplied), every boolean corresponding to an edge in the edge set supplied. True is returned for a given edge a --> b if there exists another edge b --> a in the original graph (not the given edge set!). All edges in an undirected graph are mutual. In case there are multiple edges between a and b, it is enough to have at least one edge in either direction to report all edges between them as mutual, so the multiplicity of edges do not matter.

Parameters:

• edges - edge indices which we want to check. If None, all edges are checked.

Returns:

a list of booleans, one for every edge given

Checks whether the graph is simple (no loop or multiple edges).

Returns: boolean

True if it is simple, False otherwise.

Returns the isomorphy class of the graph or its subgraph.

Isomorphy class calculations are implemented only for graphs with 3 or 4 nodes.

Parameters:

• vertices - a list of vertices if we want to calculate the isomorphy class for only a subset of vertices. None means to use the full graph.

Returns:

the isomorphy class of the (sub)graph

Checks whether the graph is isomorphic with another graph.

The algorithm being used is selected using a simple heuristic:

• If one graph is directed and the other undirected, an exception is thrown.
• If the two graphs does not have the same number of vertices and edges, it returns with False
• If the graphs have three or four vertices, then an O(1) algorithm is used with precomputed data.
• Otherwise if the graphs are directed, then the VF2 isomorphism algorithm is used (see Graph.isomorphic_vf2).
• Otherwise the BLISS isomorphism algorithm is used, see Graph.isomorphic_bliss.

Returns:

True if the graphs are isomorphic, False otherwise.

Checks whether the graph is isomorphic with another graph, using the BLISS isomorphism algorithm.

Parameters:

• other - the other graph with which we want to compare the graph.
• return_mapping_12 - if True, calculates the mapping which maps the vertices of the first graph to the second.
• return_mapping_21 - if True, calculates the mapping which maps the vertices of the second graph to the first.
• sh1 - splitting heuristics for the first graph as a case-insensitive string, with the following possible values:
  • "f": first non-singleton cell
  • "fl": first largest non-singleton cell
  • "fs": first smallest non-singleton cell
  • "fm": first maximally non-trivially connected non-singleton cell
  • "flm": largest maximally non-trivially connected non-singleton cell
  • "fsm": smallest maximally non-trivially connected non-singleton cell
• sh2 - splitting heuristics to be used for the second graph. Accepted values are as above.

Returns:

if no mapping is calculated, the result is True if the graphs are isomorphic, False otherwise. If any or both mappings are calculated, the result is a 3-tuple, the first element being the above mentioned boolean, the second element being the 1 -> 2 mapping and the third element being the 2 -> 1 mapping. If the corresponding mapping was not calculated, None is returned in the appropriate element of the 3-tuple.

Checks whether the graph is isomorphic with another graph, using the VF2 isomorphism algorithm.

Parameters:

• other - the other graph with which we want to compare the graph.
• return_mapping_12 - if True, calculates the mapping which maps the vertices of the first graph to the second.
• return_mapping_21 - if True, calculates the mapping which maps the vertices of the second graph to the first.

Returns:

if no mapping is calculated, the result is True if the graphs are isomorphic, False otherwise. If any or both mappings are calculated, the result is a 3-tuple, the first element being the above mentioned boolean, the second element being the 1 -> 2 mapping and the third element being the 2 -> 1 mapping. If the corresponding mapping was not calculated, None is returned in the appropriate element of the 3-tuple.

Returns the Laplacian matrix of a graph.

The Laplacian matrix is similar to the adjacency matrix, but the edges are denoted with -1 and the diagonal contains the node degrees.

Normalized Laplacian matrices have 1 or 0 in their diagonals (0 for nodes with no edges), edges are denoted by 1 / sqrt(d_i * d_j) where d_i is the degree of node i.

Multiple edges and self-loops are silently ignored. Although it is possible to calculate the Laplacian matrix of a directed graph, it does not make much sense.

Parameters:

• normalized - whether to return the normalized Laplacian matrix.

Returns:

the Laplacian matrix.

Returns the largest cliques of the graph as a list of tuples.

Quite intuitively a clique is considered largest if there is no clique with more vertices in the whole graph. All largest cliques are maximal (i.e. nonextendable) but not all maximal cliques are largest.

Returns the largest independent vertex sets of the graph as a list of tuples.

Quite intuitively an independent vertex set is considered largest if there is no other set with more vertices in the whole graph. All largest sets are maximal (i.e. nonextendable) but not all maximal sets are largest.

Places the vertices of the graph uniformly on a circle.

Returns:

the calculated coordinate pairs in a list.

Places the vertices on a 2D plane according to the DrL layout algorithm.

This is an algorithm suitable for quite large graphs, but it can be surprisingly slow for small ones (where the simpler force-based layouts like layout_kamada_kawai() or layout_fruchterman_reingold() are more useful.

Parameters:

• weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
• seed - if None, uses a random starting layout for the algorithm. If a matrix (list of lists), uses the given matrix as the starting position.
• fixed - if a seed is given, you can specify some vertices to be kept fixed at their original position in the seed by passing an appropriate list here. The list must have exactly as many items as the number of vertices in the graph. Items of the list that evaluate to True denote vertices that will not be moved.
• options - if you give a string argument here, you can select from five default preset parameterisations: default, coarsen for a coarser layout, coarsest for an even coarser layout, refine for refining an existing layout and final for finalizing a layout. If you supply an object that is not a string, the DrL layout parameters are retrieved from the respective keys of the object (so it should be a dict or something else that supports the mapping protocol). The following keys can be used:
  • edge_cut: edge cutting is done in the late stages of the algorithm in order to achieve less dense layouts. Edges are cut if there is a lot of stress on them (a large value in the objective function sum). The edge cutting parameter is a value between 0 and 1 with 0 representing no edge cutting and 1 representing maximal edge cutting.
  • init_iterations: number of iterations in the initialization phase
  • init_temperature: start temperature during initialization
  • init_attraction: attraction during initialization
  • init_damping_mult: damping multiplier during initialization
  • liquid_iterations, liquid_temperature, liquid_attraction, liquid_damping_mult: same parameters for the liquid phase
  • expansion_iterations, expansion_temperature, expansion_attraction, expansion_damping_mult: parameters for the expansion phase
  • cooldown_...: parameters for the cooldown phase
  • crunch_...: parameters for the crunch phase
  • simmer_...: parameters for the simmer phase

  Instead of a mapping, you can also use an arbitrary Python object here: if the object does not support the mapping protocol, an attribute of the object with the same name is looked up instead. If a parameter cannot be found either as a key or an attribute, the default from the default preset will be used.

Returns:

the calculated coordinate pairs in a list.

Places the vertices on a 2D plane according to the Fruchterman-Reingold algorithm.

This is a force directed layout, see Fruchterman, T. M. J. and Reingold, E. M.: Graph Drawing by Force-directed Placement. Software -- Practice and Experience, 21/11, 1129--1164, 1991

Parameters:

• weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
• maxiter - the number of iterations to perform.
• maxdelta - the maximum distance to move a vertex in an iteration. None means the number of vertices.
• area - the area of the square on which the vertices will be placed. None means the square of maxdelta.
• coolexp - the cooling exponent of the simulated annealing.
• repulserad - determines the radius at which vertex-vertex repulsion cancels out attraction of adjacent vertices. None means maxiter*maxdelta.
• seed - if None, uses a random starting layout for the algorithm. If a matrix (list of lists), uses the given matrix as the starting position.

Returns:

the calculated coordinate pairs in a list.

Places the vertices in the 3D space according to the Fruchterman-Reingold grid algorithm.

This is a force directed layout, see Fruchterman, T. M. J. and Reingold, E. M.: Graph Drawing by Force-directed Placement. Software -- Practice and Experience, 21/11, 1129--1164, 1991

Parameters:

• weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
• maxiter - the number of iterations to perform.
• maxdelta - the maximum distance to move a vertex in an iteration. None means the number of vertices.
• area - the area of the square on which the vertices will be placed. None means the square of maxdelta.
• coolexp - the cooling exponent of the simulated annealing.
• repulserad - determines the radius at which vertex-vertex repulsion cancels out attraction of adjacent vertices. None means maxiter*maxdelta.
• seed - if None, uses a random starting layout for the algorithm. If a matrix (list of lists), uses the given matrix as the starting position.

Returns:

the calculated coordinate triplets in a list.

This is a port of the graphopt layout algorithm by Michael Schmuhl. graphopt version 0.4.1 was rewritten in C and the support for layers was removed.

graphopt uses physical analogies for defining attracting and repelling forces among the vertices and then the physical system is simulated until it reaches an equilibrium or the maximal number of iterations is reached.

See http://www.schmuhl.org/graphopt/ for the original graphopt.

Parameters:

• niter - the number of iterations to perform. Should be a couple of hundred in general.
• node_charge - the charge of the vertices, used to calculate electric repulsion.
• node_mass - the mass of the vertices, used for the spring forces
• spring_length - the length of the springs
• spring_constant - the spring constant
• max_sa_movement - the maximum amount of movement allowed in a single step along a single axis.

Places the vertices on a 2D plane according to the Fruchterman-Reingold grid algorithm.

This is a modified version of a force directed layout, see Fruchterman, T. M. J. and Reingold, E. M.: Graph Drawing by Force-directed Placement. Software -- Practice and Experience, 21/11, 1129--1164, 1991. The algorithm partitions the 2D space to a grid and vertex repulsion is then calculated only for vertices nearby.

Parameters:

• maxiter - the number of iterations to perform.
• maxdelta - the maximum distance to move a vertex in an iteration. None means the number of vertices.
• area - the area of the square on which the vertices will be placed. None means the square of maxdelta.
• coolexp - the cooling exponent of the simulated annealing.
• repulserad - determines the radius at which vertex-vertex repulsion cancels out attraction of adjacent vertices. None means maxiter*maxdelta.
• cellsize - the size of the grid cells.
• seed - if None, uses a random starting layout for the algorithm. If a matrix (list of lists), uses the given matrix as the starting position.

Returns:

the calculated coordinate pairs in a list.

Places the vertices on a plane according to the Kamada-Kawai algorithm.

This is a force directed layout, see Kamada, T. and Kawai, S.: An Algorithm for Drawing General Undirected Graphs. Information Processing Letters, 31/1, 7--15, 1989.

Parameters:

• maxiter - the number of iterations to perform.
• sigma - the standard base deviation of the position change proposals. None means the number of vertices * 0.25
• initemp - initial temperature of the simulated annealing.
• coolexp - cooling exponent of the simulated annealing.
• kkconst - the Kamada-Kawai vertex attraction constant. None means the square of the number of vertices.
• seed - if None, uses a random starting layout for the algorithm. If a matrix (list of lists), uses the given matrix as the starting position.

Returns:

the calculated coordinate pairs in a list.

Places the vertices in the 3D space according to the Kamada-Kawai algorithm.

This is a force directed layout, see Kamada, T. and Kawai, S.: An Algorithm for Drawing General Undirected Graphs. Information Processing Letters, 31/1, 7--15, 1989.

Parameters:

• maxiter - the number of iterations to perform.
• sigma - the standard base deviation of the position change proposals. None means the number of vertices * 0.25
• initemp - initial temperature of the simulated annealing.
• coolexp - cooling exponent of the simulated annealing.
• kkconst - the Kamada-Kawai vertex attraction constant. None means the square of the number of vertices.
• seed - if None, uses a random starting layout for the algorithm. If a matrix (list of lists), uses the given matrix as the starting position.

Returns:

the calculated coordinate triplets in a list.

Places the vertices on a 2D plane according to the Large Graph Layout.

Parameters:

• maxiter - the number of iterations to perform.
• maxdelta - the maximum distance to move a vertex in an iteration. If negative, defaults to the number of vertices.
• area - the area of the square on which the vertices will be placed. If negative, defaults to the number of vertices squared.
• coolexp - the cooling exponent of the simulated annealing.
• repulserad - determines the radius at which vertex-vertex repulsion cancels out attraction of adjacent vertices. If negative, defaults to area times the number of vertices.
• cellsize - the size of the grid cells. When calculating the repulsion forces, only vertices in the same or neighboring grid cells are taken into account. Defaults to the fourth root of area.
• root - the root vertex, this is placed first, its neighbors in the first iteration, second neighbors in the second, etc. A negative number means a random vertex.

Returns:

the calculated coordinate pairs in a list.

Places the vertices of the graph randomly in a 2D space.

Returns:

the "calculated" coordinate pairs in a list.

Places the vertices of the graph randomly in a 3D space.

Returns:

the "calculated" coordinate triplets in a list.

Places the vertices on a 2D plane according to the Reingold-Tilford layout algorithm.

Parameters:

• root - the root of the tree.

Returns:

the calculated coordinate pairs in a list.

Circular Reingold-Tilford layout for trees.

This layout is similar to the Reingold-Tilford layout, but the vertices are placed in a circular way, with the root vertex in the center.

Parameters:

• root - the root of the tree.

Returns:

the calculated coordinate pairs in a list.

Places the vertices of the graph uniformly on a sphere.

Returns:

the calculated coordinate triplets in a list.

Returns the line graph of the graph.

The line graph L(G) of an undirected graph is defined as follows: L(G) has one vertex for each edge in G and two vertices in L(G) are connected iff their corresponding edges in the original graph share an end point.

The line graph of a directed graph is slightly different: two vertices are connected by a directed edge iff the target of the first vertex's corresponding edge is the same as the source of the second vertex's corresponding edge.

Returns the maximum degree of a vertex set in the graph.

This method accepts a single vertex ID or a list of vertex IDs as a parameter, and returns the degree of the given vertices (in the form of a single integer or a list, depending on the input parameter).

Parameters:

• vertices - a single vertex ID or a list of vertex IDs or None meaning all the vertices in the graph.
• type - the type of degree to be returned (OUT for out-degrees, IN IN for in-degrees or ALL for the sum of them).
• loops - whether self-loops should be counted.

Returns the maximum flow between the source and target vertices.

Parameters:

• source - the source vertex ID
• target - the target vertex ID
• capacity - the capacity of the edges. It must be a list or a valid attribute name or None. In the latter case, every edge will have the same capacity.

Returns:

the value of the maximum flow between the given vertices

Returns the maximal cliques of the graph as a list of tuples.

A maximal clique is a clique which can't be extended by adding any other vertex to it. A maximal clique is not necessarily one of the largest cliques in the graph.

Returns the maximal independent vertex sets of the graph as a list of tuples.

A maximal independent vertex set is an independent vertex set which can't be extended by adding any other vertex to it. A maximal independent vertex set is not necessarily one of the largest independent vertex sets in the graph.

Calculates the minimum cut in a graph.

Right now it is implemented only for undirected graphs, in which case it uses the Stoer-Wagner algorithm, as described in the reference given below.

The minimum cut is the minimum set of edges which needs to be removed to disconnect the graph. The minimum is calculated using the weights (capacities) of the edges, so the cut with the minimum total capacity is calculated.

Returns:

the value of the minimum cut, the IDs of vertices in the first and second partition, and the IDs of edges in the cut, packed in a 4-tuple