Lowlevel representation of a graph.
Don't use it directly, use igraph.Graph
instead.
Method  __new__ 
Create and return a new object. See help(type) for accurate signature. 
Method  add 
Adds edges to the graph. 
Method  add 
Adds vertices to the graph. 
Method 

Generates a graph from its adjacency matrix. 
Method  all 
Returns a list containing all the minimal st separators of a graph. 
Method  all 
Returns all the cuts between the source and target vertices in a directed graph. 
Method  all 
Returns all minimum cuts between the source and target vertices in a directed graph. 
Method  are 
Decides whether two given vertices are directly connected. 
Method  articulation 
Returns the list of articulation points in the graph. 
Method  assortativity 
Returns the assortativity of the graph based on numeric properties of the vertices. 
Method  assortativity 
Returns the assortativity of a graph based on vertex degrees. 
Method  assortativity 
Returns the assortativity of the graph based on vertex categories. 
Method 

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

Generates a graph from the Graph Atlas. 
Method  attributes 
No summary 
Method  authority 
Calculates Kleinberg's authority score for the vertices of the graph 
Method  automorphism 
Calculates the generators of the automorphism group of a graph using the BLISS isomorphism algorithm. 
Method  average 
Calculates the average path length in a graph. 
Method 

Generates a graph based on the BarabásiAlbert model. 
Method  betweenness 
Calculates or estimates the betweenness of vertices in a graph. 
Method  bfs 
Conducts a breadth first search (BFS) on the graph. 
Method  bfsiter 
Constructs a breadth first search (BFS) iterator of the graph. 
Method  bibcoupling 
Calculates bibliographic coupling scores for given vertices in a graph. 
Method  biconnected 
Calculates the biconnected components of the graph. 
Method  bipartite 
Internal function, undocumented. 
Method  bipartite 
Internal function, undocumented. 
Method  bridges 
Returns the list of bridges in the graph. 
Method  canonical 
Calculates the canonical permutation of a graph using the BLISS isomorphism algorithm. 
Method  chordal 
Returns the list of edges needed to be added to the graph to make it chordal. 
Method 

Generates a ChungLu random graph. 
Method  clique 
Returns the clique number of the graph. 
Method  cliques 
Returns some or all cliques of the graph as a list of tuples. 
Method  closeness 
Calculates the closeness centralities of given vertices in a graph. 
Method  cocitation 
Calculates cocitation scores for given vertices in a graph. 
Method  cohesive 
Calculates the cohesive block structure of the graph. 
Method  community 
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... 
Method  community 
Finds the community structure of the graph according to the algorithm of Clauset et al based on the greedy optimization of modularity. 
Method  community 
Finds the community structure of the network according to the Infomap method of Martin Rosvall and Carl T. Bergstrom. 
Method  community 
Finds the community structure of the graph according to the label propagation method of Raghavan et al. 
Method  community 
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. 
Method  community 
Finds the community structure of the graph using the Leiden algorithm of Traag, van Eck & Waltman. 
Method  community 
Finds the community structure of the graph according to the multilevel algorithm of Blondel et al. This is a bottomup algorithm: initially every vertex belongs to a separate community, and vertices are moved between communities iteratively in a way that maximizes the vertices' local contribution to the overall modularity score... 
Method  community 
Calculates the optimal modularity score of the graph and the corresponding community structure. 
Method  community 
Finds the community structure of the graph according to the spinglass community detection method of Reichardt & Bornholdt. 
Method  community 
Finds the community structure of the graph according to the random walk method of Latapy & Pons. 
Method  complementer 
Returns the complementer of the graph 
Method  compose 
Returns the composition of two graphs. 
Method  connected 
Calculates the (strong or weak) connected components for a given graph. 
Method  constraint 
Calculates Burt's constraint scores for given vertices in a graph. 
Method  contract 
Contracts some vertices in the graph, i.e. replaces groups of vertices with single vertices. Edges are not affected. 
Method  convergence 
Undocumented (yet). 
Method  convergence 
Undocumented (yet). 
Method  copy 
Creates a copy of the graph. 
Method  coreness 
Finds the coreness (shell index) of the vertices of the network. 
Method  count 
Calculates the number of automorphisms of a graph using the BLISS isomorphism algorithm. 
Method  count 
Determines the number of isomorphisms between the graph and another one 
Method  count 
Counts the multiplicities of the given edges. 
Method  count 
Determines the number of subisomorphisms between the graph and another one 
Method 

Generates a de Bruijn graph with parameters (m, n) 
Method  decompose 
Decomposes the graph into subgraphs. 
Method  degree 
Returns some vertex degrees from the graph. 
Method 

Generates a graph with a given degree sequence. 
Method  delete 
Removes edges from the graph. 
Method  delete 
Deletes vertices and all its edges from the graph. 
Method  density 
Calculates the density of the graph. 
Method  dfsiter 
Constructs a depth first search (DFS) iterator of the graph. 
Method  diameter 
Calculates the diameter of the graph. 
Method  difference 
Subtracts the given graph from the original 
Method  distances 
Calculates shortest path lengths for given vertices in a graph. 
Method  diversity 
Calculates the structural diversity index of the vertices. 
Method  dominator 
Returns the dominator tree from the given root node 
Method  dyad 
Dyad census, as defined by Holland and Leinhardt 
Method  eccentricity 
Calculates the eccentricities of given vertices in a graph. 
Method  ecount 
Counts the number of edges. 
Method  edge 
No summary 
Method  edge 
Calculates or estimates the edge betweennesses in a graph. 
Method  edge 
Calculates the edge connectivity of the graph or between some vertices. 
Method  eigen 
Undocumented 
Method  eigenvector 
Calculates the eigenvector centralities of the vertices in a graph. 
Method 

Generates a graph based on the ErdősRényi model. 
Method 

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

Generates a famous graph based on its name. 
Method  farthest 
Returns two vertex IDs whose distance equals the actual diameter of the graph. 
Method  feedback 
Calculates an approximately or exactly minimal feedback arc set. 
Method 

Generates a graph based on the forest fire model 
Method 

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

Generates a full citation graph 
Method  fundamental 
Finds a single fundamental cycle basis of the graph 
Method  get 
Returns the adjacency matrix of a graph. 
Method  get 
Calculates all of the shortest paths from/to a given node in a graph. 
Method  get 
Internal function, undocumented. 
Method  get 
Returns a path with the actual diameter of the graph. 
Method  get 
Returns the edge list of a graph. 
Method  get 
Returns the edge ID of an arbitrary edge between vertices v1 and v2 
Method  get 
Returns the edge IDs of some edges between some vertices. 
Method  get 
Returns all isomorphisms between the graph and another one 
Method  get 
Calculates the k shortest paths from/to a given node in a graph. 
Method  get 
Calculates the shortest path from a source vertex to a target vertex in a graph. 
Method  get 
Calculates the shortest path from a source vertex to a target vertex in a graph using the AStar algorithm and a heuristic function. 
Method  get 
Calculates the shortest paths from/to a given node in a graph. 
Method  get 
Returns all subisomorphisms between the graph and another one using the LAD algorithm. 
Method  get 
Returns all subisomorphisms between the graph and another one 
Method  girth 
Returns the girth of the graph. 
Method  gomory 
Internal function, undocumented. 
Method 

Generates a growing random graph. 
Method  harmonic 
Calculates the harmonic centralities of given vertices in a graph. 
Method  has 
Checks whether the graph has multiple edges. 
Method 

Generates a regular hexagonal lattice. 
Method  hub 
Calculates Kleinberg's hub score for the vertices of the graph 
Method  incident 
Returns the edges a given vertex is incident on. 
Method  independence 
Returns the independence number of the graph. 
Method  independent 
Returns some or all independent vertex sets of the graph as a list of tuples. 
Method  induced 
Returns a subgraph spanned by the given vertices. 
Method  is 
Returns whether the graph is acyclic (i.e. contains no cycles). 
Method  is 
Decides whether the graph is biconnected. 
Method  is 
Decides whether the graph is bipartite or not. 
Method  is 
Returns whether the graph is chordal or not. 
Method  is 
Checks whether the graph is complete, i.e. whether there is at least one connection between all distinct pairs of vertices. In directed graphs, ordered pairs are considered. 
Method  is 
Decides whether the graph is connected. 
Method  is 
Checks whether the graph is a DAG (directed acyclic graph). 
Method  is 
Checks whether the graph is directed. 
Method  is 
Checks whether a specific set of edges contain loop edges 
Method  is 
Decides whether the given vertex set is a minimal separator. 
Method  is 
Checks whether an edge is a multiple edge. 
Method  is 
Checks whether an edge has an opposite pair. 
Method  is 
Decides whether the removal of the given vertices disconnects the graph. 
Method  is 
Checks whether the graph is simple (no loop or multiple edges). 
Method  is 
Checks whether the graph is a (directed or undirected) tree graph. 
Method 

Generates a graph with a given isomorphism class. 
Method  isoclass 
Returns the isomorphism class of the graph or its subgraph. 
Method  isomorphic 
Checks whether the graph is isomorphic to another graph. 
Method  isomorphic 
Checks whether the graph is isomorphic to another graph, using the BLISS isomorphism algorithm. 
Method  isomorphic 
Checks whether the graph is isomorphic to another graph, using the VF2 isomorphism algorithm. 
Method 

Generates a kregular random graph 
Method 

Generates a Kautz graph with parameters (m, n) 
Method  knn 
Calculates the average degree of the neighbors for each vertex, and the same quantity as the function of vertex degree. 
Method  laplacian 
Returns the Laplacian matrix of a graph. 
Method  largest 
Returns the largest cliques of the graph as a list of tuples. 
Method  largest 
Returns the largest independent vertex sets of the graph as a list of tuples. 
Method 

Generates a regular square lattice. 
Method  layout 
Place the vertices of a bipartite graph in two layers. 
Method  layout 
Places the vertices of the graph uniformly on a circle or a sphere. 
Method  layout 
Places the vertices on a 2D plane according to the DavidsonHarel layout algorithm. 
Method  layout 
Places the vertices on a 2D plane or in the 3D space ccording to the DrL layout algorithm. 
Method  layout 
Places the vertices on a 2D plane according to the FruchtermanReingold algorithm. 
Method  layout 
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. 
Method  layout 
Places the vertices of a graph in a 2D or 3D grid. 
Method  layout 
Places the vertices on a plane according to the KamadaKawai algorithm. 
Method  layout 
Places the vertices on a 2D plane according to the Large Graph Layout. 
Method  layout 
Places the vertices in an Euclidean space with the given number of dimensions using multidimensional scaling. 
Method  layout 
Places the vertices of the graph randomly. 
Method  layout 
Places the vertices on a 2D plane according to the ReingoldTilford layout algorithm. 
Method  layout 
Circular ReingoldTilford layout for trees. 
Method  layout 
Calculates a starlike layout for the graph. 
Method  layout 
Uniform Manifold Approximation and Projection (UMAP). 
Method  LCF 
Generates a graph from LCF notation. 
Method  linegraph 
Returns the line graph of the graph. 
Method  list 
Lists the triangles of the graph 
Method  maxdegree 
Returns the maximum degree of a vertex set in the graph. 
Method  maxflow 
Returns the maximum flow between the source and target vertices. 
Method  maxflow 
Returns the value of the maximum flow between the source and target vertices. 
Method  maximal 
Returns the maximal cliques of the graph as a list of tuples. 
Method  maximal 
Returns the maximal independent vertex sets of the graph as a list of tuples. 
Method  maximum 
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. 
Method  mincut 
Calculates the minimum cut between the source and target vertices or within the whole graph. 
Method  mincut 
Returns the minimum cut between the source and target vertices or within the whole graph. 
Method  minimum 
Computes a minimum cycle basis of the graph 
Method  minimum 
Returns a list containing all separator vertex sets of minimum size. 
Method  modularity 
Calculates the modularity of the graph with respect to some vertex types. 
Method  modularity 
Calculates the modularity matrix of the graph. 
Method  motifs 
Counts the number of motifs in the graph 
Method  motifs 
Counts the total number of motifs in the graph 
Method  motifs 
Counts the total number of motifs in the graph 
Method  neighborhood 
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. 
Method  neighborhood 
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... 
Method  neighbors 
Returns adjacent vertices to a given vertex. 
Method  path 
Calculates the path length histogram of the graph Attention: this function is wrapped in a more convenient syntax in the derived class Graph . It is advised to use that instead of this version. 
Method  permute 
Permutes the vertices of the graph according to the given permutation and returns the new graph. 
Method  personalized 
Calculates the personalized PageRank values of a graph. 
Method  predecessors 
Returns the predecessors of a given vertex. 
Method 

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

Generates a tree from its Prüfer sequence. 
Method  radius 
Calculates the radius of the graph. 
Method  random 
Performs a random walk of a given length from a given node. 
Method 

Reads a graph from a file conforming to the DIMACS minimumcost flow file format. 
Method 

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

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

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

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

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

Reads an .lgl file used by LGL. 
Method 

Reads an .ncol file used by LGL. 
Method 

Reads a file in the Pajek format and creates a graph based on it. Only Pajek network files (.net extension) are supported, not project files (.paj). 
Method 

Generates a bipartite graph from the degree sequences of its partitions. 
Method 

Generates a graph from a degree sequence. 
Method 

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. 
Method  reciprocity 
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... 
Method  reverse 
Reverses the direction of some edges in the graph. 
Method  rewire 
Randomly rewires the graph while preserving the degree distribution. 
Method  rewire 
Rewires the edges of a graph with constant probability. 
Method 

Generates a ring graph. 
Method  SBM 
Generates a graph based on a stochastic block model. 
Method  similarity 
Dice similarity coefficient of vertices. 
Method  similarity 
Inverse logweighted similarity coefficient of vertices. 
Method  similarity 
Jaccard similarity coefficient of vertices. 
Method  simplify 
Simplifies a graph by removing selfloops and/or multiple edges. 
Method  st 
Calculates the minimum cut between the source and target vertices in a graph. 
Method 

Generates a star graph. 
Method 

Generates a nongrowing graph with edge probabilities proportional to node fitnesses. 
Method 

Generates a nongrowing graph with prescribed powerlaw degree distributions. 
Method  strength 
Returns the strength (weighted degree) of some vertices from the graph 
Method  subcomponent 
Determines the indices of vertices which are in the same component as a given vertex. 
Method  subgraph 
Returns a subgraph spanned by the given edges. 
Method  subisomorphic 
Checks whether a subgraph of the graph is isomorphic to another graph. 
Method  subisomorphic 
Checks whether a subgraph of the graph is isomorphic to another graph. 
Method  successors 
Returns the successors of a given vertex. 
Method  to 
Converts an undirected graph to directed. 
Method  to 
Converts a tree graph into a Prüfer sequence. 
Method  to 
Converts a directed graph to undirected. 
Method  topological 
Calculates a possible topological sorting of the graph. 
Method  transitivity 
Calculates the average of the vertex transitivities of the graph. 
Method  transitivity 
Calculates the local transitivity (clustering coefficient) of the given vertices in the graph. 
Method  transitivity 
Calculates the global transitivity (clustering coefficient) of the graph. 
Method 

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

Generates a random tree by sampling uniformly from the set of labelled trees with a given number of nodes. 
Method  triad 
Triad census, as defined by Davis and Leinhardt 
Method 

Generates a regular triangular lattice. 
Method  unfold 
Unfolds the graph using a BFS to a tree by duplicating vertices as necessary. 
Method  vcount 
Counts the number of vertices. 
Method  vertex 
No summary 
Method  vertex 
Calculates a greedy vertex coloring for the graph based on some heuristics. 
Method  vertex 
Calculates the vertex connectivity of the graph or between some vertices. 
Method 

This function generates networks with the smallworld property based on a variant of the WattsStrogatz model. The network is obtained by first creating a periodic undirected lattice, then rewiring both endpoints of each edge with probability ... 
Method  write 
Writes the graph in DIMACS format to the given file. 
Method  write 
Writes the graph in DOT format to the given file. 
Method  write 
Writes the edge list of a graph to a file. 
Method  write 
Writes the graph in GML format to the given file. 
Method  write 
Writes the graph to a GraphML file. 
Method  write 
Writes the graph to a file in LEDA native format. 
Method  write 
Writes the edge list of a graph to a file in .lgl format. 
Method  write 
Writes the edge list of a graph to a file in .ncol format. 
Method  write 
Writes the graph in Pajek format to the given file. 
Method  __graph 
Returns the igraph graph encapsulated by the Python object as a PyCapsule 
Method  __invalidate 
Invalidates the internal cache of the lowlevel C graph object that the Python object wraps. This function should not be used directly by igraph users, but it may be useful for benchmarking or debugging purposes. 
Method  __register 
Registers a destructor to be called when the object is freed by Python. This function should not be used directly by igraph users. 
Method  _ 
Internal function, undocumented. 
Method  _ 
Internal function, undocumented. 
Method  _ 
Internal function, undocumented. 
Method  _get 
Internal function, undocumented. 
Method  _GRG 
Internal function, undocumented. 
Method  _is 
Internal function, undocumented. 
Method  _is 
Internal function, undocumented. 
Method  _layout 
Internal function, undocumented. 
Method  _maximum 
Internal function, undocumented. 
Method  _ 
Internal function, undocumented. 
Method  _raw 
Returns the memory address of the igraph graph encapsulated by the Python object as an ordinary Python integer. 
Method  _spanning 
Internal function, undocumented. 
Method  _ 
Generates a graph from its adjacency matrix. 
igraph.Graph
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. 
igraph.Graph
Generates a graph from its adjacency matrix.
Parameters  
matrix  the adjacency matrix 
mode  the mode to be used. Possible values are:

loops  specifies how the diagonal of the matrix should be handled:

Returns a list containing all the minimal st 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.
Reference: Anne Berry, JeanPaul Bordat and Olivier Cogis: Generating all the minimal separators of a graph. In: Peter Widmayer, Gabriele Neyer and Stephan Eidenbenz (eds.): Graphtheoretic concepts in computer science, 1665, 167172, 1999. Springer.
Returns  
a list where each item lists the vertex indices of a given minimal st separator. 
igraph.Graph
Returns all the cuts between the source and target vertices in a directed graph.
This function lists all edgecuts between a source and a target vertex. Every cut is listed exactly once.
Attention: this function has a more convenient interface in class Graph
, which wraps the result in a list of Cut
objects. It is advised to use that.
Parameters  
source  the source vertex ID 
target  the target vertex ID 
Returns  
a tuple where the first element is a list of lists of edge IDs representing a cut and the second element is a list of lists of vertex IDs representing the sets of vertices that were separated by the cuts. 
Decides whether two given vertices are directly connected.
Parameters  
v1  the ID or name of the first vertex 
v2  the ID or name of 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 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 distribution 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.
References
 Newman MEJ: Mixing patterns in networks, Phys Rev E 67:026126, 2003.
 Newman MEJ: Assortative mixing in networks, Phys Rev Lett 89:208701, 2002.
Parameters  
types1  vertex types in a list or the name of a vertex attribute holding vertex types. Types are ideally denoted by numeric values. 
types2  in directed assortativity calculations, each vertex can have an outtype and an intype. In this case, types1 contains the outtypes and this parameter contains the intypes in a list or the name of a vertex attribute. If None, it is assumed to be equal to types1. 
directed  whether to consider edge directions or not. 
normalized  whether to compute the normalized covariance, i.e. Pearson correlation. Supply True here to compute the standard assortativity. 
Returns  
the assortativity coefficient  
See Also  
assortativity_degree() when the types are the vertex degrees 
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.
Parameters  
directed  whether to consider edge directions for directed graphs or not. This argument is ignored for undirected graphs. 
Returns  
the assortativity coefficient  
See Also  
assortativity() 
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.
Reference: Newman MEJ: Mixing patterns in networks, Phys Rev E 67:026126, 2003.
Parameters  
types  vertex types in a list or the name of a vertex attribute holding vertex types. Types should be denoted by numeric values. 
directed  whether to consider edge directions or not. 
normalized  whether to compute the (usual) normalized assortativity. The unnormalized version is identical to modularity. Supply True here to compute the standard assortativity. 
Returns  
the assortativity coefficient 
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.
Parameters  
n  the number of vertices in the graph 
type  matrix giving the joint distribution of vertex types 
pref  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.
Reference: Ronald C. Read and Robin J. Wilson: An Atlas of Graphs. Oxford University Press, 1998.
Parameters  
idx  The index of the graph to be generated. Indices start from zero, graphs are listed:

Calculates Kleinberg's authority score for the vertices of the graph
Parameters  
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
scale  whether to normalize the scores so that the largest one is 1. 
arpack  an ARPACKOptions object used to finetune the ARPACK eigenvector calculation. If omitted, the modulelevel variable called arpack_options is used. 
return  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  
See Also  
hub_score() 
Calculates the generators of the automorphism group of a graph using the BLISS isomorphism algorithm.
The generator set may not be minimal and may depend on the splitting heuristics. The generators are permutations represented using zerobased indexing.
Parameters  
sh  splitting heuristics for graph as a caseinsensitive string, with the following possible values:

color  optional vector storing a coloring of the vertices with respect to which the isomorphism is computed. If None, all vertices have the same color. 
Returns  
a list of integer vectors, each vector representing an automorphism group of the graph. 
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. 
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
Returns  
the average path length in the graph 
Generates a graph based on the BarabásiAlbert model.
Reference: Barabási, AL and Albert, R. 1999. Emergence of scaling in random networks. Science, 286 509512.
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 outdegree of a given vertex should also increase its citation probability (as well as its indegree), 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  the attractivity of vertices with degree zero. 
implementation  the algorithm to use to generate the network. Possible values are:

start  if given and not None, this must be another GraphBase object. igraph will use this graph as a starting point for the preferential attachment model. 
Calculates or estimates the betweenness of vertices in a graph.
Also supports calculating betweenness with shortest path length cutoffs or considering shortest paths only from certain source vertices or to certain target vertices.
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 vertices. If None, the exact betweenness is returned. 
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
sources  the set of source vertices to consider when calculating shortest paths. 
targets  the set of target vertices to consider when calculating shortest paths. 
Returns  
the (possibly cutofflimited) betweenness of the given vertices 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:

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. 
igraph.Graph
Calculates the biconnected components of the graph.
Components containing a single vertex only are not considered as being biconnected.
Parameters  
return  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 
igraph.Graph
Internal function, undocumented.
See Also  
Graph.bipartite_projection_size() 
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.
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.
Parameters  
sh  splitting heuristics for graph as a caseinsensitive string, with the following possible values:

color  optional vector storing a coloring of the vertices with respect to which the isomorphism is computed. If None, all vertices have the same color. 
Returns  
a permutation vector containing vertex IDs. Vertex 0 in the original graph will be mapped to an ID contained in the first element of this vector; vertex 1 will be mapped to the second and so on. 
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.
Parameters  
alpha  the alpha vector from the result of calling maximum_cardinality_search() on the graph. Useful only if you already have the alpha vector; simply passing None here will make igraph calculate the alpha vector on its own. 
alpham1  the inverse alpha vector from the result of calling maximum_cardinality_search() on the graph. Useful only if you already have the inverse alpha vector; simply passing None here will make igraph calculate the inverse alpha vector on its own. 
Returns  
the list of edges to add to the graph; each item in the list is a sourcetarget pair of vertex indices. 
Generates a ChungLu random graph.
In the ChungLu model, each pair of vertices i and j is connected with independent probability p_{ij} = w_{i}w_{j} ⁄ S, where w_{i} is a weight associated with vertex i and S = ∑_{k}w_{k} is the sum of weights. In the directed variant, vertices have both outweights, w^{out}, and inweights, w^{in}, with equal sums, S = ∑_{k}w^{out}_{k} = ∑_{k}w^{in}_{k}. The connection probability between i and j is p_{ij} = w^{out}_{i}w^{in}_{j} ⁄ S.
This model is commonly used to create random graphs with a fixed expected degree sequence. The expected degree of vertex i is approximately equal to the weight w_{i}. Specifically, if the graph is directed and selfloops are allowed, then the expected out and indegrees are precisely w^{out} and w^{in}. If selfloops are disallowed, then the expected out and indegrees are w^{out}(S − w^{in}) ⁄ S and w^{in}(S − w^{out}) ⁄ S, respectively. If the graph is undirected, then the expected degrees with and without selfloops are w(S + w) ⁄ S and w(S − w) ⁄ S, respectively.
A limitation of the original ChungLu model is that when some of the weights are large, the formula for p_{ij} yields values larger than 1. Chung and Lu's original paper exludes the use of such weights. When p_{ij} > 1, this function simply issues a warning and creates a connection between i and j. However, in this case the expected degrees will no longer relate to the weights in the manner stated above. Thus the original ChungLu model cannot produce certain (large) expected degrees.
The overcome this limitation, this function implements additional variants of the model, with modified expressions for the connection probability p_{ij} between vertices i and j. Let q_{ij} = w_{i}w_{j} ⁄ S, or q_{ij} = w^{out}_{i}w^{in}_{j} ⁄ S in the directed case. All model variants become equivalent in the limit of sparse graphs where q_{ij} approaches zero. In the original ChungLu model, selectable by setting variant to "original", p_{ij} = min(q_{ij}, 1). The "grg" variant, often referred to a the generalized random graph, uses p_{ij} = q_{ij} ⁄ (1 + q_{ij}), and is equivalent to a maximum entropy model (i.e. exponential random graph model) with a constraint on expected degrees, see Park and Newman (2004), Section B, setting exp( − Θ_{ij}) = w_{i}w_{j} ⁄ S. This model is also discussed by Britton, Deijfen and MartinLöf (2006). By virtue of being a degreeconstrained maximum entropy model, it generates graphs having the same degree sequence with the same probability. A third variant can be requested with "nr", and uses p_{ij} = 1 − exp( − q_{ij}). This is the underlying simple graph of a multigraph model introduced by Norros and Reittu (2006). For a discussion of these three model variants, see Section 16.4 of Bollobás, Janson, Riordan (2007), as well as Van Der Hofstad (2013).
References:
 Chung F and Lu L: Connected components in a random graph with given degree sequences. Annals of Combinatorics 6, 125145 (2002) https://doi.org/10.1007/PL00012580
 Miller JC and Hagberg A: Efficient Generation of Networks with Given Expected Degrees (2011) https://doi.org/10.1007/9783642212864_10
 Park J and Newman MEJ: Statistical mechanics of networks. Physical Review E 70, 066117 (2004). https://doi.org/10.1103/PhysRevE.70.066117
 Britton T, Deijfen M, MartinLöf A: Generating Simple Random Graphs with Prescribed Degree Distribution. J Stat Phys 124, 1377–1397 (2006). https://doi.org/10.1007/s109550069168x
 Norros I and Reittu H: On a conditionally Poissonian graph process. Advances in Applied Probability 38, 59–75 (2006). https://doi.org/10.1239/aap/1143936140
 Bollobás B, Janson S, Riordan O: The phase transition in inhomogeneous random graphs. Random Struct Algorithms 31, 3–122 (2007). https://doi.org/10.1002/rsa.20168
 Van Der Hofstad R: Critical behavior in inhomogeneous random graphs. Random Struct Algorithms 42, 480–508 (2013). https://doi.org/10.1002/rsa.20450
Parameters  
out  the vertex weights (or outweights). In sparse graphs these will be approximately equal to the expected (out)degrees. 
in_  the vertex inweights, approximately equal to the expected indegrees of the graph. If omitted, the generated graph will be undirected. 
loops  whether to allow the generation of selfloops. 
variant  the model variant to be used. Let q_{ij} = w_{i}w_{j} ⁄ S, where S = ∑_{k}w_{k}. The following variants are available:

Returns the clique number of the graph.
The clique number of the graph is the size of the largest clique.
See Also  
largest_cliques() for the largest cliques. 
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 vertices in a graph.
The closeness centrality 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.
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 vertices (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. 
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
normalized  Whether to normalize the raw closeness scores by multiplying by the number of vertices minus one. 
Returns  
the calculated closenesses in a list 
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. 
igraph.Graph
Calculates the cohesive block structure of the graph.
Attention: this function has a more convenient interface in class Graph
, which wraps the result in a CohesiveBlocks
object. It is advised to use that.
igraph.Graph
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, 78217826 (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.
Attention: this function is wrapped in a more convenient syntax in the derived class Graph
. It is advised to use that instead of this version.
Parameters  
directed  whether to take into account the directedness of the edges when we calculate the betweenness values. 
weights  name of an edge attribute or a list containing edge weights. 
Returns  
a tuple with the merge matrix that describes the dendrogram and the modularity scores before each merge. The modularity scores use the weights if the original graph was weighted. 
igraph.Graph
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 bottomup 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.
Attention: this function is wrapped in a more convenient syntax in the derived class Graph
. It is advised to use that instead of this version.
Reference: A. Clauset, M. E. J. Newman and C. Moore: Finding community structure in very large networks. Phys Rev E 70, 066111 (2004).
Parameters  
weights  name of an edge attribute or a list containing edge weights 
Returns  
a tuple with the following elements:
 
See Also  
modularity() 
igraph.Graph
Finds the community structure of the network according to the Infomap method of Martin Rosvall and Carl T. Bergstrom.
See http://www.mapequation.org for a visualization of the algorithm or one of the references provided below. References
 M. Rosvall and C. T. Bergstrom: Maps of information flow reveal community structure in complex networks. PNAS 105, 1118 (2008). http://arxiv.org/abs/0707.0609
 M. Rosvall, D. Axelsson and C. T. Bergstrom: The map equation. Eur Phys J Special Topics 178, 13 (2009). http://arxiv.org/abs/0906.1405
Parameters  
edge  name of an edge attribute or a list containing edge weights. 
vertex  name of an vertex attribute or a list containing vertex weights. 
trials  the number of attempts to partition the network. 
Returns  
the calculated membership vector and the corresponding codelength in a tuple. 
igraph.Graph
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.
Reference: Raghavan, U.N. and Albert, R. and Kumara, S. Near linear time algorithm to detect community structures in largescale networks. Phys Rev E 76:036106, 2007. http://arxiv.org/abs/0709.2938.
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 
igraph.Graph
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.
Attention: this function is wrapped in a more convenient syntax in the derived class Graph
. It is advised to use that instead of this version.
Reference: MEJ Newman: Finding community structure in networks using the eigenvectors of matrices, arXiv:physics/0605087
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. 
arpack  an ARPACKOptions object used to finetune the ARPACK eigenvector calculation. If omitted, the modulelevel variable called arpack_options is used. 
weights  name of an edge attribute or a list containing edge weights 
Returns  
a tuple where the first element is the membership vector of the clustering and the second element is the merge matrix. 
igraph.Graph
Finds the community structure of the graph using the Leiden algorithm of Traag, van Eck & Waltman.
Parameters  
edge  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
node  the node weights used in the Leiden algorithm. 
resolution  the resolution parameter to use. Higher resolutions lead to more smaller communities, while lower resolutions lead to fewer larger communities. 
normalize  if set to true, the resolution parameter will be divided by the sum of the node weights. If this is not supplied, it will default to the node degree, or weighted degree in case edge_weights are supplied. 
beta  parameter affecting the randomness in the Leiden algorithm. This affects only the refinement step of the algorithm. 
initial  if provided, the Leiden algorithm will try to improve this provided membership. If no argument is provided, the aglorithm simply starts from the singleton partition. 
n  the number of iterations to iterate the Leiden algorithm. Each iteration may improve the partition further. You can also set this parameter to a negative number, which means that the algorithm will be iterated until an iteration does not change the current membership vector any more. 
Returns  
the community membership vector. 
igraph.Graph
Finds the community structure of the graph according to the multilevel algorithm of Blondel et al. This is a bottomup algorithm: initially every vertex belongs to a separate community, and vertices are moved between communities iteratively in a way that maximizes the vertices' local contribution to the overall modularity score. When a consensus is reached (i.e. no single move would increase the modularity score), every community in the original graph is shrank to a single vertex (while keeping the total weight of the incident edges) and the process continues on the next level. The algorithm stops when it is not possible to increase the modularity any more after shrinking the communities to vertices.
Reference: VD Blondel, JL Guillaume, R Lambiotte and E Lefebvre: Fast unfolding of community hierarchies in large networks. J Stat Mech P10008 (2008), http://arxiv.org/abs/0803.0476
Attention: this function is wrapped in a more convenient syntax in the derived class Graph
. It is advised to use that instead of this version.
Parameters  
weights  name of an edge attribute or a list containing edge weights 
return  if True, returns the multilevel result. If False, only the best level (corresponding to the best modularity) is returned. 
resolution  the resolution parameter to use in the modularity measure. Smaller values result in a smaller number of larger clusters, while higher values yield a large number of small clusters. The classical modularity measure assumes a resolution parameter of 1. 
Returns  
either a single list describing the community membership of each vertex (if return_levels is False), or a list of community membership vectors, one corresponding to each level and a list of corresponding modularities (if return_levels is True).  
See Also  
modularity() 
igraph.Graph
Calculates the optimal modularity score of the graph and the corresponding community structure.
This function uses the GNU Linear Programming Kit to solve a large integer optimization problem in order to find the optimal modularity score and the corresponding community structure, therefore it is unlikely to work for graphs larger than a few (less than a hundred) vertices. Consider using one of the heuristic approaches instead if you have such a large graph.
Parameters  
weights  name of an edge attribute or a list containing edge weights. 
Returns  
the calculated membership vector and the corresponding modularity in a tuple. 
igraph.Graph
Finds the community structure of the graph according to the spinglass community detection method of Reichardt & Bornholdt.
Parameters  
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
spins  integer, the number of spins to use. This is the upper limit for the number of communities. It is not a problem to supply a (reasonably) big number here, in which case some spin states will be unpopulated. 
parupdate  whether to update the spins of the vertices in parallel (synchronously) or not 
start  the starting temperature 
stop  the stop temperature 
cool  cooling factor for the simulated annealing 
update  specifies the null model of the simulation. Possible values are "config" (a random graph with the same vertex degrees as the input graph) or "simple" (a random graph with the same number of edges) 
gamma  the gamma argument of the algorithm, specifying the balance between the importance of present and missing edges within a community. The default value of 1.0 assigns equal importance to both of them. 
implementation  currently igraph contains two implementations for the spinglass community detection algorithm. The faster original implementation is the default. The other implementation is able to take into account negative weights, this can be chosen by setting implementation to "neg". 
lambda_  the lambda argument of the algorithm, which specifies the balance between the importance of present and missing negatively weighted edges within a community. Smaller values of lambda lead to communities with less negative intraconnectivity. If the argument is zero, the algorithm reduces to a graph coloring algorithm, using the number of spins as colors. This argument is ignored if the original implementation is used. 
Returns  
the community membership vector. 
igraph.Graph
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.
Attention: this function is wrapped in a more convenient syntax in the derived class Graph
. It is advised to use that instead of this version.
Reference: Pascal Pons, Matthieu Latapy: Computing communities in large networks using random walks, http://arxiv.org/abs/physics/0512106.
Parameters  
weights  name of an edge attribute or a list containing edge weights 
steps  Undocumented 
Returns  
a tuple with the list of merges and the modularity scores corresponding to each merge  
See Also  
modularity() 
Returns the complementer of the graph
Parameters  
loops  whether to include loop edges in the complementer. 
Returns  
the complementer of the graph 
igraph.Graph
Calculates the (strong or weak) connected components for a given graph.
Attention: this function has a more convenient interface in class Graph
, which wraps the result in a VertexClustering
object. It is advised to use that.
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 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. 
Contracts some vertices in the graph, i.e. replaces groups of vertices with single vertices. Edges are not affected.
Parameters  
mapping  numeric vector which gives the mapping between old and new vertex IDs. Vertices having the same new vertex ID in this vector will be remapped into a single new vertex. It is safe to pass the membership vector of a VertexClustering object here. 
combine  specifies how to combine the attributes of the vertices being collapsed into a single one. If it is None, all the attributes will be lost. If it is a function, the attributes of the vertices will be collected and passed on to that function which will return the new attribute value that has to be assigned to the single collapsed vertex. It can also be one of the following string constants which define builtin collapsing functions: sum, prod, mean, median, max, min, first, last, random. You can also specify different combination functions for different attributes by passing a dict here which maps attribute names to functions. See simplify() for more details. 
Returns  
None.  
See Also  
simplify() 
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.
Finds the coreness (shell index) of the vertices of the network.
The kcore 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 kcore but not a member of the k + 1core.
Reference: Vladimir Batagelj, Matjaz Zaversnik: An O(m) Algorithm for Core Decomposition of Networks.
Parameters  
mode  whether to compute the incorenesses ("in"), the outcorenesses ("out") or the undirected corenesses ("all"). Ignored and assumed to be "all" for undirected graphs. 
Returns  
the corenesses for each vertex. 
Calculates the number of automorphisms of a graph using the BLISS isomorphism algorithm.
See http://www.tcs.hut.fi/Software/bliss/index.html for more information about the BLISS algorithm and canonical permutations.
Parameters  
sh  splitting heuristics for graph as a caseinsensitive string, with the following possible values:

color  optional vector storing a coloring of the vertices with respect to which the isomorphism is computed. If None, all vertices have the same color. 
Returns  
the number of automorphisms of the graph. 
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.
Parameters  
other  the other graph. If None, the number of automorphisms will be returned. 
color1  optional vector storing the coloring of the vertices of the first graph. If None, all vertices have the same color. 
color2  optional vector storing the coloring of the vertices of the second graph. If None, all vertices have the same color. 
edge  optional vector storing the coloring of the edges of the first graph. If None, all edges have the same color. 
edge  optional vector storing the coloring of the edges of the second graph. If None, all edges have the same color. 
node  a function that receives the two graphs and two node indices (one from the first graph, one from the second graph) and returns True if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on nodespecific criteria that are too complicated to be represented by node color vectors (i.e. the color1 and color2 parameters). None means that every node is compatible with every other node. 
edge  a function that receives the two graphs and two edge indices (one from the first graph, one from the second graph) and returns True if the edges given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on edgespecific criteria that are too complicated to be represented by edge color vectors (i.e. the edge_color1 and edge_color2 parameters). None means that every edge is compatible with every other node. 
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
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.
Parameters  
other  the other graph. 
color1  optional vector storing the coloring of the vertices of the first graph. If None, all vertices have the same color. 
color2  optional vector storing the coloring of the vertices of the second graph. If None, all vertices have the same color. 
edge  optional vector storing the coloring of the edges of the first graph. If None, all edges have the same color. 
edge  optional vector storing the coloring of the edges of the second graph. If None, all edges have the same color. 
node  a function that receives the two graphs and two node indices (one from the first graph, one from the second graph) and returns True if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on nodespecific criteria that are too complicated to be represented by node color vectors (i.e. the color1 and color2 parameters). None means that every node is compatible with every other node. 
edge  a function that receives the two graphs and two edge indices (one from the first graph, one from the second graph) and returns True if the edges given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on edgespecific criteria that are too complicated to be represented by edge color vectors (i.e. the edge_color1 and edge_color2 parameters). None means that every edge is compatible with every other node. 
Returns  
the number of subisomorphisms between the two given graphs 
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 
Decomposes the graph into subgraphs.
Parameters  
mode  must be either "strong" or "weak", depending on the clusters being sought. Optional, defaults to "strong". 
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 
mode  the type of degree to be returned ("out" for outdegrees, "in" for indegrees or "all" for the sum of them). 
loops  whether selfloops should be counted. 
Generates a graph with a given degree sequence.
Parameters  
out  the outdegree sequence for a directed graph. If the indegree sequence is omitted, the generated graph will be undirected, so this will be the indegree sequence as well 
in_  the indegree sequence for a directed graph. If omitted, the generated graph will be undirected. 
method  the generation method to be used. One of the following:

igraph.Graph
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. No argument deletes all edges. 
Deletes vertices and all its edges from the graph.
Parameters  
vs  a single vertex ID or the list of vertex IDs to be deleted. No argument deletes all vertices. 
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 density of the graph. 
Constructs a depth first search (DFS) 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 DFS 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 DFS tree as well. 
Returns  
the DFS iterator as an igraph.DFSIter object. 
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 
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 nonnegative. Otherwise, the BellmanFord algorithm is used if the number of requested source vertices is smaller than 100 and Johnson's algorithm is used otherwise.
Parameters  
source  a list containing the source vertex IDs which should be included in the result. If None, all vertices will be considered. 
target  a list containing the target vertex IDs which should be included in the result. If None, all vertices will be considered. 
weights  a list containing the edge weights. It can also be an attribute name (edge weights are retrieved from the given attribute) or None (all edges have equal weight). 
mode  the type of shortest paths to be used for the calculation in directed graphs. "out" means only outgoing, "in" means only incoming paths. "all" means to consider the directed graph as an undirected one. 
algorithm  the shortest path algorithm to use. "auto" selects an algorithm automatically based on whether the graph has negative weights or not. "dijkstra" uses Dijkstra's algorithm. "bellman_ford" uses the BellmanFord algorithm. "johnson" uses Johnson's algorithm. Ignored for unweighted graphs. 
Returns  
the shortest path lengths for given vertices in a matrix 
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.
Reference: Eagle N, Macy M and Claxton R: Network diversity and economic development, Science 328, 10291031, 2010.
Parameters  
vertices  the vertices for which the diversity indices must be returned. If None, uses all of the vertices in the graph. 
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
Returns  
the calculated diversity indices in a list, or a single number if a single vertex was supplied. 
Returns the dominator tree from the given root node
Parameters  
vid  the root vertex ID 
mode  either "in" or "out" 
Returns  
a list containing the dominator tree for the current graph. 
igraph.Graph
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.
Attention: this function has a more convenient interface in class Graph
, which wraps the result in a DyadCensus
object. It is advised to use that.
Returns  
the number of mutual, asymmetric and null connections in a 3tuple. 
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.
Parameters  
vertices  the vertices for which the eccentricity scores 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 edge directions are followed; "out" means that edge directions are followed the opposite direction; "all" means that directions are ignored. The argument has no effect for undirected graphs. 
weights  a list containing the edge weights. It can also be an attribute name (edge weights are retrieved from the given attribute) or None (all edges have equal weight). 
Returns  
the calculated eccentricities in a list, or a single number if a single vertex was supplied. 
Calculates or estimates the edge betweennesses in a graph.
Also supports calculating edge betweenness with shortest path length cutoffs or considering shortest paths only from certain source vertices or to certain target vertices.
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. 
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
sources  the set of source vertices to consider when calculating shortest paths. 
targets  the set of target vertices to consider when calculating shortest paths. 
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.
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 highscoring nodes contribute more to the score of the node in question than equal connections from lowscoring 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 selfloops 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.
Parameters  
directed  whether to consider edge directions in a directed graph. Ignored for undirected graphs. 
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  whether to return the actual largest eigenvalue along with the centralities 
arpack  an ARPACKOptions object that can be used to finetune the calculation. If it is omitted, the modulelevel 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) 
Generates a graph based on the ErdősRényi 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 selfloops 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  list giving the distribution of vertex types 
pref  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: https://igraph.org/c/doc.
Parameters  
name  the name of the graph to be generated. 
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. 
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.
Reference: Eades P, Lin X and Smyth WF: A fast and effective heuristic for the feedback arc set problem. In: Proc Inf Process Lett 319323, 1993.
Parameters  
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. When given, the algorithm will strive to remove lightweight edges in order to minimize the total weight of the feedback arc set. 
method  the algorithm to use. "eades" uses the greedy cycle breaking heuristic of Eades, Lin and Smyth, which is linear in the number of edges but not necessarily optimal; however, it guarantees that the number of edges to be removed is smaller than E/2  V/6. "ip" uses an integer programming formulation which is guaranteed to yield an optimal result, but is too slow for large graphs. 
Returns  
the IDs of the edges to be removed, in a list. 
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.
Parameters  
n  the number of vertices in the graph 
fw  forward burning probability 
bw  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 selfloops 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. 
Finds a single fundamental cycle basis of the graph
Parameters  
start  when None or negative, a complete fundamental cycle basis is returned. When it is a vertex or a vertex ID, the fundamental cycles associated with the BFS tree rooted in that vertex will be returned, only for the weakly connected component containing that vertex 
cutoff  when None or negative, a complete cycle basis is returned. Otherwise the BFS is stopped after this many steps, so the result will effectively include cycles of length 2*cutoff + 1 or shorter only. 
Returns  
the cycle basis as a list of tuples containing edge IDs 
igraph.Graph
Returns the adjacency matrix of a graph.
Parameters  
type  one of "lower" (uses the lower triangle of the matrix), "upper" (uses the upper triangle) or "both" (uses both parts). Ignored for directed graphs. 
loops  specifies how loop edges should be handled. False or "ignore" ignores loop edges. "once" counts each loop edge once in the diagonal. "twice" counts each loop edge twice (i.e. it counts the endpoints of the loop edges, not the edges themselves). 
Returns  
the adjacency matrix. 
Calculates all of the shortest paths from/to a given node in a graph.
Parameters  
v  the source for the calculated paths 
to  a vertex selector describing the destination for the calculated paths. This can be a single vertex ID, a list of vertex IDs, a single vertex name, a list of vertex names or a VertexSeq object. None means all the vertices. 
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  
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 vertices 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 ID or name of the first vertex 
v2  the ID or name of the second vertex 
directed  whether edge directions should be considered in directed graphs. The default is True. Ignored for undirected graphs. 
error  if True, an exception will be raised when the given edge does not exist. If False, 1 will be returned in that case. 
Returns  
the edge ID of an arbitrary edge between vertices v1 and v2 
Returns the edge IDs of some edges between some vertices.
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.
Parameters  
pairs  a list of integer pairs. Each integer pair is considered as a sourcetarget vertex pair; the corresponding edge is looked up in the graph and the edge ID is returned for each pair. 
directed  whether edge directions should be considered in directed graphs. The default is True. Ignored for undirected graphs. 
error  if True, an exception will be raised if a given edge does not exist. If False, 1 will be returned in that case. 
Returns  
the edge IDs in a list 
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.
Parameters  
other  the other graph. If None, the automorphisms will be returned. 
color1  optional vector storing the coloring of the vertices of the first graph. If None, all vertices have the same color. 
color2  optional vector storing the coloring of the vertices of the second graph. If None, all vertices have the same color. 
edge  optional vector storing the coloring of the edges of the first graph. If None, all edges have the same color. 
edge  optional vector storing the coloring of the edges of the second graph. If None, all edges have the same color. 
node  a function that receives the two graphs and two node indices (one from the first graph, one from the second graph) and returns True if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on nodespecific criteria that are too complicated to be represented by node color vectors (i.e. the color1 and color2 parameters). None means that every node is compatible with every other node. 
edge  a function that receives the two graphs and two edge indices (one from the first graph, one from the second graph) and returns True if the edges given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on edgespecific criteria that are too complicated to be represented by edge color vectors (i.e. the edge_color1 and edge_color2 parameters). None means that every edge is compatible with every other node. 
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 k shortest paths from/to a given node in a graph.
Parameters  
v  the ID or name of the vertex from which the paths are calculated. 
to  the ID or name of the vertex to which the paths are calculated. 
k  the desired number of shortest path 
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. 
output  determines what should be returned. If this is "vpath", a list of vertex IDs will be returned, one path for each target vertex. For unconnected graphs, some of the list elements may be empty. Note that in case of mode="in", the vertices in a path are returned in reversed order. If output="epath", edge IDs are returned instead of vertex IDs. 
Returns  
the k shortest paths from the given source node to the given target node in a list of vertex or edge IDs (depending on the value of the output argument). Note that in case of mode="in", the vertices in a path are returned in reversed order! 
Calculates the shortest path from a source vertex to a target vertex in a graph.
This function only returns a single shortest path. Consider using get_shortest_paths()
to find all shortest paths between a source and one or more target vertices.
Parameters  
v  the source vertex of the path 
to  the target vertex of the path 
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. "out" means to calculate paths from source to target, following edges according to their natural direction. "in" means to calculate paths from target to source, flipping the direction of each edge onthefly. "all" means to ignore edge directions. 
output  determines what should be returned. If this is "vpath", a list of vertex IDs will be returned. If this is "epath", edge IDs are returned instead of vertex IDs. 
algorithm  the shortest path algorithm to use. "auto" selects an algorithm automatically based on whether the graph has negative weights or not. "dijkstra" uses Dijkstra's algorithm. "bellman_ford" uses the BellmanFord algorithm. Ignored for unweighted graphs. 
Returns  
see the documentation of the output parameter.  
See Also  
get_shortest_paths() 
Calculates the shortest path from a source vertex to a target vertex in a graph using the AStar algorithm and a heuristic function.
Parameters  
v  the source vertex of the path 
to  the target vertex of the path 
heuristics  a function that will be called with the graph and two vertices, and must return an estimate of the cost of the path from the first vertex to the second vertex. The AStar algorithm is guaranteed to return an optimal solution if the heuristic is admissible, i.e. if it does never overestimate the cost of the shortest path from the given source vertex to the given target vertex. 
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. "out" means to calculate paths from source to target, following edges according to their natural direction. "in" means to calculate paths from target to source, flipping the direction of each edge onthefly. "all" means to ignore edge directions. 
output  determines what should be returned. If this is "vpath", a list of vertex IDs will be returned. If this is "epath", edge IDs are returned instead of vertex IDs. 
Returns  
see the documentation of the output parameter. 
Calculates the shortest paths from/to a given node in a graph.
Parameters  
v  the source/destination for the calculated paths 
to  a vertex selector describing the destination/source for the calculated paths. This can be a single vertex ID, a list of vertex IDs, a single vertex name, a list of vertex names or a VertexSeq object. None means all the vertices. 
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. 
output  determines what should be returned. If this is "vpath", a list of vertex IDs will be returned, one path for each target vertex. For unconnected graphs, some of the list elements may be empty. Note that in case of mode="in", the vertices in a path are returned in reversed order. If output="epath", edge IDs are returned instead of vertex IDs. 
algorithm  the shortest path algorithm to use. "auto" selects an algorithm automatically based on whether the graph has negative weights or not. "dijkstra" uses Dijkstra's algorithm. "bellman_ford" uses the BellmanFord algorithm. Ignored for unweighted graphs. 
Returns  
see the documentation of the output parameter. 
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.
Parameters  
other  the pattern graph we are looking for in the graph. 
domains  a list of lists, one sublist belonging to each vertex in the template graph. Sublist i contains the indices of the vertices in the original graph that may match vertex i in the template graph. None means that every vertex may match every other vertex. 
induced  whether to consider induced subgraphs only. 
time  an optimal time limit in seconds. Only the integral part of this number is taken into account. If the time limit is exceeded, the method will throw an exception. 
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 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.
Parameters  
other  the other graph. 
color1  optional vector storing the coloring of the vertices of the first graph. If None, all vertices have the same color. 
color2  optional vector storing the coloring of the vertices of the second graph. If None, all vertices have the same color. 
edge  optional vector storing the coloring of the edges of the first graph. If None, all edges have the same color. 
edge  optional vector storing the coloring of the edges of the second graph. If None, all edges have the same color. 
node  a function that receives the two graphs and two node indices (one from the first graph, one from the second graph) and returns True if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on nodespecific criteria that are too complicated to be represented by node color vectors (i.e. the color1 and color2 parameters). None means that every node is compatible with every other node. 
edge  a function that receives the two graphs and two edge indices (one from the first graph, one from the second graph) and returns True if the edges given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on edgespecific criteria that are too complicated to be represented by edge color vectors (i.e. the edge_color1 and edge_color2 parameters). None means that every edge is compatible with every other node. 
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  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 
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. 
Calculates the harmonic centralities of given vertices in a graph.
The harmonic centrality 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.
Parameters  
vertices  the vertices for which the harmonic centrality 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 not None, only paths less than or equal to this length are considered. 
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
normalized  Whether to normalize the result. If True, the result is the mean inverse path length to other vertices, i.e. it is normalized by the number of vertices minus one. If False, the result is the sum of inverse path lengths to other vertices. 
Returns  
the calculated harmonic centralities in a list 
Checks whether the graph has multiple edges.
Returns  
boolean  True if the graph has at least one multiple edge, False otherwise. 
Generates a regular hexagonal lattice.
Parameters  
dim  list with the dimensions of the lattice 
directed  whether to create a directed graph. 
mutual  whether to create all connections as mutual in case of a directed graph. 
Calculates Kleinberg's hub score for the vertices of the graph
Parameters  
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
scale  whether to normalize the scores so that the largest one is 1. 
arpack  an ARPACKOptions object used to finetune the ARPACK eigenvector calculation. If omitted, the modulelevel variable called arpack_options is used. 
return  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  
See Also  
authority_score() 
Returns the edges a given vertex is incident on.
Parameters  
vertex  a vertex ID 
mode  whether to return only successors ("out"), predecessors ("in") or both ("all"). Ignored for undirected graphs. 
Returns the independence number of the graph.
The independence number of the graph is the size of the largest independent vertex set.
See Also  
largest_independent_vertex_sets() for the largest independent vertex sets 
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. 
Returns a subgraph spanned by the given vertices.
Parameters  
vertices  a list containing the vertex IDs which should be included in the result. 
implementation  the implementation to use when constructing the new subgraph. igraph includes two implementations at the moment. "copy_and_delete" copies the original graph and removes those vertices that are not in the given set. This is more efficient if the size of the subgraph is comparable to the original graph. The other implementation ("create_from_scratch") constructs the result graph from scratch and then copies the attributes accordingly. This is a better solution if the subgraph is relatively small, compared to the original graph. "auto" selects between the two implementations automatically, based on the ratio of the size of the subgraph and the size of the original graph. 
Returns  
the subgraph 
Returns whether the graph is acyclic (i.e. contains no cycles).
Returns  
boolean  True if the graph is acyclic, False otherwise. 
Decides whether the graph is biconnected.
A graph is biconnected if it stays connected after the removal of any single vertex.
Note that there are different conventions in use about whether to consider a graph consisting of two connected vertices to be biconnected. igraph does consider it biconnected.
Returns  
boolean  True if it is biconnected, False otherwise. 
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  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. 
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.
Parameters  
alpha  the alpha vector from the result of calling maximum_cardinality_search() on the graph. Useful only if you already have the alpha vector; simply passing None here will make igraph calculate the alpha vector on its own. 
alpham1  the inverse alpha vector from the result of calling maximum_cardinality_search() on the graph. Useful only if you already have the inverse alpha vector; simply passing None here will make igraph calculate the inverse alpha vector on its own. 
Returns  
True if the graph is chordal, False otherwise. 
Checks whether the graph is complete, i.e. whether there is at least one connection between all distinct pairs of vertices. In directed graphs, ordered pairs are considered.
Returns  
boolean  True if it is complete, False otherwise. 
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 the graph is a DAG (directed acyclic graph).
A DAG is a directed graph with no directed cycles.
Returns  
boolean  True if it is a DAG, 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 
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.
Parameters  
vertices  a single vertex ID or a list of vertex IDs 
Returns  
True is the given vertex set is a minimal separator, False otherwise. 
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. 
loops  specifies whether loop edges should be treated as mutual in a directed graph. 
Returns  
a list of booleans, one for every edge given 
Decides whether the removal of the given vertices disconnects the graph.
Parameters  
vertices  a single vertex ID or a list of vertex IDs 
Returns  
True is the given vertex set is a separator, False if not. 
Checks whether the graph is simple (no loop or multiple edges).
Returns  
boolean  True if it is simple, False otherwise. 
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.
Parameters  
mode  for directed graphs, specifies how the edge directions should be taken into account. "all" means that the edge directions must be ignored, "out" means that the edges must be oriented away from the root, "in" means that the edges must be oriented towards the root. Ignored for undirected graphs. 
Returns  
boolean  True if the graph is a tree, False otherwise. 
Generates a graph with a given isomorphism class.
Currently we support directed graphs of size 3 and 4, and undirected graphs of size 3, 4, 5 or 6. Use the isoclass()
instance method to find the isomorphism class of a given graph.
Parameters  
n  the number of vertices in the graph 
cls  the isomorphism class 
directed  whether the graph should be directed. 
Returns the isomorphism class of the graph or its subgraph.
Isomorphism class calculations are implemented only for directed graphs with 3 or 4 vertices, or undirected graphs with 3, 4, 5 or 6 vertices..
Parameters  
vertices  a list of vertices if we want to calculate the isomorphism class for only a subset of vertices. None means to use the full graph. 
Returns  
the isomorphism class of the (sub)graph 
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
.
Returns  
True if the graphs are isomorphic, False otherwise. 
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.
Parameters  
other  the other graph with which we want to compare the graph. 
return  if True, calculates the mapping which maps the vertices of the first graph to the second. 
return  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 caseinsensitive string, with the following possible values:

sh2  splitting heuristics to be used for the second graph. This must be the same as sh1; alternatively, it can be None, in which case it will automatically use the same value as sh1. Currently it is present for backwards compatibility only. 
color1  optional vector storing the coloring of the vertices of the first graph. If None, all vertices have the same color. 
color2  optional vector storing the coloring of the vertices of the second graph. If None, all vertices have the same color. 
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 3tuple, 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 3tuple. 
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.
Parameters  
other  the other graph with which we want to compare the graph. If None, the automorphjisms of the graph will be tested. 
color1  optional vector storing the coloring of the vertices of the first graph. If None, all vertices have the same color. 
color2  optional vector storing the coloring of the vertices of the second graph. If None, all vertices have the same color. 
edge  optional vector storing the coloring of the edges of the first graph. If None, all edges have the same color. 
edge  optional vector storing the coloring of the edges of the second graph. If None, all edges have the same color. 
return  if True, calculates the mapping which maps the vertices of the first graph to the second. 
return  if True, calculates the mapping which maps the vertices of the second graph to the first. 
node  a function that receives the two graphs and two node indices (one from the first graph, one from the second graph) and returns True if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on nodespecific criteria that are too complicated to be represented by node color vectors (i.e. the color1 and color2 parameters). None means that every node is compatible with every other node. 
edge  a function that receives the two graphs and two edge indices (one from the first graph, one from the second graph) and returns True if the edges given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on edgespecific criteria that are too complicated to be represented by edge color vectors (i.e. the edge_color1 and edge_color2 parameters). None means that every edge is compatible with every other node. 
callback  if not None, the isomorphism search will not stop at the first match; it will call this callback function instead for every isomorphism found. The callback function must accept four arguments: the first graph, the second graph, a mapping from the nodes of the first graph to the second, and a mapping from the nodes of the second graph to the first. The function must return True if the search should continue or False otherwise. 
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 3tuple, 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 3tuple. 
Generates a kregular random graph
A kregular random graph is a random graph where each vertex has degree k. If the graph is directed, both the indegree and the outdegree of each vertex will be k.
Parameters  
n  The number of vertices in the graph 
k  The degree of each vertex if the graph is undirected, or the indegree and outdegree of each vertex if the graph is directed 
directed  whether the graph should be directed. 
multiple  whether it is allowed to create multiple edges. 
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 
Calculates the average degree of the neighbors for each vertex, and the same quantity as the function of vertex degree.
Parameters  
vids  the vertices for which the calculation is performed. None means all vertices. 
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. If this is given, the vertex strength will be used instead of the vertex degree in the calculations, but the "ordinary" vertex degree will be used for the second (degree dependent) list in the result. 
Returns  
two lists in a tuple. The first list contains the average degree of neighbors for each vertex, the second contains the average degree of neighbors as a function of vertex degree. The zeroth element of this list corresponds to vertices of degree 1. 
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.
Symmetric 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.
Leftnormalized and rightnormalized Laplacian matrices are derived from the unnormalized Laplacian by scaling the row or the column sums to be equal to 1.
Parameters  
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. When edge weights are used, the degree of a node is considered to be the sum of the weights of its incident edges. 
normalized  whether to return the normalized Laplacian matrix. False or "unnormalized" returns the unnormalized Laplacian matrix. True or "symmetric" returns the symmetric normalization of the Laplacian matrix. "left" returns the left, "right" returns the rightnormalized Laplacian matrix. 
mode  for directed graphs, specifies whether to use out or indegrees in the Laplacian matrix. "all" means that the edge directions must be ignored, "out" means that the outdegrees should be used, "in" means that the indegrees should be used. Ignored for undirected graphs. 
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.
See Also  
clique_number() for the size of the largest cliques or maximal_cliques() for the maximal cliques 
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.
See Also  
independence_number() for the size of the largest independent vertex sets or maximal_independent_vertex_sets() for the maximal (nonextendable) independent vertex sets 
Generates a regular square 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. 
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. May also be an iterable; in this case, the iterator is assumed to yield booleans that specify whether the lattice is periodic along each dimension. 
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.
Parameters  
types  an igraph vector containing the vertex types, or an attribute name. Anything that evalulates to False corresponds to vertices of the first kind, everything else to the second kind. 
hgap  minimum horizontal gap between vertices in the same layer. 
vgap  vertical gap between the two layers. 
maxiter  maximum number of iterations to take in the crossing reduction step. Increase this if you feel that you are getting too many edge crossings. 
Returns  
the calculated layout. 
Places the vertices of the graph uniformly on a circle or a sphere.
Parameters  
dim  the desired number of dimensions for the layout. dim=2 means a 2D layout, dim=3 means a 3D layout. 
order  the order in which the vertices are placed along the circle. Not supported when dim is not equal to 2. 
Returns  
the calculated layout. 
Places the vertices on a 2D plane according to the DavidsonHarel 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 finetuning phase. There is no simulated annealing in the second phase.
Parameters  
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. 
maxiter  Number of iterations to perform in the annealing phase. 
fineiter  Number of iterations to perform in the finetuning phase. Negative numbers set up a reasonable default from the base2 logarithm of the vertex count, bounded by 10 from above. 
cool  Cooling factor of the simulated annealing phase. 
weight  Weight for the nodenode distances in the energy function. 
weight  Weight for the distance from the border component of the energy function. Zero means that vertices are allowed to sit on the border of the area designated for the layout. 
weight  Weight for the edge length component of the energy function. Negative numbers are replaced by the density of the graph divided by 10. 
weight  Weight for the edge crossing component of the energy function. Negative numbers are replaced by one minus the square root of the density of the graph. 
weight  Weight for the nodeedge distance component of the energy function. Negative numbers are replaced by 0.2 minus 0.2 times the density of the graph. 
Returns  
the calculated layout. 
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 forcebased 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. 
fixed  ignored. We used to assume that the DrL layout supports fixed nodes, but later it turned out that the argument has no effect in the original DrL code. We kept the argument for sake of backwards compatibility, but it will have no effect on the final layout. 
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. 
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:
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. 
dim  the desired number of dimensions for the layout. dim=2 means a 2D layout, dim=3 means a 3D layout. 
Returns  
the calculated layout. 
Places the vertices on a 2D plane according to the FruchtermanReingold algorithm.
This is a force directed layout, see Fruchterman, T. M. J. and Reingold, E. M.: Graph Drawing by Forcedirected Placement. Software  Practice and Experience, 21/11, 11291164, 1991
Parameters  
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
niter  the number of iterations to perform. The default is 500. 
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. 
start  Real scalar, the start temperature. This is the maximum amount of movement alloved along one axis, within one step, for a vertex. Currently it is decreased linearly to zero during the iteration. The default is the square root of the number of vertices divided by 10. 
minx  if not None, it must be a vector with exactly as many elements as there are vertices in the graph. Each element is a minimum constraint on the X value of the vertex in the layout. 
maxx  similar to minx, but with maximum constraints 
miny  similar to minx, but with the Y coordinates 
maxy  similar to maxx, but with the Y coordinates 
minz  similar to minx, but with the Z coordinates. Use only for 3D layouts (dim=3). 
maxz  similar to maxx, but with the Z coordinates. Use only for 3D layouts (dim=3). 
grid  whether to use a faster, but less accurate gridbased implementation of the algorithm. "auto" decides based on the number of vertices in the graph; a grid will be used if there are at least 1000 vertices. "grid" is equivalent to True, "nogrid" is equivalent to False. 
Returns  
the calculated layout. 
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  the charge of the vertices, used to calculate electric repulsion. 
node  the mass of the vertices, used for the spring forces 
spring  the length of the springs 
spring  the spring constant 
max  the maximum amount of movement allowed in a single step along a single axis. 
seed  a matrix containing a seed layout from which the algorithm will be started. If None, a random layout will be used. 
Returns  
the calculated layout. 
Places the vertices of a graph in a 2D or 3D grid.
Parameters  
width  the number of vertices in a single row of the layout. Zero or negative numbers mean that the width should be determined automatically. 
height  the number of vertices in a single column of the layout. Zero or negative numbers mean that the height should be determined automatically. It must not be given if the number of dimensions is 2. 
dim  the desired number of dimensions for the layout. dim=2 means a 2D layout, dim=3 means a 3D layout. 
Returns  
the calculated layout. 
Places the vertices on a plane according to the KamadaKawai 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, 715, 1989.
Parameters  
maxiter  the maximum number of iterations to perform. None selects a reasonable default based on the number of vertices. 
epsilon  quit if the energy of the system changes less than epsilon. See the original paper for details. 
kkconst  the KamadaKawai vertex attraction constant. None means the number of vertices. 
seed  when None, uses a circular layout as a starting point for the algorithm when no bounds are given, or a random layout when bounds are specified for the coordinated. When the argument is a matrix (list of lists), it uses the given matrix as the initial layout. 
minx  if not None, it must be a vector with exactly as many elements as there are vertices in the graph. Each element is a minimum constraint on the X value of the vertex in the layout. 
maxx  similar to minx, but with maximum constraints 
miny  similar to minx, but with the Y coordinates 
maxy  similar to maxx, but with the Y coordinates 
minz  similar to minx, but with the Z coordinates. Use only for 3D layouts (dim=3). 
maxz  similar to maxx, but with the Z coordinates. Use only for 3D layouts (dim=3). 
dim  the desired number of dimensions for the layout. dim=2 means a 2D layout, dim=3 means a 3D layout. 
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
Returns  
the calculated layout. 
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 vertexvertex 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. None means that a random vertex will be chosen. 
Returns  
the calculated 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.
Reference: Cox & Cox: Multidimensional Scaling (1994), Chapman and Hall, London.
Parameters  
dist  the distance matrix. It must be symmetric and the symmetry is not checked  results are unspecified when a nonsymmetric distance matrix is used. If this parameter is None, the shortest path lengths will be used as distances. Directed graphs are treated as undirected when calculating the shortest path lengths to ensure symmetry. 
dim  the number of dimensions. For 2D layouts, supply 2 here; for 3D layouts, supply 3. 
arpack  an ARPACKOptions object used to finetune the ARPACK eigenvector calculation. If omitted, the modulelevel variable called arpack_options is used. 
Returns  
the calculated layout. 
Places the vertices of the graph randomly.
Parameters  
dim  the desired number of dimensions for the layout. dim=2 means a 2D layout, dim=3 means a 3D layout. 
Returns  
the coordinate pairs in a list. 
Places the vertices on a 2D plane according to the ReingoldTilford layout algorithm.
This is a tree layout. If the given graph is not a tree, a breadthfirst search is executed first to obtain a possible spanning tree.
Reference: EM Reingold, JS Tilford: Tidier Drawings of Trees. IEEE Transactions on Software Engineering 7:22, 223228, 1981.
Parameters  
mode  specifies which edges to consider when builing the tree. If it is OUT then only the outgoing, if it is IN then only the incoming edges of a parent are considered. If it is ALL then all edges are used (this was the behaviour in igraph 0.5 and before). This parameter also influences how the root vertices are calculated if they are not given. See the root parameter. 
root  the index of the root vertex or root vertices. If this is a nonempty vector then the supplied vertex IDs are used as the roots of the trees (or a single tree if the graph is connected). If this is None or an empty list, the root vertices are automatically calculated in such a way so that all other vertices would be reachable from them. Currently, automatic root selection prefers low eccentricity vertices in small graphs (fewer than 500 vertices) and high degree vertices in large graphs. This heuristic may change in future versions. Specify roots manually for a consistent output. 
rootlevel  this argument is useful when drawing forests which are not trees. It specifies the level of the root vertices for every tree in the forest. 
Returns  
the calculated layout.  
See Also  
layout_reingold_tilford_circular 
Circular ReingoldTilford layout for trees.
This layout is similar to the ReingoldTilford 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.
Reference: EM Reingold, JS Tilford: Tidier Drawings of Trees. IEEE Transactions on Software Engineering 7:22, 223228, 1981.
Returns  
the calculated layout.  
See Also  
layout_reingold_tilford 
Calculates a starlike layout for the graph.
Parameters  
center  the ID of the vertex to put in the center 
order  a numeric vector giving the order of the vertices (including the center vertex!). If it is None, the vertices will be placed in increasing vertex ID order. 
Returns  
the calculated layout. 
Uniform Manifold Approximation and Projection (UMAP).
This layout is a probabilistic algorithm that places vertices that are connected and have a short distance close by in the embedded space.
Reference: L McInnes, J Healy, J Melville: UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. arXiv:1802.03426.
Parameters  
dist  distances associated with the graph edges. If None, all edges will be assumed to convey the same distance between the vertices. Either this argument of the weights argument can be set, but not both. It is fine to set neither. 
weights  precomputed edge weights if you have them, as an alternative to setting the dist argument. Zero weights will be ignored if this argument is set, e.g. if you computed the weights via igraph.umap_compute_weights(). 
dim  the desired number of dimensions for the layout. dim=2 means a 2D layout, dim=3 means a 3D layout. 
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. 
min  the minimal distance in the embedded space beyond which the probability of being located closeby decreases. 
epochs  the number of epochs (iterations) the algorithm will iterate over. Accuracy increases with more epochs, at the cost of longer runtimes. Values between 50 and 1000 are typical. Notice that UMAP does not technically converge for symmetry reasons, but a larger number of epochs should generally give an equivalent or better layout. 
Returns  
the calculated layout. Please note that if distances are set, the graph is usually directed, whereas if weights are precomputed, the graph will be treated as undirected. A special case is when the graph is directed but the precomputed weights are symmetrized in a way only one of each pair of opposite edges has nonzero weight, e.g. as computed by igraph.umap_compute_weights(). For example: weights = igraph.umap_compute_weights(graph, dist) layout = graph.layout_umap(weights=weights)  
See Also  
igraph.umap_compute_weights() 
Generates a graph from LCF notation.
LCF is short for LederbergCoxeterFrucht, it is a concise notation for 3regular 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 
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.
Edge i in the original graph will map to vertex i of the line graph.
Lists the triangles of the graph
Returns  
the list of triangles in the graph; each triangle is represented by a tuple of length 3, containing the corresponding vertex IDs. 
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. 
mode  the type of degree to be returned ("out" for outdegrees, "in" IN for indegrees or "all" for the sum of them). 
loops  whether selfloops should be counted. 
igraph.Graph
Returns the maximum flow between the source and target vertices.
Attention: this function has a more convenient interface in class Graph
, which wraps the result in a Flow
object. It is advised to use that.
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  
a tuple containing the following: the value of the maximum flow between the given vertices, the flow value on all the edges, the edge IDs that are part of the corresponding minimum cut, and the vertex IDs on one side of the cut. For directed graphs, the flow value vector gives the flow value on each edge. For undirected graphs, the flow value is positive if the flow goes from the smaller vertex ID to the bigger one and negative if the flow goes from the bigger vertex ID to the smaller. 
Returns the value of 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.
Parameters  
min  the minimum size of maximal cliques to be returned. If zero or negative, no lower bound will be used. 
max  the maximum size of maximal cliques to be returned. If zero or negative, no upper bound will be used. If nonzero, the size of every maximal clique found will be compared to this value and a clique will be returned only if its size is smaller than this limit. 
file  a file object or the name of the file to write the results to. When this argument is None, the maximal cliques will be returned as a list of lists. 
Returns  
the maximal cliques of the graph as a list of lists, or None if the file argument was given.@see: largest_cliques() for the largest cliques. 
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.
Reference: S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka: A new algorithm for generating all the maximal independent sets. SIAM J Computing, 6:505517, 1977.
See Also  
largest_independent_vertex_sets() for the largest independent vertex sets 
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.
Returns  
a tuple consisting of the rank vector and its inverse. 
igraph.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 StoerWagner algorithm. For a given source and target, the method uses the pushrelabel algorithm; see the references below.
Attention: this function has a more convenient interface in class Graph
, which wraps the result in a Cut
object. It is advised to use that.
References
 M. Stoer, F. Wagner: A simple mincut algorithm. Journal of the ACM 44(4):585591, 1997.
 A. V. Goldberg, R. E. Tarjan: A new approach to the maximumflow problem. Journal of the ACM 35(4):921940, 1988.
Parameters  
source  the source vertex ID. If None, target must also be {None} and the calculation will be done for the entire graph (i.e. all possible vertex pairs). 
target  the target vertex ID. If None, source must also be {None} and the calculation will be done for the entire graph (i.e. all possible vertex pairs). 
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 minimum cut, the IDs of vertices in the first and second partition, and the IDs of edges in the cut, packed in a 4tuple 
Returns the minimum cut between the source and target vertices or within the whole graph.
Parameters  
source  the source vertex ID. If negative, the calculation is done for every vertex except the target and the minimum is returned. 
target  the target vertex ID. If negative, the calculation is done for every vertex except the source and the minimum is returned. 
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 minimum cut between the given vertices 
Computes a minimum cycle basis of the graph
Parameters  
cutoff  when None or negative, a complete minimum cycle basis is returned. Otherwise only those cycles in the result will be part of some minimum cycle basis that are of length 2*cutoff + 1 or shorter. Cycles longer than this limit may not be of the smallest possible size. This parameter effectively limits the depth of the BFS tree when computing candidate cycles and may speed up the computation substantially. 
complete  used only when a cutoff is specified, and in this case it specifies whether a complete basis is returned (True) or the result will be limited to cycles of length 2*cutoff + 1 or shorter only. This limits computation time, but the result may not span the entire cycle space. 
use  if True, every cycle is returned in natural order: the edge IDs will appear ordered along the cycle. If False, no guarantees are given about the ordering of edge IDs within cycles. 
Returns  
the cycle basis as a list of tuples containing edge IDs 
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.
Reference: Arkady Kanevsky: Finding all minimumsize separating vertex sets in a graph. Networks 23:533541, 1993.
Returns  
a list where each item lists the vertex indices of a given separator of minimum size. 
igraph.Graph
Calculates the modularity of the graph with respect to some vertex types.
The modularity of a graph w.r.t. some division measures how good the division is, or how separated are the different vertex types from each other. It is defined as Q = 1 ⁄ (2m)*sum(Aij − gamma*ki*kj ⁄ (2m)delta(ci, cj), i, j). m is the number of edges, Aij is the element of the A adjacency matrix in row i and column j, ki is the degree of node i, kj is the degree of node j, Ci and cj are the types of the two vertices (i and j), and gamma is a resolution parameter that defaults to 1 for the classical definition of modularity. delta(x, y) is one iff x = y, 0 otherwise.
If edge weights are given, the definition of modularity is modified as follows: Aij becomes the weight of the corresponding edge, ki is the total weight of edges incident on vertex i, kj is the total weight of edges incident on vertex j and m is the total edge weight in the graph.
Attention: method overridden in Graph
to allow VertexClustering
objects as a parameter. This method is not strictly necessary, since the VertexClustering
class provides a variable called modularity.
Reference: MEJ Newman and M Girvan: Finding and evaluating community structure in networks. Phys Rev E 69 026113, 2004.
Parameters  
membership  the membership vector, e.g. the vertex type index for each vertex. 
weights  optional edge weights or None if all edges are weighed equally. 
resolution  the resolution parameter gamma in the formula above. The classical definition of modularity is retrieved when the resolution parameter is set to 1. 
directed  whether to consider edge directions if the graph is directed. True will use the directed variant of the modularity measure where the in and outdegrees of nodes are treated separately; False will treat directed graphs as undirected. 
Returns  
the modularity score. 
Calculates the modularity matrix of the graph.
Parameters  
weights  optional edge weights or None if all edges are weighed equally. 
resolution  the resolution parameter gamma of the modularity formula. The classical definition of modularity is retrieved when the resolution parameter is set to 1. 
directed  whether to consider edge directions if the graph is directed. True will use the directed variant of the modularity measure where the in and outdegrees of nodes are treated separately; False will treat directed graphs as undirected. 
Returns  
the modularity matrix as a list of lists. 
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.
Currently we support motifs of size 3 and 4 for directed graphs, and motifs of size 3, 4, 5 or 6 for undirected graphs.
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.
Reference: S. Wernicke and F. Rasche: FANMOD: a tool for fast network motif detection, Bioinformatics 22(9), 11521153, 2006.
Parameters  
size  the size of the motifs 
cut  the cut probabilities for different levels of the search tree. This must be a list of length size or None to find all motifs. 
callback  None or a callable that will be called for every motif found in the graph. The callable must accept three parameters: the graph itself, the list of vertices in the motif and the isomorphism class of the motif (see isoclass() ). The search will stop when the callback returns an object with a nonzero truth value or raises an exception. 
Returns  
the list of motifs if callback is None, or None otherwise  
See Also  
Graph.motifs_randesu_no() 
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.
Currently we support motifs of size 3 and 4 for directed graphs, and motifs of size 3, 4, 5 or 6 for undirected graphs.
Reference: S. Wernicke and F. Rasche: FANMOD: a tool for fast network motif detection, Bioinformatics 22(9), 11521153, 2006.
Parameters  
size  the size of the motifs 
cut  the cut probabilities for different levels of the search tree. This must be a list of length size or None to find all motifs. 
sample  the size of the sample or the vertex IDs of the vertices to be used for sampling. 
See Also  
Graph.motifs_randesu() 
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.
Currently we support motifs of size 3 and 4 for directed graphs, and motifs of size 3, 4, 5 or 6 for undirected graphs.
Reference: S. Wernicke and F. Rasche: FANMOD: a tool for fast network motif detection, Bioinformatics 22(9), 11521153, 2006.
Parameters  
size  the size of the motifs 
cut  the cut probabilities for different levels of the search tree. This must be a list of length size or None to find all motifs. 
See Also  
Graph.motifs_randesu() 
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.
Parameters  
vertices  a single vertex ID or a list of vertex IDs, or None meaning all the vertices in the graph. 
order  the order of the neighborhood, i.e. the maximum number of steps to take from the seed vertex. 
mode  specifies how to take into account the direction of the edges if a directed graph is analyzed. "out" means that only the outgoing edges are followed, so all vertices reachable from the source vertex in at most order steps are counted. "in" means that only the incoming edges are followed (in reverse direction of course), so all vertices from which the source vertex is reachable in at most order steps are counted. "all" treats directed edges as undirected. 
mindist  the minimum distance required to include a vertex in the result. If this is one, the seed vertex is not included. If this is two, the direct neighbors of the seed vertex are not included either, and so on. 
Returns  
a single list specifying the neighborhood if vertices was an integer specifying a single vertex index, or a list of lists if vertices was a list or None. 
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.
Parameters  
vertices  a single vertex ID or a list of vertex IDs, or None meaning all the vertices in the graph. 
order  the order of the neighborhood, i.e. the maximum number of steps to take from the seed vertex. 
mode  specifies how to take into account the direction of the edges if a directed graph is analyzed. "out" means that only the outgoing edges are followed, so all vertices reachable from the source vertex in at most order steps are counted. "in" means that only the incoming edges are followed (in reverse direction of course), so all vertices from which the source vertex is reachable in at most order steps are counted. "all" treats directed edges as undirected. 
mindist  the minimum distance required to include a vertex in the result. If this is one, the seed vertex is not counted. If this is two, the direct neighbors of the seed vertex are not counted either, and so on. 
Returns  
a single number specifying the neighborhood size if vertices was an integer specifying a single vertex index, or a list of sizes if vertices was a list or None. 
Returns adjacent vertices to a given vertex.
Parameters  
vertex  a vertex ID 
mode  whether to return only successors ("out"), predecessors ("in") or both ("all"). Ignored for undirected graphs. 
igraph.Graph
Calculates the path length histogram of the graph Attention: this function is wrapped in a more convenient syntax in the derived class Graph
. It is advised to use that instead of this version.
Parameters  
directed  whether to consider directed paths 
Returns  
a tuple. The first item of the tuple is a list of path lengths, the ith element of the list contains the number of paths with length i + 1. The second item contains the number of unconnected vertex pairs as a float (since it might not fit into an integer) 
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.
Returns  
the new graph 
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 nonuniform distribution over the vertices in every step with probability 1 − damping instead of a uniform distribution.
Parameters  
vertices  the indices of the vertices being queried. None means all of the vertices. 
directed  whether to consider directed paths. 
damping  the damping factor. 
reset  the distribution over the vertices to be used when resetting the random walk. Can be a sequence, an iterable or a vertex attribute name as long as they return a list of floats whose length is equal to the number of vertices. If None, a uniform distribution is assumed, which makes the method equivalent to the original PageRank algorithm. 
reset  an alternative way to specify the distribution over the vertices to be used when resetting the random walk. Simply supply a list of vertex IDs here, or a VertexSeq or a Vertex . Resetting will take place using a uniform distribution over the specified vertices. 
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
arpack  an ARPACKOptions object used to finetune the ARPACK eigenvector calculation. If omitted, the modulelevel variable called arpack_options is used. This argument is ignored if not the ARPACK implementation is used, see the implementation argument. 
implementation  which implementation to use to solve the PageRank eigenproblem. Possible values are:

Returns  
a list with the personalized PageRank values of the specified vertices. 
Returns the predecessors of a given vertex.
Equivalent to calling the neighbors()
method with type="in".
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.
Parameters  
n  the number of vertices in the graph 
type  list giving the distribution of vertex types 
pref  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. 
Generates a tree from its Prüfer sequence.
A Prüfer sequence is a unique sequence of integers associated with a labelled tree. A tree on n vertices can be represented by a sequence of n − 2 integers, each between 0 and n − 1 (inclusive).
Parameters  
seq  the Prüfer sequence as an iterable of integers 
Calculates the radius of the graph.
The radius of a graph is defined as the minimum eccentricity of its vertices (see eccentricity()
).
Parameters  
mode  what kind of paths to consider for the calculation in case of directed graphs. OUT considers paths that follow edge directions, IN considers paths that follow the opposite edge directions, ALL ignores edge directions. The argument is ignored for undirected graphs. 
weights  a list containing the edge weights. It can also be an attribute name (edge weights are retrieved from the given attribute) or None (all edges have equal weight). 
Returns  
the radius  
See Also  
eccentricity() 
Performs a random walk of a given length from a given node.
Parameters  
start  the starting vertex of the walk 
steps  the number of steps that the random walk should take 
mode  whether to follow outbound edges only ("out"), inbound edges only ("in") or both ("all"). Ignored for undirected graphs.@param stuck: what to do when the random walk gets stuck. "return" returns a partial random walk; "error" throws an exception. 
stuck  Undocumented 
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
return  what to return. It can be "vertices" (default), then the function returns a list of the vertex ids visited; "edges", then the function returns a list of edge ids visited; or "both", then the function return a dictionary with keys "vertices" and "edges". 
Returns  
a random walk that starts from the given vertex and has at most the given length (shorter if the random walk got stuck). 
igraph.Graph
Reads a graph from a file conforming to the DIMACS minimumcost 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.
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 UCINET DL file and creates a graph based on it.
Parameters  
f  the name of the file or a Python file handle 
directed  whether the generated graph should be directed. 
Reads an edge list from a file and creates a graph based on it.
Please note that the vertex indices are zerobased. A vertex of zero degree will be created for every integer that is in range but does not appear in the edgelist.
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 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/).
Parameters  
f  the name of the file or a Python file handle 
directed  whether the generated graph should be directed. 
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', even if there are no weights in the file. If False, the edge weights are never added, even if they are present. "auto" or "if_present" means that weights are added if there is at least one weighted edge in the input file, but they are not added otherwise. 
directed  whether the graph being created should be directed 
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.
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', even if there are no weights in the file. If False, the edge weights are never added, even if they are present. "auto" or "if_present" means that weights are added if there is at least one weighted edge in the input file, but they are not added otherwise. 
directed  whether the graph being created should be directed 
Reads a file in the Pajek format and creates a graph based on it. Only Pajek network files (.net extension) are supported, not project files (.paj).
Parameters  
f  the name of the file or a Python file handle 
Generates a bipartite graph from the degree sequences of its partitions.
This method implements a HavelHakimi style graph construction for biparite graphs. 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 multiedges are allowed) are specified in the allowed_edge_types parameter. Selfloops are never created, since a graph with selfloops is not bipartite.
Parameters  
degrees1  the degrees of the first partition. 
degrees2  the degrees of the second partition. 
allowed  controls whether multiedges are allowed during the generation process. Possible values are:

method  controls how the vertices are selected during the generation process. Possible values are:
The smallest smallest method is guaranteed to produce a connected graph, if one exists. 
Generates a graph from a degree sequence.
This method implements a HavelHakimi 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.
References
 V. Havel, Poznámka o existenci konečných grafů (A remark on the existence of finite graphs), Časopis pro pěstování matematiky 80, 477480 (1955). http://eudml.org/doc/19050
 S. L. Hakimi, On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph, Journal of the SIAM 10, 3 (1962). https://www.jstor.org/stable/2098770
 D. J. Kleitman and D. L. Wang, Algorithms for Constructing Graphs and Digraphs with Given Valences and Factors, Discrete Mathematics 6, 1 (1973). https://doi.org/10.1016/0012365X%2873%2990037X
 Sz. Horvát and C. D. Modes, Connectedness matters: construction and exact random sampling of connected networks (2021). https://doi.org/10.1088/2632072X/abced5
Parameters  
out  the degree sequence of an undirected graph (if in_=None), or the outdegree sequence of a directed graph. 
in_  None to generate an undirected graph, the indegree sequence to generate a directed graph. 
allowed  controls whether loops or multiedges are allowed during the generation process. Note that not all combinations are supported for all types of graphs; an exception will be raised for unsupported combinations. Possible values are:

method  controls how the vertices are selected during the generation process. Possible values are:
In the undirected case, smallest is guaranteed to produce a connected graph. See Horvát and Modes (2021) for details. 
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 outdegree of a given vertex should also increase its citation probability (as well as its indegree), 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. 
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 nonmutual) connection between them. In other words, (unordered) vertex pairs are classified into three groups: (1) disconnected, (2) nonreciprocally 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".
Parameters  
ignore  whether loop edges should be ignored. 
mode  the algorithm to use to calculate the reciprocity; see above for more details. 
Returns  
the reciprocity of the graph 
Reverses the direction of some edges in the graph.
This function is a noop for undirected graphs.
Parameters  
es  the list of edges to be reversed. Edges are identifed by edge IDs. EdgeSeq objects are also accepted here. When omitted, all edges will be reversed. 
Randomly rewires the graph while preserving the degree distribution.
Please note that the rewiring is done "inplace", so the original graph will be modified. If you want to preserve the original graph, use the copy
method before.
Parameters  
n  the number of rewiring trials. 
mode  the rewiring algorithm to use. It can either be "simple" or "loops"; the former does not create or destroy loop edges while the latter does. 
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 "inplace", so the original graph will be modified. If you want to preserve the original graph, use the copy
method before.
Parameters  
prob  rewiring probability 
loops  whether the algorithm is allowed to create loop edges 
multiple  whether the algorithm is allowed to create multiple edges. 
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 graph based on a stochastic block model.
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.
Parameters  
n  the number of vertices in the graph 
pref  matrix giving the connection probabilities for different vertex types. 
block  list giving the number of vertices in each block; must sum up to n. 
directed  whether to generate a directed graph. 
loops  whether loop edges are allowed. 
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.
Parameters  
vertices  the vertices to be analysed. If None and pairs is also None, all vertices will be considered. 
pairs  the vertex pairs to be analysed. If this is given, vertices must be None, and the similarity values will be calculated only for the given pairs. Vertex pairs must be specified as tuples of vertex IDs. 
mode  which neighbors should be considered for directed graphs. Can be "all", "in" or "out", ignored for undirected graphs. 
loops  whether vertices should be considered adjacent to themselves. Setting this to True assumes a loop edge for all vertices even if none is present in the graph. Setting this to False may result in strange results: nonadjacent vertices may have larger similarities compared to the case when an edge is added between them  however, this might be exactly the result you want to get. 
Returns  
the pairwise similarity coefficients for the vertices specified, in the form of a matrix if pairs is None or in the form of a list if pairs is not None. 
Inverse logweighted similarity coefficient of vertices.
Each vertex is assigned a weight which is 1 / log(degree). The logweighted similarity of two vertices is the sum of the weights of their common neighbors.
Note that the presence of loop edges may yield counterintuitive results. A node with a loop edge is considered to be a neighbor of itself twice (because there are two edge stems incident on the node). Adding a loop edge to a node may decrease its similarity to other nodes, but it may also increase it. For instance, if nodes A and B are connected but share no common neighbors, their similarity is zero. However, if a loop edge is added to B, then B itself becomes a common neighbor of A and B and thus the similarity of A and B will be increased. Consider removing loop edges explicitly before invoking this function using Graph.simplify()
.
Parameters  
vertices  the vertices to be analysed. If None, all vertices will be considered. 
mode  which neighbors should be considered for directed graphs. Can be "all", "in" or "out", ignored for undirected graphs. "in" means that the weights are determined by the outdegrees, "out" means that the weights are determined by the indegrees. 
Returns  
the pairwise similarity coefficients for the vertices specified, in the form of a matrix (list of lists). 
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.
Parameters  
vertices  the vertices to be analysed. If None and pairs is also None, all vertices will be considered. 
pairs  the vertex pairs to be analysed. If this is given, vertices must be None, and the similarity values will be calculated only for the given pairs. Vertex pairs must be specified as tuples of vertex IDs. 
mode  which neighbors should be considered for directed graphs. Can be "all", "in" or "out", ignored for undirected graphs. 
loops  whether vertices should be considered adjacent to themselves. Setting this to True assumes a loop edge for all vertices even if none is present in the graph. Setting this to False may result in strange results: nonadjacent vertices may have larger similarities compared to the case when an edge is added between them  however, this might be exactly the result you want to get. 
Returns  
the pairwise similarity coefficients for the vertices specified, in the form of a matrix if pairs is None or in the form of a list if pairs is not None. 
Simplifies a graph by removing selfloops 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 builtin function and as a string constant.
Parameters  
multiple  whether to remove multiple edges. 
loops  whether to remove loops. 
combine  specifies how to combine the attributes of multiple edges between the same pair of vertices into a single attribute. If it is None, only one of the edges will be kept and all the attributes will be lost. If it is a function, the attributes of multiple edges will be collected and passed on to that function which will return the new attribute value that has to be assigned to the single collapsed edge. It can also be one of the following string constants:
You can also use a dict mapping edge attribute names to functions or the above string constants if you want to make the behaviour of the simplification process depend on the name of the attribute. None is a special key in this dict, its value will be used for all the attributes not specified explicitly in the dictionary. 
igraph.Graph
Calculates the minimum cut between the source and target vertices in a graph.
Attention: this function has a more convenient interface in class Graph
, which wraps the result in a list of Cut
objects. It is advised to use that.
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 minimum cut, the IDs of vertices in the first and second partition, and the IDs of edges in the cut, packed in a 4tuple 
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 either "in", "out", "mutual" or "undirected" 
center  Vertex ID for the central vertex in the star. 
Generates a nongrowing 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 outfitness and as a target proportional to its infitness.
Parameters  
m  the number of edges in the graph 
fitness  a numeric vector with nonnegative entries, one for each vertex. These values represent the fitness scores (outfitness scores for directed graphs). fitness is an alias of this keyword argument. 
fitness  a numeric vector with nonnegative entries, one for each vertex. These values represent the infitness scores for directed graphs. For undirected graphs, this argument must be None. 
loops  whether loop edges are allowed. 
multiple  whether multiple edges are allowed. 
Returns  
a directed or undirected graph with the prescribed powerlaw degree distributions. 
Generates a nongrowing graph with prescribed powerlaw degree distributions.
References
 Goh KI, Kahng B, Kim D: Universal behaviour of load distribution in scalefree networks. Phys Rev Lett 87(27):278701, 2001.
 Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in scalefree networks under the Achlioptas process. Phys Rev Lett 103:135702, 2009.
Parameters  
n  the number of vertices in the graph 
m  the number of edges in the graph 
exponent  the exponent of the outdegree distribution, which must be between 2 and infinity (inclusive). When exponent_in is not given or negative, the graph will be undirected and this parameter specifies the degree distribution. exponent is an alias to this keyword argument. 
exponent  the exponent of the indegree distribution, which must be between 2 and infinity (inclusive) It can also be negative, in which case an undirected graph will be generated. 
loops  whether loop edges are allowed. 
multiple  whether multiple edges are allowed. 
finite  whether to apply a finitesize correction to the generated fitness values for exponents less than 3. See the paper of Cho et al for more details. 
Returns  
a directed or undirected graph with the prescribed powerlaw degree distributions. 
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).
Parameters  
vertices  a single vertex ID or a list of vertex IDs 
mode  the type of degree to be returned ("out" for outdegrees, "in" for indegrees or "all" for the sum of them). 
loops  whether selfloops should be counted. 
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. ``None`` means to treat the graph as unweighted, falling back to ordinary degree calculations. 
Determines the indices of vertices which are in the same component as a given vertex.
Parameters  
v  the index of the vertex used as the source/destination 
mode  if equals to "in", returns the vertex IDs from where the given vertex can be reached. If equals to "out", returns the vertex IDs which are reachable from the given vertex. If equals to "all", returns all vertices within the same component as the given vertex, ignoring edge directions. Note that this is not equal to calculating the union of the results of "in" and "out". 
Returns  
the indices of vertices which are in the same component as a given vertex. 
Returns a subgraph spanned by the given edges.
Parameters  
edges  a list containing the edge IDs which should be included in the result. 
delete  if True, vertices not incident on any of the specified edges will be deleted from the result. If False, all vertices will be kept. 
Returns  
the subgraph 
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.
Parameters  
other  the pattern graph we are looking for in the graph. 
domains  a list of lists, one sublist belonging to each vertex in the template graph. Sublist i contains the indices of the vertices in the original graph that may match vertex i in the template graph. None means that every vertex may match every other vertex. 
induced  whether to consider induced subgraphs only. 
time  an optimal time limit in seconds. Only the integral part of this number is taken into account. If the time limit is exceeded, the method will throw an exception. 
return  when True, the function will return a tuple, where the first element is a boolean denoting whether a subisomorphism has been found or not, and the second element describes the mapping of the vertices from the template graph to the original graph. When False, only the boolean is returned. 
Returns  
if no mapping is calculated, the result is True if the graph contains a subgraph that is isomorphic to the given template, False otherwise. If the mapping is calculated, the result is a tuple, the first element being the above mentioned boolean, and the second element being the mapping from the target to the original graph. 
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.
Parameters  
other  the other graph with which we want to compare the graph. 
color1  optional vector storing the coloring of the vertices of the first graph. If None, all vertices have the same color. 
color2  optional vector storing the coloring of the vertices of the second graph. If None, all vertices have the same color. 
edge  optional vector storing the coloring of the edges of the first graph. If None, all edges have the same color. 
edge  optional vector storing the coloring of the edges of the second graph. If None, all edges have the same color. 
return  if True, calculates the mapping which maps the vertices of the first graph to the second. The mapping can contain 1 if a given node is not mapped. 
return  if True, calculates the mapping which maps the vertices of the second graph to the first. The mapping can contain 1 if a given node is not mapped. 
callback  if not None, the subisomorphism search will not stop at the first match; it will call this callback function instead for every subisomorphism found. The callback function must accept four arguments: the first graph, the second graph, a mapping from the nodes of the first graph to the second, and a mapping from the nodes of the second graph to the first. The function must return True if the search should continue or False otherwise. 
node  a function that receives the two graphs and two node indices (one from the first graph, one from the second graph) and returns True if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on nodespecific criteria that are too complicated to be represented by node color vectors (i.e. the color1 and color2 parameters). None means that every node is compatible with every other node. 
edge  a function that receives the two graphs and two edge indices (one from the first graph, one from the second graph) and returns True if the edges given by the two indices are compatible (i.e. they could be matched to each other) or False otherwise. This can be used to restrict the set of isomorphisms based on edgespecific criteria that are too complicated to be represented by edge color vectors (i.e. the edge_color1 and edge_color2 parameters). None means that every edge is compatible with every other node. 
Returns  
if no mapping is calculated, the result is True if the graph contains a subgraph that's isomorphic to the given one, False otherwise. If any or both mappings are calculated, the result is a 3tuple, 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 3tuple. 
Returns the successors of a given vertex.
Equivalent to calling the neighbors()
method with type="out".
Converts an undirected graph to directed.
Parameters  
mode  specifies how to convert undirected edges into directed ones. True or "mutual" creates a mutual edge pair for each undirected edge. False or "arbitrary" picks an arbitrary (but deterministic) edge direction for each edge. "random" picks a random direction for each edge. "acyclic" picks the edge directions in a way that the resulting graph will be acyclic if there were no selfloops in the original graph. 
Converts a directed graph to undirected.
Parameters  
mode  specifies what to do with multiple directed edges going between the same vertex pair. True or "collapse" means that only a single edge should be created from multiple directed edges. False or "each" means that every edge will be kept (with the arrowheads removed). "mutual" creates one undirected edge for each mutual directed edge pair. 
combine  specifies how to combine the attributes of multiple edges between the same pair of vertices into a single attribute. See simplify() for more details. 
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.
Parameters  
mode  if "out", vertices are returned according to the forward topological order  all vertices come before their successors. If "in", all vertices come before their ancestors. 
Returns  
a possible topological ordering as a list 
igraph.Graph
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.
Reference: D. J. Watts and S. Strogatz: Collective dynamics of smallworld networks. Nature 393(6884):440442, 1998.
Parameters  
mode  defines how to treat vertices with degree less than two. If TRANSITIVITT_ZERO or "zero", these vertices will have zero transitivity. If TRANSITIVITY_NAN or "nan", these vertices will be excluded from the average. 
See Also  
transitivity_undirected() , transitivity_local_undirected() 
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).
References:
 D. J. Watts and S. Strogatz: Collective dynamics of smallworld networks. Nature 393(6884):440442, 1998.
 Barrat A, Barthelemy M, PastorSatorras R and Vespignani A: The architecture of complex weighted networks. PNAS 101, 3747 (2004). http://arxiv.org/abs/condmat/0311416.
Parameters  
vertices  a list containing the vertex IDs which should be included in the result. None means all of the vertices. 
mode  defines how to treat vertices with degree less than two. If TRANSITIVITT_ZERO or "zero", these vertices will have zero transitivity. If TRANSITIVITY_NAN or "nan", these vertices will have NaN (not a number) as their transitivity. 
weights  edge weights to be used. Can be a sequence or iterable or even an edge attribute name. 
Returns  
the transitivities for the given vertices in a list  
See Also  
transitivity_undirected() , transitivity_avglocal_undirected() 
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.
Reference: S. Wasserman and K. Faust: Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press, 1994.
Parameters  
mode  if TRANSITIVITY_ZERO or "zero", the result will be zero if the graph does not have any triplets. If "nan" or TRANSITIVITY_NAN, the result will be NaN (not a number). 
Returns  
the transitivity  
See Also  
transitivity_local_undirected() , transitivity_avglocal_undirected() 
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 
mode  determines whether the tree should be directed, and if this is the case, also its orientation. Must be one of "in", "out" and "undirected". 
Generates a random tree by sampling uniformly from the set of labelled trees with a given number of nodes.
Parameters  
n  the number of vertices in the tree 
directed  whether the graph should be directed 
method  the generation method to be used. One of the following:

igraph.Graph
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.
Attention: this function has a more convenient interface in class Graph
, which wraps the result in a TriadCensus
object. It is advised to use that. The name of the triplet classes are also documented there.
Generates a regular triangular lattice.
Parameters  
dim  list with the dimensions of the lattice 
directed  whether to create a directed graph. 
mutual  whether to create all connections as mutual in case of a directed graph. 
Unfolds the graph using a BFS to a tree by duplicating vertices as necessary.
Parameters  
sources  the source vertices to start the unfolding from. It should be a list of vertex indices, preferably one vertex from each connected component. You can use topological_sorting() to determine a suitable set. A single vertex index is also accepted. 
mode  which edges to follow during the BFS. OUT follows outgoing edges, IN follows incoming edges, ALL follows both. Ignored for undirected graphs. 
Returns  
the unfolded tree graph and a mapping from the new vertex indices to the old ones. 
Calculates a greedy vertex coloring for the graph based on some heuristics.
Parameters  
method  the heuristics to use. colored_neighbors always picks the vertex with the largest number of colored neighbors as the next vertex to pick a color for. dsatur picks the vertex with the largest number of unique colors in its neighborhood; this is also known as the DSatur heuristics (hence the name). 
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.
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. 
neighbors  tells igraph what to do when the two vertices are connected. "error" raises an exception, "negative" returns a negative value, "number_of_nodes" or "nodes" returns the number of nodes, or "ignore" ignores the edge. 
Returns  
the vertex connectivity 
This function generates networks with the smallworld property based on a variant of the WattsStrogatz model. The network is obtained by first creating a periodic undirected lattice, then rewiring both endpoints of each edge with probability p, while avoiding the creation of multiedges.
This process differs from the original model of Watts and Strogatz (see reference) in that it rewires both endpoints of edges. Thus in the limit of p=1, we obtain a G(n,m) random graph with the same number of vertices and edges as the original lattice. In comparison, the original WattsStrogatz model only rewires a single endpoint of each edge, thus the network does not become fully random even for <code>p=1</code>.
For appropriate choices of p, both models exhibit the property of simultaneously having short path lengths and high clustering.
Reference: Duncan J Watts and Steven H Strogatz: Collective dynamics of small world networks, Nature 393, 440442, 1998
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. 
p  rewiring probability 
loops  specifies whether loop edges are allowed 
multiple  specifies whether multiple edges are allowed 
See Also  
Lattice() , rewire() , rewire_edges() if more flexibility is needed 
igraph.Graph
Writes the graph in DIMACS format to the given file.
Parameters  
f  the name of the file to be written or a Python file handle 
source  the source vertex ID 
target  the target vertex ID 
capacity  the capacities of the edges in a list. If it is not a list, the corresponding edge attribute will be used to retrieve capacities. 
Writes the graph in DOT format to the given file.
DOT is the format used by the GraphViz software package.
Parameters  
f  the name of the file to be written or a Python file handle 
Writes the edge list of a graph to a file.
Directed edges are written in (from, to) order.
Parameters  
f  the name of the file to be written or a Python file handle 
Writes the graph in GML format to the given file.
Parameters  
f  the name of the file to be written or a Python file handle 
creator  optional creator information to be written to the file. If None, the current date and time is added. 
ids  optional numeric vertex IDs to use in the file. This must be a list of integers or None. If None, the id attribute of the vertices are used, or if they don't exist, numeric vertex IDs will be generated automatically. 
Writes the graph to a GraphML file.
Parameters  
f  the name of the file to be written or a Python file handle 
prefixattr  whether attribute names in the written file should be prefixed with g_, v_ and e_ for graph, vertex and edge attributes, respectively. This might be needed to ensure the uniqueness of attribute identifiers in the written 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.
Parameters  
f  the name of the file to be written or a Python file handle 
names  the name of the vertex attribute to be stored along with the vertices. It is usually used to store the vertex names (hence the name of the keyword argument), but you may also use a numeric attribute. If you don't want to store any vertex attributes, supply None here. 
weights  the name of the edge attribute to be stored along with the edges. It is usually used to store the edge weights (hence the name of the keyword argument), but you may also use a string attribute. If you don't want to store any edge attributes, supply None here. 
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.
Parameters  
f  the name of the file to be written or a Python file handle 
names  the name of the vertex attribute containing the name of the vertices. If you don't want to store vertex names, supply None here. 
weights  the name of the edge attribute containing the weight of the vertices. If you don't want to store weights, supply None here. 
isolates  whether to include isolated vertices in the output. 
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.
Parameters  
f  the name of the file to be written or a Python file handle 
names  the name of the vertex attribute containing the name of the vertices. If you don't want to store vertex names, supply None here. 
weights  the name of the edge attribute containing the weight of the vertices. If you don't want to store weights, supply None here. 
Writes the graph in Pajek format to the given file.
Parameters  
f  the name of the file to be written or a Python file handle 
Returns the igraph graph encapsulated by the Python object as a PyCapsule
.A PyCapsule is practically a regular C pointer, wrapped in a Python object. This function should not be used directly by igraph users, it is useful only in the case when the underlying igraph object must be passed to other C code through Python.
Invalidates the internal cache of the lowlevel C graph object that the Python object wraps. This function should not be used directly by igraph users, but it may be useful for benchmarking or debugging purposes.
Registers a destructor to be called when the object is freed by Python. This function should not be used directly by igraph users.
Returns the memory address of the igraph graph encapsulated by the Python object as an ordinary Python integer.
This function should not be used directly by igraph users, it is useful only if you want to access some unwrapped function in the C core of igraph using the ctypes module.
Generates a graph from its adjacency matrix.
Parameters  
matrix  the adjacency matrix 
mode  the mode to be used. Possible values are:

loops  specifies how to handle loop edges. When False or "ignore", the diagonal of the adjacency matrix will be ignored. When True or "once", the diagonal is assumed to contain the weight of the corresponding loop edge. When "twice", the diagonal is assumed to contain twice the weight of the corresponding loop edge. 
Returns  
a pair consisting of the graph itself and its edge weight vector 