python-igraph manual

For using igraph from Python

   Home       Trees       Indices       Help   
Package igraph :: Class Graph
[hide private]

Class Graph

source code

object --+    
         |    
 GraphBase --+
             |
            Graph

Generic graph.

This class is built on top of GraphBase, so the order of the methods in the Epydoc documentation is a little bit obscure: inherited methods come after the ones implemented directly in the subclass. Graph provides many functions that GraphBase does not, mostly because these functions are not speed critical and they were easier to implement in Python than in pure C. An example is the attribute handling in the constructor: the constructor of Graph accepts three dictionaries corresponding to the graph, vertex and edge attributes while the constructor of GraphBase does not. This extension was needed to make Graph serializable through the pickle module. Graph also overrides some functions from GraphBase to provide a more convenient interface; e.g., layout functions return a Layout instance from Graph instead of a list of coordinate pairs.

Graphs can also be indexed by strings or pairs of vertex indices or vertex names. When a graph is indexed by a string, the operation translates to the retrieval, creation, modification or deletion of a graph attribute:

>>> g = Graph.Full(3)
>>> g["name"] = "Triangle graph"
>>> g["name"]
'Triangle graph'
>>> del g["name"]

When a graph is indexed by a pair of vertex indices or names, the graph itself is treated as an adjacency matrix and the corresponding cell of the matrix is returned:

>>> g = Graph.Full(3)
>>> g.vs["name"] = ["A", "B", "C"]
>>> g[1, 2]
1
>>> g["A", "B"]
1
>>> g["A", "B"] = 0
>>> g.ecount()
2

Assigning values different from zero or one to the adjacency matrix will be translated to one, unless the graph is weighted, in which case the numbers will be treated as weights:

>>> g.is_weighted()
False
>>> g["A", "B"] = 2
>>> g["A", "B"]
1
>>> g.es["weight"] = 1.0
>>> g.is_weighted()
True
>>> g["A", "B"] = 2
>>> g["A", "B"]
2
>>> g.es["weight"]
[1.0, 1.0, 2]
Instance Methods [hide private]
 
omega()
Returns the clique number of the graph.
source code
 
alpha()
Returns the independence number of the graph.
source code
 
shell_index(mode=ALL)
Finds the coreness (shell index) of the vertices of the network.
source code
 
cut_vertices()
Returns the list of articulation points in the graph.
source code
 
evcent(directed=True, scale=True, weights=None, return_eigenvalue=False, arpack_options=None)
Calculates the eigenvector centralities of the vertices in a graph.
source code
 
vertex_disjoint_paths(source=-1, target=-1, checks=True, neighbors="error")
Calculates the vertex connectivity of the graph or between some vertices.
source code
 
edge_disjoint_paths(source=-1, target=-1, checks=True)
Calculates the edge connectivity of the graph or between some vertices.
source code
 
cohesion(source=-1, target=-1, checks=True, neighbors="error")
Calculates the vertex connectivity of the graph or between some vertices.
source code
 
adhesion(source=-1, target=-1, checks=True)
Calculates the edge connectivity of the graph or between some vertices.
source code
 
shortest_paths_dijkstra(source=None, target=None, weights=None, mode=OUT)
Calculates shortest path lengths for given vertices in a graph.
source code
 
subgraph(vertices, implementation="auto")
Returns a subgraph spanned by the given vertices.
source code
 
__init__(n=None, edges=None, directed=None, graph_attrs=None, vertex_attrs=None, edge_attrs=None)
Constructs a graph from scratch.
source code
 
add_edge(source, target, **kwds)
Adds a single edge to the graph.
source code
 
add_edges(es)
Adds some edges to the graph.
source code
 
add_vertex(name=None, **kwds)
Adds a single vertex to the graph.
source code
 
add_vertices(n)
Adds some vertices to the graph.
source code
 
adjacent(vertex, mode=OUT)
Returns the edges a given vertex is incident on.
source code
 
as_directed(*args, **kwds)
Returns a directed copy of this graph.
source code
 
as_undirected(*args, **kwds)
Returns an undirected copy of this graph.
source code
 
delete_edges(self, *args, **kwds)
Deletes some edges from the graph.
source code
 
indegree(self, *args, **kwds)
Returns the in-degrees in a list.
source code
 
outdegree(self, *args, **kwds)
Returns the out-degrees in a list.
source code
 
all_st_cuts(self, source, target)
Returns all the cuts between the source and target vertices in a directed graph.
source code
 
all_st_mincuts(self, source, target, capacity=None)
Returns all the mincuts between the source and target vertices in a directed graph.
source code
 
biconnected_components(self, return_articulation_points=False)
Calculates the biconnected components of the graph.
source code
 
blocks(self, return_articulation_points=False)
Calculates the biconnected components of the graph.
source code
 
cohesive_blocks()
Calculates the cohesive block structure of the graph.
source code
 
clusters(mode=STRONG)
Calculates the (strong or weak) clusters (connected components) for a given graph.
source code
 
components(mode=STRONG)
Calculates the (strong or weak) clusters (connected components) for a given graph.
source code
 
degree_distribution(bin_width=1, ...)
Calculates the degree distribution of the graph.
source code
 
dyad_census()
Calculates the dyad census of the graph.
source code
 
get_adjacency(self, type=2, attribute=None, default=0, eids=False)
Returns the adjacency matrix of a graph.
source code
 
get_adjlist(mode=OUT)
Returns the adjacency list representation of the graph.
source code
 
get_adjedgelist(mode=OUT)
Returns the incidence list representation of the graph.
source code
 
get_inclist(mode=OUT)
Returns the incidence list representation of the graph.
source code
 
gomory_hu_tree(capacity=None, flow="flow")
Calculates the Gomory-Hu tree of an undirected graph with optional edge capacities.
source code
 
is_named()
Returns whether the graph is named, i.e.
source code
 
is_weighted()
Returns whether the graph is weighted, i.e.
source code
 
maxflow(source, target, capacity=None)
Returns a maximum flow between the given source and target vertices in a graph.
source code
 
mincut(source=None, target=None, capacity=None)
Calculates the minimum cut between the given source and target vertices or within the whole graph.
source code
 
st_mincut(source, target, capacity=None)
Calculates the minimum cut between the source and target vertices in a graph.
source code
 
modularity(membership, weights=None)
Calculates the modularity score of the graph with respect to a given clustering.
source code
 
path_length_hist(directed=True)
Returns the path length histogram of the graph
source code
 
pagerank(self, vertices=None, directed=True, damping=0.85, weights=None, arpack_options=None, implementation='prpack', niter=1000, eps=0.001)
Calculates the Google PageRank values of a graph.
source code
 
spanning_tree(self, weights=None, return_tree=True)
Calculates a minimum spanning tree for a graph.
source code
 
transitivity_avglocal_undirected(self, mode='nan', weights=None)
Calculates the average of the vertex transitivities of the graph.
source code
 
triad_census()
Calculates the triad census of the graph.
source code
 
count_automorphisms_vf2(self, color=None, edge_color=None, node_compat_fn=None, edge_compat_fn=None)
Returns the number of automorphisms of the graph.
source code
 
get_automorphisms_vf2(self, color=None, edge_color=None, node_compat_fn=None, edge_compat_fn=None)
Returns all the automorphisms of the graph
source code
 
community_fastgreedy(self, weights=None)
Community structure based on the greedy optimization of modularity.
source code
 
community_infomap(self, edge_weights=None, vertex_weights=None, trials=10)
Finds the community structure of the network according to the Infomap method of Martin Rosvall and Carl T.
source code
 
community_leading_eigenvector_naive(clusters=None, return_merges=False)
A naive implementation of Newman's eigenvector community structure detection.
source code
 
community_leading_eigenvector(clusters=None, weights=None, arpack_options=None)
Newman's leading eigenvector method for detecting community structure.
source code
 
community_label_propagation(weights=None, initial=None, fixed=None)
Finds the community structure of the graph according to the label propagation method of Raghavan et al.
source code
 
community_multilevel(self, weights=None, return_levels=False)
Community structure based on the multilevel algorithm of Blondel et al.
source code
 
community_optimal_modularity(self, *args, **kwds)
Calculates the optimal modularity score of the graph and the corresponding community structure.
source code
 
community_edge_betweenness(self, clusters=None, directed=True, weights=None)
Community structure based on the betweenness of the edges in the network.
source code
 
community_spinglass(weights=None, spins=25, parupdate=False, start_temp=1, stop_temp=0.01, cool_fact=0.99, update_rule="config", gamma=1, implementation="orig", lambda_=1)
Finds the community structure of the graph according to the spinglass community detection method of Reichardt & Bornholdt.
source code
 
community_walktrap(self, weights=None, steps=4)
Community detection algorithm of Latapy & Pons, based on random walks.
source code
 
k_core(self, *args)
Returns some k-cores of the graph.
source code
 
layout(self, layout=None, *args, **kwds)
Returns the layout of the graph according to a layout algorithm.
source code
 
layout_auto(self, *args, **kwds)
Chooses and runs a suitable layout function based on simple topological properties of the graph.
source code
 
layout_sugiyama(layers=None, weights=None, hgap=1, vgap=1, maxiter=100, return_extended_graph=False)
Places the vertices using a layered Sugiyama layout.
source code
 
maximum_bipartite_matching(self, types='type', weights=None, eps=None)
Finds a maximum matching in a bipartite graph.
source code
 
write_adjacency(self, f, sep=' ', eol='\n', *args, **kwds)
Writes the adjacency matrix of the graph to the given file
source code
 
write_dimacs(self, f, source=None, target=None, capacity='capacity')
Writes the graph in DIMACS format to the given file.
source code
 
write_graphmlz(self, f, compresslevel=9)
Writes the graph to a zipped GraphML file.
source code
 
write_pickle(self, fname=None, version=-1)
Saves the graph in Python pickled format
source code
 
write_picklez(self, fname=None, version=-1)
Saves the graph in Python pickled format, compressed with gzip.
source code
 
write_svg(self, fname, layout='auto', width=None, height=None, labels='label', colors='color', shapes='shape', vertex_size=10, edge_colors='color', font_size=16, *args, **kwds)
Saves the graph as an SVG (Scalable Vector Graphics) file
source code
 
write(self, f, format=None, *args, **kwds)
Unified writing function for graphs.
source code
 
save(self, f, format=None, *args, **kwds)
Unified writing function for graphs.
source code
 
bipartite_projection(self, types='type', multiplicity=True, probe1=-1, which='both')
Projects a bipartite graph into two one-mode graphs.
source code
 
bipartite_projection_size(types="type")
Calculates the number of vertices and edges in the bipartite projections of this graph according to the specified vertex types.
source code
 
get_incidence(self, types="type")
Returns the incidence matrix of a bipartite graph.
source code
 
__iadd__(self, other)
In-place addition (disjoint union).
source code
 
__add__(self, other)
Copies the graph and extends the copy depending on the type of the other object given.
source code
 
__isub__(self, other)
In-place subtraction (difference).
source code
 
__sub__(self, other)
Removes the given object(s) from the graph
source code
 
__mul__(self, other)
Copies exact replicas of the original graph an arbitrary number of times.
source code
 
__nonzero__(self)
Returns True if the graph has at least one vertex, False otherwise.
source code
 
__coerce__(self, other)
Coercion rules.
source code
 
__reduce__(self)
Support for pickling.
source code
 
__plot__(self, context, bbox, palette, *args, **kwds)
Plots the graph to the given Cairo context in the given bounding box
source code
 
__str__(self)
Returns a string representation of the graph.
source code
 
summary(self, verbosity=0, width=None, *args, **kwds)
Returns the summary of the graph.
source code
 
layout_fruchterman_reingold_3d(*args, **kwds)
Alias for layout_fruchterman_reingold() with dim=3.
source code
 
layout_kamada_kawai_3d(*args, **kwds)
Alias for layout_kamada_kawai() with dim=3.
source code
 
layout_random_3d(*args, **kwds)
Alias for layout_random() with dim=3.
source code
 
layout_grid_3d(*args, **kwds)
Alias for layout_grid() with dim=3.
source code
 
layout_sphere(*args, **kwds)
Alias for layout_circle() with dim=3.
source code
 
layout_bipartite(types="type", hgap=1, vgap=1, maxiter=100)
Place the vertices of a bipartite graph in two layers.
source code
 
layout_circle(dim=2)
Places the vertices of the graph uniformly on a circle or a sphere.
source code
 
layout_drl(weights=None, fixed=None, seed=None, options=None, dim=2)
Places the vertices on a 2D plane or in the 3D space ccording to the DrL layout algorithm.
source code
 
layout_fruchterman_reingold(weights=None, maxiter=500, maxdelta=None, area=None, coolexp=1.5, repulserad=None, seed=None, minx=None, maxx=None, miny=None, maxy=None, minz=None, maxz=None, dim=2)
Places the vertices on a 2D plane or in the 3D space according to the Fruchterman-Reingold algorithm.
source code
 
layout_graphopt(niter=500, node_charge=0.001, node_mass=30, spring_length=0, spring_constant=1, max_sa_movement=5, seed=None)
This is a port of the graphopt layout algorithm by Michael Schmuhl.
source code
 
layout_grid(width=0, height=0, dim=2)
Places the vertices of a graph in a 2D or 3D grid.
source code
 
layout_grid_fruchterman_reingold(maxiter=500, maxdelta=None, area=None, coolexp=0.99, repulserad=maxiter*maxdelta, cellsize=None, seed=None)
Places the vertices on a 2D plane according to the Fruchterman-Reingold grid algorithm.
source code
 
layout_kamada_kawai(maxiter=1000, sigma=None, initemp=10, coolexp=0.99, kkconst=None, seed=None, minx=None, maxx=None, miny=None, maxy=None, minz=None, maxz=None, dim=2)
Places the vertices on a plane according to the Kamada-Kawai algorithm.
source code
 
layout_lgl(maxiter=150, maxdelta=-1, area=-1, coolexp=1.5, repulserad=-1, cellsize=-1, root=None)
Places the vertices on a 2D plane according to the Large Graph Layout.
source code
 
layout_mds(dist=None, dim=2, arpack_options=None)
Places the vertices in an Euclidean space with the given number of dimensions using multidimensional scaling.
source code
 
layout_random(dim=2)
Places the vertices of the graph randomly.
source code
 
layout_reingold_tilford(mode="out", root=None, rootlevel=None)
Places the vertices on a 2D plane according to the Reingold-Tilford layout algorithm.
source code
 
layout_reingold_tilford_circular(mode="out", root=None, rootlevel=None)
Circular Reingold-Tilford layout for trees.
source code
 
layout_star(center=0, order=None)
Calculates a star-like layout for the graph.
source code

Inherited from GraphBase: Adjacency, Asymmetric_Preference, Atlas, Barabasi, De_Bruijn, Degree_Sequence, Erdos_Renyi, Establishment, Famous, Forest_Fire, Full, Full_Citation, Growing_Random, Isoclass, K_Regular, Kautz, LCF, Lattice, Preference, Read_DL, Read_Edgelist, Read_GML, Read_GraphDB, Read_GraphML, Read_Lgl, Read_Ncol, Read_Pajek, Recent_Degree, Ring, SBM, Star, Static_Fitness, Static_Power_Law, Tree, Watts_Strogatz, Weighted_Adjacency, __and__, __delitem__, __getitem__, __invert__, __new__, __or__, __rand__, __ror__, __setitem__, all_minimal_st_separators, are_connected, articulation_points, assortativity, assortativity_degree, assortativity_nominal, attributes, authority_score, average_path_length, betweenness, bfs, bfsiter, bibcoupling, canonical_permutation, clique_number, cliques, closeness, cocitation, complementer, compose, constraint, contract_vertices, convergence_degree, convergence_field_size, copy, coreness, count_isomorphisms_vf2, count_multiple, count_subisomorphisms_vf2, decompose, degree, delete_vertices, density, diameter, difference, disjoint_union, diversity, eccentricity, ecount, edge_attributes, edge_betweenness, edge_connectivity, eigenvector_centrality, farthest_points, feedback_arc_set, get_all_shortest_paths, get_diameter, get_edgelist, get_eid, get_eids, get_isomorphisms_vf2, get_shortest_paths, get_subisomorphisms_lad, get_subisomorphisms_vf2, girth, has_multiple, hub_score, incident, independence_number, independent_vertex_sets, induced_subgraph, intersection, is_bipartite, is_connected, is_dag, is_directed, is_loop, is_minimal_separator, is_multiple, is_mutual, is_separator, is_simple, isoclass, isomorphic, isomorphic_bliss, isomorphic_vf2, knn, laplacian, largest_cliques, largest_independent_vertex_sets, linegraph, maxdegree, maxflow_value, maximal_cliques, maximal_independent_vertex_sets, mincut_value, minimum_size_separators, motifs_randesu, motifs_randesu_estimate, motifs_randesu_no, neighborhood, neighborhood_size, neighbors, permute_vertices, personalized_pagerank, predecessors, radius, reciprocity, rewire, rewire_edges, shortest_paths, similarity_dice, similarity_inverse_log_weighted, similarity_jaccard, simplify, strength, subcomponent, subgraph_edges, subisomorphic_lad, subisomorphic_vf2, successors, to_directed, to_undirected, topological_sorting, transitivity_local_undirected, transitivity_undirected, unfold_tree, union, vcount, vertex_attributes, vertex_connectivity, write_dot, write_edgelist, write_gml, write_graphml, write_leda, write_lgl, write_ncol, write_pajek

Inherited from GraphBase (private): _Random_Bipartite

Inherited from object: __delattr__, __format__, __getattribute__, __hash__, __reduce_ex__, __repr__, __setattr__, __sizeof__, __subclasshook__

Class Methods [hide private]
 
Read_Adjacency(klass, f, sep=None, comment_char='#', attribute=None, *args, **kwds)
Constructs a graph based on an adjacency matrix from the given file
source code
 
Read_DIMACS(f, directed=False)
Reads a graph from a file conforming to the DIMACS minimum-cost flow file format.
source code
 
Read_GraphMLz(f, directed=True, index=0)
Reads a graph from a zipped GraphML file.
source code
 
Read_Pickle(klass, fname=None)
Reads a graph from Python pickled format
source code
 
Read_Picklez(klass, fname, *args, **kwds)
Reads a graph from compressed Python pickled format, uncompressing it on-the-fly.
source code
 
_identify_format(filename)
Tries to identify the format of the graph stored in the file with the given filename.
source code
 
Read(klass, f, format=None, *args, **kwds)
Unified reading function for graphs.
source code
 
Load(klass, f, format=None, *args, **kwds)
Unified reading function for graphs.
source code
 
DictList(klass, vertices, edges, directed=False, vertex_name_attr='name', edge_foreign_keys=('source', 'target'), iterative=False)
Constructs a graph from a list-of-dictionaries representation.
source code
 
TupleList(klass, edges, directed=False, vertex_name_attr='name', edge_attrs=None, weights=False)
Constructs a graph from a list-of-tuples representation.
source code
 
Formula(Graph, formula= None, attr= "name", simplify= True)
Generates a graph from a graph formula
source code
 
Bipartite(types, edges, directed=False)
Creates a bipartite graph with the given vertex types and edges.
source code
 
Full_Bipartite(n1, n2, directed=False, mode=ALL)
Generates a full bipartite graph (directed or undirected, with or without loops).
source code
 
Random_Bipartite(klass, *args, **kwds)
Generates a random bipartite graph with the given number of vertices and edges (if m is given), or with the given number of vertices and the given connection probability (if p is given).
source code
 
GRG(n, radius, torus=False, return_coordinates=False)
Generates a random geometric graph.
source code
 
Incidence(matrix, directed=False, mode=ALL, multiple=False)
Creates a bipartite graph from an incidence matrix.
source code
 
_reconstruct(cls, attrs, *args, **kwds)
Reconstructs a Graph object from Python's pickled format.
source code
Class Variables [hide private]
  _format_mapping = {'adj': ('Read_Adjacency', 'write_adjacency'...
  _layout_mapping = {'auto': 'layout_auto', 'automatic': 'layout...
Properties [hide private]
  vs
The vertex sequence of the graph
  es
The edge sequence of the graph

Inherited from object: __class__

Method Details [hide private]

omega()

source code 

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.

alpha()

source code 

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

shell_index(mode=ALL)

source code 

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

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

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

Reference: Vladimir Batagelj, Matjaz Zaversnik: An O(m) Algorithm for Core Decomposition of Networks.

cut_vertices()

source code 

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.

evcent(directed=True, scale=True, weights=None, return_eigenvalue=False, arpack_options=None)

source code 

Calculates the eigenvector centralities of the vertices in a graph.

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_eigenvalue - whether to return the actual largest eigenvalue along with the centralities
  • arpack_options - an ARPACKOptions object that can be used to fine-tune the calculation. If it is omitted, the module-level variable called arpack_options is used.
Returns:
the eigenvector centralities in a list and optionally the largest eigenvalue (as a second member of a tuple)

vertex_disjoint_paths(source=-1, target=-1, checks=True, neighbors="error")

source code 

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, "infinity" returns infinity, "ignore" ignores the edge.
Returns:
the vertex connectivity

edge_disjoint_paths(source=-1, target=-1, checks=True)

source code 

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

cohesion(source=-1, target=-1, checks=True, neighbors="error")

source code 

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, "infinity" returns infinity, "ignore" ignores the edge.
Returns:
the vertex connectivity

adhesion(source=-1, target=-1, checks=True)

source code 

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

shortest_paths_dijkstra(source=None, target=None, weights=None, mode=OUT)

source code 

Calculates shortest path lengths for given vertices in a graph.

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

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.
Returns:
the shortest path lengths for given vertices in a matrix

subgraph(vertices, implementation="auto")

source code 

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

__init__(n=None, edges=None, directed=None, graph_attrs=None, vertex_attrs=None, edge_attrs=None)
(Constructor)

source code 

Constructs a graph from scratch.

Parameters:
  • n - the number of vertices. Can be omitted, the default is zero.
  • edges - the edge list where every list item is a pair of integers. If any of the integers is larger than n-1, the number of vertices is adjusted accordingly.
  • directed - whether the graph should be directed
  • graph_attrs - the attributes of the graph as a dictionary.
  • vertex_attrs - the attributes of the vertices as a dictionary. Every dictionary value must be an iterable with exactly n items.
  • edge_attrs - the attributes of the edges as a dictionary. Every dictionary value must be an iterable with exactly m items where m is the number of edges.
Overrides: object.__init__

add_edge(source, target, **kwds)

source code 

Adds a single edge to the graph.

Keyword arguments (except the source and target arguments) will be assigned to the edge as attributes.

Parameters:
  • source - the source vertex of the edge or its name.
  • target - the target vertex of the edge or its name.

add_edges(es)

source code 

Adds some edges to the graph.

Parameters:
  • es - the list of edges to be added. Every edge is represented with a tuple containing the vertex IDs or names of the two endpoints. Vertices are enumerated from zero.
Overrides: GraphBase.add_edges

add_vertex(name=None, **kwds)

source code 

Adds a single vertex to the graph. Keyword arguments will be assigned as vertex attributes. Note that name as a keyword argument is treated specially; if a graph has name as a vertex attribute, it allows one to refer to vertices by their names in most places where igraph expects a vertex ID.

add_vertices(n)

source code 

Adds some vertices to the graph.

Parameters:
  • n - the number of vertices to be added, or the name of a single vertex to be added, or an iterable of strings, each corresponding to the name of a vertex to be added. Names will be assigned to the name vertex attribute.
Overrides: GraphBase.add_vertices

adjacent(vertex, mode=OUT)

source code 

Returns the edges a given vertex is incident on.

Deprecated: replaced by Graph.incident() since igraph 0.6

as_directed(*args, **kwds)

source code 

Returns a directed copy of this graph. Arguments are passed on to Graph.to_directed() that is invoked on the copy.

as_undirected(*args, **kwds)

source code 

Returns an undirected copy of this graph. Arguments are passed on to Graph.to_undirected() that is invoked on the copy.

delete_edges(self, *args, **kwds)

source code 

Deletes some edges from the graph.

The set of edges to be deleted is determined by the positional and keyword arguments. If any keyword argument is present, or the first positional argument is callable, an edge sequence is derived by calling EdgeSeq.select with the same positional and keyword arguments. Edges in the derived edge sequence will be removed. Otherwise the first positional argument is considered as follows:

  • None - deletes all edges
  • a single integer - deletes the edge with the given ID
  • a list of integers - deletes the edges denoted by the given IDs
  • a list of 2-tuples - deletes the edges denoted by the given source-target vertex pairs. When multiple edges are present between a given source-target vertex pair, only one is removed.
Parameters:
  • es - the list of edges to be removed. Edges are identifed by edge IDs. EdgeSeq objects are also accepted here.
Overrides: GraphBase.delete_edges

indegree(self, *args, **kwds)

source code 

Returns the in-degrees in a list.

See degree for possible arguments.

outdegree(self, *args, **kwds)

source code 

Returns the out-degrees in a list.

See degree for possible arguments.

all_st_cuts(self, source, target)

source code 

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

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

Parameters:
  • source - the source vertex ID
  • target - the target vertex ID
Returns:
a list of Cut objects.
Overrides: GraphBase.all_st_cuts

Reference: JS Provan and DR Shier: A paradigm for listing (s,t)-cuts in graphs. Algorithmica 15, 351--372, 1996.

all_st_mincuts(self, source, target, capacity=None)

source code 

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

This function lists all minimum edge-cuts between a source and a target vertex.

Parameters:
  • source - the source vertex ID
  • target - the target vertex ID
  • capacity - the edge capacities (weights). If None, all edges have equal weight. May also be an attribute name.
Returns:
a list of Cut objects.
Overrides: GraphBase.all_st_mincuts

Reference: JS Provan and DR Shier: A paradigm for listing (s,t)-cuts in graphs. Algorithmica 15, 351--372, 1996.

biconnected_components(self, return_articulation_points=False)

source code 

Calculates the biconnected components of the graph.

Parameters:
  • return_articulation_points - whether to return the articulation points as well
Returns:
a VertexCover object describing the biconnected components, and optionally the list of articulation points as well
Overrides: GraphBase.biconnected_components

blocks(self, return_articulation_points=False)

source code 

Calculates the biconnected components of the graph.

Parameters:
  • return_articulation_points - whether to return the articulation points as well
Returns:
a VertexCover object describing the biconnected components, and optionally the list of articulation points as well

cohesive_blocks()

source code 

Calculates the cohesive block structure of the graph.

Cohesive blocking is a method of determining hierarchical subsets of graph vertices based on their structural cohesion (i.e. vertex connectivity). For a given graph G, a subset of its vertices S is said to be maximally k-cohesive if there is no superset of S with vertex connectivity greater than or equal to k. Cohesive blocking is a process through which, given a k-cohesive set of vertices, maximally l-cohesive subsets are recursively identified with l > k. Thus a hierarchy of vertex subsets is obtained in the end, with the entire graph G at its root.

Returns:
an instance of CohesiveBlocks. See the documentation of CohesiveBlocks for more information.
Overrides: GraphBase.cohesive_blocks

See Also: CohesiveBlocks

clusters(mode=STRONG)

source code 

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

Parameters:
  • mode - must be either STRONG or WEAK, depending on the clusters being sought. Optional, defaults to STRONG.
Returns:
a VertexClustering object
Overrides: GraphBase.clusters

components(mode=STRONG)

source code 

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

Parameters:
  • mode - must be either STRONG or WEAK, depending on the clusters being sought. Optional, defaults to STRONG.
Returns:
a VertexClustering object

degree_distribution(bin_width=1, ...)

source code 

Calculates the degree distribution of the graph.

Unknown keyword arguments are directly passed to degree().

Parameters:
  • bin_width - the bin width of the histogram
Returns:
a histogram representing the degree distribution of the graph.

dyad_census()

source code 

Calculates the dyad census of the graph.

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 from a to b or from b to a but not the other way round) and null (there is no connection between a and b).

Returns:
a DyadCensus object.
Overrides: GraphBase.dyad_census

Reference: Holland, P.W. and Leinhardt, S. (1970). A Method for Detecting Structure in Sociometric Data. American Journal of Sociology, 70, 492-513.

get_adjacency(self, type=2, attribute=None, default=0, eids=False)

source code 

Returns the adjacency matrix of a graph.

Parameters:
  • type - either GET_ADJACENCY_LOWER (uses the lower triangle of the matrix) or GET_ADJACENCY_UPPER (uses the upper triangle) or GET_ADJACENCY_BOTH (uses both parts). Ignored for directed graphs.
  • attribute - if None, returns the ordinary adjacency matrix. When the name of a valid edge attribute is given here, the matrix returned will contain the default value at the places where there is no edge or the value of the given attribute where there is an edge. Multiple edges are not supported, the value written in the matrix in this case will be unpredictable. This parameter is ignored if eids is True
  • default - the default value written to the cells in the case of adjacency matrices with attributes.
  • eids - specifies whether the edge IDs should be returned in the adjacency matrix. Since zero is a valid edge ID, the cells in the matrix that correspond to unconnected vertex pairs will contain -1 instead of 0 if eids is True. If eids is False, the number of edges will be returned in the matrix for each vertex pair.
Returns:
the adjacency matrix as a Matrix.
Overrides: GraphBase.get_adjacency

get_adjlist(mode=OUT)

source code 

Returns the adjacency list representation of the graph.

The adjacency list representation is a list of lists. Each item of the outer list belongs to a single vertex of the graph. The inner list contains the neighbors of the given vertex.

Parameters:
  • mode - if OUT, returns the successors of the vertex. If IN, returns the predecessors of the vertex. If ALL, both the predecessors and the successors will be returned. Ignored for undirected graphs.

get_adjedgelist(mode=OUT)

source code 

Returns the incidence list representation of the graph.

Deprecated: replaced by Graph.get_inclist() since igraph 0.6

See Also: Graph.get_inclist()

get_inclist(mode=OUT)

source code 

Returns the incidence list representation of the graph.

The incidence list representation is a list of lists. Each item of the outer list belongs to a single vertex of the graph. The inner list contains the IDs of the incident edges of the given vertex.

Parameters:
  • mode - if OUT, returns the successors of the vertex. If IN, returns the predecessors of the vertex. If ALL, both the predecessors and the successors will be returned. Ignored for undirected graphs.

gomory_hu_tree(capacity=None, flow="flow")

source code 

Calculates the Gomory-Hu tree of an undirected graph with optional edge capacities.

The Gomory-Hu tree is a concise representation of the value of all the maximum flows (or minimum cuts) in a graph. The vertices of the tree correspond exactly to the vertices of the original graph in the same order. Edges of the Gomory-Hu tree are annotated by flow values. The value of the maximum flow (or minimum cut) between an arbitrary (u,v) vertex pair in the original graph is then given by the minimum flow value (i.e. edge annotation) along the shortest path between u and v in the Gomory-Hu tree.

Parameters:
  • capacity - the edge capacities (weights). If None, all edges have equal weight. May also be an attribute name.
  • flow - the name of the edge attribute in the returned graph in which the flow values will be stored.
Returns:
the Gomory-Hu tree as a Graph object.
Overrides: GraphBase.gomory_hu_tree

is_named()

source code 

Returns whether the graph is named, i.e. whether it has a "name" vertex attribute.

is_weighted()

source code 

Returns whether the graph is weighted, i.e. whether it has a "weight" edge attribute.

maxflow(source, target, capacity=None)

source code 

Returns a maximum flow between the given source and target vertices in a graph.

A maximum flow from source to target is an assignment of non-negative real numbers to the edges of the graph, satisfying two properties:

  1. For each edge, the flow (i.e. the assigned number) is not more than the capacity of the edge (see the capacity argument)
  2. For every vertex except the source and the target, the incoming flow is the same as the outgoing flow.

The value of the flow is the incoming flow of the target or the outgoing flow of the source (which are equal). The maximum flow is the maximum possible such value.

Parameters:
  • capacity - the edge capacities (weights). If None, all edges have equal weight. May also be an attribute name.
Returns:
a Flow object describing the maximum flow
Overrides: GraphBase.maxflow

mincut(source=None, target=None, capacity=None)

source code 

Calculates the minimum cut between the given 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 neither the source nor the target are given). The minimum is calculated using the weights (capacities) of the edges, so the cut with the minimum total capacity is calculated.

For undirected graphs and no source and target, the method uses the Stoer-Wagner algorithm. For a given source and target, the method uses the push-relabel algorithm; see the references below.

Parameters:
  • source - the source vertex ID. If None, the 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, the source must also be None and the calculation will be done for the entire graph (i.e. all possible vertex pairs).
  • capacity - the edge capacities (weights). If None, all edges have equal weight. May also be an attribute name.
Returns:
a Cut object describing the minimum cut
Overrides: GraphBase.mincut

st_mincut(source, target, capacity=None)

source code 

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

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 4-tuple
Overrides: GraphBase.st_mincut

modularity(membership, weights=None)

source code 

Calculates the modularity score of the graph with respect to a given clustering.

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's defined as Q=1/(2m)*sum(Aij-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, and Ci and cj are the types of the two vertices (i and j). 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 adjacent to vertex i, kj is the total weight of edges adjacent to vertex j and m is the total edge weight in the graph.

Parameters:
  • membership - a membership list or a VertexClustering object
  • weights - optional edge weights or None if all edges are weighed equally. Attribute names are also allowed.
Returns:
the modularity score
Overrides: GraphBase.modularity

Reference: MEJ Newman and M Girvan: Finding and evaluating community structure in networks. Phys Rev E 69 026113, 2004.

path_length_hist(directed=True)

source code 

Returns the path length histogram of the graph

Parameters:
  • directed - whether to consider directed paths. Ignored for undirected graphs.
Returns:
a Histogram object. The object will also have an unconnected attribute that stores the number of unconnected vertex pairs (where the second vertex can not be reached from the first one). The latter one will be of type long (and not a simple integer), since this can be very large.
Overrides: GraphBase.path_length_hist

pagerank(self, vertices=None, directed=True, damping=0.85, weights=None, arpack_options=None, implementation='prpack', niter=1000, eps=0.001)

source code 

Calculates the Google PageRank values of a graph.

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. 1-damping is the PageRank value for nodes with no incoming links. It is also the probability of resetting the random walk to a uniform distribution in each step.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
  • arpack_options - an ARPACKOptions object used to fine-tune the ARPACK eigenvector calculation. If omitted, the module-level 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:
    • "prpack": use the PRPACK library. This is a new implementation in igraph 0.7
    • "arpack": use the ARPACK library. This implementation was used from version 0.5, until version 0.7.
    • "power": use a simple power method. This is the implementation that was used before igraph version 0.5.
  • niter - The number of iterations to use in the power method implementation. It is ignored in the other implementations
  • eps - The power method implementation will consider the calculation as complete if the difference of PageRank values between iterations change less than this value for every node. It is ignored by the other implementations.
Returns:
a list with the Google PageRank values of the specified vertices.

spanning_tree(self, weights=None, return_tree=True)

source code 

Calculates a minimum spanning tree for a graph.

Parameters:
  • weights - a vector containing weights for every edge in the graph. None means that the graph is unweighted.
  • return_tree - whether to return the minimum spanning tree (when return_tree is True) or to return the IDs of the edges in the minimum spanning tree instead (when return_tree is False). The default is True for historical reasons as this argument was introduced in igraph 0.6.
Returns:
the spanning tree as a Graph object if return_tree is True or the IDs of the edges that constitute the spanning tree if return_tree is False.

Reference: Prim, R.C.: Shortest connection networks and some generalizations. Bell System Technical Journal 36:1389-1401, 1957.

transitivity_avglocal_undirected(self, mode='nan', weights=None)

source code 

Calculates the average of the vertex transitivities of the graph.

In the unweighted case, 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. The calculation is slightly more involved for weighted graphs; in this case, weights are taken into account according to the formula of Barrat et al (see the references).

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.

Parameters:
  • mode - defines how to treat vertices with degree less than two. If TRANSITIVITY_ZERO or "zero", these vertices will have zero transitivity. If TRANSITIVITY_NAN or "nan", these vertices will be excluded from the average.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
Overrides: GraphBase.transitivity_avglocal_undirected

See Also: transitivity_undirected(), transitivity_local_undirected()

Reference:
  • Watts DJ and Strogatz S: Collective dynamics of small-world networks. Nature 393(6884):440-442, 1998.
  • Barrat A, Barthelemy M, Pastor-Satorras R and Vespignani A: The architecture of complex weighted networks. PNAS 101, 3747 (2004). http://arxiv.org/abs/cond-mat/0311416.

triad_census()

source code 

Calculates the triad census of the graph.

Returns:
a TriadCensus object.
Overrides: GraphBase.triad_census

Reference: Davis, J.A. and Leinhardt, S. (1972). The Structure of Positive Interpersonal Relations in Small Groups. In: J. Berger (Ed.), Sociological Theories in Progress, Volume 2, 218-251. Boston: Houghton Mifflin.

count_automorphisms_vf2(self, color=None, edge_color=None, node_compat_fn=None, edge_compat_fn=None)

source code 

Returns the number of automorphisms of the graph.

This function simply calls count_isomorphisms_vf2 with the graph itself. See count_isomorphisms_vf2 for an explanation of the parameters.

Returns:
the number of automorphisms of the graph

See Also: Graph.count_isomorphisms_vf2

get_automorphisms_vf2(self, color=None, edge_color=None, node_compat_fn=None, edge_compat_fn=None)

source code 

Returns all the automorphisms of the graph

This function simply calls get_isomorphisms_vf2 with the graph itself. See get_isomorphisms_vf2 for an explanation of the parameters.

Returns:
a list of lists, each item containing a possible mapping of the graph vertices to itself according to the automorphism

See Also: Graph.get_isomorphisms_vf2

community_fastgreedy(self, weights=None)

source code 

Community structure based on the greedy optimization of modularity.

This algorithm merges individual nodes into communities in a way that greedily maximizes the modularity score of the graph. It can be proven that if no merge can increase the current modularity score, the algorithm can be stopped since no further increase can be achieved.

This algorithm is said to run almost in linear time on sparse graphs.

Parameters:
  • weights - edge attribute name or a list containing edge weights
Returns:
an appropriate VertexDendrogram object.
Overrides: GraphBase.community_fastgreedy

Reference: A Clauset, MEJ Newman and C Moore: Finding community structure in very large networks. Phys Rev E 70, 066111 (2004).

community_infomap(self, edge_weights=None, vertex_weights=None, trials=10)

source code 

Finds the community structure of the network according to the Infomap method of Martin Rosvall and Carl T. Bergstrom.

Parameters:
  • edge_weights - name of an edge attribute or a list containing edge weights.
  • vertex_weights - name of an vertex attribute or a list containing vertex weights.
  • trials - the number of attempts to partition the network.
Returns:
an appropriate VertexClustering object with an extra attribute called codelength that stores the code length determined by the algorithm.
Overrides: GraphBase.community_infomap
Reference:

community_leading_eigenvector_naive(clusters=None, return_merges=False)

source code 

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

Parameters:
  • clusters - the desired number of communities. If None, 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, so the actual number of discovered communities can be less than the desired one.
  • return_merges - whether the returned object should be a dendrogram instead of a single clustering.
Returns:
an appropriate VertexClustering or VertexDendrogram object.

Reference: MEJ Newman: Finding community structure in networks using the eigenvectors of matrices, arXiv:physics/0605087

community_leading_eigenvector(clusters=None, weights=None, arpack_options=None)

source code 

Newman's leading eigenvector method for detecting community structure. This is the proper implementation of the recursive, divisive algorithm: each split is done by maximizing the modularity regarding the original network.

Parameters:
  • clusters - the desired number of communities. If None, 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, so the actual number of discovered communities can be less than the desired one.
  • weights - name of an edge attribute or a list containing edge weights.
  • arpack_options - an ARPACKOptions object used to fine-tune the ARPACK eigenvector calculation. If omitted, the module-level variable called arpack_options is used.
Returns:
an appropriate VertexClustering object.
Overrides: GraphBase.community_leading_eigenvector

Reference: MEJ Newman: Finding community structure in networks using the eigenvectors of matrices, arXiv:physics/0605087

community_label_propagation(weights=None, initial=None, fixed=None)

source code 

Finds the community structure of the graph according to the label propagation method of Raghavan et al. Initially, each vertex is assigned a different label. After that, each vertex chooses the dominant label in its neighbourhood in each iteration. Ties are broken randomly and the order in which the vertices are updated is randomized before every iteration. The algorithm ends when vertices reach a consensus. Note that since ties are broken randomly, there is no guarantee that the algorithm returns the same community structure after each run. In fact, they frequently differ. See the paper of Raghavan et al on how to come up with an aggregated community structure.

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

Reference: Raghavan, U.N. and Albert, R. and Kumara, S. Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76:036106, 2007. http://arxiv.org/abs/0709.2938.

community_multilevel(self, weights=None, return_levels=False)

source code 

Community structure based on the multilevel algorithm of Blondel et al.

This is a bottom-up 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 adjacent 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.

This algorithm is said to run almost in linear time on sparse graphs.

Parameters:
  • weights - edge attribute name or a list containing edge weights
  • return_levels - if True, the communities at each level are returned in a list. If False, only the community structure with the best modularity is returned.
Returns:
a list of VertexClustering objects, one corresponding to each level (if return_levels is True), or a VertexClustering corresponding to the best modularity.
Overrides: GraphBase.community_multilevel

Reference: VD Blondel, J-L 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

community_optimal_modularity(self, *args, **kwds)

source code 

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.
Overrides: GraphBase.community_optimal_modularity

community_edge_betweenness(self, clusters=None, directed=True, weights=None)

source code 

Community structure based on the betweenness of the edges in the network.

The idea is that the betweenness of the edges connecting two communities is typically high, as many of the shortest paths between nodes in separate communities go through them. So we gradually remove the edge with the highest betweenness and recalculate the betweennesses after every removal. This way sooner or later the network falls of to separate components. The result of the clustering will be represented by a dendrogram.

Parameters:
  • clusters - the number of clusters we would like to see. This practically defines the "level" where we "cut" the dendrogram to get the membership vector of the vertices. If None, the dendrogram is cut at the level which maximizes the modularity.
  • directed - whether the directionality of the edges should be taken into account or not.
  • weights - name of an edge attribute or a list containing edge weights.
Returns:
a VertexDendrogram object, initally cut at the maximum modularity or at the desired number of clusters.
Overrides: GraphBase.community_edge_betweenness

community_spinglass(weights=None, spins=25, parupdate=False, start_temp=1, stop_temp=0.01, cool_fact=0.99, update_rule="config", gamma=1, implementation="orig", lambda_=1)

source code 

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_temp - the starting temperature
  • stop_temp - the stop temperature
  • cool_fact - cooling factor for the simulated annealing
  • update_rule - 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 of 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 intra-connectivity. 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. Note the underscore at the end of the argument name; this is due to the fact that lambda is a reserved keyword in Python.
Returns:
an appropriate VertexClustering object.
Overrides: GraphBase.community_spinglass
Reference:

community_walktrap(self, weights=None, steps=4)

source code 

Community detection algorithm of Latapy & Pons, based on random walks.

The basic idea of the algorithm is that short random walks tend to stay in the same community. The result of the clustering will be represented as a dendrogram.

Parameters:
  • weights - name of an edge attribute or a list containing edge weights
  • steps - length of random walks to perform
Returns:
a VertexDendrogram object, initially cut at the maximum modularity.
Overrides: GraphBase.community_walktrap

Reference: Pascal Pons, Matthieu Latapy: Computing communities in large networks using random walks, http://arxiv.org/abs/physics/0512106.

k_core(self, *args)

source code 

Returns some k-cores of the graph.

The method accepts an arbitrary number of arguments representing the desired indices of the k-cores to be returned. The arguments can also be lists or tuples. The result is a single Graph object if an only integer argument was given, otherwise the result is a list of Graph objects representing the desired k-cores in the order the arguments were specified. If no argument is given, returns all k-cores in increasing order of k.

layout(self, layout=None, *args, **kwds)

source code 

Returns the layout of the graph according to a layout algorithm.

Parameters and keyword arguments not specified here are passed to the layout algorithm directly. See the documentation of the layout algorithms for the explanation of these parameters.

Registered layout names understood by this method are:

Parameters:
  • layout - the layout to use. This can be one of the registered layout names or a callable which returns either a Layout object or a list of lists containing the coordinates. If None, uses the value of the plotting.layout configuration key.
Returns:
a Layout object.

layout_auto(self, *args, **kwds)

source code 

Chooses and runs a suitable layout function based on simple topological properties of the graph.

This function tries to choose an appropriate layout function for the graph using the following rules:

  1. If the graph has an attribute called layout, it will be used. It may either be a Layout instance, a list of coordinate pairs, the name of a layout function, or a callable function which generates the layout when called with the graph as a parameter.
  2. Otherwise, if the graph has vertex attributes called x and y, these will be used as coordinates in the layout. When a 3D layout is requested (by setting dim to 3), a vertex attribute named z will also be needed.
  3. Otherwise, if the graph is connected and has at most 100 vertices, the Kamada-Kawai layout will be used (see Graph.layout_kamada_kawai()).
  4. Otherwise, if the graph has at most 1000 vertices, the Fruchterman-Reingold layout will be used (see Graph.layout_fruchterman_reingold()).
  5. If everything else above failed, the DrL layout algorithm will be used (see Graph.layout_drl()).

All the arguments of this function except dim are passed on to the chosen layout function (in case we have to call some layout function).

Parameters:
  • dim - specifies whether we would like to obtain a 2D or a 3D layout.
Returns:
a Layout object.

layout_sugiyama(layers=None, weights=None, hgap=1, vgap=1, maxiter=100, return_extended_graph=False)

source code 

Places the vertices using a layered Sugiyama layout.

This is a layered layout that is most suitable for directed acyclic graphs, although it works on undirected or cyclic graphs as well.

Each vertex is assigned to a layer and each layer is placed on a horizontal line. Vertices within the same layer are then permuted using the barycenter heuristic that tries to minimize edge crossings.

Dummy vertices will be added on edges that span more than one layer. The returned layout therefore contains more rows than the number of nodes in the original graph; the extra rows correspond to the dummy vertices.

Parameters:
  • layers - a vector specifying a non-negative integer layer index for each vertex, or the name of a numeric vertex attribute that contains the layer indices. If None, a layering will be determined automatically. For undirected graphs, a spanning tree will be extracted and vertices will be assigned to layers using a breadth first search from the node with the largest degree. For directed graphs, cycles are broken by reversing the direction of edges in an approximate feedback arc set using the heuristic of Eades, Lin and Smyth, and then using longest path layering to place the vertices in layers.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
  • hgap - minimum horizontal gap between vertices in the same layer.
  • vgap - vertical gap between layers. The layer index will be multiplied by vgap to obtain the Y coordinate.
  • 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.
  • return_extended_graph - specifies that the extended graph with the added dummy vertices should also be returned. When this is True, the result will be a tuple containing the layout and the extended graph. The first |V| nodes of the extended graph will correspond to the nodes of the original graph, the remaining ones are dummy nodes. Plotting the extended graph with the returned layout and hidden dummy nodes will produce a layout that is similar to the original graph, but with the added edge bends. The extended graph also contains an edge attribute called _original_eid which specifies the ID of the edge in the original graph from which the edge of the extended graph was created.
Returns:
the calculated layout, which may (and usually will) have more rows than the number of vertices; the remaining rows correspond to the dummy nodes introduced in the layering step. When return_extended_graph is True, it will also contain the extended graph.
Reference:
  • K Sugiyama, S Tagawa, M Toda: Methods for visual understanding of hierarchical system structures. IEEE Systems, Man and Cybernetics 11(2):109-125, 1981.
  • P Eades, X Lin and WF Smyth: A fast effective heuristic for the feedback arc set problem. Information Processing Letters 47:319-323, 1993.

maximum_bipartite_matching(self, types='type', weights=None, eps=None)

source code 

Finds a maximum matching in a bipartite graph.

A maximum matching is a set of edges such that each vertex is incident on at most one matched edge and the number (or weight) of such edges in the set is as large as possible.

Parameters:
  • types - vertex types in a list or the name of a vertex attribute holding vertex types. Types should be denoted by zeros and ones (or False and True) for the two sides of the bipartite graph. If omitted, it defaults to type, which is the default vertex type attribute for bipartite graphs.
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
  • eps - a small real number used in equality tests in the weighted bipartite matching algorithm. Two real numbers are considered equal in the algorithm if their difference is smaller than this value. This is required to avoid the accumulation of numerical errors. If you pass None here, igraph will try to determine an appropriate value automatically.
Returns:
an instance of Matching.

write_adjacency(self, f, sep=' ', eol='\n', *args, **kwds)

source code 

Writes the adjacency matrix of the graph to the given file

All the remaining arguments not mentioned here are passed intact to Graph.get_adjacency.

Parameters:
  • f - the name of the file to be written.
  • sep - the string that separates the matrix elements in a row
  • eol - the string that separates the rows of the matrix. Please note that igraph is able to read back the written adjacency matrix if and only if this is a single newline character

Read_Adjacency(klass, f, sep=None, comment_char='#', attribute=None, *args, **kwds)
Class Method

source code 

Constructs a graph based on an adjacency matrix from the given file

Additional positional and keyword arguments not mentioned here are passed intact to Graph.Adjacency.

Parameters:
  • f - the name of the file to be read or a file object
  • sep - the string that separates the matrix elements in a row. None means an arbitrary sequence of whitespace characters.
  • comment_char - lines starting with this string are treated as comments.
  • attribute - an edge attribute name where the edge weights are stored in the case of a weighted adjacency matrix. If None, no weights are stored, values larger than 1 are considered as edge multiplicities.
Returns:
the created graph

write_dimacs(self, f, source=None, target=None, capacity='capacity')

source code 

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. If None, igraph will try to infer it from the source graph attribute.
  • target - the target vertex ID. If None, igraph will try to infer it from the target graph attribute.
  • capacity - the capacities of the edges in a list or the name of an edge attribute that holds the capacities. If there is no such edge attribute, every edge will have a capacity of 1.
Overrides: GraphBase.write_dimacs

write_graphmlz(self, f, compresslevel=9)

source code 

Writes the graph to a zipped GraphML file.

The library uses the gzip compression algorithm, so the resulting file can be unzipped with regular gzip uncompression (like gunzip or zcat from Unix command line) or the Python gzip module.

Uses a temporary file to store intermediate GraphML data, so make sure you have enough free space to store the unzipped GraphML file as well.

Parameters:
  • f - the name of the file to be written.
  • compresslevel - the level of compression. 1 is fastest and produces the least compression, and 9 is slowest and produces the most compression.

Read_DIMACS(f, directed=False)
Class Method

source code 

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

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

Restrictions compared to the official description of the format are as follows:

  • 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 indices of the source and target vertices are attached as graph attributes source and target, the edge capacities are stored in the capacity edge attribute.
Overrides: GraphBase.Read_DIMACS

Read_GraphMLz(f, directed=True, index=0)
Class Method

source code 

Reads a graph from a zipped GraphML file.

Parameters:
  • f - the name of the file
  • index - if the GraphML file contains multiple graphs, specified the one that should be loaded. Graph indices start from zero, so if you want to load the first graph, specify 0 here.
Returns:
the loaded graph object

write_pickle(self, fname=None, version=-1)

source code 

Saves the graph in Python pickled format

Parameters:
  • fname - the name of the file or a stream to save to. If None, saves the graph to a string and returns the string.
  • version - pickle protocol version to be used. If -1, uses the highest protocol available
Returns:
None if the graph was saved successfully to the given file, or a string if fname was None.

write_picklez(self, fname=None, version=-1)

source code 

Saves the graph in Python pickled format, compressed with gzip.

Saving in this format is a bit slower than saving in a Python pickle without compression, but the final file takes up much less space on the hard drive.

Parameters:
  • fname - the name of the file or a stream to save to.
  • version - pickle protocol version to be used. If -1, uses the highest protocol available
Returns:
None if the graph was saved successfully to the given file.

Read_Pickle(klass, fname=None)
Class Method

source code 

Reads a graph from Python pickled format

Parameters:
  • fname - the name of the file, a stream to read from, or a string containing the pickled data. The string is assumed to hold pickled data if it is longer than 40 characters and contains a substring that's peculiar to pickled versions of an igraph Graph object.
Returns:
the created graph object.

Read_Picklez(klass, fname, *args, **kwds)
Class Method

source code 

Reads a graph from compressed Python pickled format, uncompressing it on-the-fly.

Parameters:
  • fname - the name of the file or a stream to read from.
Returns:
the created graph object.

write_svg(self, fname, layout='auto', width=None, height=None, labels='label', colors='color', shapes='shape', vertex_size=10, edge_colors='color', font_size=16, *args, **kwds)

source code 

Saves the graph as an SVG (Scalable Vector Graphics) file

The file will be Inkscape (http://inkscape.org) compatible. In Inkscape, as nodes are rearranged, the edges auto-update.

Parameters:
  • fname - the name of the file
  • layout - the layout of the graph. Can be either an explicitly specified layout (using a list of coordinate pairs) or the name of a layout algorithm (which should refer to a method in the Graph object, but without the layout_ prefix.
  • width - the preferred width in pixels (default: 400)
  • height - the preferred height in pixels (default: 400)
  • labels - the vertex labels. Either it is the name of a vertex attribute to use, or a list explicitly specifying the labels. It can also be None.
  • colors - the vertex colors. Either it is the name of a vertex attribute to use, or a list explicitly specifying the colors. A color can be anything acceptable in an SVG file.
  • shapes - the vertex shapes. Either it is the name of a vertex attribute to use, or a list explicitly specifying the shapes as integers. Shape 0 means hidden (nothing is drawn), shape 1 is a circle, shape 2 is a rectangle and shape 3 is a rectangle that automatically sizes to the inner text.
  • vertex_size - vertex size in pixels
  • edge_colors - the edge colors. Either it is the name of an edge attribute to use, or a list explicitly specifying the colors. A color can be anything acceptable in an SVG file.
  • font_size - font size. If it is a string, it is written into the SVG file as-is (so you can specify anything which is valid as the value of the font-size style). If it is a number, it is interpreted as pixel size and converted to the proper attribute value accordingly.

_identify_format(filename)
Class Method

source code 

Tries to identify the format of the graph stored in the file with the given filename. It identifies most file formats based on the extension of the file (and not on syntactic evaluation). The only exception is the adjacency matrix format and the edge list format: the first few lines of the file are evaluated to decide between the two.

Parameters:
  • filename - the name of the file or a file object whose name attribute is set.
Returns:
the format of the file as a string.

Note: Internal function, should not be called directly.

Read(klass, f, format=None, *args, **kwds)
Class Method

source code 

Unified reading function for graphs.

This method tries to identify the format of the graph given in the first parameter and calls the corresponding reader method.

The remaining arguments are passed to the reader method without any changes.

Parameters:
  • f - the file containing the graph to be loaded
  • format - the format of the file (if known in advance). None means auto-detection. Possible values are: "ncol" (NCOL format), "lgl" (LGL format), "graphdb" (GraphDB format), "graphml", "graphmlz" (GraphML and gzipped GraphML format), "gml" (GML format), "net", "pajek" (Pajek format), "dimacs" (DIMACS format), "edgelist", "edges" or "edge" (edge list), "adjacency" (adjacency matrix), "pickle" (Python pickled format), "picklez" (gzipped Python pickled format)
Raises:
  • IOError - if the file format can't be identified and none was given.

Load(klass, f, format=None, *args, **kwds)
Class Method

source code 

Unified reading function for graphs.

This method tries to identify the format of the graph given in the first parameter and calls the corresponding reader method.

The remaining arguments are passed to the reader method without any changes.

Parameters:
  • f - the file containing the graph to be loaded
  • format - the format of the file (if known in advance). None means auto-detection. Possible values are: "ncol" (NCOL format), "lgl" (LGL format), "graphdb" (GraphDB format), "graphml", "graphmlz" (GraphML and gzipped GraphML format), "gml" (GML format), "net", "pajek" (Pajek format), "dimacs" (DIMACS format), "edgelist", "edges" or "edge" (edge list), "adjacency" (adjacency matrix), "pickle" (Python pickled format), "picklez" (gzipped Python pickled format)
Raises:
  • IOError - if the file format can't be identified and none was given.

write(self, f, format=None, *args, **kwds)

source code 

Unified writing function for graphs.

This method tries to identify the format of the graph given in the first parameter (based on extension) and calls the corresponding writer method.

The remaining arguments are passed to the writer method without any changes.

Parameters:
  • f - the file containing the graph to be saved
  • format - the format of the file (if one wants to override the format determined from the filename extension, or the filename itself is a stream). None means auto-detection. Possible values are:
    • "adjacency": adjacency matrix format
    • "dimacs": DIMACS format
    • "dot", "graphviz": GraphViz DOT format
    • "edgelist", "edges" or "edge": numeric edge list format
    • "gml": GML format
    • "graphml" and "graphmlz": standard and gzipped GraphML format
    • "gw", "leda", "lgr": LEDA native format
    • "lgl": LGL format
    • "ncol": NCOL format
    • "net", "pajek": Pajek format
    • "pickle", "picklez": standard and gzipped Python pickled format
    • "svg": SVG format
Raises:
  • IOError - if the file format can't be identified and none was given.

save(self, f, format=None, *args, **kwds)

source code 

Unified writing function for graphs.

This method tries to identify the format of the graph given in the first parameter (based on extension) and calls the corresponding writer method.

The remaining arguments are passed to the writer method without any changes.

Parameters:
  • f - the file containing the graph to be saved
  • format - the format of the file (if one wants to override the format determined from the filename extension, or the filename itself is a stream). None means auto-detection. Possible values are:
    • "adjacency": adjacency matrix format
    • "dimacs": DIMACS format
    • "dot", "graphviz": GraphViz DOT format
    • "edgelist", "edges" or "edge": numeric edge list format
    • "gml": GML format
    • "graphml" and "graphmlz": standard and gzipped GraphML format
    • "gw", "leda", "lgr": LEDA native format
    • "lgl": LGL format
    • "ncol": NCOL format
    • "net", "pajek": Pajek format
    • "pickle", "picklez": standard and gzipped Python pickled format
    • "svg": SVG format
Raises:
  • IOError - if the file format can't be identified and none was given.

DictList(klass, vertices, edges, directed=False, vertex_name_attr='name', edge_foreign_keys=('source', 'target'), iterative=False)
Class Method

source code 

Constructs a graph from a list-of-dictionaries representation.

This representation assumes that vertices and edges are encoded in two lists, each list containing a Python dict for each vertex and each edge, respectively. A distinguished element of the vertex dicts contain a vertex ID which is used in the edge dicts to refer to source and target vertices. All the remaining elements of the dict are considered vertex and edge attributes. Note that the implementation does not assume that the objects passed to this method are indeed lists of dicts, but they should be iterable and they should yield objects that behave as dicts. So, for instance, a database query result is likely to be fit as long as it's iterable and yields dict-like objects with every iteration.

Parameters:
  • vertices - the data source for the vertices or None if there are no special attributes assigned to vertices and we should simply use the edge list of dicts to infer vertex names.
  • edges - the data source for the edges.
  • directed - whether the constructed graph will be directed
  • vertex_name_attr - the name of the distinguished key in the dicts in the vertex data source that contains the vertex names. Ignored if vertices is None.
  • edge_foreign_keys - the name of the attributes in the dicts in the edge data source that contain the source and target vertex names.
  • iterative - whether to add the edges to the graph one by one, iteratively, or to build a large edge list first and use that to construct the graph. The latter approach is faster but it may not be suitable if your dataset is large. The default is to add the edges in a batch from an edge list.
Returns:
the graph that was constructed

TupleList(klass, edges, directed=False, vertex_name_attr='name', edge_attrs=None, weights=False)
Class Method

source code 

Constructs a graph from a list-of-tuples representation.

This representation assumes that the edges of the graph are encoded in a list of tuples (or lists). Each item in the list must have at least two elements, which specify the source and the target vertices of the edge. The remaining elements (if any) specify the edge attributes of that edge, where the names of the edge attributes originate from the edge_attrs list. The names of the vertices will be stored in the vertex attribute given by vertex_name_attr.

The default parameters of this function are suitable for creating unweighted graphs from lists where each item contains the source vertex and the target vertex. If you have a weighted graph, you can use items where the third item contains the weight of the edge by setting edge_attrs to "weight" or ["weight"]. If you have even more edge attributes, add them to the end of each item in the edges list and also specify the corresponding edge attribute names in edge_attrs as a list.

Parameters:
  • edges - the data source for the edges. This must be a list where each item is a tuple (or list) containing at least two items: the name of the source and the target vertex. Note that names will be assigned to the name vertex attribute (or another vertex attribute if vertex_name_attr is specified), even if all the vertex names in the list are in fact numbers.
  • directed - whether the constructed graph will be directed
  • vertex_name_attr - the name of the vertex attribute that will contain the vertex names.
  • edge_attrs - the names of the edge attributes that are filled with the extra items in the edge list (starting from index 2, since the first two items are the source and target vertices). None means that only the source and target vertices will be extracted from each item. If you pass a string here, it will be wrapped in a list for convenience.
  • weights - alternative way to specify that the graph is weighted. If you set weights to true and edge_attrs is not given, it will be assumed that edge_attrs is ["weight"] and igraph will parse the third element from each item into an edge weight. If you set weights to a string, it will be assumed that edge_attrs contains that string only, and igraph will store the edge weights in that attribute.
Returns:
the graph that was constructed

Formula(Graph, formula= None, attr= "name", simplify= True)
Class Method

source code 

Generates a graph from a graph formula

A graph formula is a simple string representation of a graph. It is very handy for creating small graphs quickly. The string consists of vertex names separated by edge operators. An edge operator is a sequence of dashes (-) that may or may not start with an arrowhead (< at the beginning of the sequence or > at the end of the sequence). The edge operators can be arbitrarily long, i.e., you may use as many dashes to draw them as you like. This makes a total of four different edge operators:

  • ----- makes an undirected edge
  • <---- makes a directed edge pointing from the vertex on the right hand side of the operator to the vertex on the left hand side
  • ----> is the opposite of <----
  • <---> creates a mutual directed edge pair between the two vertices

If you only use the undirected edge operator (-----), the graph will be undirected. Otherwise it will be directed. Vertex names used in the formula will be assigned to the name vertex attribute of the graph.

Some simple examples:

>>> from igraph import Graph
>>> print Graph.Formula()           # empty graph
IGRAPH UN-- 0 0 --
+ attr: name (v)
>>> g = Graph.Formula("A-B")        # undirected graph
>>> g.vs["name"]
['A', 'B']
>>> print g
IGRAPH UN-- 2 1 --
+ attr: name (v)
+ edges (vertex names):
A--B
>>> g.get_edgelist()
[(0, 1)]
>>> g2 = Graph.Formula("A-----------B")
>>> g2.isomorphic(g)
True
>>> g = Graph.Formula("A  --->  B") # directed graph
>>> g.vs["name"]
['A', 'B']
>>> print g
IGRAPH DN-- 2 1 --
+ attr: name (v)
+ edges (vertex names):
A->B

If you have may disconnected componnets, you can separate them with commas. You can also specify isolated vertices:

>>> g = Graph.Formula("A--B, C--D, E--F, G--H, I, J, K")
>>> print ", ".join(g.vs["name"])
A, B, C, D, E, F, G, H, I, J, K
>>> g.clusters().membership
[0, 0, 1, 1, 2, 2, 3, 3, 4, 5, 6]

The colon (:) operator can be used to specify vertex sets. If an edge operator connects two vertex sets, then every vertex from the first vertex set will be connected to every vertex in the second set:

>>> g = Graph.Formula("A:B:C:D --- E:F:G")
>>> g.isomorphic(Graph.Full_Bipartite(4, 3))
True

Note that you have to quote vertex names if they include spaces or special characters:

>>> g = Graph.Formula('"this is" +- "a silly" -+ "graph here"')
>>> g.vs["name"]
['this is', 'a silly', 'graph here']
Parameters:
  • formula - the formula itself
  • attr - name of the vertex attribute where the vertex names will be stored
  • simplify - whether the simplify the constructed graph
Returns:
the constructed graph:

Bipartite(types, edges, directed=False)
Class Method

source code 

Creates a bipartite graph with the given vertex types and edges. This is similar to the default constructor of the graph, the only difference is that it checks whether all the edges go between the two vertex classes and it assigns the type vector to a type attribute afterwards.

Examples:

>>> g = Graph.Bipartite([0, 1, 0, 1], [(0, 1), (2, 3), (0, 3)])
>>> g.is_bipartite()
True
>>> g.vs["type"]
[False, True, False, True]
Parameters:
  • types - the vertex types as a boolean list. Anything that evaluates to False will denote a vertex of the first kind, anything that evaluates to True will denote a vertex of the second kind.
  • edges - the edges as a list of tuples.
  • directed - whether to create a directed graph. Bipartite networks are usually undirected, so the default is False
Returns:
the graph with a binary vertex attribute named "type" that stores the vertex classes.

Full_Bipartite(n1, n2, directed=False, mode=ALL)
Class Method

source code 

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

>>> g = Graph.Full_Bipartite(2, 3)
>>> g.is_bipartite()
True
>>> g.vs["type"]
[False, False, True, True, True]
Parameters:
  • n1 - the number of vertices of the first kind.
  • n2 - the number of vertices of the second kind.
  • directed - whether tp generate a directed graph.
  • mode - if OUT, then all vertices of the first kind are connected to the others; IN specifies the opposite direction, ALL creates mutual edges. Ignored for undirected graphs.
Returns:
the graph with a binary vertex attribute named "type" that stores the vertex classes.

Random_Bipartite(klass, *args, **kwds)
Class Method

source code 

Generates a random bipartite graph with the given number of vertices and edges (if m is given), or with the given number of vertices and the given connection probability (if p is given).

If m is given but p is not, the generated graph will have n1 vertices of type 1, n2 vertices of type 2 and m randomly selected edges between them. If p is given but m is not, the generated graph will have n1 vertices of type 1 and n2 vertices of type 2, and each edge will exist between them with probability p.

Parameters:
  • n1 - the number of vertices of type 1.
  • n2 - the number of vertices of type 2.
  • 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.
  • neimode - if the graph is directed, specifies how the edges will be generated. If it is "all", edges will be generated in both directions (from type 1 to type 2 and vice versa) independently. If it is "out" edges will always point from type 1 to type 2. If it is "in", edges will always point from type 2 to type 1. This argument is ignored for undirected graphs.

GRG(n, radius, torus=False, return_coordinates=False)
Class Method

source code 

Generates a random geometric graph.

The algorithm drops the vertices randomly on the 2D unit square and connects them if they are closer to each other than the given radius. The coordinates of the vertices are stored in the vertex attributes x and y.

Parameters:
  • n - The number of vertices in the graph
  • radius - The given radius
  • torus - This should be True if we want to use a torus instead of a square.

Incidence(matrix, directed=False, mode=ALL, multiple=False)
Class Method

source code 

Creates a bipartite graph from an incidence matrix.

Example:

>>> g = Graph.Incidence([[0, 1, 1], [1, 1, 0]])
Parameters:
  • matrix - the incidence matrix.
  • directed - whether to create a directed graph.
  • mode - defines the direction of edges in the graph. If OUT, then edges go from vertices of the first kind (corresponding to rows of the matrix) to vertices of the second kind (the columns of the matrix). If IN, the opposite direction is used. ALL creates mutual edges. Ignored for undirected graphs.
  • multiple - defines what to do with non-zero entries in the matrix. If False, non-zero entries will create an edge no matter what the value is. If True, non-zero entries are rounded up to the nearest integer and this will be the number of multiple edges created.
Returns:
the graph with a binary vertex attribute named "type" that stores the vertex classes.

bipartite_projection(self, types='type', multiplicity=True, probe1=-1, which='both')

source code 

Projects a bipartite graph into two one-mode graphs. Edge directions are ignored while projecting.

Examples:

>>> g = Graph.Full_Bipartite(10, 5)
>>> g1, g2 = g.bipartite_projection()
>>> g1.isomorphic(Graph.Full(10))
True
>>> g2.isomorphic(Graph.Full(5))
True
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.
  • multiplicity - if True, then igraph keeps the multiplicity of the edges in the projection in an edge attribute called "weight". E.g., if there is an A-C-B and an A-D-B triplet in the bipartite graph and there is no other X (apart from X=B and X=D) for which an A-X-B triplet would exist in the bipartite graph, the multiplicity of the A-B edge in the projection will be 2.
  • probe1 - this argument can be used to specify the order of the projections in the resulting list. If given and non-negative, then it is considered as a vertex ID; the projection containing the vertex will be the first one in the result.
  • which - this argument can be used to specify which of the two projections should be returned if only one of them is needed. Passing 0 here means that only the first projection is returned, while 1 means that only the second projection is returned. (Note that we use 0 and 1 because Python indexing is zero-based). False is equivalent to 0 and True is equivalent to 1. Any other value means that both projections will be returned in a tuple.
Returns:
a tuple containing the two projected one-mode graphs if which is not 1 or 2, or the projected one-mode graph specified by the which argument if its value is 0, 1, False or True.
Overrides: GraphBase.bipartite_projection

bipartite_projection_size(types="type")

source code 

Calculates the number of vertices and edges in the bipartite projections of this graph according to the specified vertex types. This is useful if you have a bipartite graph and you want to estimate the amount of memory you would need to calculate the projections themselves.

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.
Returns:
a 4-tuple containing the number of vertices and edges in the first projection, followed by the number of vertices and edges in the second projection.
Overrides: GraphBase.bipartite_projection_size

get_incidence(self, types="type")

source code 

Returns the incidence matrix of a bipartite graph. The incidence matrix is an n times m matrix, where n and m are the number of vertices in the two vertex classes.

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.
Returns:
the incidence matrix and two lists in a triplet. The first list defines the mapping between row indices of the matrix and the original vertex IDs. The second list is the same for the column indices.
Overrides: GraphBase.get_incidence

__iadd__(self, other)

source code 

In-place addition (disjoint union).

See Also: __add__

__add__(self, other)
(Addition operator)

source code 

Copies the graph and extends the copy depending on the type of the other object given.

Parameters:
  • other - if it is an integer, the copy is extended by the given number of vertices. If it is a string, the copy is extended by a single vertex whose name attribute will be equal to the given string. If it is a tuple with two elements, the copy is extended by a single edge. If it is a list of tuples, the copy is extended by multiple edges. If it is a Graph, a disjoint union is performed.

__isub__(self, other)

source code 

In-place subtraction (difference).

See Also: __sub__

__sub__(self, other)
(Subtraction operator)

source code 

Removes the given object(s) from the graph

Parameters:
  • other - if it is an integer, removes the vertex with the given ID from the graph (note that the remaining vertices will get re-indexed!). If it is a tuple, removes the given edge. If it is a graph, takes the difference of the two graphs. Accepts lists of integers or lists of tuples as well, but they can't be mixed! Also accepts Edge and EdgeSeq objects.

__mul__(self, other)

source code 

Copies exact replicas of the original graph an arbitrary number of times.

Parameters:
  • other - if it is an integer, multiplies the graph by creating the given number of identical copies and taking the disjoint union of them.

__coerce__(self, other)

source code 

Coercion rules.

This method is needed to allow the graph to react to additions with lists, tuples, integers, strings, vertices, edges and so on.

_reconstruct(cls, attrs, *args, **kwds)
Class Method

source code 

Reconstructs a Graph object from Python's pickled format.

This method is for internal use only, it should not be called directly.

__reduce__(self)

source code 

Support for pickling.

Overrides: object.__reduce__

__plot__(self, context, bbox, palette, *args, **kwds)

source code 

Plots the graph to the given Cairo context in the given bounding box

The visual style of vertices and edges can be modified at three places in the following order of precedence (lower indices override higher indices):

  1. Keyword arguments of this function (or of plot() which is passed intact to Graph.__plot__().
  2. Vertex or edge attributes, specified later in the list of keyword arguments.
  3. igraph-wide plotting defaults (see igraph.config.Configuration)
  4. Built-in defaults.

E.g., if the vertex_size keyword attribute is not present, but there exists a vertex attribute named size, the sizes of the vertices will be specified by that attribute.

Besides the usual self-explanatory plotting parameters (context, bbox, palette), it accepts the following keyword arguments:

  • autocurve: whether to use curves instead of straight lines for multiple edges on the graph plot. This argument may be True or False; when omitted, True is assumed for graphs with less than 10.000 edges and False otherwise.
  • drawer_factory: a subclass of AbstractCairoGraphDrawer which will be used to draw the graph. You may also provide a function here which takes two arguments: the Cairo context to draw on and a bounding box (an instance of BoundingBox). If this keyword argument is missing, igraph will use the default graph drawer which should be suitable for most purposes. It is safe to omit this keyword argument unless you need to use a specific graph drawer.
  • keep_aspect_ratio: whether to keep the aspect ratio of the layout that igraph calculates to place the nodes. True means that the layout will be scaled proportionally to fit into the bounding box where the graph is to be drawn but the aspect ratio will be kept the same (potentially leaving empty space next to, below or above the graph). False means that the layout will be scaled independently along the X and Y axis in order to fill the entire bounding box. The default is False.
  • layout: the layout to be used. If not an instance of Layout, it will be passed to Graph.layout to calculate the layout. Note that if you want a deterministic layout that does not change with every plot, you must either use a deterministic layout function (like Graph.layout_circle) or calculate the layout in advance and pass a Layout object here.
  • margin: the top, right, bottom, left margins as a 4-tuple. If it has less than 4 elements or is a single float, the elements will be re-used until the length is at least 4.
  • mark_groups: whether to highlight some of the vertex groups by colored polygons. This argument can be one of the following:
    • False: no groups will be highlighted
    • A dict mapping tuples of vertex indices to color names. The given vertex groups will be highlighted by the given colors.
    • A list containing pairs or an iterable yielding pairs, where the first element of each pair is a list of vertex indices and the second element is a color.

    In place of lists of vertex indices, you may also use VertexSeq instances.

    In place of color names, you may also use color indices into the current palette. None as a color name will mean that the corresponding group is ignored.

  • vertex_size: size of the vertices. The corresponding vertex attribute is called size. The default is 10. Vertex sizes are measured in the unit of the Cairo context on which igraph is drawing.
  • vertex_color: color of the vertices. The corresponding vertex attribute is color, the default is red. Colors can be specified either by common X11 color names (see the source code of igraph.drawing.colors for a list of known colors), by 3-tuples of floats (ranging between 0 and 255 for the R, G and B components), by CSS-style string specifications (#rrggbb) or by integer color indices of the specified palette.
  • vertex_frame_color: color of the frame (i.e. stroke) of the vertices. The corresponding vertex attribute is frame_color, the default is black. See vertex_color for the possible ways of specifying a color.
  • vertex_frame_width: the width of the frame (i.e. stroke) of the vertices. The corresponding vertex attribute is frame_width. The default is 1. Vertex frame widths are measured in the unit of the Cairo context on which igraph is drawing.
  • vertex_shape: shape of the vertices. Alternatively it can be specified by the shape vertex attribute. Possibilities are: square, {circle}, {triangle}, {triangle-down} or hidden. See the source code of igraph.drawing for a list of alternative shape names that are also accepted and mapped to these.
  • vertex_label: labels drawn next to the vertices. The corresponding vertex attribute is label.
  • vertex_label_dist: distance of the midpoint of the vertex label from the center of the corresponding vertex. The corresponding vertex attribute is label_dist.
  • vertex_label_color: color of the label. Corresponding vertex attribute: label_color. See vertex_color for color specification syntax.
  • vertex_label_size: font size of the label, specified in the unit of the Cairo context on which we are drawing. Corresponding vertex attribute: label_size.
  • vertex_label_angle: the direction of the line connecting the midpoint of the vertex with the midpoint of the label. This can be used to position the labels relative to the vertices themselves in conjunction with vertex_label_dist. Corresponding vertex attribute: label_angle. The default is -math.pi/2.
  • vertex_order: drawing order of the vertices. This must be a list or tuple containing vertex indices; vertices are then drawn according to this order.
  • vertex_order_by: an alternative way to specify the drawing order of the vertices; this attribute is interpreted as the name of a vertex attribute, and vertices are drawn such that those with a smaller attribute value are drawn first. You may also reverse the order by passing a tuple here; the first element of the tuple should be the name of the attribute, the second element specifies whether the order is reversed (True, False, "asc" and "desc" are accepted values).
  • edge_color: color of the edges. The corresponding edge attribute is color, the default is red. See vertex_color for color specification syntax.
  • edge_curved: whether the edges should be curved. Positive numbers correspond to edges curved in a counter-clockwise direction, negative numbers correspond to edges curved in a clockwise direction. Zero represents straight edges. True is interpreted as 0.5, False is interpreted as 0. The default is 0 which makes all the edges straight.
  • edge_width: width of the edges in the default unit of the Cairo context on which we are drawing. The corresponding edge attribute is width, the default is 1.
  • edge_arrow_size: arrow size of the edges. The corresponding edge attribute is arrow_size, the default is 1.
  • edge_arrow_width: width of the arrowhead on the edge. The corresponding edge attribute is arrow_width, the default is 1.
  • edge_order: drawing order of the edges. This must be a list or tuple containing edge indices; edges are then drawn according to this order.
  • edge_order_by: an alternative way to specify the drawing order of the edges; this attribute is interpreted as the name of an edge attribute, and edges are drawn such that those with a smaller attribute value are drawn first. You may also reverse the order by passing a tuple here; the first element of the tuple should be the name of the attribute, the second element specifies whether the order is reversed (True, False, "asc" and "desc" are accepted values).

__str__(self)
(Informal representation operator)

source code 

Returns a string representation of the graph.

Behind the scenes, this method constructs a GraphSummary instance and invokes its __str__ method with a verbosity of 1 and attribute printing turned off.

See the documentation of GraphSummary for more details about the output.

Overrides: object.__str__

summary(self, verbosity=0, width=None, *args, **kwds)

source code 

Returns the summary of the graph.

The output of this method is similar to the output of the __str__ method. If verbosity is zero, only the header line is returned (see __str__ for more details), otherwise the header line and the edge list is printed.

Behind the scenes, this method constructs a GraphSummary object and invokes its __str__ method.

Parameters:
  • verbosity - if zero, only the header line is returned (see __str__ for more details), otherwise the header line and the full edge list is printed.
  • width - the number of characters to use in one line. If None, no limit will be enforced on the line lengths.
Returns:
the summary of the graph.

layout_fruchterman_reingold_3d(*args, **kwds)

source code 

Alias for layout_fruchterman_reingold() with dim=3.

See Also: Graph.layout_fruchterman_reingold()

layout_kamada_kawai_3d(*args, **kwds)

source code 

Alias for layout_kamada_kawai() with dim=3.

See Also: Graph.layout_kamada_kawai()

layout_random_3d(*args, **kwds)

source code 

Alias for layout_random() with dim=3.

See Also: Graph.layout_random()

layout_grid_3d(*args, **kwds)

source code 

Alias for layout_grid() with dim=3.

See Also: Graph.layout_grid()

layout_sphere(*args, **kwds)

source code 

Alias for layout_circle() with dim=3.

See Also: Graph.layout_circle()

layout_bipartite(types="type", hgap=1, vgap=1, maxiter=100)

source code 

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.
Overrides: GraphBase.layout_bipartite

layout_circle(dim=2)

source code 

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.
Returns:
the calculated layout.
Overrides: GraphBase.layout_circle

layout_drl(weights=None, fixed=None, seed=None, options=None, dim=2)

source code 

Places the vertices on a 2D plane or in the 3D space ccording to the DrL layout algorithm.

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

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

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

  • 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.
Overrides: GraphBase.layout_drl

layout_fruchterman_reingold(weights=None, maxiter=500, maxdelta=None, area=None, coolexp=1.5, repulserad=None, seed=None, minx=None, maxx=None, miny=None, maxy=None, minz=None, maxz=None, dim=2)

source code 

Places the vertices on a 2D plane or in the 3D space according to the Fruchterman-Reingold algorithm.

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

Parameters:
  • weights - edge weights to be used. Can be a sequence or iterable or even an edge attribute name.
  • maxiter - the number of iterations to perform. The default is 500.
  • maxdelta - the maximum distance to move a vertex in an iteration. The default is the number of vertices.
  • area - the area of the square on which the vertices will be placed. The default is the square of the number of vertices.
  • coolexp - the cooling exponent of the simulated annealing. The default is 1.5.
  • repulserad - determines the radius at which vertex-vertex repulsion cancels out attraction of adjacent vertices. The default is the number of vertices^3.
  • 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).
  • 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.
  • 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.
Overrides: GraphBase.layout_fruchterman_reingold

layout_graphopt(niter=500, node_charge=0.001, node_mass=30, spring_length=0, spring_constant=1, max_sa_movement=5, seed=None)

source code 

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

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

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

Parameters:
  • niter - the number of iterations to perform. Should be a couple of hundred in general.
  • node_charge - the charge of the vertices, used to calculate electric repulsion.
  • node_mass - the mass of the vertices, used for the spring forces
  • spring_length - the length of the springs
  • spring_constant - the spring constant
  • max_sa_movement - the maximum amount of movement allowed in a single step along a single axis.
  • 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.
Overrides: GraphBase.layout_graphopt

layout_grid(width=0, height=0, dim=2)

source code 

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.
Overrides: GraphBase.layout_grid

layout_grid_fruchterman_reingold(maxiter=500, maxdelta=None, area=None, coolexp=0.99, repulserad=maxiter*maxdelta, cellsize=None, seed=None)

source code 

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

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

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

layout_kamada_kawai(maxiter=1000, sigma=None, initemp=10, coolexp=0.99, kkconst=None, seed=None, minx=None, maxx=None, miny=None, maxy=None, minz=None, maxz=None, dim=2)

source code 

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

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

Parameters:
  • maxiter - the number of iterations to perform.
  • sigma - the standard base deviation of the position change proposals. None means the number of vertices / 4
  • initemp - initial temperature of the simulated annealing.
  • coolexp - cooling exponent of the simulated annealing.
  • kkconst - the Kamada-Kawai vertex attraction constant. None means the square of the number of vertices.
  • 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).
  • 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.
  • 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.
Overrides: GraphBase.layout_kamada_kawai

layout_lgl(maxiter=150, maxdelta=-1, area=-1, coolexp=1.5, repulserad=-1, cellsize=-1, root=None)

source code 

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

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

layout_mds(dist=None, dim=2, arpack_options=None)

source code 

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.

Parameters:
  • dist - the distance matrix. It must be symmetric and the symmetry is not checked -- results are unspecified when a non-symmetric 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_options - an ARPACKOptions object used to fine-tune the ARPACK eigenvector calculation. If omitted, the module-level variable called arpack_options is used.
Returns:
the calculated layout.
Overrides: GraphBase.layout_mds

Reference: Cox & Cox: Multidimensional Scaling (1994), Chapman and Hall, London.

layout_random(dim=2)

source code 

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.
Overrides: GraphBase.layout_random

layout_reingold_tilford(mode="out", root=None, rootlevel=None)

source code 

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

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

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 non-empty 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 based on topological sorting, performed with the opposite of the mode argument.
  • 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.
Overrides: GraphBase.layout_reingold_tilford

See Also: layout_reingold_tilford_circular

Reference: EM Reingold, JS Tilford: Tidier Drawings of Trees. IEEE Transactions on Software Engineering 7:22, 223-228, 1981.

layout_reingold_tilford_circular(mode="out", root=None, rootlevel=None)

source code 

Circular Reingold-Tilford layout for trees.

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

See layout_reingold_tilford for the explanation of the parameters.

Returns:
the calculated layout.
Overrides: GraphBase.layout_reingold_tilford_circular

See Also: layout_reingold_tilford

Reference: EM Reingold, JS Tilford: Tidier Drawings of Trees. IEEE Transactions on Software Engineering 7:22, 223-228, 1981.

layout_star(center=0, order=None)

source code 

Calculates a star-like 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.
Overrides: GraphBase.layout_star

Class Variable Details [hide private]

_format_mapping

Value:
{'adj': ('Read_Adjacency', 'write_adjacency'),
 'adjacency': ('Read_Adjacency', 'write_adjacency'),
 'dimacs': ('Read_DIMACS', 'write_dimacs'),
 'dot': (None, 'write_dot'),
 'edge': ('Read_Edgelist', 'write_edgelist'),
 'edgelist': ('Read_Edgelist', 'write_edgelist'),
 'edges': ('Read_Edgelist', 'write_edgelist'),
 'gml': ('Read_GML', 'write_gml'),
...

_layout_mapping

Value:
{'auto': 'layout_auto',
 'automatic': 'layout_auto',
 'bipartite': 'layout_bipartite',
 'circle': 'layout_circle',
 'circular': 'layout_circle',
 'drl': 'layout_drl',
 'fr': 'layout_fruchterman_reingold',
 'fruchterman_reingold': 'layout_fruchterman_reingold',
...

Property Details [hide private]

vs

The vertex sequence of the graph

Get Method:
unreachable.vs(self) - The vertex sequence of the graph

es

The edge sequence of the graph

Get Method:
unreachable.es(self) - The edge sequence of the graph

   Home       Trees       Indices       Help