Create and return a new object. See help(type) for accurate signature.

Counts the number of vertices.

Counts the number of edges.

Checks whether the graph is a DAG (directed acyclic graph).

A DAG is a directed graph with no directed cycles.

Checks whether the graph is directed.

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

Checks whether the graph is a (directed or undirected) tree graph.

For directed trees, the function may require that the edges are oriented outwards from the root or inwards to the root, depending on the value of the mode argument.

Adds vertices to the graph.

Deletes vertices and all its edges from the graph.

Adds edges to the graph.

Removes edges from the graph.

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

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).

Returns the strength (weighted degree) of some vertices from the graph

This method accepts a single vertex ID or a list of vertex IDs as a parameter, and returns the strength (that is, the sum of the weights of all incident edges) of the given vertices (in the form of a single integer or a list, depending on the input parameter).

Checks whether a specific set of edges contain loop edges

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.

Checks whether the graph has multiple edges.

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.

Counts the multiplicities of the given edges.

Returns adjacent vertices to a given vertex.

Returns the successors of a given vertex.

Equivalent to calling the neighbors() method with type="out".

Returns the predecessors of a given vertex.

Equivalent to calling the neighbors() method with type="in".

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

Returns the edge IDs of some edges between some vertices.

This method can operate in two different modes, depending on which of the keyword arguments pairs and path are given.

The method does not consider multiple edges; if there are multiple edges between a pair of vertices, only the ID of one of the edges is returned.

Returns the edges a given vertex is incident on.

Generates a graph from its adjacency matrix.

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

This is the asymmetric variant of 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.

Generates a graph from the Graph Atlas.

Generates a graph based on the Barabasi-Albert model.

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.

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.

Generates a graph based on the Erdos-Renyi model.

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: https://igraph.org/c/doc.

Generates a graph based on the forest fire model

The forest fire model is a growing 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.

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.

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

Generates a growing random graph.

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.

Generates a k-regular random graph

A k-regular random graph is a random graph where each vertex has degree k. If the graph is directed, both the in-degree and the out-degree of each vertex will be k.

Generates a graph based on vertex types and connection probabilities.

This is practically the nongrowing variant of 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.

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.

Generates a graph based on a stochastic blockmodel.

A given number of vertices are generated. Every vertex is assigned to a vertex type according to the given block sizes. Vertices of the same type will be assigned consecutive vertex IDs. Finally, every vertex pair is evaluated and an edge is created between them with a probability depending on the types of the vertices involved. The probabilities are taken from the preference matrix.

Generates a star graph.

Generates a regular lattice.

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.

Generates a graph from a degree sequence.

This method implements a Havel-Hakimi style graph construction from a given degree sequence. In each step, the algorithm picks two vertices in a deterministic manner and connects them. The way the vertices are picked is defined by the method parameter. The allowed edge types (i.e. whether multiple or loop edges are allowed) are specified in the allowed_edge_types parameter.

Generates a ring graph.

Generates a non-growing graph with edge probabilities proportional to node fitnesses.

The algorithm randomly selects vertex pairs and connects them until the given number of edges are created. Each vertex is selected with a probability proportional to its fitness; for directed graphs, a vertex is selected as a source proportional to its out-fitness and as a target proportional to its in-fitness.

Generates a non-growing graph with prescribed power-law degree distributions.

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

Generates a graph with a given degree sequence.

Generates a graph with a given isomorphism class.

Generates a random tree by sampling uniformly from the set of labelled trees with a given number of nodes.

Generates a graph from its adjacency matrix.

Decides whether two given vertices are directly connected.

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 assortativity of the graph based on numeric properties of the vertices.

This coefficient is basically the correlation between the actual connectivity patterns of the vertices and the pattern expected from the disribution of the vertex types.

See equation (21) in Newman MEJ: Mixing patterns in networks, Phys Rev E 67:026126 (2003) for the proper definition. The actual calculation is performed using equation (26) in the same paper for directed graphs, and equation (4) in Newman MEJ: Assortative mixing in networks, Phys Rev Lett 89:208701 (2002) for undirected graphs.

Returns the assortativity of a graph based on vertex degrees.

See assortativity() for the details. assortativity_degree() simply calls assortativity() with the vertex degrees as types.

Returns the assortativity of the graph based on vertex categories.

Assuming that the vertices belong to different categories, this function calculates the assortativity coefficient, which specifies the extent to which the connections stay within categories. The assortativity coefficient is one if all the connections stay within categories and minus one if all the connections join vertices of different categories. For a randomly connected network, it is asymptotically zero.

See equation (2) in Newman MEJ: Mixing patterns in networks, Phys Rev E 67:026126 (2003) for the proper definition.

Calculates the average path length in a graph.

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

Calculates or estimates the betweenness of vertices in a graph.

Keyword arguments:

Calculates the biconnected components of the graph.

Components containing a single vertex only are not considered as being biconnected.

Internal function, undocumented.

Internal function, undocumented.

Returns the list of bridges in the graph.

An edge is a bridge if its removal increases the number of (weakly) connected components in the graph.

chordal_complation(alpha=None, alpham1=None) --

Returns the list of edges needed to be added to the graph to make it chordal.

A graph is chordal if each of its cycles of four or more nodes has a chord, i.e. an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes.

The chordal completion of a graph is the list of edges that needed to be added to the graph to make it chordal. It is an empty list if the graph is already chordal.

Note that at the moment igraph does not guarantee that the returned chordal completion is minimal; there may exist a subset of the returned chordal completion that is still a valid chordal completion.

Calculates the closeness centralities of given vertices 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 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.

Calculates the harmonic centralities of given vertices in a graph.

The harmonic 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 mean inverse distance to all other vertices.

If the graph is not connected, and there is no path between two vertices, the inverse distance is taken to be zero.

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

Creates a copy of the graph.

Attributes are copied by reference; in other words, if you use mutable Python objects as attribute values, these objects will still be shared between the old and new graph. You can use `deepcopy()` from the `copy` module if you need a truly deep copy of the graph.

Decomposes the graph into subgraphs.

Contracts some vertices in the graph, i.e. replaces groups of vertices with single vertices. Edges are not affected.

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.

Calculates the density of the graph.

Calculates the diameter of the graph.

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.

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.

Calculates the structural diversity index of the vertices.

The structural diversity index of a vertex is simply the (normalized) Shannon entropy of the weights of the edges incident on the vertex.

The measure is defined for undirected graphs only; edge directions are ignored.

Calculates the eccentricities of given vertices in a graph.

The eccentricity of a vertex is calculated by measuring the shortest distance from (or to) the vertex, to (or from) all other vertices in the graph, and taking the maximum.

Calculates or estimates the edge betweennesses in a graph.

Undocumented

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.

Calculates the eigenvector centralities of the vertices in a graph.

Eigenvector centrality is a measure of the importance of a node in a network. It assigns relative scores to all nodes in the network based on the principle that connections from high-scoring nodes contribute more to the score of the node in question than equal connections from low-scoring nodes. In practice, the centralities are determined by calculating eigenvector corresponding to the largest positive eigenvalue of the adjacency matrix. In the undirected case, this function considers the diagonal entries of the adjacency matrix to be twice the number of self-loops on the corresponding vertex.

In the directed case, the left eigenvector of the adjacency matrix is calculated. In other words, the centrality of a vertex is proportional to the sum of centralities of vertices pointing to it.

Eigenvector centrality is meaningful only for connected graphs. Graphs that are not connected should be decomposed into connected components, and the eigenvector centrality calculated for each separately.

Calculates an approximately or exactly minimal feedback arc set.

A feedback arc set is a set of edges whose removal makes the graph acyclic. Since this is always possible by removing all the edges, we are in general interested in removing the smallest possible number of edges, or an edge set with as small total weight as possible. This method calculates one such edge set. Note that the task is trivial for an undirected graph as it is enough to find a spanning tree and then remove all the edges not in the spanning tree. Of course it is more complicated for directed graphs.

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

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

Returns the girth of the graph.

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

Undocumented (yet).

Undocumented (yet).

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

Returns a subgraph spanned by the given vertices.

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.

Returns whether the graph is chordal or not.

A graph is chordal if each of its cycles of four or more nodes has a chord, i.e. an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes.

Calculates the average degree of the neighbors for each vertex, and the same quantity as the function of vertex degree.

Decides whether the graph is connected.

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).

Conducts a maximum cardinality search on the graph. The function computes a rank alpha for each vertex such that visiting vertices in decreasing rank order corresponds to always choosing the vertex with the most already visited neighbors as the next one to visit.

Maximum cardinality search is useful in deciding the chordality of a graph: a graph is chordal if and only if any two neighbors of a vertex that are higher in rank than the original vertex are connected to each other.

The result of this function can be passed to is_chordal() to speed up the chordality computation if you also need the result of the maximum cardinality search for other purposes.

For each vertex specified by vertices, returns the vertices reachable from that vertex in at most order steps. If mindist is larger than zero, vertices that are reachable in less than mindist steps are excluded.

For each vertex specified by vertices, returns the number of vertices reachable from that vertex in at most order steps. If mindist is larger than zero, vertices that are reachable in less than mindist steps are excluded.

Calculates the personalized PageRank values of a graph.

The personalized PageRank calculation is similar to the PageRank calculation, but the random walk is reset to a non-uniform distribution over the vertices in every step with probability 1-damping instead of a uniform distribution.

Calculates the path length histogram of the graph

Permutes the vertices of the graph according to the given permutation and returns the new graph.

Vertex k of the original graph will become vertex permutation[k] in the new graph. No validity checks are performed on the permutation vector.

Calculates the radius of the graph.

The radius of a graph is defined as the minimum eccentricity of its vertices (see eccentricity()).

Reciprocity defines the proportion of mutual connections in a directed graph. It is most commonly defined as the probability that the opposite counterpart of a directed edge is also included in the graph. This measure is calculated if mode is "default".

Prior to igraph 0.6, another measure was implemented, defined as the probability of mutual connection between a vertex pair if we know that there is a (possibly non-mutual) connection between them. In other words, (unordered) vertex pairs are classified into three groups: (1) disconnected, (2) non-reciprocally connected and (3) reciprocally connected. The result is the size of group (3), divided by the sum of sizes of groups (2) and (3). This measure is calculated if mode is "ratio".

Randomly rewires the graph while preserving the degree distribution.

Please note that the rewiring is done "in-place", so the original graph will be modified. If you want to preserve the original graph, use the copy method before.

Rewires the edges of a graph with constant probability.

Each endpoint of each edge of the graph will be rewired with a constant probability, given in the first argument.

Please note that the rewiring is done "in-place", so the original graph will be modified. If you want to preserve the original graph, use the copy method before.

Calculates shortest path lengths for given vertices in a graph.

The algorithm used for the calculations is selected automatically: a simple BFS is used for unweighted graphs, Dijkstra's algorithm is used when all the weights are positive. Otherwise, the Bellman-Ford algorithm is used if the number of requested source vertices is larger than 100 and Johnson's algorithm is used otherwise.

Simplifies a graph by removing self-loops and/or multiple edges.

For example, suppose you have a graph with an edge attribute named weight. graph.simplify(combine_edges=max) will take the maximum of the weights of multiple edges and assign that weight to the collapsed edge. graph.simplify(combine_edges=sum) will take the sum of the weights. You can also write graph.simplify(combine_edges=dict(weight="sum")) or graph.simplify(combine_edges=dict(weight=sum)), since sum is recognised both as a Python built-in function and as a string constant.

Determines the indices of vertices which are in the same component as a given vertex.

Returns a subgraph spanned by the given edges.

Calculates a possible topological sorting of the graph.

Returns a partial sorting and issues a warning if the graph is not a directed acyclic graph.

Converts a tree graph into a Prufer sequence.

Calculates the global transitivity (clustering coefficient) of the graph.

The transitivity measures the probability that two neighbors of a vertex are connected. More precisely, this is the ratio of the triangles and connected triplets in the graph. The result is a single real number. Directed graphs are considered as undirected ones.

Note that this measure is different from the local transitivity measure (see transitivity_local_undirected()) as it calculates a single value for the whole graph.

Calculates the local transitivity (clustering coefficient) of the given vertices in the graph.

The transitivity measures the probability that two neighbors of a vertex are connected. In case of the local transitivity, this probability is calculated separately for each vertex.

Note that this measure is different from the global transitivity measure (see transitivity_undirected()) as it calculates a transitivity value for each vertex individually.

The traditional local transitivity measure applies for unweighted graphs only. When the weights argument is given, this function calculates the weighted local transitivity proposed by Barrat et al (see references).

Calculates the average of the vertex transitivities of the graph.

The transitivity measures the probability that two neighbors of a vertex are connected. In case of the average local transitivity, this probability is calculated for each vertex and then the average is taken. Vertices with less than two neighbors require special treatment, they will either be left out from the calculation or they will be considered as having zero transitivity, depending on the mode parameter.

Note that this measure is different from the global transitivity measure (see transitivity_undirected()) as it simply takes the average local transitivity across the whole network.

Unfolds the graph using a BFS to a tree by duplicating vertices as necessary.

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

The vertex connectivity between two given vertices is the number of vertices that have to be removed in order to disconnect the two vertices into two separate components. This is also the number of vertex disjoint directed paths between the vertices (apart from the source and target vertices of course). The vertex connectivity of the graph is the minimal vertex connectivity over all vertex pairs.

This method calculates the vertex 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 vertex connectivity is returned.

Calculates bibliographic coupling scores for given vertices in a graph.

Calculates cocitation scores for given vertices in a graph.

Dice similarity coefficient of vertices.

The Dice similarity coefficient of two vertices is twice the number of their common neighbors divided by the sum of their degrees. This coefficient is very similar to the Jaccard coefficient, but usually gives higher similarities than its counterpart.

Inverse log-weighted similarity coefficient of vertices.

Each vertex is assigned a weight which is 1 / log(degree). The log-weighted similarity of two vertices is the sum of the weights of their common neighbors.

Jaccard similarity coefficient of vertices.

The Jaccard similarity coefficient of two vertices is the number of their common neighbors divided by the number of vertices that are adjacent to at least one of them.

Counts the number of motifs in the graph

Motifs are small subgraphs of a given structure in a graph. It is argued that the motif profile (ie. the number of different motifs in the graph) is characteristic for different types of networks and network function is related to the motifs in the graph.

This function is able to find the different motifs of size three and four (ie. the number of different subgraphs with three and four vertices) in the network.

In a big network the total number of motifs can be very large, so it takes a lot of time to find all of them. In such cases, a sampling method can be used. This function is capable of doing sampling via the cut_prob argument. This argument gives the probability that a branch of the motif search tree will not be explored.

Counts the total number of motifs in the graph

Motifs are small subgraphs of a given structure in a graph. This function counts the total number of motifs in a graph without assigning isomorphism classes to them.

Counts the total number of motifs in the graph

Motifs are small subgraphs of a given structure in a graph. This function estimates the total number of motifs in a graph without assigning isomorphism classes to them by extrapolating from a random sample of vertices.

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.

Triad census, as defined by Davis and Leinhardt

Calculating the triad census means classifying every triplets of vertices in a directed graph. A triplet can be in one of 16 states, these are listed in the documentation of the C interface of igraph.

Place the vertices of a bipartite graph in two layers.

The layout is created by placing the vertices in two rows, according to their types. The positions of the vertices within the rows are then optimized to minimize the number of edge crossings using the heuristic used by the Sugiyama layout algorithm.

Places the vertices of the graph uniformly on a circle or a sphere.

Places the vertices of a graph in a 2D or 3D grid.

Calculates a star-like layout for the graph.

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.

Places the vertices on a 2D plane according to the Davidson-Harel layout algorithm.

The algorithm uses simulated annealing and a sophisticated energy function, which is unfortunately hard to parameterize for different graphs. The original publication did not disclose any parameter values, and the ones below were determined by experimentation.

The algorithm consists of two phases: an annealing phase and a fine-tuning phase. There is no simulated annealing in the second phase.

Places the vertices on a 2D plane or in the 3D space ccording 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.

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

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.

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

Places the vertices in an Euclidean space with the given number of dimensions using multidimensional scaling.

This layout requires a distance matrix, where the intersection of row i and column j specifies the desired distance between vertex i and vertex j. The algorithm will try to place the vertices in a way that approximates the distance relations prescribed in the distance matrix. igraph uses the classical multidimensional scaling by Torgerson (see reference below).

For unconnected graphs, the method will decompose the graph into weakly connected components and then lay out the components individually using the appropriate parts of the distance matrix.

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

This is a tree layout. If the given graph is not a tree, a breadth-first search is executed first to obtain a possible spanning tree.

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.

See layout_reingold_tilford for the explanation of the parameters.

Places the vertices of the graph randomly.

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

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

Constructs a depth first search (DFS) iterator of the graph.

Returns the adjacency matrix of a graph.

Returns the edge list of a graph.

Internal function, undocumented.

Converts an undirected graph to directed.

Converts a directed graph to undirected.

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 vertices 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.

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 vertices are identified by 's' in the FLOW field, target vertices are identified by 't'.
• Node indices start from 1. Only a single source and target node is allowed.

Reads an UCINET DL file and creates a graph based on it.

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

Please note that the vertex indices are zero-based. A vertex of zero degree will be created for every integer that is in range but does not appear in the edgelist.

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

GraphDB is a binary format, used in the graph database for isomorphism testing (see http://amalfi.dis.unina.it/graph/).

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

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

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 repository of LGL for more information.

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

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.

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

Writes the graph in DIMACS format to the given file.

Writes the graph in DOT format to the given file.

DOT is the format used by the GraphViz software package.

Writes the edge list of a graph to a file.

Directed edges are written in (from, to) order.

Writes the graph in GML format to the given file.

Writes the edge list of a graph to a file in .ncol format.

Note that multiple edges and/or loops break the LGL software, but igraph does not check for this condition. Unless you know that the graph does not have multiple edges and/or loops, it is wise to call simplify() before saving.

Writes the edge list of a graph to a file in .lgl format.

Note that multiple edges and/or loops break the LGL software, but igraph does not check for this condition. Unless you know that the graph does not have multiple edges and/or loops, it is wise to call simplify() before saving.

Writes the graph in Pajek format to the given file.

Writes the graph to a GraphML file.

Writes the graph to a file in LEDA native format.

The LEDA format supports at most one attribute per vertex and edge. You can specify which vertex and edge attribute you want to use. Note that the name of the attribute is not saved in the LEDA file.

Calculates the canonical permutation of a graph using the BLISS isomorphism algorithm.

Passing the permutation returned here to permute_vertices() will transform the graph into its canonical form.

See http://www.tcs.hut.fi/Software/bliss/index.html for more information about the BLISS algorithm and canonical permutations.

Returns the isomorphism class of the graph or its subgraph.

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

Checks whether the graph is isomorphic to 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 isomorphic_vf2).
• Otherwise the BLISS isomorphism algorithm is used, see isomorphic_bliss.

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

See http://www.tcs.hut.fi/Software/bliss/index.html for more information about the BLISS algorithm.

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

Vertex and edge colors may be used to restrict the isomorphisms, as only vertices and edges with the same color will be allowed to match each other.

Determines the number of isomorphisms between the graph and another one

Vertex and edge colors may be used to restrict the isomorphisms, as only vertices and edges with the same color will be allowed to match each other.

Returns all isomorphisms between the graph and another one

Vertex and edge colors may be used to restrict the isomorphisms, as only vertices and edges with the same color will be allowed to match each other.

Checks whether a subgraph of the graph is isomorphic to another graph.

Vertex and edge colors may be used to restrict the isomorphisms, as only vertices and edges with the same color will be allowed to match each other.

Determines the number of subisomorphisms between the graph and another one

Vertex and edge colors may be used to restrict the isomorphisms, as only vertices and edges with the same color will be allowed to match each other.

Returns all subisomorphisms between the graph and another one

Vertex and edge colors may be used to restrict the isomorphisms, as only vertices and edges with the same color will be allowed to match each other.

Checks whether a subgraph of the graph is isomorphic to another graph.

The optional domains argument may be used to restrict vertices that may match each other. You can also specify whether you are interested in induced subgraphs only or not.

Returns all subisomorphisms between the graph and another one using the LAD algorithm.

The optional domains argument may be used to restrict vertices that may match each other. You can also specify whether you are interested in induced subgraphs only or not.

Returns the complementer of the graph

Returns the composition of two graphs.

Subtracts the given graph from the original

Returns the dominator tree from the given root node

Returns the value of the maximum flow between the source and target vertices.

Returns the maximum flow between the source and target vertices.

Returns all the cuts between the source and target vertices in a directed graph.

This function lists all edge-cuts between a source and a target vertex. Every cut is listed exactly once.

Returns all minimum cuts between the source and target vertices in a directed graph.

Returns the minimum cut between the source and target vertices or within the whole graph.

Calculates the minimum cut between the source and target vertices or within the whole graph.

The minimum cut is the minimum set of edges that needs to be removed to separate the source and the target (if they are given) or to disconnect the graph (if the source and target are not given). The minimum is calculated using the weights (capacities) of the edges, so the cut with the minimum total capacity is calculated. For undirected graphs and no source and target, the method uses the Stoer-Wagner algorithm. For a given source and target, the method uses the push-relabel algorithm; see the references below.

Calculates the minimum cut between the source and target vertices in a graph.

Internal function, undocumented.

Returns a list containing all the minimal s-t separators of a graph.

A minimal separator is a set of vertices whose removal disconnects the graph, while the removal of any subset of the set keeps the graph connected.

Decides whether the given vertex set is a minimal separator.

A minimal separator is a set of vertices whose removal disconnects the graph, while the removal of any subset of the set keeps the graph connected.

Decides whether the removal of the given vertices disconnects the graph.

Returns a list containing all separator vertex sets of minimum size.

A vertex set is a separator if its removal disconnects the graph. This method lists all the separators for which no smaller separator set exists in the given graph.

Calculates the cohesive block structure of the graph.

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)

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 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 clique number of the graph.

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

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.