dynamo.vf.vfGraph¶

class dynamo.vf.vfGraph(*args, **kwds)[source]¶: A class for manipulating the graph creating from the transition matrix, built from the (reconstructed) vector field. This is a derived class from igraph’s Graph.

Attributes table¶

`es`	The edge sequence of the graph
`vs`	The vertex sequence of the graph

Methods table¶

`Adjacency`(matrix[, mode, loops])	Generates a graph from its adjacency matrix.
`Asymmetric_Preference`(type_dist_matrix, ...)	Generates a graph based on asymmetric vertex types and connection probabilities.
`Atlas`()	Generates a graph from the Graph Atlas.
`Barabasi`(m[, outpref, directed, power, ...])	Generates a graph based on the Barabási-Albert model.
`Biadjacency`(matrix[, directed, mode, ...])	Creates a bipartite graph from a bipartite adjacency matrix.
`Bipartite`(types, edges[, directed])	Creates a bipartite graph with the given vertex types and edges.
`Chung_Lu`([in_, loops, variant])	Generates a Chung-Lu random graph.
`DataFrame`([directed, vertices, use_vids])	Generates a graph from one or two dataframes.
`De_Bruijn`(n)	Generates a de Bruijn graph with parameters (m, n)
`Degree_Sequence`([in_, method])	Generates a graph with a given degree sequence.
`DictDict`([directed, vertex_name_attr])	Constructs a graph from a dict-of-dicts representation.
`DictList`(edges[, directed, ...])	Constructs a graph from a list-of-dictionaries representation.
`Erdos_Renyi`(p, m[, directed, loops, ...])	Generates a graph based on the Erdős-Rényi model.
`Establishment`(k, type_dist, pref_matrix[, ...])	Generates a graph based on a simple growing model with vertex types.
`Famous`()	Generates a famous graph based on its name.
`Forest_Fire`(fw_prob[, bw_factor, ambs, directed])	Generates a graph based on the forest fire model
`Formula`([formula, attr, simplify])	Generates a graph from a graph formula
`Full`([directed, loops])	Generates a full graph (directed or undirected, with or without loops).
`Full_Bipartite`(n1, n2[, directed, mode])	Generates a full bipartite graph (directed or undirected, with or without loops).
`Full_Citation`([directed])	Generates a full citation graph
`GRG`(n, radius[, torus])	Generates a random geometric graph.
`Growing_Random`(m[, directed, citation])	Generates a growing random graph.
`Hexagonal_Lattice`([directed, mutual])	Generates a regular hexagonal lattice.
`Hypercube`([directed])	Generates an n-dimensional hypercube graph.
`Incidence`(args, *kwds)	Deprecated alias to L{Graph.Biadjacency()}.
`Isoclass`(cls[, directed])	Generates a graph with a given isomorphism class.
`K_Regular`(k[, directed, multiple])	Generates a k-regular random graph
`Kautz`(n)	Generates a Kautz graph with parameters (m, n)
`LCF`(shifts, repeats)	Generates a graph from LCF notation.
`Lattice`([nei, directed, mutual, circular])	Generates a regular square lattice.
`ListDict`([directed, vertex_name_attr])	Constructs a graph from a dict-of-lists representation.
`Load`(f[, format])	Unified reading function for graphs.
`Nearest_Neighbor_Graph`([k, r, metric, directed])	Constructs a k nearest neighbor graph of a give point set.
`Preference`(type_dist, pref_matrix[, ...])	Generates a graph based on vertex types and connection probabilities.
`Prufer`()	Generates a tree from its Prüfer sequence.
`Random_Bipartite`(n1, n2[, p, m, directed, ...])	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).
`Read`(f[, format])	Unified reading function for graphs.
`Read_Adjacency`(f[, sep, comment_char, attribute])	Constructs a graph based on an adjacency matrix from the given file.
`Read_DIMACS`(f[, directed])	Reads a graph from a file conforming to the DIMACS minimum-cost flow file format.
`Read_DL`([directed])	Reads an UCINET DL file and creates a graph based on it.
`Read_Edgelist`([directed])	Reads an edge list from a file and creates a graph based on it.
`Read_GML`()	Reads a GML file and creates a graph based on it.
`Read_GraphDB`([directed])	Reads a GraphDB format file and creates a graph based on it.
`Read_GraphML`([index])	Reads a GraphML format file and creates a graph based on it.
`Read_GraphMLz`(f[, index])	Reads a graph from a zipped GraphML file.
`Read_Lgl`([names, weights, directed])	Reads an .lgl file used by LGL.
`Read_Ncol`([names, weights, directed])	Reads an .ncol file used by LGL.
`Read_Pajek`()	Reads a file in the Pajek format and creates a graph based on it.
`Read_Pickle`([fname])	Reads a graph from Python pickled format
`Read_Picklez`(fname)	Reads a graph from compressed Python pickled format, uncompressing it on-the-fly.
`Realize_Bipartite_Degree_Sequence`(degrees2)	Generates a bipartite graph from the degree sequences of its partitions.
`Realize_Degree_Sequence`([in_, ...])	Generates a graph from a degree sequence.
`Recent_Degree`(m, window[, outpref, ...])	Generates a graph based on a stochastic model where the probability of an edge gaining a new node is proportional to the edges gained in a given time window.
`Ring`([directed, mutual, circular])	Generates a ring graph.
`SBM`(block_sizes[, directed, allowed_edge_types])	Generates a graph based on a stochastic block model.
`Star`([mode, center])	Generates a star graph.
`Static_Fitness`(fitness_out[, fitness_in, ...])	Generates a non-growing graph with edge probabilities proportional to node fitnesses.
`Static_Power_Law`(m, exponent_out[, ...])	Generates a non-growing graph with prescribed power-law degree distributions.
`Tree`(children[, mode])	Generates a tree in which almost all vertices have the same number of children.
`Tree_Game`([directed, method])	Generates a random tree by sampling uniformly from the set of labelled trees with a given number of nodes.
`Triangular_Lattice`([directed, mutual])	Generates a regular triangular lattice.
`TupleList`([directed, vertex_name_attr, ...])	Constructs a graph from a list-of-tuples representation.
`Watts_Strogatz`(size, nei, p[, ...])	This function generates networks with the small-world property based on a variant of the Watts-Strogatz model.
`Weighted_Adjacency`(matrix[, mode, attr, loops])	Generates a graph from its weighted adjacency matrix.
`add_edge`(source, target, **kwds)	Adds a single edge to the graph.
`add_edges`(es[, attributes])	Adds some edges to the graph.
`add_vertex`([name])	Adds a single vertex to the graph.
`add_vertices`(n[, attributes])	Adds some vertices to the graph.
`adhesion`([target, checks])	Calculates the edge connectivity of the graph or between some vertices.
`all_minimal_st_separators`()	Returns a list containing all the minimal s-t separators of a graph.
`all_st_cuts`(source, target)	Returns all the cuts between the source and target vertices in a directed graph.
`all_st_mincuts`(source, target[, capacity])	Returns all the mincuts between the source and target vertices in a directed graph.
`alpha`()	Returns the independence number of the graph.
`are_adjacent`(v2)	Decides whether two given vertices are directly connected.
`are_connected`(args, *kwds)	Deprecated alias to L{Graph.are_adjacent()}.
`articulation_points`()	Returns the list of articulation points in the graph.
`as_directed`(args, *kwds)	Returns a directed copy of this graph.
`as_undirected`(args, *kwds)	Returns an undirected copy of this graph.
`assortativity`([types2, directed, ...])	Returns the assortativity of the graph based on numeric properties of the vertices.
`assortativity_degree`()	Returns the assortativity of a graph based on vertex degrees.
`assortativity_nominal`([directed, ...])	Returns the assortativity of the graph based on vertex categories.
`attributes`()	@return: the attribute name list of the graph
`authority_score`([scale, arpack_options, ...])	Calculates Kleinberg's authority score for the vertices of the graph
`automorphism_group`([color])	Calculates the generators of the automorphism group of a graph using the BLISS isomorphism algorithm.
`average_path_length`([unconn, weights])	Calculates the average path length in a graph.
`betweenness`([directed, cutoff, weights, ...])	Calculates or estimates the betweenness of vertices in a graph.
`bfs`([mode])	Conducts a breadth first search (BFS) on the graph.
`bfsiter`([mode, advanced])	Constructs a breadth first search (BFS) iterator of the graph.
`bibcoupling`()	Calculates bibliographic coupling scores for given vertices in a graph.
`biconnected_components`([...])	Calculates the biconnected components of the graph.
`bipartite_projection`([types, multiplicity, ...])	Projects a bipartite graph into two one-mode graphs.
`bipartite_projection_size`([types])	Calculates the number of vertices and edges in the bipartite projections of this graph according to the specified vertex types.
`blocks`([return_articulation_points])	Calculates the biconnected components of the graph.
`bridges`()	Returns the list of bridges in the graph.
`build_graph`(adj_mat)	build sparse diffusion graph.
`canonical_permutation`([color])	Calculates the canonical permutation of a graph using the BLISS isomorphism algorithm.
`chordal_completion`([alpham1])	Returns the list of edges needed to be added to the graph to make it chordal.
`clear`()	Clears the graph, deleting all vertices, edges, and attributes.
`clique_number`()	Returns the clique number of the graph.
`cliques`([max, max_results])	Returns some or all cliques of the graph as a list of tuples.
`closeness`([mode, cutoff, weights, normalized])	Calculates the closeness centralities of given vertices in a graph.
`clusters`([mode])	Deprecated alias to L{Graph.connected_components()}.
`cocitation`()	Calculates cocitation scores for given vertices in a graph.
`cohesion`([target, checks, neighbors])	Calculates the vertex connectivity of the graph or between some vertices.
`cohesive_blocks`()	Calculates the cohesive block structure of the graph.
`community_edge_betweenness`([clusters, ...])	Community structure based on the betweenness of the edges in the network.
`community_fastgreedy`([weights])	Community structure based on the greedy optimization of modularity.
`community_fluid_communities`(no_of_communities)	Community detection based on fluids interacting on the graph.
`community_infomap`([edge_weights, ...])	Finds the community structure of the network according to the Infomap method of Martin Rosvall and Carl T.
`community_label_propagation`([weights, ...])	Finds the community structure of the graph according to the label propagation method of Raghavan et al.
`community_leading_eigenvector`([clusters, ...])	Newman's leading eigenvector method for detecting community structure.
`community_leiden`([objective_function, ...])	Finds the community structure of the graph using the Leiden algorithm of Traag, van Eck & Waltman.
`community_multilevel`([weights, ...])	Community structure based on the multilevel algorithm of Blondel et al.
`community_optimal_modularity`(args, *kwds)	Calculates the optimal modularity score of the graph and the corresponding community structure.
`community_spinglass`(args, *kwds)	Finds the community structure of the graph according to the spinglass community detection method of Reichardt & Bornholdt.
`community_voronoi`([lengths, weights, mode, ...])	Finds communities using Voronoi partitioning.
`community_walktrap`([weights, steps])	Community detection algorithm of Latapy & Pons, based on random walks.
`complementer`()	Returns the complementer of the graph
`components`([mode])	Calculates the (strong or weak) connected components for a given graph.
`compose`()	Returns the composition of two graphs.
`connected_components`([mode])	Calculates the (strong or weak) connected components for a given graph.
`constraint`([weights])	Calculates Burt's constraint scores for given vertices in a graph.
`contract_vertices`([combine_attrs])	Contracts some vertices in the graph, i.e. replaces groups of vertices with single vertices.
`convergence_degree`()	Undocumented (yet).
`convergence_field_size`()	Undocumented (yet).
`convert_to_class`(obj)
`copy`()	Creates a copy of the graph.
`coreness`()	Finds the coreness (shell index) of the vertices of the network.
`count_automorphisms`([color])	Calculates the number of automorphisms of a graph using the BLISS isomorphism algorithm.
`count_automorphisms_vf2`([color, edge_color, ...])	Returns the number of automorphisms of the graph.
`count_isomorphisms_vf2`([color1, color2, ...])	Determines the number of isomorphisms between the graph and another one
`count_multiple`()	Counts the multiplicities of the given edges.
`count_subisomorphisms_vf2`([color1, color2, ...])	Determines the number of subisomorphisms between the graph and another one
`cut_vertices`()	Returns the list of articulation points in the graph.
`decompose`([maxcompno, minelements])	Decomposes the graph into subgraphs.
`degree`([mode, loops])	Returns some vertex degrees from the graph.
`degree_distribution`([bin_width])	Calculates the degree distribution of the graph.
`delete_edges`(args, *kwds)	Deletes some edges from the graph.
`delete_vertices`()	Deletes vertices and all its edges from the graph.
`density`([weights])	Calculates the density of the graph.
`dfs`(vid[, mode])	Conducts a depth first search (DFS) on the graph.
`dfsiter`([mode, advanced])	Constructs a depth first search (DFS) iterator of the graph.
`diameter`([unconn, weights])	Calculates the diameter of the graph.
`difference`()	Subtracts the given graph from the original
`disjoint_union`(other)	Creates the disjoint union of two (or more) graphs.
`distances`([target, weights, mode, algorithm])	Calculates shortest path lengths for given vertices in a graph.
`diversity`([weights])	Calculates the structural diversity index of the vertices.
`dominator`([mode])	Returns the dominator tree from the given root node
`dyad_census`(args, *kwds)	Calculates the dyad census of the graph.
`eccentricity`([mode, weights])	Calculates the eccentricities of given vertices in a graph.
`ecount`()	Counts the number of edges.
`edge_attributes`()	@return: the attribute name list of the edges of the graph
`edge_betweenness`([cutoff, weights, sources, ...])	Calculates or estimates the edge betweennesses in a graph.
`edge_connectivity`([target, checks])	Calculates the edge connectivity of the graph or between some vertices.
`edge_disjoint_paths`([target, checks])	Calculates the edge connectivity of the graph or between some vertices.
`eigen_adjacency`([which, arpack_options])
`eigenvector_centrality`([scale, weights, ...])	Calculates the eigenvector centralities of the vertices in a graph.
`evcent`([scale, weights, return_eigenvalue, ...])	Calculates the eigenvector centralities of the vertices in a graph.
`farthest_points`([unconn, weights])	Returns two vertex IDs whose distance equals the actual diameter of the graph.
`feedback_arc_set`([method])	Calculates an approximately or exactly minimal feedback arc set.
`feedback_vertex_set`([method])	Calculates a minimum feedback vertex set.
`from_graph_tool`(g)	Converts the graph from graph-tool
`from_networkx`([vertex_attr_hashable])	Converts the graph from networkx
`fundamental_cycles`([cutoff, weights])	Finds a single fundamental cycle basis of the graph
`get_adjacency`([type, attribute, default, eids])	Returns the adjacency matrix of a graph.
`get_adjacency_sparse`([attribute])	Returns the adjacency matrix of a graph as a SciPy CSR matrix.
`get_adjlist`([mode, loops, multiple])	Returns the adjacency list representation of the graph.
`get_all_shortest_paths`([to, weights, mode])	Calculates all of the shortest paths from/to a given node in a graph.
`get_all_simple_paths`(v[, to, minlen, ...])	Calculates all the simple paths from a given node to some other nodes (or all of them) in a graph.
`get_automorphisms_vf2`([color, edge_color, ...])	Returns all the automorphisms of the graph
`get_biadjacency`([types])	Returns the bipartite adjacency matrix of a bipartite graph.
`get_diameter`([unconn, weights])	Returns a path with the actual diameter of the graph.
`get_edge_dataframe`()	Export edges with attributes to pandas.DataFrame
`get_edgelist`()	Returns the edge list of a graph.
`get_eid`(v2[, directed, error])	Returns the edge ID of an arbitrary edge between vertices v1 and v2
`get_eids`([directed, error])	Returns the edge IDs of some edges between some vertices.
`get_incidence`(args, *kwds)	Deprecated alias to L{Graph.get_biadjacency()}.
`get_inclist`([mode, loops])	Returns the incidence list representation of the graph.
`get_isomorphisms_vf2`([color1, color2, ...])	Returns all isomorphisms between the graph and another one
`get_k_shortest_paths`(to[, k, weights, mode, ...])	Calculates the k shortest paths from/to a given node in a graph.
`get_shortest_path`(to[, weights, mode, ...])	Calculates the shortest path from a source vertex to a target vertex in a graph.
`get_shortest_path_astar`(to, heuristics[, ...])	Calculates the shortest path from a source vertex to a target vertex in a graph using the A-Star algorithm and a heuristic function.
`get_shortest_paths`([to, weights, mode, ...])	Calculates the shortest paths from/to a given node in a graph.
`get_subisomorphisms_lad`([domains, induced, ...])	Returns all subisomorphisms between the graph and another one using the LAD algorithm.
`get_subisomorphisms_vf2`([color1, color2, ...])	Returns all subisomorphisms between the graph and another one
`get_vertex_dataframe`()	Export vertices with attributes to pandas.DataFrame
`girth`()	Returns the girth of the graph.
`gomory_hu_tree`([capacity, flow])	Calculates the Gomory-Hu tree of an undirected graph with optional edge capacities.
`harmonic_centrality`([mode, cutoff, weights, ...])	Calculates the harmonic centralities of given vertices in a graph.
`has_multiple`()	Checks whether the graph has multiple edges.
`hub_score`([scale, arpack_options, ...])	Calculates Kleinberg's hub score for the vertices of the graph
`incident`([mode])	Returns the edges a given vertex is incident on.
`indegree`(args, *kwds)	Returns the in-degrees in a list.
`independence_number`()	Returns the independence number of the graph.
`independent_vertex_sets`([max, max_results])	Returns some or all independent vertex sets of the graph as a list of tuples.
`induced_subgraph`([implementation])	Returns a subgraph spanned by the given vertices.
`intersection`(other[, byname])	Creates the intersection of two (or more) graphs.
`is_acyclic`()	Returns whether the graph is acyclic (i.e. contains no cycles).
`is_biconnected`()	Decides whether the graph is biconnected.
`is_bipartite`()	Decides whether the graph is bipartite or not.
`is_chordal`([alpham1])	Returns whether the graph is chordal or not.
`is_clique`([directed])	Decides whether a set of vertices is a clique, i.e. a fully connected subgraph.
`is_complete`()	Checks whether the graph is complete, i.e. whether there is at least one connection between all distinct pairs of vertices.
`is_connected`()	Decides whether the graph is connected.
`is_dag`()	Checks whether the graph is a DAG (directed acyclic graph).
`is_directed`()	Checks whether the graph is directed.
`is_independent_vertex_set`()	Decides whether no two vertices within a set are adjacent.
`is_loop`()	Checks whether a specific set of edges contain loop edges
`is_minimal_separator`()	Decides whether the given vertex set is a minimal separator.
`is_multiple`()	Checks whether an edge is a multiple edge.
`is_mutual`([loops])	Checks whether an edge has an opposite pair.
`is_named`()	Returns whether the graph is named.
`is_separator`()	Decides whether the removal of the given vertices disconnects the graph.
`is_simple`()	Checks whether the graph is simple (no loop or multiple edges).
`is_tree`()	Checks whether the graph is a (directed or undirected) tree graph.
`is_weighted`()	Returns whether the graph is weighted.
`isoclass`()	Returns the isomorphism class of the graph or its subgraph.
`isomorphic`()	Checks whether the graph is isomorphic to another graph.
`isomorphic_bliss`([return_mapping_12, ...])	Checks whether the graph is isomorphic to another graph, using the BLISS isomorphism algorithm.
`isomorphic_vf2`([color1, color2, ...])	Checks whether the graph is isomorphic to another graph, using the VF2 isomorphism algorithm.
`k_core`(*args)	Returns some k-cores of the graph.
`knn`([weights])	Calculates the average degree of the neighbors for each vertex, and the same quantity as the function of vertex degree.
`laplacian`([normalized, mode])	Returns the Laplacian matrix of a graph.
`largest_cliques`()	Returns the largest cliques of the graph as a list of tuples.
`largest_independent_vertex_sets`()	Returns the largest independent vertex sets of the graph as a list of tuples.
`layout`([layout])	Returns the layout of the graph according to a layout algorithm.
`layout_auto`(args, *kwds)	Chooses and runs a suitable layout function based on simple topological properties of the graph.
`layout_bipartite`(**kwds)	Place the vertices of a bipartite graph in two layers.
`layout_circle`(**kwds)	Places the vertices of the graph uniformly on a circle or a sphere.
`layout_davidson_harel`(**kwds)	Places the vertices on a 2D plane according to the Davidson-Harel layout algorithm.
`layout_drl`(**kwds)	Places the vertices on a 2D plane or in the 3D space ccording to the DrL layout algorithm.
`layout_fruchterman_reingold`(**kwds)	Places the vertices on a 2D plane according to the Fruchterman-Reingold algorithm.
`layout_fruchterman_reingold_3d`(**kwds)	Alias for L{layout_fruchterman_reingold()} with dim=3.
`layout_graphopt`(**kwds)	This is a port of the graphopt layout algorithm by Michael Schmuhl.
`layout_grid`(**kwds)	Places the vertices of a graph in a 2D or 3D grid.
`layout_grid_3d`(**kwds)	Alias for L{layout_grid()} with dim=3.
`layout_kamada_kawai`(**kwds)	Places the vertices on a plane according to the Kamada-Kawai algorithm.
`layout_kamada_kawai_3d`(**kwds)	Alias for L{layout_kamada_kawai()} with dim=3.
`layout_lgl`(**kwds)	Places the vertices on a 2D plane according to the Large Graph Layout.
`layout_mds`(**kwds)	Places the vertices in an Euclidean space with the given number of dimensions using multidimensional scaling.
`layout_random`(**kwds)	Places the vertices of the graph randomly.
`layout_random_3d`(**kwds)	Alias for L{layout_random()} with dim=3.
`layout_reingold_tilford`(**kwds)	Places the vertices on a 2D plane according to the Reingold-Tilford layout algorithm.
`layout_reingold_tilford_circular`(**kwds)	Circular Reingold-Tilford layout for trees.
`layout_sphere`(**kwds)	Alias for L{layout_circle()} with dim=3.
`layout_star`(**kwds)	Calculates a star-like layout for the graph.
`layout_sugiyama`([layers, weights, hgap, ...])	Places the vertices using a layered Sugiyama layout.
`layout_umap`(**kwds)	Uniform Manifold Approximation and Projection (UMAP).
`linegraph`()	Returns the line graph of the graph.
`list_triangles`()	Lists the triangles of the graph
`maxdegree`([mode, loops])	Returns the maximum degree of a vertex set in the graph.
`maxflow`(source, target[, capacity])	Returns a maximum flow between the given source and target vertices in a graph.
`maxflow_value`(target[, capacity])	Returns the value of the maximum flow between the source and target vertices.
`maximal_cliques`([max, file, max_results])	Returns the maximal cliques of the graph as a list of tuples.
`maximal_independent_vertex_sets`([max, ...])	Returns the maximal independent vertex sets of the graph as a list of tuples.
`maximum_bipartite_matching`([types, weights, eps])	Finds a maximum matching in a bipartite graph.
`maximum_cardinality_search`()	Conducts a maximum cardinality search on the graph.
`mean_degree`()	Calculates the mean degree of the graph.
`mincut`([source, target, capacity])	Calculates the minimum cut between the given source and target vertices or within the whole graph.
`mincut_value`([target, capacity])	Returns the minimum cut between the source and target vertices or within the whole graph.
`minimum_cycle_basis`([complete, ...])	Computes a minimum cycle basis of the graph
`minimum_size_separators`()	Returns a list containing all separator vertex sets of minimum size.
`modularity`(membership[, weights, ...])	Calculates the modularity score of the graph with respect to a given clustering.
`modularity_matrix`([resolution, directed])	Calculates the modularity matrix of the graph.
`motifs_randesu`([cut_prob, callback])	Counts the number of motifs in the graph
`motifs_randesu_estimate`([cut_prob, sample])	Counts the total number of motifs in the graph
`motifs_randesu_no`([cut_prob])	Counts the total number of motifs in the graph
`multimaxflow`(sources, sinks)	Multi-source multi-sink maximum flow.
`neighborhood`([order, mode, mindist])	For each vertex specified by I{vertices}, returns the vertices reachable from that vertex in at most I{order} steps.
`neighborhood_size`([order, mode, mindist])	For each vertex specified by I{vertices}, returns the number of vertices reachable from that vertex in at most I{order} steps.
`neighbors`([mode, loops, multiple])	Returns adjacent vertices to a given vertex.
`omega`()	Returns the clique number of the graph.
`outdegree`(args, *kwds)	Returns the out-degrees in a list.
`pagerank`([vertices, directed, damping, ...])	Calculates the PageRank values of a graph.
`path_length_hist`([directed])	Returns the path length histogram of the graph
`permute_vertices`()	Permutes the vertices of the graph according to the given permutation and returns the new graph.
`personalized_pagerank`([directed, damping, ...])	Calculates the personalized PageRank values of a graph.
`predecessors`(vertex[, loops, multiple])	Returns the predecessors of a given vertex.
`radius`([weights])	Calculates the radius of the graph.
`random_walk`(steps[, mode, stuck, weights, ...])	Performs a random walk of a given length from a given node.
`reciprocity`([mode])	Reciprocity defines the proportion of mutual connections in a directed graph.
`reverse_edges`()	Reverses the direction of some edges in the graph.
`rewire`([n, allowed_edge_types, mode])	Randomly rewires the graph while preserving the degree distribution.
`rewire_edges`([allowed_edge_types])	Rewires the edges of a graph with constant probability.
`save`(f[, format])	Unified writing function for graphs.
`shell_index`()	Finds the coreness (shell index) of the vertices of the network.
`shortest_paths`(args, *kwds)	Deprecated alias to L{Graph.distances()}.
`shortest_paths_dijkstra`(args, *kwds)	Deprecated alias to L{Graph.distances()}.
`similarity_dice`([pairs, mode, loops])	Dice similarity coefficient of vertices.
`similarity_inverse_log_weighted`([mode])	Inverse log-weighted similarity coefficient of vertices.
`similarity_jaccard`([pairs, mode, loops])	Jaccard similarity coefficient of vertices.
`simple_cycles`([min, max, output])	Finds simple cycles in a graph
`simplify`([loops, combine_edges])	Simplifies a graph by removing self-loops and/or multiple edges.
`spanning_tree`([weights, return_tree, method])	Calculates a minimum spanning tree for a graph.
`st_mincut`(source, target[, capacity])	Calculates the minimum cut between the source and target vertices in a graph.
`strength`([mode, loops, weights])	Returns the strength (weighted degree) of some vertices from the graph
`subcomponent`([mode])	Determines the indices of vertices which are in the same component as a given vertex.
`subgraph`([implementation])	Returns a subgraph spanned by the given vertices.
`subgraph_edges`([delete_vertices])	Returns a subgraph spanned by the given edges.
`subisomorphic_lad`([domains, induced, ...])	Checks whether a subgraph of the graph is isomorphic to another graph.
`subisomorphic_vf2`([color1, color2, ...])	Checks whether a subgraph of the graph is isomorphic to another graph.
`successors`(vertex[, loops, multiple])	Returns the successors of a given vertex.
`summary`([verbosity, width])	Returns the summary of the graph.
`to_dict_dict`([use_vids, edge_attrs, ...])	Export graph to dictionary of dicts of edge attributes
`to_dict_list`([use_vids, skip_none, ...])	Export graph as two lists of dictionaries, for vertices and edges.
`to_directed`()	Converts an undirected graph to directed.
`to_graph_tool`([graph_attributes, ...])	Converts the graph to graph-tool
`to_list_dict`([use_vids, ...])	Export graph to a dictionary of lists (or other sequences).
`to_networkx`([create_using, vertex_attr_hashable])	Converts the graph to networkx format.
`to_prufer`()	Converts a tree graph into a Prüfer sequence.
`to_tuple_list`([use_vids, edge_attrs, ...])	Export graph to a list of edge tuples
`to_undirected`([combine_edges])	Converts a directed graph to undirected.
`topological_sorting`()	Calculates a possible topological sorting of the graph.
`transitivity_avglocal_undirected`([mode, weights])	Calculates the average of the vertex transitivities of the graph.
`transitivity_local_undirected`([mode, weights])	Calculates the local transitivity (clustering coefficient) of the given vertices in the graph.
`transitivity_undirected`()	Calculates the global transitivity (clustering coefficient) of the graph.
`triad_census`(args, *kwds)	Calculates the triad census of the graph.
`unfold_tree`([mode])	Unfolds the graph using a BFS to a tree by duplicating vertices as necessary.
`union`(other[, byname])	Creates the union of two (or more) graphs.
`vcount`()	Counts the number of vertices.
`vertex_attributes`()	@return: the attribute name list of the vertices of the graph
`vertex_coloring_greedy`()	Calculates a greedy vertex coloring for the graph based on some heuristics.
`vertex_connectivity`([target, checks, neighbors])	Calculates the vertex connectivity of the graph or between some vertices.
`vertex_disjoint_paths`([target, checks, ...])	Calculates the vertex connectivity of the graph or between some vertices.
`write`(f[, format])	Unified writing function for graphs.
`write_adjacency`(f[, sep, eol])	Writes the adjacency matrix of the graph to the given file
`write_dimacs`(f[, source, target, capacity])	Writes the graph in DIMACS format to the given file.
`write_dot`()	Writes the graph in DOT format to the given file.
`write_edgelist`()	Writes the edge list of a graph to a file.
`write_gml`([creator, ids])	Writes the graph in GML format to the given file.
`write_graphml`([prefixattr])	Writes the graph to a GraphML file.
`write_graphmlz`(f[, compresslevel])	Writes the graph to a zipped GraphML file.
`write_leda`([names, weights])	Writes the graph to a file in LEDA native format.
`write_lgl`([names, weights, isolates])	Writes the edge list of a graph to a file in .lgl format.
`write_ncol`([names, weights])	Writes the edge list of a graph to a file in .ncol format.
`write_pajek`()	Writes the graph in Pajek format to the given file.
`write_pickle`([fname, version])	Saves the graph in Python pickled format
`write_picklez`([fname, version])	Saves the graph in Python pickled format, compressed with gzip.
`write_svg`(fname[, layout, width, height, ...])	Saves the graph as an SVG (Scalable Vector Graphics) file

Attributes¶

vfGraph.es[source]¶: The edge sequence of the graph

vfGraph.vs[source]¶: The vertex sequence of the graph

Methods¶

classmethod vfGraph.Adjacency(matrix, mode='directed', loops='once')[source]¶

Generates a graph from its adjacency matrix.

@param matrix: the adjacency matrix. Possible types are:

a list of lists
a numpy 2D array or matrix (will be converted to list of lists)
a scipy.sparse matrix (will be converted to a COO matrix, but not to a dense matrix)
a pandas.DataFrame (column/row names must match, and will be used as vertex names).

@param mode: the mode to be used. Possible values are:

C{“directed”} - the graph will be directed and a matrix element specifies the number of edges between two vertices.
C{“undirected”} - the graph will be undirected and a matrix element specifies the number of edges between two vertices. The matrix must be symmetric.
C{“max”} - undirected graph will be created and the number of edges between vertex M{i} and M{j} is M{max(A(i,j), A(j,i))}
C{“min”} - like C{“max”}, but with M{min(A(i,j), A(j,i))}
C{“plus”} - like C{“max”}, but with M{A(i,j) + A(j,i)}
C{“upper”} - undirected graph with the upper right triangle of the matrix (including the diagonal)
C{“lower”} - undirected graph with the lower left triangle of the matrix (including the diagonal)

@param loops: specifies how to handle loop edges. When C{False} or

C{“ignore”}, the diagonal of the adjacency matrix will be ignored. When C{True} or C{“once”}, the diagonal is assumed to contain the multiplicity of the corresponding loop edge. When C{“twice”}, the diagonal is assumed to contain I{twice} the multiplicity of the corresponding loop edge.

vfGraph.Asymmetric_Preference(type_dist_matrix, pref_matrix, attribute=None, loops=False)¶

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

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

@param n: the number of vertices in the graph @param type_dist_matrix: matrix giving the joint distribution of vertex

types

@param pref_matrix: matrix giving the connection probabilities for: different vertex types.
@param attribute: the vertex attribute name used to store the vertex: types. If C{None}, vertex types are not stored.

@param loops: whether loop edges are allowed.

vfGraph.Atlas()¶

Generates a graph from the Graph Atlas.

B{Reference}: Ronald C. Read and Robin J. Wilson: I{An Atlas of Graphs}. Oxford University Press, 1998.

@param idx: The index of the graph to be generated.

Indices start from zero, graphs are listed:

in increasing order of number of vertices;

for a fixed number of vertices, in increasing order of the number of edges;

for fixed numbers of vertices and edges, in increasing order of the degree sequence, for example 111223 < 112222;

for fixed degree sequence, in increasing number of automorphisms.

vfGraph.Barabasi(m, outpref=False, directed=False, power=1, zero_appeal=1, implementation='psumtree', start_from=None)¶

Generates a graph based on the Barabási-Albert model.

B{Reference}: Barabási, A-L and Albert, R. 1999. Emergence of scaling in random networks. I{Science}, 286 509-512.

@param n: the number of vertices @param m: either the number of outgoing edges generated for

each vertex or a list containing the number of outgoing edges for each vertex explicitly.

@param outpref: C{True} if the out-degree of a given vertex

should also increase its citation probability (as well as its in-degree), but it defaults to C{False}.

@param directed: C{True} if the generated graph should be

directed (default: C{False}).

@param power: the power constant of the nonlinear model.

It can be omitted, and in this case the usual linear model will be used.

@param zero_appeal: the attractivity of vertices with degree

zero.

@param implementation: the algorithm to use to generate the

network. Possible values are:

C{“bag”}: the algorithm that was the default in igraph before 0.6. It works by putting the ids of the vertices into a bag (multiset) exactly as many times as their in-degree, plus once more. The required number of cited vertices are then drawn from the bag with replacement. It works only for I{power}=1 and I{zero_appeal}=1.

C{“psumtree”}: this algorithm uses a partial prefix-sum tree to generate the graph. It does not generate multiple edges and it works for any values of I{power} and I{zero_appeal}.

C{“psumtree_multiple”}: similar to C{“psumtree”}, but it will generate multiple edges as well. igraph before 0.6 used this algorithm for I{power}s other than 1.

@param start_from: if given and not C{None}, this must be another

L{GraphBase} object. igraph will use this graph as a starting point for the preferential attachment model.

classmethod vfGraph.Biadjacency(matrix, directed=False, mode='out', multiple=False, weighted=None, *args, **kwds)[source]¶

Creates a bipartite graph from a bipartite adjacency matrix.

Example:

>>> g = Graph.Biadjacency([[0, 1, 1], [1, 1, 0]])

@param matrix: the bipartite adjacency matrix. @param directed: whether to create a directed graph. @param mode: defines the direction of edges in the graph. If

C{“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 C{“in”}, the opposite direction is used. C{“all”} creates mutual edges. Ignored for undirected graphs.

@param multiple: defines what to do with non-zero entries in the: matrix. If C{False}, non-zero entries will create an edge no matter what the value is. If C{True}, non-zero entries are rounded up to the nearest integer and this will be the number of multiple edges created.
@param weighted: defines whether to create a weighted graph from the: adjacency matrix. If it is c{None} then an unweighted graph is created and the multiple argument is used to determine the edges of the graph. If it is a string then for every non-zero matrix entry, an edge is created and the value of the entry is added as an edge attribute named by the weighted argument. If it is C{True} then a weighted graph is created and the name of the edge attribute will be C{“weight”}.

@raise ValueError: if the weighted and multiple are passed together.

@return: the graph with a binary vertex attribute named C{“type”} that: stores the vertex classes.

classmethod vfGraph.Bipartite(types, edges, directed=False, *args, **kwds)[source]¶

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 C{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]

@param types: the vertex types as a boolean list. Anything that: evaluates to C{False} will denote a vertex of the first kind, anything that evaluates to C{True} will denote a vertex of the second kind.

@param edges: the edges as a list of tuples. @param directed: whether to create a directed graph. Bipartite

networks are usually undirected, so the default is C{False}

@return: the graph with a binary vertex attribute named C{“type”} that: stores the vertex classes.

vfGraph.Chung_Lu(in_=None, loops=True, variant='original')¶

Generates a Chung-Lu random graph.

In the original Chung-Lu model, each pair of vertices M{i} and M{j} is connected with independent probability M{p_{ij} = w_i w_j / S}, where M{w_i} is a weight associated with vertex M{i} and M{S = sum_k w_k} is the sum of weights. In the directed variant, vertices have both out-weights, M{w^text{out}}, and in-weights, M{w^text{in}}, with equal sums, M{S = sum_k w^text{out}_k = sum_k w^text{in}_k}. The connection probability between M{i} and M{j} is M{p_{ij} = w^text{out}_i w^text{in}_j / S}.

This model is commonly used to create random graphs with a fixed I{expected} degree sequence. The expected degree of vertex M{i} is approximately equal to the weight M{w_i}. Specifically, if the graph is directed and self-loops are allowed, then the expected out- and in-degrees are precisely M{w^text{out}} and M{w^text{in}}. If self-loops are disallowed, then the expected out- and in-degrees are M{w^text{out} (S - w^text{in}) / S} and M{w^text{in} (S - w^text{out}) / S}, respectively. If the graph is undirected, then the expected degrees with and without self-loops are M{w (S + w) / S} and M{w (S - w) / S}, respectively.

A limitation of the original Chung-Lu model is that when some of the weights are large, the formula for M{p_{ij}} yields values larger than 1. Chung and Lu’s original paper excludes the use of such weights. When M{p_{ij} > 1}, this function simply issues a warning and creates a connection between M{i} and M{j}. However, in this case the expected degrees will no longer relate to the weights in the manner stated above. Thus the original Chung-Lu model cannot produce certain (large) expected degrees.

The overcome this limitation, this function implements additional variants of the model, with modified expressions for the connection probability M{p_{ij}} between vertices M{i} and M{j}. Let M{q_{ij} = w_i w_j / S}, or M{q_{ij} = w^out_i w^in_j / S} in the directed case. All model variants become equivalent in the limit of sparse graphs where M{q_{ij}} approaches zero. In the original Chung-Lu model, selectable by setting C{variant} to C{“original”}, M{p_{ij} = min(q_{ij}, 1)}. The C{“maxent”} variant, sometimes referred to as the generalized random graph, uses M{p_{ij} = q_{ij} / (1 + q_{ij})}, and is equivalent to a maximum entropy model (i.e. exponential random graph model) with a constraint on expected degrees, see Park and Newman (2004), Section B, setting M{exp(-Theta_{ij}) = w_i w_j / S}. This model is also discussed by Britton, Deijfen and Martin-Löf (2006). By virtue of being a degree-constrained maximum entropy model, it generates graphs having the same degree sequence with the same probability. A third variant can be requested with C{“nr”}, and uses M{p_{ij} = 1 - exp(-q_{ij})}. This is the underlying simple graph of a multigraph model introduced by Norros and Reittu (2006). For a discussion of these three model variants, see Section 16.4 of Bollobás, Janson, Riordan (2007), as well as Van Der Hofstad (2013).

B{References:}

Chung F and Lu L: Connected components in a random graph with given degree sequences. I{Annals of Combinatorics} 6, 125-145 (2002) U{https://doi.org/10.1007/PL00012580}

Miller JC and Hagberg A: Efficient Generation of Networks with Given Expected Degrees (2011) U{https://doi.org/10.1007/978-3-642-21286-4_10}

Park J and Newman MEJ: Statistical mechanics of networks. I{Physical Review E} 70, 066117 (2004). U{https://doi.org/10.1103/PhysRevE.70.066117}

Britton T, Deijfen M, Martin-Löf A: Generating Simple Random Graphs with Prescribed Degree Distribution. I{J Stat Phys} 124, 1377–1397 (2006). U{https://doi.org/10.1007/s10955-006-9168-x}

Norros I and Reittu H: On a conditionally Poissonian graph process. I{Advances in Applied Probability} 38, 59–75 (2006). U{https://doi.org/10.1239/aap/1143936140}

Bollobás B, Janson S, Riordan O: The phase transition in inhomogeneous random graphs. I{Random Struct Algorithms} 31, 3–122 (2007). U{https://doi.org/10.1002/rsa.20168}

Van Der Hofstad R: Critical behavior in inhomogeneous random graphs. I{Random Struct Algorithms} 42, 480–508 (2013). U{https://doi.org/10.1002/rsa.20450}

@param out: the vertex weights (or out-weights). In sparse graphs: these will be approximately equal to the expected (out-)degrees.
@param in_: the vertex in-weights, approximately equal to the expected: in-degrees of the graph. If omitted, the generated graph will be undirected.

@param loops: whether to allow the generation of self-loops. @param variant: the model variant to be used. Let M{q_{ij}=w_i w_j / S},

where M{S = sum_k w_k}. The following variants are available:

C{“original”} – the original Chung-Lu model with M{p_{ij} = min(1, q_{ij})}.

C{“maxent”} – maximum entropy model with fixed expected degrees M{p_{ij} = q_{ij} / (1 + q_{ij})}

C{“nr”} – Norros and Reittu’s model, M{p_{ij} = 1 - exp(-q_{ij})}

classmethod vfGraph.DataFrame(directed=True, vertices=None, use_vids=True)[source]¶

Generates a graph from one or two dataframes.

@param edges: pandas DataFrame containing edges and metadata. The first: two columns of this DataFrame contain the source and target vertices for each edge. These indicate the vertex IDs as nonnegative integers rather than vertex names unless C{use_vids} is False. Further columns may contain edge attributes.

@param directed: whether the graph is directed @param vertices: None (default) or pandas DataFrame containing vertex

metadata. The DataFrame’s index must contain the vertex IDs as a sequence of intergers from 0 to C{len(vertices) - 1}. If C{use_vids} is C{False}, the first column must contain the unique vertex names. Vertex names should be strings for full compatibility, but many functions will work if you set the name with any hashable object. All other columns will be added as vertex attributes by column name.

@param use_vids: whether to interpret the first two columns of the C{edges}: argument as vertex ids (0-based integers) instead of vertex names. If this argument is set to True and the first two columns of C{edges} are not integers, an error is thrown.

@return: the graph

Vertex names in either the C{edges} or C{vertices} arguments that are set to NaN (not a number) will be set to the string “NA”. That might lead to unexpected behaviour: fill your NaNs with values before calling this function to mitigate.

vfGraph.De_Bruijn(n)¶

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

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

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

@param m: the size of the alphabet @param n: the length of the strings

vfGraph.Degree_Sequence(in_=None, method='configuration')¶

Generates a graph with a given degree sequence.

@param out: the out-degree sequence for a directed graph. If the: in-degree sequence is omitted, the generated graph will be undirected, so this will be the in-degree sequence as well
@param in_: the in-degree sequence for a directed graph.: If omitted, the generated graph will be undirected.

@param method: the generation method to be used. One of the following:

C{“configuration”} – simple generator that implements the stub-matching configuration model. It may generate self-loops and multiple edges. This method does not sample multigraphs uniformly, but it can be used to implement uniform sampling for simple graphs by rejecting any result that is non-simple (i.e. contains loops or multi-edges).

C{“fast_heur_simple”} – similar to C{“configuration”} but avoids the generation of multiple and loop edges at the expense of increased time complexity. The method will re-start the generation every time it gets stuck in a configuration where it is not possible to insert any more edges without creating loops or multiple edges, and there is no upper bound on the number of iterations, but it will succeed eventually if the input degree sequence is graphical and throw an exception if the input degree sequence is not graphical. This method does not sample simple graphs uniformly.

C{“configuration_simple”} – similar to C{“configuration”} but rejects generated graphs if they are not simple. This method samples simple graphs uniformly.

C{“edge_switching_simple”} – an MCMC sampler based on degree-preserving edge switches. It generates simple undirected or directed graphs. The algorithm uses L{Graph.Realize_Degree_Sequence()} to construct an initial graph, then rewires it using L{Graph.rewire()}.

C{“vl”} – a more sophisticated generator that can sample undirected, connected simple graphs approximately uniformly. It uses edge-switching Monte-Carlo methods to randomize the graphs. This generator should be favoured if undirected and connected graphs are to be generated and execution time is not a concern. igraph uses the original implementation of Fabien Viger; see the following URL and the paper cited on it for the details of the algorithm: U{https://www-complexnetworks.lip6.fr/~latapy/FV/generation.html}.

classmethod vfGraph.DictDict(directed=False, vertex_name_attr='name')[source]¶

Constructs a graph from a dict-of-dicts representation.

Each key can be an integer or a string and represent a vertex. Each value is a dict representing edges (outgoing if the graph is directed) from that vertex. Each dict key is an integer/string for a target vertex, such that an edge will be created between those two vertices. Integers are interpreted as vertex_ids from 0 (as used in igraph), strings are interpreted as vertex names, in which case vertices are given separate numeric ids. Each value is a dictionary of edge attributes for that edge.

Example

>>> {'Alice': {'Bob': {'weight': 1.5}, 'David': {'weight': 2}}}

creates a graph with three vertices (Alice, Bob, and David) and two edges:

Alice - Bob (with weight 1.5)

Alice - David (with weight 2)

@param edges: the dict of dict of dicts specifying the edges and their: attributes

@param directed: whether to create a directed graph @param vertex_name_attr: vertex attribute that will store the names

@returns: a Graph object

classmethod vfGraph.DictList(edges, directed=False, vertex_name_attr='name', edge_foreign_keys=('source', 'target'), iterative=False)[source]¶

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

This function is useful when you have two lists of dictionaries, one for vertices and one for edges, each containing their attributes (e.g. name, weight). Of course, the edge dictionary must also contain two special keys that indicate the source and target vertices connected by that edge. Non-list iterables should work as long as they yield dictionaries or dict-like objects (they should have the ‘items’ and ‘__getitem__’ methods). 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.

@param vertices: the list of dictionaries for the vertices or C{None} if: there are no special attributes assigned to vertices and we should simply use the edge list of dicts to infer vertex names.
@param edges: the list of dictionaries for the edges. Each dict must have: at least the two keys specified by edge_foreign_keys to label the source and target vertices, while additional items will be treated as edge attributes.

@param directed: whether the constructed graph will be directed @param vertex_name_attr: the name of the distinguished key in the

dicts in the vertex data source that contains the vertex names. Ignored if C{vertices} is C{None}.

@param edge_foreign_keys: tuple specifying the attributes in each edge: dictionary that contain the source (1st) and target (2nd) vertex names. These items of each dictionary are also added as edge_attributes.
@param 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.

@return: the graph that was constructed

Example:

>>> vertices = [{'name': 'apple'}, {'name': 'pear'}, {'name': 'peach'}]
>>> edges = [{'source': 'apple', 'target': 'pear', 'weight': 1.2},
...          {'source': 'apple', 'target': 'peach', 'weight': 0.9}]
>>> g = Graph.DictList(vertices, edges)

The graph has three vertices with names and two edges with weights.

vfGraph.Erdos_Renyi(p, m, directed=False, loops=False, edge_labeled=False)¶

Generates a graph based on the Erdős-Rényi model.

@param n: the number of vertices. @param p: the probability of edges. If given, C{m} must be missing. @param m: the number of edges. If given, C{p} must be missing. @param directed: whether to generate a directed graph. @param loops: whether self-loops are allowed. @param edge_labeled: whether to sample uniformly from the set of

I{ordered} edge lists. Use C{False} to recover the classic Erdős-Rényi model.

vfGraph.Establishment(k, type_dist, pref_matrix, directed=False)¶

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

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

@param n: the number of vertices in the graph @param k: the number of connections tried in each step @param type_dist: list giving the distribution of vertex types @param pref_matrix: matrix (list of lists) giving the connection

probabilities for different vertex types

@param directed: whether to generate a directed graph.

vfGraph.Famous()¶

Generates a famous graph based on its name.

Several famous graphs are known to C{igraph} including (but not limited to) the Chvatal graph, the Petersen graph or the Tutte graph. This method generates one of them based on its name (case insensitive). See the documentation of the C interface of C{igraph} for the names available: U{https://igraph.org/c/doc}.

@param name: the name of the graph to be generated.

vfGraph.Forest_Fire(fw_prob, bw_factor=0.0, ambs=1, directed=False)¶

Generates a graph based on the forest fire model

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

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

classmethod vfGraph.Formula(formula=None, attr='name', simplify=True)[source]¶

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 (C{-}) that may or may not start with an arrowhead (C{<} at the beginning of the sequence or C{>} 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:

C{—–} makes an undirected edge

C{<—-} makes a directed edge pointing from the vertex on the right hand side of the operator to the vertex on the left hand side

C{—->} is the opposite of C{<—-}

C{<—>} creates a mutual directed edge pair between the two vertices

If you only use the undirected edge operator (C{—–}), the graph will be undirected. Otherwise it will be directed. Vertex names used in the formula will be assigned to the C{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 many 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.connected_components().membership
[0, 0, 1, 1, 2, 2, 3, 3, 4, 5, 6]

The colon (C{:}) 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']

@param formula: the formula itself @param attr: name of the vertex attribute where the vertex names

will be stored

@param simplify: whether to simplify the constructed graph @return: the constructed graph:

vfGraph.Full(directed=False, loops=False)¶

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

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

classmethod vfGraph.Full_Bipartite(n1, n2, directed=False, mode='all', *args, **kwds)[source]¶

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]

@param n1: the number of vertices of the first kind. @param n2: the number of vertices of the second kind. @param directed: whether tp generate a directed graph. @param mode: if C{“out”}, then all vertices of the first kind are

connected to the others; C{“in”} specifies the opposite direction, C{“all”} creates mutual edges. Ignored for undirected graphs.

@return: the graph with a binary vertex attribute named C{“type”} that: stores the vertex classes.

vfGraph.Full_Citation(directed=False)¶

Generates a full citation graph

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

@param n: the number of vertices. @param directed: whether to generate a directed graph.

classmethod vfGraph.GRG(n, radius, torus=False)[source]¶

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 C{x} and C{y}.

@param n: The number of vertices in the graph @param radius: The given radius @param torus: This should be C{True} if we want to use a torus instead of a

square.

vfGraph.Growing_Random(m, directed=False, citation=False)¶

Generates a growing random graph.

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

recently added vertex.

vfGraph.Hexagonal_Lattice(directed=False, mutual=True)¶

Generates a regular hexagonal lattice.

@param dim: list with the dimensions of the lattice @param directed: whether to create a directed graph. @param mutual: whether to create all connections as mutual

in case of a directed graph.

vfGraph.Hypercube(directed=False)¶

Generates an n-dimensional hypercube graph.

The hypercube graph M{Q_n} has M{2^n} vertices and M{2^{n-1} n} edges. Two vertices are connected when the binary representations of their vertex IDs differ in precisely one bit. @param n: the dimension of the hypercube graph @param directed: whether to create a directed graph; edges will point

from lower index vertices towards higher index ones.

classmethod vfGraph.Incidence(*args, **kwds)[source]¶: Deprecated alias to L{Graph.Biadjacency()}.

vfGraph.Isoclass(cls, directed=False)¶

Generates a graph with a given isomorphism class.

Currently we support directed graphs of size 3 and 4, and undirected graphs of size 3, 4, 5 or 6. Use the L{isoclass()} instance method to find the isomorphism class of a given graph.

@param n: the number of vertices in the graph @param cls: the isomorphism class @param directed: whether the graph should be directed.

vfGraph.K_Regular(k, directed=False, multiple=False)¶

Generates a k-regular random graph

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

@param n: The number of vertices in the graph

@param k: The degree of each vertex if the graph is undirected, or the in-degree: and out-degree of each vertex if the graph is directed

@param directed: whether the graph should be directed. @param multiple: whether it is allowed to create multiple edges.

vfGraph.Kautz(n)¶

Generates a Kautz graph with parameters (m, n)

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

@param m: the size of the alphabet minus one @param n: the length of the strings minus one

vfGraph.LCF(shifts, repeats)¶

Generates a graph from LCF notation.

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

@param n: the number of vertices @param shifts: the shifts in a list or tuple @param repeats: the number of repeats

vfGraph.Lattice(nei=1, directed=False, mutual=True, circular=True)¶

Generates a regular square lattice.

@param dim: list with the dimensions of the lattice @param nei: value giving the distance (number of steps) within which

two vertices will be connected.

@param directed: whether to create a directed graph. @param mutual: whether to create all connections as mutual

in case of a directed graph.

@param circular: whether the generated lattice is periodic. May also be an: iterable; in this case, the iterator is assumed to yield booleans that specify whether the lattice is periodic along each dimension.

classmethod vfGraph.ListDict(directed=False, vertex_name_attr='name')[source]¶

Constructs a graph from a dict-of-lists representation.

This function is used to construct a graph from a dictionary of lists. Other, non-list sequences (e.g. tuples) and lazy iterators are are accepted. For each key x, its corresponding value must be a sequence of multiple values y: the edge (x,y) will be created in the graph. x and y must be either one of:

two integers: the vertices with those ids will be connected

two strings: the vertices with those names will be connected

If names are used, the order of vertices is not guaranteed, and each vertex will be given the vertex_name_attr attribute.

@param edges: the dict of sequences describing the edges @param directed: whether to create a directed graph @param vertex_name_attr: vertex attribute that will store the names

@returns: a Graph object

Example:

>>> mydict = {'apple': ['pear', 'peach'], 'pear': ['peach']}
>>> g = Graph.ListDict(mydict)

# The graph has three vertices with names and three edges connecting # each pair.

classmethod vfGraph.Load(f, format=None, *args, **kwds)[source]¶

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.

@param f: the file containing the graph to be loaded @param format: the format of the file (if known in advance).

C{None} means auto-detection. Possible values are: C{“ncol”} (NCOL format), C{“lgl”} (LGL format), C{“graphdb”} (GraphDB format), C{“graphml”}, C{“graphmlz”} (GraphML and gzipped GraphML format), C{“gml”} (GML format), C{“net”}, C{“pajek”} (Pajek format), C{“dimacs”} (DIMACS format), C{“edgelist”}, C{“edges”} or C{“edge”} (edge list), C{“adjacency”} (adjacency matrix), C{“dl”} (DL format used by UCINET), C{“pickle”} (Python pickled format), C{“picklez”} (gzipped Python pickled format)

@raises IOError: if the file format can’t be identified and: none was given.

vfGraph.Nearest_Neighbor_Graph(k=1, r=-1, metric='euclidean', directed=False)¶

Constructs a k nearest neighbor graph of a give point set. Each point is connected to at most k spatial neighbors within a radius of 1.

@param points: coordinates of the points to use, in an arbitrary number of dimensions @param k: at most how many neighbors to connect to. Pass a negative value to ignore @param r: only neighbors within this radius are considered. Pass a negative value to ignore @param metric: the metric to use. C{“euclidean”} and C{“manhattan”} are supported. @param directed: whethe to create directed edges. @return: the nearest neighbor graph.

vfGraph.Preference(type_dist, pref_matrix, attribute=None, directed=False, loops=False)¶

Generates a graph based on vertex types and connection probabilities.

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

@param n: the number of vertices in the graph @param type_dist: list giving the distribution of vertex types @param pref_matrix: matrix giving the connection probabilities for

different vertex types.

@param attribute: the vertex attribute name used to store the vertex: types. If C{None}, vertex types are not stored.

@param directed: whether to generate a directed graph. @param loops: whether loop edges are allowed.

vfGraph.Prufer()¶

Generates a tree from its Prüfer sequence.

A Prüfer sequence is a unique sequence of integers associated with a labelled tree. A tree on M{n} vertices can be represented by a sequence of M{n-2} integers, each between M{0} and M{n-1} (inclusive).

@param seq: the Prüfer sequence as an iterable of integers

classmethod vfGraph.Random_Bipartite(n1, n2, p=None, m=None, directed=False, neimode='all', allowed_edge_types='simple', edge_labeled=False, *args, **kwds)[source]¶

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.

@param n1: the number of vertices of type 1. @param n2: the number of vertices of type 2. @param p: the probability of edges. If given, C{m} must be missing. @param m: the number of edges. If given, C{p} must be missing. @param directed: whether to generate a directed graph. @param neimode: if the graph is directed, specifies how the edges will be

generated. If it is C{“all”}, edges will be generated in both directions (from type 1 to type 2 and vice versa) independently. If it is C{“out”} edges will always point from type 1 to type 2. If it is C{“in”}, edges will always point from type 2 to type 1. This argument is ignored for undirected graphs.

@param allowed_edge_types: controls whether multi-edges are allowed

during the generation process. Possible values are:

C{“simple”}: simple graphs (no self-loops)

C{“multi”}: multi-edges allowed

@param edge_labeled: whether to sample uniformly from the set of

I{ordered} edge lists. Use C{False} to recover the classic random bipartite model.

classmethod vfGraph.Read(f, format=None, *args, **kwds)[source]¶

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.

@param f: the file containing the graph to be loaded @param format: the format of the file (if known in advance).

C{None} means auto-detection. Possible values are: C{“ncol”} (NCOL format), C{“lgl”} (LGL format), C{“graphdb”} (GraphDB format), C{“graphml”}, C{“graphmlz”} (GraphML and gzipped GraphML format), C{“gml”} (GML format), C{“net”}, C{“pajek”} (Pajek format), C{“dimacs”} (DIMACS format), C{“edgelist”}, C{“edges”} or C{“edge”} (edge list), C{“adjacency”} (adjacency matrix), C{“dl”} (DL format used by UCINET), C{“pickle”} (Python pickled format), C{“picklez”} (gzipped Python pickled format)

@raises IOError: if the file format can’t be identified and: none was given.

classmethod vfGraph.Read_Adjacency(f, sep=None, comment_char='#', attribute=None, *args, **kwds)[source]¶

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

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

@param f: the name of the file to be read or a file object @param sep: the string that separates the matrix elements in a row.

C{None} means an arbitrary sequence of whitespace characters.

@param comment_char: lines starting with this string are treated: as comments.
@param attribute: an edge attribute name where the edge weights are: stored in the case of a weighted adjacency matrix. If C{None}, no weights are stored, values larger than 1 are considered as edge multiplicities.

@return: the created graph

classmethod vfGraph.Read_DIMACS(f, directed=False)[source]¶

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

For the exact definition of the format, see U{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.

@param f: the name of the file or a Python file handle @param directed: whether the generated graph should be directed. @return: the generated graph. The indices of the source and target

vertices are attached as graph attributes C{source} and C{target}, the edge capacities are stored in the C{capacity} edge attribute.

vfGraph.Read_DL(directed=True)¶

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

@param f: the name of the file or a Python file handle @param directed: whether the generated graph should be directed.

vfGraph.Read_Edgelist(directed=True)¶

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

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

@param f: the name of the file or a Python file handle @param directed: whether the generated graph should be directed.

vfGraph.Read_GML()¶

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

@param f: the name of the file or a Python file handle

vfGraph.Read_GraphDB(directed=False)¶

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

GraphDB is a binary format, used in the graph database for isomorphism testing (see U{https://mivia.unisa.it/datasets/graph-database/arg-database/}).

@param f: the name of the file or a Python file handle @param directed: whether the generated graph should be directed.

vfGraph.Read_GraphML(index=0)¶

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

@param f: the name of the file or a Python file handle @param index: if the GraphML file contains multiple graphs,

specifies the one that should be loaded. Graph indices start from zero, so if you want to load the first graph, specify 0 here.

classmethod vfGraph.Read_GraphMLz(f, index=0)[source]¶

Reads a graph from a zipped GraphML file.

@param f: the name of the file @param 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.

@return: the loaded graph object

vfGraph.Read_Lgl(names=True, weights='if_present', directed=True)¶

Reads an .lgl file used by LGL.

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

This format is used by the Large Graph Layout program. See the U{documentation of LGL <http://bioinformatics.icmb.utexas.edu/lgl/>} regarding the exact format description.

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

@param f: the name of the file or a Python file handle @param names: If C{True}, the vertex names are added as a

vertex attribute called ‘name’.

@param weights: If True, the edge weights are added as an: edge attribute called ‘weight’, even if there are no weights in the file. If False, the edge weights are never added, even if they are present. C{“auto”} or C{“if_present”} means that weights are added if there is at least one weighted edge in the input file, but they are not added otherwise.
@param directed: whether the graph being created should be: directed

vfGraph.Read_Ncol(names=True, weights='if_present', directed=True)¶

Reads an .ncol file used by LGL.

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

This format is used by the Large Graph Layout program. See the U{repository of LGL <https://github.com/TheOpteProject/LGL/>} for more information.

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

@param f: the name of the file or a Python file handle @param names: If C{True}, the vertex names are added as a

vertex attribute called ‘name’.

@param weights: If True, the edge weights are added as an: edge attribute called ‘weight’, even if there are no weights in the file. If False, the edge weights are never added, even if they are present. C{“auto”} or C{“if_present”} means that weights are added if there is at least one weighted edge in the input file, but they are not added otherwise.
@param directed: whether the graph being created should be: directed

vfGraph.Read_Pajek()¶

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

@param f: the name of the file or a Python file handle

classmethod vfGraph.Read_Pickle(fname=None)[source]¶

Reads a graph from Python pickled format

@param fname: the name of the file, a stream to read from, or: a string containing the pickled data.

@return: the created graph object.

classmethod vfGraph.Read_Picklez(fname)[source]¶

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

@param fname: the name of the file or a stream to read from. @return: the created graph object.

vfGraph.Realize_Bipartite_Degree_Sequence(degrees2, allowed_edge_types='simple', method='smallest')¶

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

This method implements a Havel-Hakimi style graph construction for biparite graphs. In each step, the algorithm picks two vertices in a deterministic manner and connects them. The way the vertices are picked is defined by the C{method} parameter. The allowed edge types (i.e. whether multi-edges are allowed) are specified in the C{allowed_edge_types} parameter. Self-loops are never created, since a graph with self-loops is not bipartite.

@param degrees1: the degrees of the first partition. @param degrees2: the degrees of the second partition. @param allowed_edge_types: controls whether multi-edges are allowed

during the generation process. Possible values are:

C{“simple”}: simple graphs (no multi-edges)

C{“multi”}: multi-edges allowed

@param method: controls how the vertices are selected during the generation

process. Possible values are:

C{smallest}: The vertex with smallest remaining degree first.

C{largest}: The vertex with the largest remaining degree first.

C{index}: The vertices are selected in order of their index.

The smallest C{smallest} method is guaranteed to produce a connected graph, if one exists.

vfGraph.Realize_Degree_Sequence(in_=None, allowed_edge_types='simple', method='smallest')¶

Generates a graph from a degree sequence.

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

B{References}

V. Havel, Poznámka o existenci konečných grafů (A remark on the existence of finite graphs), Časopis pro pěstování matematiky 80, 477-480 (1955). U{http://eudml.org/doc/19050}

S. L. Hakimi, On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph, I{Journal of the SIAM} 10, 3 (1962). U{https://www.jstor.org/stable/2098770}

D. J. Kleitman and D. L. Wang, Algorithms for Constructing Graphs and Digraphs with Given Valences and Factors, I{Discrete Mathematics} 6, 1 (1973). U{https://doi.org/10.1016/0012-365X%2873%2990037-X}

Sz. Horvát and C. D. Modes, Connectedness matters: construction and exact random sampling of connected networks (2021). U{https://doi.org/10.1088/2632-072X/abced5}

@param out: the degree sequence of an undirected graph (if in_=None),

or the out-degree sequence of a directed graph.

@param in_: None to generate an undirected graph, the in-degree sequence

to generate a directed graph.

@param allowed_edge_types: controls whether loops or multi-edges are allowed

during the generation process. Note that not all combinations are supported for all types of graphs; an exception will be raised for unsupported combinations. Possible values are:

C{“simple”}: simple graphs (no self-loops, no multi-edges)

C{“loops”}: single self-loops allowed, but not multi-edges

C{“multi”}: multi-edges allowed, but not self-loops

C{“all”}: multi-edges and self-loops allowed

@param method: controls how the vertices are selected during the generation

process. Possible values are:

C{smallest}: The vertex with smallest remaining degree first.

C{largest}: The vertex with the largest remaining degree first.

C{index}: The vertices are selected in order of their index.

In the undirected case, C{smallest} is guaranteed to produce a connected graph. See Horvát and Modes (2021) for details.

vfGraph.Recent_Degree(m, window, outpref=False, directed=False, power=1)¶

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

@param n: the number of vertices @param m: either the number of outgoing edges generated for

each vertex or a list containing the number of outgoing edges for each vertex explicitly.

@param window: size of the window in time steps @param outpref: C{True} if the out-degree of a given vertex

should also increase its citation probability (as well as its in-degree), but it defaults to C{False}.

@param directed: C{True} if the generated graph should be: directed (default: C{False}).
@param power: the power constant of the nonlinear model.: It can be omitted, and in this case the usual linear model will be used.

vfGraph.Ring(directed=False, mutual=False, circular=True)¶

Generates a ring graph.

@param n: the number of vertices in the ring @param directed: whether to create a directed ring. @param mutual: whether to create mutual edges in a directed ring. @param circular: whether to create a closed ring.

vfGraph.SBM(block_sizes, directed=False, allowed_edge_types='simple')¶

Generates a graph based on a stochastic block model.

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

@param pref_matrix: matrix giving the connection probabilities (or expected: edge multiplicities for multigraphs) between different vertex types.
@param block_sizes: list giving the number of vertices in each block; must: sum up to I{n}.

@param directed: whether to generate a directed graph. @param allowed_edge_types: controls whether loops or multi-edges are allowed

during the generation process. Note that not all combinations are supported for all types of graphs; an exception will be raised for unsupported combinations. Possible values are:

C{“simple”}: simple graphs (no self-loops, no multi-edges)

C{“loops”}: single self-loops allowed, but not multi-edges

C{“multi”}: multi-edges allowed, but not self-loops

C{“all”}: multi-edges and self-loops allowed

vfGraph.Star(mode='undirected', center=0)¶

Generates a star graph.

@param n: the number of vertices in the graph @param mode: Gives the type of the star graph to create. Should be

either “in”, “out”, “mutual” or “undirected”

@param center: Vertex ID for the central vertex in the star.

vfGraph.Static_Fitness(fitness_out, fitness_in=None, allowed_edge_types='simple')¶

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

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

@param m: the number of edges in the graph @param fitness_out: a numeric vector with non-negative entries, one for each

vertex. These values represent the fitness scores (out-fitness scores for directed graphs). I{fitness} is an alias of this keyword argument.

@param fitness_in: a numeric vector with non-negative entries, one for each

vertex. These values represent the in-fitness scores for directed graphs. For undirected graphs, this argument must be C{None}.

@param allowed_edge_types: controls whether loops or multi-edges are allowed

during the generation process. Note that not all combinations are supported for all types of graphs; an exception will be raised for unsupported combinations. Possible values are:

C{“simple”}: simple graphs (no self-loops, no multi-edges)

C{“loops”}: single self-loops allowed, but not multi-edges

C{“multi”}: multi-edges allowed, but not self-loops

C{“all”}: multi-edges and self-loops allowed

@return: a directed or undirected graph with the prescribed power-law

degree distributions.

vfGraph.Static_Power_Law(m, exponent_out, exponent_in=-1, allowed_edge_types='simple', finite_size_correction=True)¶

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

B{References}

Goh K-I, Kahng B, Kim D: Universal behaviour of load distribution in scale-free networks. I{Phys Rev Lett} 87(27):278701, 2001.

Cho YS, Kim JS, Park J, Kahng B, Kim D: Percolation transitions in scale-free networks under the Achlioptas process. I{Phys Rev Lett} 103:135702, 2009.

@param n: the number of vertices in the graph @param m: the number of edges in the graph @param exponent_out: the exponent of the out-degree distribution, which

must be between 2 and infinity (inclusive). When I{exponent_in} is not given or negative, the graph will be undirected and this parameter specifies the degree distribution. I{exponent} is an alias to this keyword argument.

@param exponent_in: the exponent of the in-degree distribution, which

must be between 2 and infinity (inclusive) It can also be negative, in which case an undirected graph will be generated.

@param allowed_edge_types: controls whether loops or multi-edges are allowed

during the generation process. Note that not all combinations are supported for all types of graphs; an exception will be raised for unsupported combinations. Possible values are:

C{“simple”}: simple graphs (no self-loops, no multi-edges)

C{“loops”}: single self-loops allowed, but not multi-edges

C{“multi”}: multi-edges allowed, but not self-loops

C{“all”}: multi-edges and self-loops allowed

@param finite_size_correction: whether to apply a finite-size correction

to the generated fitness values for exponents less than 3. See the paper of Cho et al for more details.

@return: a directed or undirected graph with the prescribed power-law

degree distributions.

vfGraph.Tree(children, mode='undirected')¶

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

@param n: the number of vertices in the graph @param children: the number of children of a vertex in the graph @param mode: determines whether the tree should be directed, and if

this is the case, also its orientation. Must be one of C{“in”}, C{“out”} and C{“undirected”}.

vfGraph.Tree_Game(directed=False, method='lerw')¶

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

@param n: the number of vertices in the tree @param directed: whether the graph should be directed @param method: the generation method to be used. One of the following:

C{“prufer”} – samples Prüfer sequences uniformly, then converts them to trees

C{“lerw”} – performs a loop-erased random walk on the complete graph to uniformly sample its spanning trees (Wilson’s algorithm). This is the default choice as it supports both directed and undirected graphs.

vfGraph.Triangular_Lattice(directed=False, mutual=True)¶

Generates a regular triangular lattice.

@param dim: list with the dimensions of the lattice @param directed: whether to create a directed graph. @param mutual: whether to create all connections as mutual

in case of a directed graph.

classmethod vfGraph.TupleList(directed=False, vertex_name_attr='name', edge_attrs=None, weights=False)[source]¶

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 C{edge_attrs} list. The names of the vertices will be stored in the vertex attribute given by C{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 C{edge_attrs} to C{“weight”} or C{[“weight”]}. If you have even more edge attributes, add them to the end of each item in the C{edges} list and also specify the corresponding edge attribute names in C{edge_attrs} as a list.

@param 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 C{name} vertex attribute (or another vertex attribute if C{vertex_name_attr} is specified), even if all the vertex names in the list are in fact numbers.

@param directed: whether the constructed graph will be directed @param vertex_name_attr: the name of the vertex attribute that will

contain the vertex names.

@param 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). If C{None} or an empty sequence, only the source and target vertices will be extracted and additional tuple items will be ignored. If a string, it is interpreted as a single edge attribute.
@param weights: alternative way to specify that the graph is: weighted. If you set C{weights} to C{true} and C{edge_attrs} is not given, it will be assumed that C{edge_attrs} is C{[“weight”]} and igraph will parse the third element from each item into an edge weight. If you set C{weights} to a string, it will be assumed that C{edge_attrs} contains that string only, and igraph will store the edge weights in that attribute.

@return: the graph that was constructed

vfGraph.Watts_Strogatz(size, nei, p, allowed_edge_types='simple')¶

This function generates networks with the small-world property based on a variant of the Watts-Strogatz model. The network is obtained by first creating a periodic undirected lattice, then rewiring both endpoints of each edge with probability I{p}, while avoiding the creation of multi-edges.

This process differs from the original model of Watts and Strogatz (see reference) in that it rewires I{both} endpoints of edges. Thus in the limit of C{p=1}, we obtain a G(n,m) random graph with the same number of vertices and edges as the original lattice. In comparison, the original Watts-Strogatz model only rewires a single endpoint of each edge, thus the network does not become fully random even for <code>p=1</code>.

For appropriate choices of I{p}, both models exhibit the property of simultaneously having short path lengths and high clustering.

B{Reference}: Duncan J Watts and Steven H Strogatz: Collective dynamics of small world networks, I{Nature} 393, 440-442, 1998

@param dim: the dimension of the lattice @param size: the size of the lattice along all dimensions @param nei: value giving the distance (number of steps) within which

two vertices will be connected.

@param p: rewiring probability

@param allowed_edge_types: controls whether loops or multi-edges are allowed

during the generation process. Note that not all combinations are supported for all types of graphs; an exception will be raised for unsupported combinations. Possible values are:

C{“simple”}: simple graphs (no self-loops, no multi-edges)

C{“loops”}: single self-loops allowed, but not multi-edges

C{“multi”}: multi-edges allowed, but not self-loops

C{“all”}: multi-edges and self-loops allowed

@see: L{Lattice()}, L{rewire()}, L{rewire_edges()} if more flexibility is

needed

classmethod vfGraph.Weighted_Adjacency(matrix, mode='directed', attr='weight', loops='once')[source]¶

Generates a graph from its weighted adjacency matrix.

Only edges with a non-zero weight are created.

@param matrix: the adjacency matrix. Possible types are:

a list of lists
a numpy 2D array or matrix (will be converted to list of lists)
a scipy.sparse matrix (will be converted to a COO matrix, but not to a dense matrix)

@param mode: the mode to be used. Possible values are:

C{“directed”} - the graph will be directed and a matrix element specifies the weight of the corresponding edge.
C{“undirected”} - the graph will be undirected and a matrix element specifies the weight of the corresponding edge. The matrix must be symmetric.
C{“max”} - undirected graph will be created and the weight of the edge between vertex M{i} and M{j} is M{max(A(i,j), A(j,i))}
C{“min”} - like C{“max”}, but with M{min(A(i,j), A(j,i))}
C{“plus”} - like C{“max”}, but with M{A(i,j) + A(j,i)}
C{“upper”} - undirected graph with the upper right triangle of the matrix (including the diagonal)
C{“lower”} - undirected graph with the lower left triangle of the matrix (including the diagonal)

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

@param attr: the name of the edge attribute that stores the edge

weights.

@param loops: specifies how to handle loop edges. When C{False} or

C{“ignore”}, the diagonal of the adjacency matrix will be ignored. When C{True} or C{“once”}, the diagonal is assumed to contain the weight of the corresponding loop edge. When C{“twice”}, the diagonal is assumed to contain I{twice} the weight of the corresponding loop edge.

vfGraph.add_edge(source, target, **kwds)[source]¶

Adds a single edge to the graph.

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

The performance cost of adding a single edge or several edges to a graph is similar. Thus, when adding several edges, a single C{add_edges()} call is more efficient than multiple C{add_edge()} calls.

@param source: the source vertex of the edge or its name. @param target: the target vertex of the edge or its name.

@return: the newly added edge as an L{Edge} object. Use: C{add_edges([(source, target)])} if you don’t need the L{Edge} object and want to avoid the overhead of creating it.

vfGraph.add_edges(es, attributes=None)[source]¶

Adds some edges to the graph.

@param 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.
@param attributes: dict of sequences, each of length equal to the: number of edges to be added, containing the attributes of the new edges.

vfGraph.add_vertex(name=None, **kwds)[source]¶

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

@return: the newly added vertex as a L{Vertex} object. Use: C{add_vertices(1)} if you don’t need the L{Vertex} object and want to avoid the overhead of creating t.

vfGraph.add_vertices(n, attributes=None)[source]¶

Adds some vertices to the graph.

Note that if C{n} is a sequence of strings, indicating the names of the new vertices, and attributes has a key C{name}, the two conflict. In that case the attribute will be applied.

@param n: the number of vertices to be added, or the name of a single: vertex to be added, or a sequence of strings, each corresponding to the name of a vertex to be added. Names will be assigned to the C{name} vertex attribute.
@param attributes: dict of sequences, each of length equal to the: number of vertices to be added, containing the attributes of the new vertices. If n is a string (so a single vertex is added), then the values of this dict are the attributes themselves, but if n=1 then they have to be lists of length 1.

vfGraph.adhesion(target=-1, checks=True)¶

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.

@param source: the source vertex involved in the calculation. @param target: the target vertex involved in the calculation. @param checks: if the whole graph connectivity is calculated and this is

C{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 C{True}. The parameter is ignored if the connectivity between two given vertices is computed.

@return: the edge connectivity

vfGraph.all_minimal_st_separators()¶

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

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

B{Reference}: Anne Berry, Jean-Paul Bordat and Olivier Cogis: Generating all the minimal separators of a graph. In: Peter Widmayer, Gabriele Neyer and Stephan Eidenbenz (eds.): Graph-theoretic concepts in computer science, 1665, 167-172, 1999. Springer.

@return: a list where each item lists the vertex indices of a given: minimal s-t separator.

vfGraph.all_st_cuts(source, target)[source]¶

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.

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

@param source: the source vertex ID @param target: the target vertex ID @return: a list of L{Cut} objects.

vfGraph.all_st_mincuts(source, target, capacity=None)[source]¶

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.

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

@param source: the source vertex ID @param target: the target vertex ID @param capacity: the edge capacities (weights). If C{None}, all

edges have equal weight. May also be an attribute name.

@return: a list of L{Cut} objects.

vfGraph.alpha()¶

Returns the independence number of the graph.

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

@see: L{largest_independent_vertex_sets()} for the largest independent: vertex sets

vfGraph.are_adjacent(v2)¶

Decides whether two given vertices are directly connected.

@param v1: the ID or name of the first vertex @param v2: the ID or name of the second vertex @return: C{True} if there exists an edge from v1 to v2, C{False}

otherwise.

vfGraph.are_connected(*args, **kwds)[source]¶: Deprecated alias to L{Graph.are_adjacent()}.

vfGraph.articulation_points()¶

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.

vfGraph.as_directed(*args, **kwds)[source]¶: Returns a directed copy of this graph. Arguments are passed on to L{GraphBase.to_directed()} that is invoked on the copy.

vfGraph.as_undirected(*args, **kwds)[source]¶: Returns an undirected copy of this graph. Arguments are passed on to L{GraphBase.to_undirected()} that is invoked on the copy.

vfGraph.assortativity(types2=None, directed=True, normalized=True, weights=None)¶

Returns the assortativity of the graph based on numeric properties of the vertices.

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

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

B{References}

Newman MEJ: Mixing patterns in networks, I{Phys Rev E} 67:026126, 2003.

Newman MEJ: Assortative mixing in networks, I{Phys Rev Lett} 89:208701, 2002.

@param types1: vertex types in a list or the name of a vertex attribute: holding vertex types. Types are ideally denoted by numeric values.
@param types2: in directed assortativity calculations, each vertex can: have an out-type and an in-type. In this case, I{types1} contains the out-types and this parameter contains the in-types in a list or the name of a vertex attribute. If C{None}, it is assumed to be equal to I{types1}.

@param directed: whether to consider edge directions or not. @param normalized: whether to compute the normalized covariance, i.e.

Pearson correlation. Supply True here to compute the standard assortativity.

@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.

@return: the assortativity coefficient

@see: L{assortativity_degree()} when the types are the vertex degrees

vfGraph.assortativity_degree()¶

Returns the assortativity of a graph based on vertex degrees.

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

@param directed: whether to consider edge directions for directed graphs: or not. This argument is ignored for undirected graphs.

@return: the assortativity coefficient

@see: L{assortativity()}

vfGraph.assortativity_nominal(directed=True, normalized=True, weights=None)¶

Returns the assortativity of the graph based on vertex categories.

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

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

B{Reference}: Newman MEJ: Mixing patterns in networks, I{Phys Rev E} 67:026126, 2003.

@param types: vertex types in a list or the name of a vertex attribute: holding vertex types. Types should be denoted by numeric values.

@param directed: whether to consider edge directions or not. @param normalized: whether to compute the (usual) normalized assortativity.

The unnormalized version is identical to modularity. Supply True here to compute the standard assortativity.

@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.

@return: the assortativity coefficient

vfGraph.attributes()¶: @return: the attribute name list of the graph

vfGraph.authority_score(scale=True, arpack_options=None, return_eigenvalue=False)¶

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

@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.
@param arpack_options: an L{ARPACKOptions} object used to fine-tune: the ARPACK eigenvector calculation. If omitted, the module-level variable called C{arpack_options} is used.

@param return_eigenvalue: whether to return the largest eigenvalue @return: the authority scores in a list and optionally the largest eigenvalue

as a second member of a tuple

@see: hub_score()

vfGraph.automorphism_group(color=None)¶

Calculates the generators of the automorphism group of a graph using the BLISS isomorphism algorithm.

The generator set may not be minimal and may depend on the splitting heuristics. The generators are permutations represented using zero-based indexing.

@param sh: splitting heuristics for graph as a case-insensitive string,

with the following possible values:

C{“f”}: first non-singleton cell

C{“fl”}: first largest non-singleton cell

C{“fs”}: first smallest non-singleton cell

C{“fm”}: first maximally non-trivially connected non-singleton cell

C{“flm”}: largest maximally non-trivially connected non-singleton cell

C{“fsm”}: smallest maximally non-trivially connected non-singleton cell

@param color: optional vector storing a coloring of the vertices

with respect to which the isomorphism is computed. If C{None}, all vertices have the same color.

@return: a list of integer vectors, each vector representing an automorphism

group of the graph.

vfGraph.average_path_length(unconn=True, weights=None)¶

Calculates the average path length in a graph.

@param directed: whether to consider directed paths in case of a: directed graph. Ignored for undirected graphs.
@param unconn: what to do when the graph is unconnected. If C{True},: the average of the geodesic lengths in the components is calculated. Otherwise for all unconnected vertex pairs, a path length equal to the number of vertices is used.
@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.

@return: the average path length in the graph

vfGraph.betweenness(directed=True, cutoff=None, weights=None, sources=None, targets=None)¶

Calculates or estimates the betweenness of vertices in a graph.

Also supports calculating betweenness with shortest path length cutoffs or considering shortest paths only from certain source vertices or to certain target vertices.

Keyword arguments: @param vertices: the vertices for which the betweennesses must be returned.

If C{None}, assumes all of the vertices in the graph.

@param directed: whether to consider directed paths. @param cutoff: if it is an integer, only paths less than or equal to this

length are considered, effectively resulting in an estimation of the betweenness for the given vertices. If C{None}, the exact betweenness is returned.

@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.
@param sources: the set of source vertices to consider when calculating: shortest paths.
@param targets: the set of target vertices to consider when calculating: shortest paths.

@return: the (possibly cutoff-limited) betweenness of the given vertices in a list

vfGraph.bfs(mode='out')¶

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

@param vid: the root vertex ID @param mode: either C{“in”} or C{“out”} or C{“all”}, ignored

for undirected graphs.

@return: a tuple with the following items:

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

vfGraph.bfsiter(mode='out', advanced=False)¶

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

@param vid: the root vertex ID @param mode: either C{“in”} or C{“out”} or C{“all”}. @param advanced: if C{False}, the iterator returns the next

vertex in BFS order in every step. If C{True}, the iterator returns the distance of the vertex from the root and the parent of the vertex in the BFS tree as well.

@return: the BFS iterator as an L{igraph.BFSIter} object.

vfGraph.bibcoupling()¶

Calculates bibliographic coupling scores for given vertices in a graph.

@param vertices: the vertices to be analysed. If C{None}, all vertices: will be considered.

@return: bibliographic coupling scores for all given vertices in a matrix.

vfGraph.biconnected_components(return_articulation_points=False)[source]¶

Calculates the biconnected components of the graph.

@param return_articulation_points: whether to return the articulation: points as well
@return: a L{VertexCover} object describing the biconnected components,: and optionally the list of articulation points as well

vfGraph.bipartite_projection(types='type', multiplicity=True, probe1=-1, which='both')[source]¶

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

@param types: an igraph vector containing the vertex types, or an: attribute name. Anything that evalulates to C{False} corresponds to vertices of the first kind, everything else to the second kind.
@param multiplicity: if C{True}, then igraph keeps the multiplicity of: the edges in the projection in an edge attribute called C{“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.
@param 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.
@param 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). C{False} is equivalent to 0 and C{True} is equivalent to 1. Any other value means that both projections will be returned in a tuple.
@return: a tuple containing the two projected one-mode graphs if C{which}: is not 1 or 2, or the projected one-mode graph specified by the C{which} argument if its value is 0, 1, C{False} or C{True}.

vfGraph.bipartite_projection_size(types='type', *args, **kwds)[source]¶

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.

@param types: an igraph vector containing the vertex types, or an: attribute name. Anything that evalulates to C{False} corresponds to vertices of the first kind, everything else to the second kind.
@return: 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.

vfGraph.blocks(return_articulation_points=False)[source]¶

Calculates the biconnected components of the graph.

@param return_articulation_points: whether to return the articulation: points as well
@return: a L{VertexCover} object describing the biconnected components,: and optionally the list of articulation points as well

vfGraph.bridges()¶

Returns the list of bridges in the graph.

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

vfGraph.build_graph(adj_mat)[source]¶: build sparse diffusion graph. The adjacency matrix needs to preserves divergence.

vfGraph.canonical_permutation(color=None)¶

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

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

See U{https://users.aalto.fi/~tjunttil/bliss/} for more information about the BLISS algorithm and canonical permutations.

@param sh: splitting heuristics for graph as a case-insensitive string,

with the following possible values:

C{“f”}: first non-singleton cell

C{“fl”}: first largest non-singleton cell

C{“fs”}: first smallest non-singleton cell

C{“fm”}: first maximally non-trivially connected non-singleton cell

C{“flm”}: largest maximally non-trivially connected non-singleton cell

C{“fsm”}: smallest maximally non-trivially connected non-singleton cell

@param color: optional vector storing a coloring of the vertices

with respect to which the isomorphism is computed. If C{None}, all vertices have the same color.

@return: a permutation vector containing vertex IDs. Vertex 0 in the original

graph will be mapped to an ID contained in the first element of this vector; vertex 1 will be mapped to the second and so on.

vfGraph.chordal_completion(alpham1=None)¶

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

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

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

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

@param alpha: the alpha vector from the result of calling: L{maximum_cardinality_search()} on the graph. Useful only if you already have the alpha vector; simply passing C{None} here will make igraph calculate the alpha vector on its own.
@param alpham1: the inverse alpha vector from the result of calling: L{maximum_cardinality_search()} on the graph. Useful only if you already have the inverse alpha vector; simply passing C{None} here will make igraph calculate the inverse alpha vector on its own.
@return: the list of edges to add to the graph; each item in the list is a: source-target pair of vertex indices.

vfGraph.clear()[source]¶

Clears the graph, deleting all vertices, edges, and attributes.

@see: L{GraphBase.delete_vertices} and L{Graph.delete_edges}.

vfGraph.clique_number()¶

Returns the clique number of the graph.

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

@see: L{largest_cliques()} for the largest cliques.

vfGraph.cliques(max=0, max_results=None)¶

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

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

@param min: the minimum size of cliques to be returned. If zero or: negative, no lower bound will be used.
@param max: the maximum size of cliques to be returned. If zero or: negative, no upper bound will be used.
@param max_results: the maximum number of results to return. C{None}: means no limit on the number of results.

vfGraph.closeness(mode='all', cutoff=None, weights=None, normalized=True)¶

Calculates the closeness centralities of given vertices in a graph.

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

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

@param vertices: the vertices for which the closenesses must: be returned. If C{None}, uses all of the vertices in the graph.
@param mode: must be one of C{“in”}, C{“out”} and C{“all”}. C{“in”} means: that the length of the incoming paths, C{“out”} means that the length of the outgoing paths must be calculated. C{“all”} means that both of them must be calculated.
@param cutoff: if it is an integer, only paths less than or equal to this: length are considered, effectively resulting in an estimation of the closeness for the given vertices (which is always an underestimation of the real closeness, since some vertex pairs will appear as disconnected even though they are connected).. If C{None}, the exact closeness is returned.
@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.
@param normalized: Whether to normalize the raw closeness scores by: multiplying by the number of vertices minus one.

@return: the calculated closenesses in a list

vfGraph.clusters(mode='strong')[source]¶: Deprecated alias to L{Graph.connected_components()}.

vfGraph.cocitation()¶

Calculates cocitation scores for given vertices in a graph.

@param vertices: the vertices to be analysed. If C{None}, all vertices: will be considered.

@return: cocitation scores for all given vertices in a matrix.

vfGraph.cohesion(target=-1, checks=True, neighbors='error')¶

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.

@param source: the source vertex involved in the calculation. @param target: the target vertex involved in the calculation. @param checks: if the whole graph connectivity is calculated and this is

C{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 C{True}. The parameter is ignored if the connectivity between two given vertices is computed.

@param neighbors: tells igraph what to do when the two vertices are: connected. C{“error”} raises an exception, C{“negative”} returns a negative value, C{“number_of_nodes”} or C{“nodes”} returns the number of nodes, or C{“ignore”} ignores the edge.

@return: the vertex connectivity

vfGraph.cohesive_blocks()[source]¶

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.

@return: an instance of L{CohesiveBlocks}. See the documentation of: L{CohesiveBlocks} for more information.

@see: L{CohesiveBlocks}

vfGraph.community_edge_betweenness(clusters=None, directed=True, weights=None)[source]¶

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.

When edge weights are given, the ratio of betweenness and weight values is used to choose which edges to remove first, as described in M. E. J. Newman: Analysis of Weighted Networks (2004), Section C. Thus, edges with large weights are treated as strong connections, and will be removed later than weak connections having similar betweenness. Weights are also used for calculating modularity.

@param 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 C{None}, the dendrogram is cut at the level that maximizes the modularity when the graph is unweighted; otherwise the dendrogram is cut at at a single cluster (because cluster count selection based on modularities does not make sense for this method if not all the weights are equal).
@param directed: whether the directionality of the edges should be: taken into account or not.
@param weights: name of an edge attribute or a list containing: edge weights. Higher weights indicate stronger connections.
@return: a L{VertexDendrogram} object, initally cut at the maximum: modularity or at the desired number of clusters.

vfGraph.community_fastgreedy(weights=None)[source]¶

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.

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

@param weights: edge attribute name or a list containing edge: weights

@return: an appropriate L{VertexDendrogram} object.

vfGraph.community_fluid_communities(no_of_communities)[source]¶

Community detection based on fluids interacting on the graph.

The algorithm is based on the simple idea of several fluids interacting in a non-homogeneous environment (the graph topology), expanding and contracting based on their interaction and density. Weighted graphs are not supported.

This function implements the community detection method described in: Parés F, Gasulla DG, et. al. (2018) Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm.

@param no_of_communities: The number of communities to be found. Must be: greater than 0 and fewer than or equal to the number of vertices in the graph.

@return: an appropriate L{VertexClustering} object.

vfGraph.community_infomap(edge_weights=None, vertex_weights=None, trials=10)[source]¶

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

B{References}

M. Rosvall and C. T. Bergstrom: Maps of information flow reveal community structure in complex networks, I{PNAS} 105, 1118 (2008). U{https://doi.org/10.1073/pnas.0706851105}, U{https://arxiv.org/abs/0707.0609}.

M. Rosvall, D. Axelsson, and C. T. Bergstrom: The map equation, I{Eur Phys. J Special Topics} 178, 13 (2009). U{https://doi.org/10.1140/epjst/e2010-01179-1}, U{https://arxiv.org/abs/0906.1405}.

@param edge_weights: name of an edge attribute or a list containing: edge weights.
@param vertex_weights: name of a vertex attribute or a list containing: vertex weights.

@param trials: the number of attempts to partition the network. @return: an appropriate L{VertexClustering} object with an extra attribute

called C{codelength} that stores the code length determined by the algorithm.

vfGraph.community_label_propagation(weights=None, initial=None, fixed=None)[source]¶

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.

Also note that the community _labels_ (numbers) have no semantic meaning and igraph is free to re-number communities. If you use fixed labels, igraph may still re-number the communities, but co-community membership constraints will be respected: if you had two vertices with fixed labels that belonged to the same community, they will still be in the same community at the end. Similarly, if you had two vertices with fixed labels that belonged to different communities, they will still be in different communities at the end.

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

@param weights: name of an edge attribute or a list containing: edge weights
@param initial: name of a vertex attribute or a list containing: the initial vertex labels. Labels are identified by integers from zero to M{n-1} where M{n} is the number of vertices. Negative numbers may also be present in this vector, they represent unlabeled vertices.
@param fixed: a list of booleans for each vertex. C{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. It may also be the name of a vertex attribute; each attribute value will be interpreted as a Boolean.

@return: an appropriate L{VertexClustering} object.

vfGraph.community_leading_eigenvector(clusters=None, weights=None, arpack_options=None)[source]¶

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.

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

@param clusters: the desired number of communities. If C{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.
@param weights: name of an edge attribute or a list containing: edge weights.
@param arpack_options: an L{ARPACKOptions} object used to fine-tune: the ARPACK eigenvector calculation. If omitted, the module-level variable called C{arpack_options} is used.

@return: an appropriate L{VertexClustering} object.

vfGraph.community_leiden(objective_function='CPM', weights=None, resolution=1.0, beta=0.01, initial_membership=None, n_iterations=2, node_weights=None, node_in_weights=None, **kwds)[source]¶

Finds the community structure of the graph using the Leiden algorithm of Traag, van Eck & Waltman.

B{Reference}: Traag, V. A., Waltman, L., & van Eck, N. J. (2019). From Louvain to Leiden: guaranteeing well-connected communities. I{Scientific Reports}, 9(1), 5233. doi: 10.1038/s41598-019-41695-z

@param objective_function: whether to use the Constant Potts: Model (CPM) or modularity. Must be either C{“CPM”} or C{“modularity”}.
@param weights: edge weights to be used. Can be a sequence or: iterable or even an edge attribute name.
@param resolution: the resolution parameter to use. Higher resolutions: lead to more smaller communities, while lower resolutions lead to fewer larger communities.
@param beta: parameter affecting the randomness in the Leiden: algorithm. This affects only the refinement step of the algorithm.
@param initial_membership: if provided, the Leiden algorithm: will try to improve this provided membership. If no argument is provided, the aglorithm simply starts from the singleton partition.
@param n_iterations: the number of iterations to iterate the Leiden: algorithm. Each iteration may improve the partition further. Using a negative number of iterations will run until a stable iteration is encountered (i.e. the quality was not increased during that iteration).
@param node_weights: the node weights used in the Leiden algorithm.: If this is not provided, it will be automatically determined on the basis of whether you want to use CPM or modularity. If you do provide this, please make sure that you understand what you are doing.
@param node_in_weights: the inbound node weights used in the directed: variant of the Leiden algorithm. If this is not provided, it will be automatically determined on the basis of whether you want to use CPM or modularity. If you do provide this, please make sure that you understand what you are doing.
@return: an appropriate L{VertexClustering} object with an extra attribute: called C{quality} that stores the value of the internal quality function optimized by the algorithm.

vfGraph.community_multilevel(weights=None, return_levels=False, resolution=1)[source]¶

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 shrunk to a single vertex (while keeping the total weight of the incident edges) and the process continues on the next level. The algorithm stops when it is not possible to increase the modularity anymore after shrinking the communities to vertices.

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

B{Reference}: VD Blondel, J-L Guillaume, R Lambiotte and E Lefebvre: Fast unfolding of community hierarchies in large networks, I{J Stat Mech} P10008 (2008). U{https://arxiv.org/abs/0803.0476}

@param weights: edge attribute name or a list containing edge: weights
@param return_levels: if C{True}, the communities at each level are: returned in a list. If C{False}, only the community structure with the best modularity is returned.
@param resolution: the resolution parameter to use in the modularity: measure. Smaller values result in a smaller number of larger clusters, while higher values yield a large number of small clusters. The classical modularity measure assumes a resolution parameter of 1.
@return: a list of L{VertexClustering} objects, one corresponding to: each level (if C{return_levels} is C{True}), or a L{VertexClustering} corresponding to the best modularity.

vfGraph.community_optimal_modularity(*args, **kwds)[source]¶

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.

@return: the calculated membership vector and the corresponding: modularity in a tuple.

vfGraph.community_spinglass(*args, **kwds)[source]¶

Finds the community structure of the graph according to the spinglass community detection method of Reichardt & Bornholdt.

B{References}

Reichardt J and Bornholdt S: Statistical mechanics of community detection. I{Phys Rev E} 74:016110 (2006). U{https://arxiv.org/abs/cond-mat/0603718}.

Traag VA and Bruggeman J: Community detection in networks with positive and negative links. I{Phys Rev E} 80:036115 (2009). U{https://arxiv.org/abs/0811.2329}.

@keyword weights: edge weights to be used. Can be a sequence or: iterable or even an edge attribute name.
@keyword 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.
@keyword parupdate: whether to update the spins of the vertices in: parallel (synchronously) or not

@keyword start_temp: the starting temperature @keyword stop_temp: the stop temperature @keyword cool_fact: cooling factor for the simulated annealing @keyword update_rule: specifies the null model of the simulation.

Possible values are C{“config”} (a random graph with the same vertex degrees as the input graph) or C{“simple”} (a random graph with the same number of edges)

@keyword 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.
@keyword 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 C{implementation} to C{“neg”}
@keyword 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.

@return: an appropriate L{VertexClustering} object.

vfGraph.community_voronoi(lengths=None, weights=None, mode='out', radius=None)[source]¶

Finds communities using Voronoi partitioning.

This function finds communities using a Voronoi partitioning of vertices based on the given edge lengths divided by the edge clustering coefficient. The generator vertices are chosen to be those with the largest local relative density within a radius, with the local relative density of a vertex defined as C{s * m / (m + k)}, where C{s} is the strength of the vertex, C{m} is the number of edges within the vertex’s first order neighborhood, while C{k} is the number of edges with only one endpoint within this neighborhood.

B{References}

Deritei et al., Community detection by graph Voronoi diagrams, I{New Journal of Physics} 16, 063007 (2014). U{https://doi.org/10.1088/1367-2630/16/6/063007}.

Molnár et al., Community Detection in Directed Weighted Networks using Voronoi Partitioning, I{Scientific Reports} 14, 8124 (2024). U{https://doi.org/10.1038/s41598-024-58624-4}.

@param lengths: edge lengths, or C{None} to consider all edges as having: unit length. Voronoi partitioning will use edge lengths equal to lengths / ECC where ECC is the edge clustering coefficient.
@param weights: edge weights, or C{None} to consider all edges as having: unit weight. Weights are used when selecting generator points, as well as for computing modularity.
@param mode: specifies how to use the direction of edges when computing: distances from generator points. If C{“out”} (the default), distances from generator points to all other nodes are considered following the direction of edges. If C{“in”}, distances are computed in the reverse direction (i.e., from all nodes to generator points). If C{“all”}, edge directions are ignored and the graph is treated as undirected. This parameter is ignored for undirected graphs.
@param radius: the radius/resolution to use when selecting generator points.: The larger this value, the fewer partitions there will be. Pass C{None} to automatically select the radius that maximizes modularity.
@return: an appropriate L{VertexClustering} object with an extra attribute: called C{generators} (the generator vertices).

vfGraph.community_walktrap(weights=None, steps=4)[source]¶

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.

B{Reference}: Pascal Pons, Matthieu Latapy: Computing communities in large networks using random walks, U{https://arxiv.org/abs/physics/0512106}.

@param weights: name of an edge attribute or a list containing: edge weights

@param steps: length of random walks to perform

@return: a L{VertexDendrogram} object, initially cut at the maximum: modularity.

vfGraph.complementer()¶

Returns the complementer of the graph

@param loops: whether to include loop edges in the complementer. @return: the complementer of the graph

vfGraph.components(mode='strong')[source]¶

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

@param mode: must be either C{“strong”} or C{“weak”}, depending on the: connected components being sought. Optional, defaults to C{“strong”}.

@return: a L{VertexClustering} object

vfGraph.compose()¶: Returns the composition of two graphs.

vfGraph.connected_components(mode='strong')[source]¶

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

@param mode: must be either C{“strong”} or C{“weak”}, depending on the: connected components being sought. Optional, defaults to C{“strong”}.

@return: a L{VertexClustering} object

vfGraph.constraint(weights=None)¶

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

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

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

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

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

For isolated vertices, constraint is undefined.

@param vertices: the vertices to be analysed or C{None} for all vertices. @param weights: weights associated to the edges. Can be an attribute name

as well. If C{None}, every edge will have the same weight.

@return: constraint scores for all given vertices in a matrix.

vfGraph.contract_vertices(combine_attrs=None)¶

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

@param mapping: numeric vector which gives the mapping between old and: new vertex IDs. Vertices having the same new vertex ID in this vector will be remapped into a single new vertex. It is safe to pass the membership vector of a L{VertexClustering} object here.
@param combine_attrs: specifies how to combine the attributes of: the vertices being collapsed into a single one. If it is C{None}, all the attributes will be lost. If it is a function, the attributes of the vertices will be collected and passed on to that function which will return the new attribute value that has to be assigned to the single collapsed vertex. It can also be one of the following string constants which define built-in collapsing functions: C{sum}, C{prod}, C{mean}, C{median}, C{max}, C{min}, C{first}, C{last}, C{random}. You can also specify different combination functions for different attributes by passing a dict here which maps attribute names to functions. See L{simplify()} for more details.

@return: C{None}. @see: L{simplify()}

vfGraph.convergence_degree()¶: Undocumented (yet).

vfGraph.convergence_field_size()¶: Undocumented (yet).

classmethod vfGraph.convert_to_class(obj)[source]¶

vfGraph.copy()¶

Creates a copy of the graph.

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

vfGraph.coreness()¶

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

The M{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 M{k} if it is a member of the M{k}-core but not a member of the M{k+1}-core.

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

@param mode: whether to compute the in-corenesses (C{“in”}), the: out-corenesses (C{“out”}) or the undirected corenesses (C{“all”}). Ignored and assumed to be C{“all”} for undirected graphs.

@return: the corenesses for each vertex.

vfGraph.count_automorphisms(color=None)¶

Calculates the number of automorphisms of a graph using the BLISS isomorphism algorithm.

See U{https://users.aalto.fi/~tjunttil/bliss/} for more information about the BLISS algorithm and canonical permutations.

@param sh: splitting heuristics for graph as a case-insensitive string,

with the following possible values:

C{“f”}: first non-singleton cell

C{“fl”}: first largest non-singleton cell

C{“fs”}: first smallest non-singleton cell

C{“fm”}: first maximally non-trivially connected non-singleton cell

C{“flm”}: largest maximally non-trivially connected non-singleton cell

C{“fsm”}: smallest maximally non-trivially connected non-singleton cell

@param color: optional vector storing a coloring of the vertices

with respect to which the isomorphism is computed. If C{None}, all vertices have the same color.

@return: the number of automorphisms of the graph.

vfGraph.count_automorphisms_vf2(color=None, edge_color=None, node_compat_fn=None, edge_compat_fn=None)[source]¶

Returns the number of automorphisms of the graph.

This function simply calls C{count_isomorphisms_vf2} with the graph itgraph. See C{count_isomorphisms_vf2} for an explanation of the parameters.

@return: the number of automorphisms of the graph @see: Graph.count_isomorphisms_vf2

vfGraph.count_isomorphisms_vf2(color1=None, color2=None, edge_color1=None, edge_color2=None, node_compat_fn=None, edge_compat_fn=None)¶

Determines the number of isomorphisms between the graph and another one

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

@param other: the other graph. If C{None}, the number of automorphisms: will be returned.
@param color1: optional vector storing the coloring of the vertices of: the first graph. If C{None}, all vertices have the same color.
@param color2: optional vector storing the coloring of the vertices of: the second graph. If C{None}, all vertices have the same color.
@param edge_color1: optional vector storing the coloring of the edges of: the first graph. If C{None}, all edges have the same color.
@param edge_color2: optional vector storing the coloring of the edges of: the second graph. If C{None}, all edges have the same color.
@param node_compat_fn: a function that receives the two graphs and two: node indices (one from the first graph, one from the second graph) and returns C{True} if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or C{False} otherwise. This can be used to restrict the set of isomorphisms based on node-specific criteria that are too complicated to be represented by node color vectors (i.e. the C{color1} and C{color2} parameters). C{None} means that every node is compatible with every other node.
@param edge_compat_fn: a function that receives the two graphs and two: edge indices (one from the first graph, one from the second graph) and returns C{True} if the edges given by the two indices are compatible (i.e. they could be matched to each other) or C{False} otherwise. This can be used to restrict the set of isomorphisms based on edge-specific criteria that are too complicated to be represented by edge color vectors (i.e. the C{edge_color1} and C{edge_color2} parameters). C{None} means that every edge is compatible with every other node.
@return: the number of isomorphisms between the two given graphs (or the: number of automorphisms if C{other} is C{None}.

vfGraph.count_multiple()¶

Counts the multiplicities of the given edges.

@param edges: edge indices for which we want to count their: multiplicity. If C{None}, all edges are counted.

@return: the multiplicities of the given edges as a list.

vfGraph.count_subisomorphisms_vf2(color1=None, color2=None, edge_color1=None, edge_color2=None, node_compat_fn=None, edge_compat_fn=None)¶

Determines the number of subisomorphisms between the graph and another one

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

@param other: the other graph. @param color1: optional vector storing the coloring of the vertices of

the first graph. If C{None}, all vertices have the same color.

@param color2: optional vector storing the coloring of the vertices of: the second graph. If C{None}, all vertices have the same color.
@param edge_color1: optional vector storing the coloring of the edges of: the first graph. If C{None}, all edges have the same color.
@param edge_color2: optional vector storing the coloring of the edges of: the second graph. If C{None}, all edges have the same color.
@param node_compat_fn: a function that receives the two graphs and two: node indices (one from the first graph, one from the second graph) and returns C{True} if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or C{False} otherwise. This can be used to restrict the set of isomorphisms based on node-specific criteria that are too complicated to be represented by node color vectors (i.e. the C{color1} and C{color2} parameters). C{None} means that every node is compatible with every other node.
@param edge_compat_fn: a function that receives the two graphs and two: edge indices (one from the first graph, one from the second graph) and returns C{True} if the edges given by the two indices are compatible (i.e. they could be matched to each other) or C{False} otherwise. This can be used to restrict the set of isomorphisms based on edge-specific criteria that are too complicated to be represented by edge color vectors (i.e. the C{edge_color1} and C{edge_color2} parameters). C{None} means that every edge is compatible with every other node.

@return: the number of subisomorphisms between the two given graphs

vfGraph.cut_vertices()¶

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.

vfGraph.decompose(maxcompno=None, minelements=1)¶

Decomposes the graph into subgraphs.

@param mode: must be either C{“strong”} or C{“weak”}, depending on: the clusters being sought. Optional, defaults to C{“strong”}.
@param maxcompno: maximum number of components to return.: C{None} means all possible components.
@param minelements: minimum number of vertices in a component.: By setting this to 2, isolated vertices are not returned as separate components.
@return: a list of the subgraphs. Every returned subgraph is a: copy of the original.

vfGraph.degree(mode='all', loops=True)¶

Returns some vertex degrees from the graph.

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

@param vertices: a single vertex ID or a list of vertex IDs @param mode: the type of degree to be returned (C{“out”} for

out-degrees, C{“in”} for in-degrees or C{“all”} for the sum of them).

@param loops: whether self-loops should be counted.

vfGraph.degree_distribution(bin_width=1, *args, **kwds)[source]¶

Calculates the degree distribution of the graph.

Unknown keyword arguments are directly passed to L{GraphBase.degree}.

@param bin_width: the bin width of the histogram @return: a histogram representing the degree distribution of the

graph.

vfGraph.delete_edges(*args, **kwds)[source]¶

Deletes some edges from the graph.

The set of edges to be deleted is determined by the positional and keyword arguments. If the function is called without any arguments, all edges are deleted. If any keyword argument is present, or the first positional argument is callable, an edge sequence is derived by calling L{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:

Deprecation notice: C{delete_edges(None)} has been replaced by C{delete_edges()} - with no arguments - since igraph 0.8.3.

C{None} - deletes all edges (deprecated since 0.8.3)

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.

vfGraph.delete_vertices()¶

Deletes vertices and all its edges from the graph.

@param vs: a single vertex ID or the list of vertex IDs: to be deleted. No argument deletes all vertices.

vfGraph.density(weights=None)¶

Calculates the density of the graph.

@param loops: whether to take loops into consideration. If C{True},: the algorithm assumes that there might be some loops in the graph and calculates the density accordingly. If C{False}, the algorithm assumes that there can’t be any loops.
@param weights: weights associated to the edges. Can be an attribute name: as well. If C{None}, every edge will have the same weight.

@return: the (weighted or unweighted) density of the graph.

vfGraph.dfs(vid, mode=1)[source]¶

Conducts a depth first search (DFS) on the graph.

@param vid: the root vertex ID @param mode: either C{“in”} or C{“out”} or C{“all”}, ignored

for undirected graphs.

@return: a tuple with the following items:

The vertex IDs visited (in order)
The parent of every vertex in the DFS

vfGraph.dfsiter(mode='out', advanced=False)¶

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

@param vid: the root vertex ID @param mode: either C{“in”} or C{“out”} or C{“all”}. @param advanced: if C{False}, the iterator returns the next

vertex in DFS order in every step. If C{True}, the iterator returns the distance of the vertex from the root and the parent of the vertex in the DFS tree as well.

@return: the DFS iterator as an L{igraph.DFSIter} object.

vfGraph.diameter(unconn=True, weights=None)¶

Calculates the diameter of the graph.

@param directed: whether to consider directed paths. @param unconn: if C{True} and the graph is unconnected, the

longest geodesic within a component will be returned. If C{False} and the graph is unconnected, the result is the number of vertices if there are no weights or infinity if there are weights.

@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.

@return: the diameter

vfGraph.difference()¶: Subtracts the given graph from the original

vfGraph.disjoint_union(other)[source]¶

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

@param other: graph or list of graphs to be united with the current one. @return: the disjoint union graph

vfGraph.distances(target=None, weights=None, mode='out', algorithm='auto')¶

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 non-negative. Otherwise, the Bellman-Ford algorithm is used if the number of requested source vertices is smaller than 100 and Johnson’s algorithm is used otherwise.

@param source: a list containing the source vertex IDs which should be: included in the result. If C{None}, all vertices will be considered.
@param target: a list containing the target vertex IDs which should be: included in the result. If C{None}, all vertices will be considered.
@param weights: a list containing the edge weights. It can also be: an attribute name (edge weights are retrieved from the given attribute) or C{None} (all edges have equal weight).
@param mode: the type of shortest paths to be used for the: calculation in directed graphs. C{“out”} means only outgoing, C{“in”} means only incoming paths. C{“all”} means to consider the directed graph as an undirected one.
@param algorithm: the shortest path algorithm to use. C{“auto”} selects an: algorithm automatically based on whether the graph has negative weights or not. C{“dijkstra”} uses Dijkstra’s algorithm. C{“bellman_ford”} uses the Bellman-Ford algorithm. C{“johnson”} uses Johnson’s algorithm. Ignored for unweighted graphs.

@return: the shortest path lengths for given vertices in a matrix

vfGraph.diversity(weights=None)¶

Calculates the structural diversity index of the vertices.

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

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

B{Reference}: Eagle N, Macy M and Claxton R: Network diversity and economic development, I{Science} 328, 1029-1031, 2010.

@param vertices: the vertices for which the diversity indices must: be returned. If C{None}, uses all of the vertices in the graph.
@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.
@return: the calculated diversity indices in a list, or a single number if: a single vertex was supplied.

vfGraph.dominator(mode='out')¶

Returns the dominator tree from the given root node

@param vid: the root vertex ID @param mode: either C{“in”} or C{“out”} @return: a list containing the dominator tree for the current graph.

vfGraph.dyad_census(*args, **kwds)[source]¶

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 I{a} to I{b} and also from I{b} to I{a}), asymmetric (there is an edge from I{a} to I{b} or from I{b} to I{a} but not the other way round) and null (there is no connection between I{a} and I{b}).

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

@return: a L{DyadCensus} object.

vfGraph.eccentricity(mode='all', weights=None)¶

Calculates the eccentricities of given vertices in a graph.

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

@param vertices: the vertices for which the eccentricity scores must: be returned. If C{None}, uses all of the vertices in the graph.
@param mode: must be one of C{“in”}, C{“out”} and C{“all”}. C{“in”} means: that edge directions are followed; C{“out”} means that edge directions are followed the opposite direction; C{“all”} means that directions are ignored. The argument has no effect for undirected graphs.
@param weights: a list containing the edge weights. It can also be: an attribute name (edge weights are retrieved from the given attribute) or C{None} (all edges have equal weight).
@return: the calculated eccentricities in a list, or a single number if: a single vertex was supplied.

vfGraph.ecount()¶

Counts the number of edges.

@return: the number of edges in the graph. @rtype: integer

vfGraph.edge_attributes()¶: @return: the attribute name list of the edges of the graph

vfGraph.edge_betweenness(cutoff=None, weights=None, sources=None, targets=None)¶

Calculates or estimates the edge betweennesses in a graph.

Also supports calculating edge betweenness with shortest path length cutoffs or considering shortest paths only from certain source vertices or to certain target vertices.

@param directed: whether to consider directed paths. @param cutoff: if it is an integer, only paths less than or equal to this

length are considered, effectively resulting in an estimation of the betweenness values. If C{None}, the exact betweennesses are returned.

@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.
@param sources: the set of source vertices to consider when calculating: shortest paths.
@param targets: the set of target vertices to consider when calculating: shortest paths.
@return: a list with the (exact or estimated) edge betweennesses of all: edges.

vfGraph.edge_connectivity(target=-1, checks=True)¶

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

@param source: the source vertex involved in the calculation. @param target: the target vertex involved in the calculation. @param checks: if the whole graph connectivity is calculated and this is

C{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 C{True}. The parameter is ignored if the connectivity between two given vertices is computed.

@return: the edge connectivity

vfGraph.edge_disjoint_paths(target=-1, checks=True)¶

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

@param source: the source vertex involved in the calculation. @param target: the target vertex involved in the calculation. @param checks: if the whole graph connectivity is calculated and this is

C{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 C{True}. The parameter is ignored if the connectivity between two given vertices is computed.

@return: the edge connectivity

vfGraph.eigen_adjacency(which=None, arpack_options=None)¶

vfGraph.eigenvector_centrality(scale=True, weights=None, return_eigenvalue=False, arpack_options=None)¶

Calculates the eigenvector centralities of the vertices in a graph.

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

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

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

@param directed: whether to consider edge directions in a directed: graph. Ignored for undirected graphs.
@param weights: edge weights given as a list or an edge attribute. If: C{None}, all edges have equal weight.
@param return_eigenvalue: whether to return the actual largest: eigenvalue along with the centralities
@param arpack_options: an L{ARPACKOptions} object that can be used: to fine-tune the calculation. If it is omitted, the module-level variable called C{arpack_options} is used.
@return: the eigenvector centralities in a list and optionally the: largest eigenvalue (as a second member of a tuple)

vfGraph.evcent(scale=True, weights=None, return_eigenvalue=False, arpack_options=None)¶

Calculates the eigenvector centralities of the vertices in a graph.

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

@param directed: whether to consider edge directions in a directed: graph. Ignored for undirected graphs.
@param weights: edge weights given as a list or an edge attribute. If: C{None}, all edges have equal weight.
@param return_eigenvalue: whether to return the actual largest: eigenvalue along with the centralities
@param arpack_options: an L{ARPACKOptions} object that can be used: to fine-tune the calculation. If it is omitted, the module-level variable called C{arpack_options} is used.
@return: the eigenvector centralities in a list and optionally the: largest eigenvalue (as a second member of a tuple)

vfGraph.farthest_points(unconn=True, weights=None)¶

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

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

@param directed: whether to consider directed paths. @param unconn: if C{True} and the graph is unconnected, the

longest geodesic within a component will be returned. If C{False} and the graph is unconnected, the result contains the number of vertices if there are no weights or infinity if there are weights.

@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.
@return: a triplet containing the two vertex IDs and their distance.: The IDs are C{None} if the graph is unconnected and C{unconn} is C{False}.

vfGraph.feedback_arc_set(method='eades')¶

Calculates an approximately or exactly minimal feedback arc set.

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

B{Reference}: Eades P, Lin X and Smyth WF: A fast and effective heuristic for the feedback arc set problem. In: I{Proc Inf Process Lett} 319-323, 1993.

@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name. When given, the algorithm will strive to remove lightweight edges in order to minimize the total weight of the feedback arc set.
@param method: the algorithm to use. C{“eades”} uses the greedy cycle: breaking heuristic of Eades, Lin and Smyth, which is linear in the number of edges but not necessarily optimal; however, it guarantees that the number of edges to be removed is smaller than |E|/2 - |V|/6. C{“ip”} uses the most efficient available integer programming formulation which is guaranteed to yield an optimal result. Specific integer programming formulations can be selected using C{“ip_ti”} (using triangle inequalities) and C{“ip_cg”} (a minimum set cover formulation using incremental constraint generation). Note that the minimum feedback arc set problem is NP-hard, therefore all methods that obtain exact optimal solutions are infeasibly slow on large graphs.

@return: the IDs of the edges to be removed, in a list.

vfGraph.feedback_vertex_set(method='ip')¶

Calculates a minimum feedback vertex set.

A feedback vertex set is a set of edges whose removal makes the graph acyclic. Finding a minimum feedback vertex set is an NP-hard problem both in directed and undirected graphs.

@param weights: vertex weights to be used. Can be a sequence or iterable or: even a vertex attribute name. When given, the algorithm will strive to remove lightweight vertices in order to minimize the total weight of the feedback vertex set.
@param method: the algorithm to use. C{“ip”} uses an exact integer programming: approach, and is currently the only available method.

@return: the IDs of the vertices to be removed, in a list.

classmethod vfGraph.from_graph_tool(g)[source]¶

Converts the graph from graph-tool

@param g: graph-tool Graph

classmethod vfGraph.from_networkx(vertex_attr_hashable='_nx_name')[source]¶

Converts the graph from networkx

Vertex names will be stored as a vertex_attr_hashable attribute (usually “_nx_name”, but see below). Because igraph stored vertices in an ordered manner, vertices will get new IDs from 0 up. In case of multigraphs, each edge will have an “_nx_multiedge_key” attribute, to distinguish edges that connect the same two vertices.

@param g: networkx Graph or DiGraph @param vertex_attr_hashable: attribute used to store the Python

hashable used by networkx to identify each vertex. The default value ‘_nx_name’ ensures lossless round trip conversions to/from networkx. An alternative choice is ‘name’: in that case, using strings for vertex names is recommended and, if the graph is re-exported to networkx, Graph.to_networkx(vertex_attr_hashable=”name”) must be used to recover the correct vertex nomenclature in the exported network.

vfGraph.fundamental_cycles(cutoff=None, weights=None)¶

Finds a single fundamental cycle basis of the graph

@param start_vid: when C{None} or negative, a complete fundamental cycle basis is: returned. When it is a vertex or a vertex ID, the fundamental cycles associated with the BFS tree rooted in that vertex will be returned, only for the weakly connected component containing that vertex
@param cutoff: when C{None} or negative, a complete cycle basis is returned. Otherwise: the BFS is stopped after this many steps, so the result will effectively include cycles of length M{2 * cutoff + 1} or shorter only.
@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.

@return: the cycle basis as a list of tuples containing edge IDs

vfGraph.get_adjacency(type=2, attribute=None, default=0, eids=False)[source]¶

Returns the adjacency matrix of a graph.

@param type: either C{GET_ADJACENCY_LOWER} (uses the lower: triangle of the matrix) or C{GET_ADJACENCY_UPPER} (uses the upper triangle) or C{GET_ADJACENCY_BOTH} (uses both parts). Ignored for directed graphs.
@param attribute: if C{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 I{eids} is C{True}
@param default: the default value written to the cells in the: case of adjacency matrices with attributes.
@param 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 I{eids} is C{True}. If I{eids} is C{False}, the number of edges will be returned in the matrix for each vertex pair.

@return: the adjacency matrix as a L{Matrix}.

vfGraph.get_adjacency_sparse(attribute=None)[source]¶

Returns the adjacency matrix of a graph as a SciPy CSR matrix.

@param attribute: if C{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.

@return: the adjacency matrix as a C{scipy.sparse.csr_matrix}.

vfGraph.get_adjlist(mode='out', loops='twice', multiple=True)[source]¶

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.

@param mode: if C{“out”}, returns the successors of the vertex. If: C{“in”}, returns the predecessors of the vertex. If C{“all”}, both the predecessors and the successors will be returned. Ignored for undirected graphs.
@param loops: whether to return loops in I{undirected} graphs once: (C{“once”}), twice (C{“twice”}) or not at all (C{“ignore”}). C{False} is accepted as an alias to C{“ignore”} and C{True} is accepted as an alias to C{“twice”}. For directed graphs, C{“twice”} is equivalent to C{“once”} (except when C{mode} is C{“all”} because the graph is then treated as undirected).
@param multiple: whether to return endpoints of multiple edges as many: times as their multiplicities.

vfGraph.get_all_shortest_paths(to=None, weights=None, mode='out')¶

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

@param v: the source for the calculated paths @param to: a vertex selector describing the destination for

the calculated paths. This can be a single vertex ID, a list of vertex IDs, a single vertex name, a list of vertex names or a L{VertexSeq} object. C{None} means all the vertices.

@param weights: edge weights in a list or the name of an edge attribute: holding edge weights. If C{None}, all edges are assumed to have equal weight.
@param mode: the directionality of the paths. C{“in”} means to: calculate incoming paths, C{“out”} means to calculate outgoing paths, C{“all”} means to calculate both ones.
@return: all of the shortest path from the given node to every other: reachable node in the graph in a list. Note that in case of mode=C{“in”}, the vertices in a path are returned in reversed order!

vfGraph.get_all_simple_paths(v, to=None, minlen=0, maxlen=-1, mode='out', max_results=None)[source]¶

Calculates all the simple paths from a given node to some other nodes (or all of them) in a graph.

A path is simple if its vertices are unique, i.e. no vertex is visited more than once.

Note that potentially there are exponentially many paths between two vertices of a graph, especially if your graph is lattice-like. In this case, you may run out of memory when using this function.

@param v: the source for the calculated paths @param to: a vertex selector describing the destination for the calculated

paths. This can be a single vertex ID, a list of vertex IDs, a single vertex name, a list of vertex names or a L{VertexSeq} object. C{None} means all the vertices.

@param minlen: minimum length of path that is considered. @param maxlen: maximum length of path that is considered. If negative,

paths of all lengths are considered.

@param mode: the directionality of the paths. C{“in”} means to calculate: incoming paths, C{“out”} means to calculate outgoing paths, C{“all”} means to calculate both ones.
@param max_results: the maximum number of results to return. C{None} means: no limit on the number of results.
@return: all of the simple paths from the given node to every other: reachable node in the graph in a list. Note that in case of mode=C{“in”}, the vertices in a path are returned in reversed order!

vfGraph.get_automorphisms_vf2(color=None, edge_color=None, node_compat_fn=None, edge_compat_fn=None)[source]¶

Returns all the automorphisms of the graph

This function simply calls C{get_isomorphisms_vf2} with the graph itgraph. See C{get_isomorphisms_vf2} for an explanation of the parameters.

@return: a list of lists, each item containing a possible mapping: of the graph vertices to itgraph according to the automorphism

@see: Graph.get_isomorphisms_vf2

vfGraph.get_biadjacency(types='type', *args, **kwds)[source]¶

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

@param types: a vector containing the vertex types, or an: attribute name. Anything that evalulates to C{False} corresponds to vertices of the first kind, everything else to the second kind.
@return: the bipartite adjacency 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.

vfGraph.get_diameter(unconn=True, weights=None)¶

Returns a path with the actual diameter of the graph.

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

@param directed: whether to consider directed paths. @param unconn: if C{True} and the graph is unconnected, the

longest geodesic within a component will be returned. If C{False} and the graph is unconnected, the result is the number of vertices if there are no weights or infinity if there are weights.

@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.

@return: the vertices in the path in order.

vfGraph.get_edge_dataframe()[source]¶

Export edges with attributes to pandas.DataFrame

If you want to use source and target vertex IDs as index, you can do:

>>> from string import ascii_letters
>>> graph = Graph.GRG(25, 0.4)
>>> graph.vs["name"] = ascii_letters[:graph.vcount()]
>>> df = graph.get_edge_dataframe()
>>> df.set_index(['source', 'target'], inplace=True)

The index will be a pandas.MultiIndex. You can use the C{drop=False} option to keep the C{source} and C{target} columns.

If you want to use vertex names in the source and target columns:

>>> df = graph.get_edge_dataframe()
>>> df_vert = graph.get_vertex_dataframe()
>>> df['source'].replace(df_vert['name'], inplace=True)
>>> df['target'].replace(df_vert['name'], inplace=True)
>>> df_vert.set_index('name', inplace=True)  # Optional

@return: a pandas.DataFrame representing edges and their attributes.: The index uses edge IDs, from 0 to M - 1 where M is the number of edges. The first two columns of the dataframe represent the IDs of source and target vertices for each edge. These columns have names “source” and “target”. If your edges have attributes with the same names, they will be present in the dataframe, but not in the first two columns.

vfGraph.get_edgelist()¶: Returns the edge list of a graph.

vfGraph.get_eid(v2, directed=True, error=True)¶

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

@param v1: the ID or name of the first vertex @param v2: the ID or name of the second vertex @param directed: whether edge directions should be considered in

directed graphs. The default is C{True}. Ignored for undirected graphs.

@param error: if C{True}, an exception will be raised when the: given edge does not exist. If C{False}, -1 will be returned in that case.

@return: the edge ID of an arbitrary edge between vertices v1 and v2

vfGraph.get_eids(directed=True, error=True)¶

Returns the edge IDs of some edges between some vertices.

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

@param pairs: a list of integer pairs. Each integer pair is considered: as a source-target vertex pair; the corresponding edge is looked up in the graph and the edge ID is returned for each pair.
@param directed: whether edge directions should be considered in: directed graphs. The default is C{True}. Ignored for undirected graphs.
@param error: if C{True}, an exception will be raised if a given: edge does not exist. If C{False}, -1 will be returned in that case.

@return: the edge IDs in a list

vfGraph.get_incidence(*args, **kwds)[source]¶: Deprecated alias to L{Graph.get_biadjacency()}.

vfGraph.get_inclist(mode='out', loops='twice')[source]¶

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.

@param mode: if C{“out”}, returns the successors of each vertex. If: C{“in”}, returns the predecessors of each vertex. If C{“all”}, both the predecessors and the successors will be returned. Ignored for undirected graphs.
@param loops: whether to return loops in I{undirected} graphs once: (C{“once”}), twice (C{“twice”}) or not at all (C{“ignore”}). C{False} is accepted as an alias to C{“ignore”} and C{True} is accepted as an alias to C{“twice”}. For directed graphs, C{“twice”} is equivalent to C{“once”} (except when C{mode} is C{“all”} because the graph is then treated as undirected).

vfGraph.get_isomorphisms_vf2(color1=None, color2=None, edge_color1=None, edge_color2=None, node_compat_fn=None, edge_compat_fn=None)¶

Returns all isomorphisms between the graph and another one

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

@param other: the other graph. If C{None}, the automorphisms: will be returned.
@param color1: optional vector storing the coloring of the vertices of: the first graph. If C{None}, all vertices have the same color.
@param color2: optional vector storing the coloring of the vertices of: the second graph. If C{None}, all vertices have the same color.
@param edge_color1: optional vector storing the coloring of the edges of: the first graph. If C{None}, all edges have the same color.
@param edge_color2: optional vector storing the coloring of the edges of: the second graph. If C{None}, all edges have the same color.
@param node_compat_fn: a function that receives the two graphs and two: node indices (one from the first graph, one from the second graph) and returns C{True} if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or C{False} otherwise. This can be used to restrict the set of isomorphisms based on node-specific criteria that are too complicated to be represented by node color vectors (i.e. the C{color1} and C{color2} parameters). C{None} means that every node is compatible with every other node.
@param edge_compat_fn: a function that receives the two graphs and two: edge indices (one from the first graph, one from the second graph) and returns C{True} if the edges given by the two indices are compatible (i.e. they could be matched to each other) or C{False} otherwise. This can be used to restrict the set of isomorphisms based on edge-specific criteria that are too complicated to be represented by edge color vectors (i.e. the C{edge_color1} and C{edge_color2} parameters). C{None} means that every edge is compatible with every other node.
@return: a list of lists, each item of the list containing the mapping: from vertices of the second graph to the vertices of the first one

vfGraph.get_k_shortest_paths(to, k=1, weights=None, mode='out', output='vpath')¶

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

@param v: the ID or name of the vertex from which the paths are calculated. @param to: the ID or name of the vertex to which the paths are calculated. @param k: the desired number of shortest path @param weights: edge weights in a list or the name of an edge attribute

holding edge weights. If C{None}, all edges are assumed to have equal weight.

@param mode: the directionality of the paths. C{“in”} means to: calculate incoming paths, C{“out”} means to calculate outgoing paths, C{“all”} means to calculate both ones.
@param output: determines what should be returned. If this is: C{“vpath”}, a list of vertex IDs will be returned, one path for each target vertex. For unconnected graphs, some of the list elements may be empty. Note that in case of mode=C{“in”}, the vertices in a path are returned in reversed order. If C{output=”epath”}, edge IDs are returned instead of vertex IDs.
@return: the k shortest paths from the given source node to the given target node: in a list of vertex or edge IDs (depending on the value of the C{output} argument). Note that in case of mode=C{“in”}, the vertices in a path are returned in reversed order!

vfGraph.get_shortest_path(to, weights=None, mode='out', output='vpath', algorithm='auto')¶

Calculates the shortest path from a source vertex to a target vertex in a graph.

This function only returns a single shortest path. Consider using L{get_shortest_paths()} to find all shortest paths between a source and one or more target vertices.

@param v: the source vertex of the path @param to: the target vertex of the path @param weights: edge weights in a list or the name of an edge attribute

holding edge weights. If C{None}, all edges are assumed to have equal weight.

@param mode: the directionality of the paths. C{“out”} means to: calculate paths from source to target, following edges according to their natural direction. C{“in”} means to calculate paths from target to source, flipping the direction of each edge on-the-fly. C{“all”} means to ignore edge directions.
@param output: determines what should be returned. If this is: C{“vpath”}, a list of vertex IDs will be returned. If this is C{“epath”}, edge IDs are returned instead of vertex IDs.
@param algorithm: the shortest path algorithm to use. C{“auto”} selects an: algorithm automatically based on whether the graph has negative weights or not. C{“dijkstra”} uses Dijkstra’s algorithm. C{“bellman_ford”} uses the Bellman-Ford algorithm. Ignored for unweighted graphs.

@return: see the documentation of the C{output} parameter. @see: L{get_shortest_paths()}

vfGraph.get_shortest_path_astar(to, heuristics, weights=None, mode='out', output='vpath')¶

Calculates the shortest path from a source vertex to a target vertex in a graph using the A-Star algorithm and a heuristic function.

@param v: the source vertex of the path @param to: the target vertex of the path @param heuristics: a function that will be called with the graph and two

vertices, and must return an estimate of the cost of the path from the first vertex to the second vertex. The A-Star algorithm is guaranteed to return an optimal solution if the heuristic is I{admissible}, i.e. if it does never overestimate the cost of the shortest path from the given source vertex to the given target vertex.

@param weights: edge weights in a list or the name of an edge attribute: holding edge weights. If C{None}, all edges are assumed to have equal weight.
@param mode: the directionality of the paths. C{“out”} means to: calculate paths from source to target, following edges according to their natural direction. C{“in”} means to calculate paths from target to source, flipping the direction of each edge on-the-fly. C{“all”} means to ignore edge directions.
@param output: determines what should be returned. If this is: C{“vpath”}, a list of vertex IDs will be returned. If this is C{“epath”}, edge IDs are returned instead of vertex IDs.

@return: see the documentation of the C{output} parameter.

vfGraph.get_shortest_paths(to=None, weights=None, mode='out', output='vpath', algorithm='auto')¶

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

@param v: the source/destination for the calculated paths @param to: a vertex selector describing the destination/source for

the calculated paths. This can be a single vertex ID, a list of vertex IDs, a single vertex name, a list of vertex names or a L{VertexSeq} object. C{None} means all the vertices.

@param weights: edge weights in a list or the name of an edge attribute: holding edge weights. If C{None}, all edges are assumed to have equal weight.
@param mode: the directionality of the paths. C{“in”} means to: calculate incoming paths, C{“out”} means to calculate outgoing paths, C{“all”} means to calculate both ones.
@param output: determines what should be returned. If this is: C{“vpath”}, a list of vertex IDs will be returned, one path for each target vertex. For unconnected graphs, some of the list elements may be empty. Note that in case of mode=C{“in”}, the vertices in a path are returned in reversed order. If C{output=”epath”}, edge IDs are returned instead of vertex IDs.
@param algorithm: the shortest path algorithm to use. C{“auto”} selects an: algorithm automatically based on whether the graph has negative weights or not. C{“dijkstra”} uses Dijkstra’s algorithm. C{“bellman_ford”} uses the Bellman-Ford algorithm. Ignored for unweighted graphs.

@return: see the documentation of the C{output} parameter.

vfGraph.get_subisomorphisms_lad(domains=None, induced=False, time_limit=0)¶

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

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

@param other: the pattern graph we are looking for in the graph. @param domains: a list of lists, one sublist belonging to each vertex in

the template graph. Sublist M{i} contains the indices of the vertices in the original graph that may match vertex M{i} in the template graph. C{None} means that every vertex may match every other vertex.

@param induced: whether to consider induced subgraphs only. @param time_limit: an optimal time limit in seconds. Only the integral

part of this number is taken into account. If the time limit is exceeded, the method will throw an exception.

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

vfGraph.get_subisomorphisms_vf2(color1=None, color2=None, edge_color1=None, edge_color2=None, node_compat_fn=None, edge_compat_fn=None)¶

Returns all subisomorphisms between the graph and another one

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

@param other: the other graph. @param color1: optional vector storing the coloring of the vertices of

the first graph. If C{None}, all vertices have the same color.

@param color2: optional vector storing the coloring of the vertices of: the second graph. If C{None}, all vertices have the same color.
@param edge_color1: optional vector storing the coloring of the edges of: the first graph. If C{None}, all edges have the same color.
@param edge_color2: optional vector storing the coloring of the edges of: the second graph. If C{None}, all edges have the same color.
@param node_compat_fn: a function that receives the two graphs and two: node indices (one from the first graph, one from the second graph) and returns C{True} if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or C{False} otherwise. This can be used to restrict the set of isomorphisms based on node-specific criteria that are too complicated to be represented by node color vectors (i.e. the C{color1} and C{color2} parameters). C{None} means that every node is compatible with every other node.
@param edge_compat_fn: a function that receives the two graphs and two: edge indices (one from the first graph, one from the second graph) and returns C{True} if the edges given by the two indices are compatible (i.e. they could be matched to each other) or C{False} otherwise. This can be used to restrict the set of isomorphisms based on edge-specific criteria that are too complicated to be represented by edge color vectors (i.e. the C{edge_color1} and C{edge_color2} parameters). C{None} means that every edge is compatible with every other node.
@return: a list of lists, each item of the list containing the mapping: from vertices of the second graph to the vertices of the first one

vfGraph.get_vertex_dataframe()[source]¶

Export vertices with attributes to pandas.DataFrame

If you want to use vertex names as index, you can do:

>>> from string import ascii_letters
>>> graph = Graph.GRG(25, 0.4)
>>> graph.vs["name"] = ascii_letters[:graph.vcount()]
>>> df = graph.get_vertex_dataframe()
>>> df.set_index('name', inplace=True)

@return: a pandas.DataFrame representing vertices and their attributes.: The index uses vertex IDs, from 0 to N - 1 where N is the number of vertices.

vfGraph.girth()¶

Returns the girth of the graph.

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

@param return_shortest_circle: whether to return one of the shortest: circles found in the graph.
@return: the length of the shortest circle or (if C{return_shortest_circle}): is true, the shortest circle itself as a list

vfGraph.gomory_hu_tree(capacity=None, flow='flow')[source]¶

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.

@param capacity: the edge capacities (weights). If C{None}, all: edges have equal weight. May also be an attribute name.
@param flow: the name of the edge attribute in the returned graph: in which the flow values will be stored.

@return: the Gomory-Hu tree as a L{Graph} object.

vfGraph.harmonic_centrality(mode='all', cutoff=None, weights=None, normalized=True)¶

Calculates the harmonic centralities of given vertices in a graph.

The harmonic centrality of a vertex measures how easily other vertices can be reached from it (or the other way: how easily it can be reached from the other vertices). It is defined as the mean inverse distance to all other vertices.

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

@param vertices: the vertices for which the harmonic centrality must: be returned. If C{None}, uses all of the vertices in the graph.
@param mode: must be one of C{“in”}, C{“out”} and C{“all”}. C{“in”} means: that the length of the incoming paths, C{“out”} means that the length of the outgoing paths must be calculated. C{“all”} means that both of them must be calculated.
@param cutoff: if it is not C{None}, only paths less than or equal to this: length are considered.
@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.
@param normalized: Whether to normalize the result. If True, the: result is the mean inverse path length to other vertices, i.e. it is normalized by the number of vertices minus one. If False, the result is the sum of inverse path lengths to other vertices.

@return: the calculated harmonic centralities in a list

vfGraph.has_multiple()¶

Checks whether the graph has multiple edges.

@return: C{True} if the graph has at least one multiple edge,: C{False} otherwise.

@rtype: boolean

vfGraph.hub_score(scale=True, arpack_options=None, return_eigenvalue=False)¶

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

@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.
@param arpack_options: an L{ARPACKOptions} object used to fine-tune: the ARPACK eigenvector calculation. If omitted, the module-level variable called C{arpack_options} is used.

@param return_eigenvalue: whether to return the largest eigenvalue @return: the hub scores in a list and optionally the largest eigenvalue

as a second member of a tuple

@see: authority_score()

vfGraph.incident(mode='out')¶

Returns the edges a given vertex is incident on.

@param vertex: a vertex ID @param mode: whether to return only successors (C{“out”}),

predecessors (C{“in”}) or both (C{“all”}). Ignored for undirected graphs.@param loops: whether to return loops in I{undirected} graphs once (C{“once”}), twice (C{“twice”}) or not at all (C{“ignore”}). C{False} is accepted as an alias to C{“ignore”} and C{True} is accepted as an alias to C{“twice”}. For directed graphs, C{“twice”} is equivalent to C{“once”} (except when C{mode} is C{“all”} because the graph is then treated as undirected).

vfGraph.indegree(*args, **kwds)[source]¶

Returns the in-degrees in a list.

See L{GraphBase.degree} for possible arguments.

vfGraph.independence_number()¶

Returns the independence number of the graph.

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

@see: L{largest_independent_vertex_sets()} for the largest independent: vertex sets

vfGraph.independent_vertex_sets(max=0, max_results=None)¶

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

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

@param min: the minimum size of sets to be returned. If zero or: negative, no lower bound will be used.
@param max: the maximum size of sets to be returned. If zero or: negative, no upper bound will be used.
@param max_results: the maximum number of results to return. C{None}: means no limit on the number of results.

vfGraph.induced_subgraph(implementation='auto')¶

Returns a subgraph spanned by the given vertices.

@param vertices: a list containing the vertex IDs which: should be included in the result.
@param implementation: the implementation to use when constructing: the new subgraph. igraph includes two implementations at the moment. C{“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 (C{“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. C{“auto”} selects between the two implementations automatically, based on the ratio of the size of the subgraph and the size of the original graph.

@return: the subgraph

vfGraph.intersection(other, byname='auto')[source]¶

Creates the intersection of two (or more) graphs.

@param other: graph or list of graphs to be intersected with: the current one.
@param byname: whether to use vertex names instead of ids. See: L{igraph.operators.intersection} for details.

@return: the intersection graph

vfGraph.is_acyclic()¶

Returns whether the graph is acyclic (i.e. contains no cycles).

@return: C{True} if the graph is acyclic, C{False} otherwise. @rtype: boolean

vfGraph.is_biconnected()¶

Decides whether the graph is biconnected.

A graph is biconnected if it stays connected after the removal of any single vertex.

Note that there are different conventions in use about whether to consider a graph consisting of two connected vertices to be biconnected. igraph does consider it biconnected.

@return: C{True} if it is biconnected, C{False} otherwise. @rtype: boolean

vfGraph.is_bipartite()¶

Decides whether the graph is bipartite or not.

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

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

vfGraph.is_chordal(alpham1=None)¶

Returns whether the graph is chordal or not.

@param alpha: the alpha vector from the result of calling: L{maximum_cardinality_search()} on the graph. Useful only if you already have the alpha vector; simply passing C{None} here will make igraph calculate the alpha vector on its own.
@param alpham1: the inverse alpha vector from the result of calling: L{maximum_cardinality_search()} on the graph. Useful only if you already have the inverse alpha vector; simply passing C{None} here will make igraph calculate the inverse alpha vector on its own.

@return: C{True} if the graph is chordal, C{False} otherwise.

vfGraph.is_clique(directed=False)¶

Decides whether a set of vertices is a clique, i.e. a fully connected subgraph.

@param vertices: a list of vertex IDs. @param directed: whether to require mutual connections between vertex pairs

in directed graphs.

@return: C{True} is the given vertex set is a clique, C{False} if not.

vfGraph.is_complete()¶

Checks whether the graph is complete, i.e. whether there is at least one connection between all distinct pairs of vertices. In directed graphs, ordered pairs are considered.

@return: C{True} if it is complete, C{False} otherwise. @rtype: boolean

vfGraph.is_connected()¶

Decides whether the graph is connected.

@param mode: whether we should calculate strong or weak connectivity. @return: C{True} if the graph is connected, C{False} otherwise.

vfGraph.is_dag()¶

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

A DAG is a directed graph with no directed cycles.

@return: C{True} if it is a DAG, C{False} otherwise. @rtype: boolean

vfGraph.is_directed()¶

Checks whether the graph is directed.

@return: C{True} if it is directed, C{False} otherwise. @rtype: boolean

vfGraph.is_independent_vertex_set()¶

Decides whether no two vertices within a set are adjacent.

@param vertices: a list of vertex IDs. @return: C{True} is the given vertices form an independent set, C{False} if not.

vfGraph.is_loop()¶

Checks whether a specific set of edges contain loop edges

@param edges: edge indices which we want to check. If C{None}, all: edges are checked.

@return: a list of booleans, one for every edge given

vfGraph.is_minimal_separator()¶

Decides whether the given vertex set is a minimal separator.

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

@param vertices: a single vertex ID or a list of vertex IDs @return: C{True} is the given vertex set is a minimal separator, C{False}

otherwise.

vfGraph.is_multiple()¶

Checks whether an edge is a multiple edge.

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

@param edges: edge indices which we want to check. If C{None}, all: edges are checked.

@return: a list of booleans, one for every edge given

vfGraph.is_mutual(loops=True)¶

Checks whether an edge has an opposite pair.

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

@param edges: edge indices which we want to check. If C{None}, all: edges are checked.
@param loops: specifies whether loop edges should be treated as mutual: in a directed graph.

@return: a list of booleans, one for every edge given

vfGraph.is_named()[source]¶

Returns whether the graph is named.

A graph is named if and only if it has a C{“name”} vertex attribute.

vfGraph.is_separator()¶

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

@param vertices: a single vertex ID or a list of vertex IDs @return: C{True} is the given vertex set is a separator, C{False} if not.

vfGraph.is_simple()¶

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

@return: C{True} if it is simple, C{False} otherwise. @rtype: boolean

vfGraph.is_tree()¶

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

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

@param mode: for directed graphs, specifies how the edge directions: should be taken into account. C{“all”} means that the edge directions must be ignored, C{“out”} means that the edges must be oriented away from the root, C{“in”} means that the edges must be oriented towards the root. Ignored for undirected graphs.

@return: C{True} if the graph is a tree, C{False} otherwise. @rtype: boolean

vfGraph.is_weighted()[source]¶

Returns whether the graph is weighted.

A graph is weighted if and only if it has a C{“weight”} edge attribute.

vfGraph.isoclass()¶

Returns the isomorphism class of the graph or its subgraph.

Isomorphism class calculations are implemented only for directed graphs with 3 or 4 vertices, or undirected graphs with 3, 4, 5 or 6 vertices..

@param vertices: a list of vertices if we want to calculate the: isomorphism class for only a subset of vertices. C{None} means to use the full graph.

@return: the isomorphism class of the (sub)graph

vfGraph.isomorphic()¶

Checks whether the graph is isomorphic to another graph.

The algorithm being used is selected using a simple heuristic:

If one graph is directed and the other undirected, an exception is thrown.

If the two graphs does not have the same number of vertices and edges, it returns with C{False}

If the graphs have three or four vertices, then an O(1) algorithm is used with precomputed data.

Otherwise if the graphs are directed, then the VF2 isomorphism algorithm is used (see L{isomorphic_vf2}).

Otherwise the BLISS isomorphism algorithm is used, see L{isomorphic_bliss}.

@return: C{True} if the graphs are isomorphic, C{False} otherwise.

vfGraph.isomorphic_bliss(return_mapping_12=False, return_mapping_21=False, sh1='fl', sh2=None, color1=None, color2=None)¶

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

See U{https://users.aalto.fi/~tjunttil/bliss/} for more information about the BLISS algorithm.

@param other: the other graph with which we want to compare the graph. @param color1: optional vector storing the coloring of the vertices of

the first graph. If C{None}, all vertices have the same color.

@param color2: optional vector storing the coloring of the vertices of

the second graph. If C{None}, all vertices have the same color.

@param return_mapping_12: if C{True}, calculates the mapping which maps

the vertices of the first graph to the second.

@param return_mapping_21: if C{True}, calculates the mapping which maps

the vertices of the second graph to the first.

@param sh1: splitting heuristics for the first graph as a

case-insensitive string, with the following possible values:

C{“f”}: first non-singleton cell

C{“fl”}: first largest non-singleton cell

C{“fs”}: first smallest non-singleton cell

C{“fm”}: first maximally non-trivially connected non-singleton cell

C{“flm”}: largest maximally non-trivially connected non-singleton cell

C{“fsm”}: smallest maximally non-trivially connected non-singleton cell

@param sh2: splitting heuristics to be used for the second graph.

This must be the same as C{sh1}; alternatively, it can be C{None}, in which case it will automatically use the same value as C{sh1}. Currently it is present for backwards compatibility only.

@return: if no mapping is calculated, the result is C{True} if the graphs

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

vfGraph.isomorphic_vf2(color1=None, color2=None, edge_color1=None, edge_color2=None, return_mapping_12=False, return_mapping_21=False, node_compat_fn=None, edge_compat_fn=None, callback=None)¶

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

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

@param other: the other graph with which we want to compare the graph.: If C{None}, the automorphjisms of the graph will be tested.
@param color1: optional vector storing the coloring of the vertices of: the first graph. If C{None}, all vertices have the same color.
@param color2: optional vector storing the coloring of the vertices of: the second graph. If C{None}, all vertices have the same color.
@param edge_color1: optional vector storing the coloring of the edges of: the first graph. If C{None}, all edges have the same color.
@param edge_color2: optional vector storing the coloring of the edges of: the second graph. If C{None}, all edges have the same color.
@param return_mapping_12: if C{True}, calculates the mapping which maps: the vertices of the first graph to the second.
@param return_mapping_21: if C{True}, calculates the mapping which maps: the vertices of the second graph to the first.
@param callback: if not C{None}, the isomorphism search will not stop at: the first match; it will call this callback function instead for every isomorphism found. The callback function must accept four arguments: the first graph, the second graph, a mapping from the nodes of the first graph to the second, and a mapping from the nodes of the second graph to the first. The function must return C{True} if the search should continue or C{False} otherwise.
@param node_compat_fn: a function that receives the two graphs and two: node indices (one from the first graph, one from the second graph) and returns C{True} if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or C{False} otherwise. This can be used to restrict the set of isomorphisms based on node-specific criteria that are too complicated to be represented by node color vectors (i.e. the C{color1} and C{color2} parameters). C{None} means that every node is compatible with every other node.
@param edge_compat_fn: a function that receives the two graphs and two: edge indices (one from the first graph, one from the second graph) and returns C{True} if the edges given by the two indices are compatible (i.e. they could be matched to each other) or C{False} otherwise. This can be used to restrict the set of isomorphisms based on edge-specific criteria that are too complicated to be represented by edge color vectors (i.e. the C{edge_color1} and C{edge_color2} parameters). C{None} means that every edge is compatible with every other node.
@return: if no mapping is calculated, the result is C{True} if the graphs: are isomorphic, C{False} otherwise. If any or both mappings are calculated, the result is a 3-tuple, the first element being the above mentioned boolean, the second element being the 1 -> 2 mapping and the third element being the 2 -> 1 mapping. If the corresponding mapping was not calculated, C{None} is returned in the appropriate element of the 3-tuple.

vfGraph.k_core(*args)[source]¶

Returns some k-cores of the graph.

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

vfGraph.knn(weights=None)¶

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

@param vids: the vertices for which the calculation is performed.: C{None} means all vertices.
@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name. If this is given, the vertex strength will be used instead of the vertex degree in the calculations, but the “ordinary” vertex degree will be used for the second (degree- dependent) list in the result.
@return: two lists in a tuple. The first list contains the average: degree of neighbors for each vertex, the second contains the average degree of neighbors as a function of vertex degree. The zeroth element of this list corresponds to vertices of degree 1.

vfGraph.laplacian(normalized='unnormalized', mode='out')¶

Returns the Laplacian matrix of a graph.

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

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

Left-normalized and right-normalized Laplacian matrices are derived from the unnormalized Laplacian by scaling the row or the column sums to be equal to 1.

@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name. When edge weights are used, the degree of a node is considered to be the sum of the weights of its incident edges.
@param normalized: whether to return the normalized Laplacian matrix.: C{False} or C{“unnormalized”} returns the unnormalized Laplacian matrix. C{True} or C{“symmetric”} returns the symmetric normalization of the Laplacian matrix. C{“left”} returns the left-, C{“right”} returns the right-normalized Laplacian matrix.
@param mode: for directed graphs, specifies whether to use out- or in-degrees: in the Laplacian matrix. C{“all”} means that the edge directions must be ignored, C{“out”} means that the out-degrees should be used, C{“in”} means that the in-degrees should be used. Ignored for undirected graphs.

@return: the Laplacian matrix.

vfGraph.largest_cliques()¶

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

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

@see: L{clique_number()} for the size of the largest cliques or: L{maximal_cliques()} for the maximal cliques

vfGraph.largest_independent_vertex_sets()¶

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

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

@see: L{independence_number()} for the size of the largest independent: vertex sets or L{maximal_independent_vertex_sets()} for the maximal (nonextendable) independent vertex sets

vfGraph.layout(layout=None, *args, **kwds)[source]¶

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:

C{auto}, C{automatic}: automatic layout (see L{Graph.layout_auto})

C{bipartite}: bipartite layout (see L{GraphBase.layout_bipartite})

C{circle}, C{circular}: circular layout (see L{GraphBase.layout_circle})

C{dh}, C{davidson_harel}: Davidson-Harel layout (see L{GraphBase.layout_davidson_harel})

C{drl}: DrL layout for large graphs (see L{GraphBase.layout_drl})

C{drl_3d}: 3D DrL layout for large graphs (see L{GraphBase.layout_drl})

C{fr}, C{fruchterman_reingold}: Fruchterman-Reingold layout (see L{GraphBase.layout_fruchterman_reingold}).

C{fr_3d}, C{fr3d}, C{fruchterman_reingold_3d}: 3D Fruchterman- Reingold layout (see L{GraphBase.layout_fruchterman_reingold}).

C{grid}: regular grid layout in 2D (see L{GraphBase.layout_grid})

C{grid_3d}: regular grid layout in 3D (see L{GraphBase.layout_grid})

C{graphopt}: the graphopt algorithm (see L{GraphBase.layout_graphopt})

C{kk}, C{kamada_kawai}: Kamada-Kawai layout (see L{GraphBase.layout_kamada_kawai})

C{kk_3d}, C{kk3d}, C{kamada_kawai_3d}: 3D Kamada-Kawai layout (see L{GraphBase.layout_kamada_kawai})

C{lgl}, C{large}, C{large_graph}: Large Graph Layout (see L{GraphBase.layout_lgl})

C{mds}: multidimensional scaling layout (see L{GraphBase.layout_mds})

C{random}: random layout (see L{GraphBase.layout_random})

C{random_3d}: random 3D layout (see L{GraphBase.layout_random})

C{rt}, C{tree}, C{reingold_tilford}: Reingold-Tilford tree layout (see L{GraphBase.layout_reingold_tilford})

C{rt_circular}, C{reingold_tilford_circular}: circular Reingold-Tilford tree layout (see L{GraphBase.layout_reingold_tilford_circular})

C{sphere}, C{spherical}, C{circle_3d}, C{circular_3d}: spherical layout (see L{GraphBase.layout_circle})

C{star}: star layout (see L{GraphBase.layout_star})

C{sugiyama}: Sugiyama layout (see L{Graph.layout_sugiyama})

@param layout: the layout to use. This can be one of the registered: layout names or a callable which returns either a L{Layout} object or a list of lists containing the coordinates. If C{None}, uses the value of the C{plotting.layout} configuration key.

@return: a L{Layout} object.

vfGraph.layout_auto(*args, **kwds)[source]¶

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:

If the graph has an attribute called C{layout}, it will be used. It may either be a L{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.

Otherwise, if the graph has vertex attributes called C{x} and C{y}, these will be used as coordinates in the layout. When a 3D layout is requested (by setting C{dim} to 3), a vertex attribute named C{z} will also be needed.

Otherwise, if the graph is connected and has at most 100 vertices, the Kamada-Kawai layout will be used (see L{GraphBase.layout_kamada_kawai()}).

Otherwise, if the graph has at most 1000 vertices, the Fruchterman-Reingold layout will be used (see L{GraphBase.layout_fruchterman_reingold()}).

If everything else above failed, the DrL layout algorithm will be used (see L{GraphBase.layout_drl()}).

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

@keyword dim: specifies whether we would like to obtain a 2D or a: 3D layout.

@return: a L{Layout} object.

vfGraph.layout_bipartite(**kwds)[source]¶

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.

@param types: an igraph vector containing the vertex types, or an: attribute name. Anything that evalulates to C{False} corresponds to vertices of the first kind, everything else to the second kind.

@param hgap: minimum horizontal gap between vertices in the same layer. @param vgap: vertical gap between the two layers. @param 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: the calculated layout.

vfGraph.layout_circle(**kwds)[source]¶

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

@param dim: the desired number of dimensions for the layout. dim=2: means a 2D layout, dim=3 means a 3D layout.
@param order: the order in which the vertices are placed along the: circle. Not supported when I{dim} is not equal to 2.

@return: the calculated layout.

vfGraph.layout_davidson_harel(**kwds)[source]¶

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

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

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

@param seed: if C{None}, uses a random starting layout for the algorithm.: If a matrix (list of lists), uses the given matrix as the starting position.

@param maxiter: Number of iterations to perform in the annealing phase. @param fineiter: Number of iterations to perform in the fine-tuning phase.

Negative numbers set up a reasonable default from the base-2 logarithm of the vertex count, bounded by 10 from above.

@param cool_fact: Cooling factor of the simulated annealing phase. @param weight_node_dist: Weight for the node-node distances in the energy

function.

@param weight_border: Weight for the distance from the border component of: the energy function. Zero means that vertices are allowed to sit on the border of the area designated for the layout.
@param weight_edge_lengths: Weight for the edge length component of the: energy function. Negative numbers are replaced by the density of the graph divided by 10.
@param weight_edge_crossings: Weight for the edge crossing component of the: energy function. Negative numbers are replaced by one minus the square root of the density of the graph.
@param weight_node_edge_dist: Weight for the node-edge distance component: of the energy function. Negative numbers are replaced by 0.2 minus 0.2 times the density of the graph.

@return: the calculated layout.

vfGraph.layout_drl(**kwds)[source]¶

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 C{layout_kamada_kawai()} or C{layout_fruchterman_reingold()} are more useful.

@param weights: edge weights to be used. Can be a sequence or iterable or

even an edge attribute name.

@param seed: if C{None}, uses a random starting layout for the

algorithm. If a matrix (list of lists), uses the given matrix as the starting position.

@param fixed: ignored. We used to assume that the DrL layout supports

fixed nodes, but later it turned out that the argument has no effect in the original DrL code. We kept the argument for sake of backwards compatibility, but it will have no effect on the final layout.

@param options: if you give a string argument here, you can select from

five default preset parameterisations: C{default}, C{coarsen} for a coarser layout, C{coarsest} for an even coarser layout, C{refine} for refining an existing layout and C{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:

C{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.

C{init_iterations}: number of iterations in the initialization phase

C{init_temperature}: start temperature during initialization

C{init_attraction}: attraction during initialization

C{init_damping_mult}: damping multiplier during initialization

C{liquid_iterations}, C{liquid_temperature}, C{liquid_attraction}, C{liquid_damping_mult}: same parameters for the liquid phase

C{expansion_iterations}, C{expansion_temperature}, C{expansion_attraction}, C{expansion_damping_mult}: parameters for the expansion phase

C{cooldown_…}: parameters for the cooldown phase

C{crunch_…}: parameters for the crunch phase

C{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 C{default} preset will be used.

@param dim: the desired number of dimensions for the layout. dim=2

means a 2D layout, dim=3 means a 3D layout.

@return: the calculated layout.

vfGraph.layout_fruchterman_reingold(**kwds)[source]¶

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

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

@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.
@param niter: the number of iterations to perform. The default: is 500.
@param start_temp: Real scalar, the start temperature. This is the: maximum amount of movement alloved along one axis, within one step, for a vertex. Currently it is decreased linearly to zero during the iteration. The default is the square root of the number of vertices divided by 10.
@param minx: if not C{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.

@param maxx: similar to I{minx}, but with maximum constraints @param miny: similar to I{minx}, but with the Y coordinates @param maxy: similar to I{maxx}, but with the Y coordinates @param minz: similar to I{minx}, but with the Z coordinates. Use only

for 3D layouts (C{dim}=3).

@param maxz: similar to I{maxx}, but with the Z coordinates. Use only: for 3D layouts (C{dim}=3).
@param seed: if C{None}, uses a random starting layout for the: algorithm. If a matrix (list of lists), uses the given matrix as the starting position.
@param grid: whether to use a faster, but less accurate grid-based: implementation of the algorithm. C{“auto”} decides based on the number of vertices in the graph; a grid will be used if there are at least 1000 vertices. C{“grid”} is equivalent to C{True}, C{“nogrid”} is equivalent to C{False}.

@return: the calculated layout.

vfGraph.layout_fruchterman_reingold_3d(**kwds)[source]¶

Alias for L{layout_fruchterman_reingold()} with dim=3.

@see: Graph.layout_fruchterman_reingold()

vfGraph.layout_graphopt(**kwds)[source]¶

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 U{https://web.archive.org/web/20220611030748/http://www.schmuhl.org/graphopt/} and U{https://sourceforge.net/projects/graphopt/} for the original graphopt.

@param niter: the number of iterations to perform. Should be a couple: of hundred in general.
@param node_charge: the charge of the vertices, used to calculate electric: repulsion.

@param node_mass: the mass of the vertices, used for the spring forces @param spring_length: the length of the springs @param spring_constant: the spring constant @param max_sa_movement: the maximum amount of movement allowed in a single

step along a single axis.

@param seed: a matrix containing a seed layout from which the algorithm: will be started. If C{None}, a random layout will be used.

@return: the calculated layout.

vfGraph.layout_grid(**kwds)[source]¶

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

@param width: the number of vertices in a single row of the layout.: Zero or negative numbers mean that the width should be determined automatically.
@param 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.
@param dim: the desired number of dimensions for the layout. dim=2: means a 2D layout, dim=3 means a 3D layout.

@return: the calculated layout.

vfGraph.layout_grid_3d(**kwds)[source]¶

Alias for L{layout_grid()} with dim=3.

@see: Graph.layout_grid()

vfGraph.layout_kamada_kawai(**kwds)[source]¶

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.

@param maxiter: the maximum number of iterations to perform. C{None} selects: a reasonable default based on the number of vertices.
@param seed: when C{None}, uses a circular layout as a starting point for the: algorithm when no bounds are given, or a random layout when bounds are specified for the coordinated. When the argument is a matrix (list of lists), it uses the given matrix as the initial layout.
@param epsilon: quit if the energy of the system changes less than: epsilon. See the original paper for details.
@param kkconst: the Kamada-Kawai vertex attraction constant.: C{None} means the number of vertices.
@param minx: if not C{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.

for 3D layouts (C{dim}=3).

@param maxz: similar to I{maxx}, but with the Z coordinates. Use only: for 3D layouts (C{dim}=3).
@param dim: the desired number of dimensions for the layout. dim=2: means a 2D layout, dim=3 means a 3D layout.
@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.

@return: the calculated layout.

vfGraph.layout_kamada_kawai_3d(**kwds)[source]¶

Alias for L{layout_kamada_kawai()} with dim=3.

@see: Graph.layout_kamada_kawai()

vfGraph.layout_lgl(**kwds)[source]¶

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

@param maxiter: the number of iterations to perform. @param maxdelta: the maximum distance to move a vertex in

an iteration. If negative, defaults to the number of vertices.

@param area: the area of the square on which the vertices: will be placed. If negative, defaults to the number of vertices squared.

@param coolexp: the cooling exponent of the simulated annealing. @param repulserad: determines the radius at which vertex-vertex

repulsion cancels out attraction of adjacent vertices. If negative, defaults to M{area} times the number of vertices.

@param 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 M{area}.
@param root: the root vertex, this is placed first, its neighbors: in the first iteration, second neighbors in the second, etc. C{None} means that a random vertex will be chosen.

@return: the calculated layout.

vfGraph.layout_mds(**kwds)[source]¶

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 M{i} and column M{j} specifies the desired distance between vertex M{i} and vertex M{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.

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

@param 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 C{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.
@param dim: the number of dimensions. For 2D layouts, supply: 2 here; for 3D layouts, supply 3.
@param arpack_options: an L{ARPACKOptions} object used to fine-tune: the ARPACK eigenvector calculation. If omitted, the module-level variable called C{arpack_options} is used.

@return: the calculated layout.

vfGraph.layout_random(**kwds)[source]¶

Places the vertices of the graph randomly.

@param dim: the desired number of dimensions for the layout. dim=2: means a 2D layout, dim=3 means a 3D layout.

@return: the coordinate pairs in a list.

vfGraph.layout_random_3d(**kwds)[source]¶

Alias for L{layout_random()} with dim=3.

@see: Graph.layout_random()

vfGraph.layout_reingold_tilford(**kwds)[source]¶

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.

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

@param mode: specifies which edges to consider when builing the tree.: If it is C{OUT} then only the outgoing, if it is C{IN} then only the incoming edges of a parent are considered. If it is C{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 I{root} parameter.
@param 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 C{None} or an empty list, the root vertices are automatically calculated in such a way so that all other vertices would be reachable from them. Currently, automatic root selection prefers low eccentricity vertices in small graphs (fewer than 500 vertices) and high degree vertices in large graphs. This heuristic may change in future versions. Specify roots manually for a consistent output.
@param 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.

@return: the calculated layout.

@see: layout_reingold_tilford_circular

vfGraph.layout_reingold_tilford_circular(**kwds)[source]¶

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 L{layout_reingold_tilford} for the explanation of the parameters.

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

@return: the calculated layout.

@see: layout_reingold_tilford

vfGraph.layout_sphere(**kwds)[source]¶

Alias for L{layout_circle()} with dim=3.

@see: Graph.layout_circle()

vfGraph.layout_star(**kwds)[source]¶

Calculates a star-like layout for the graph.

@param center: the ID of the vertex to put in the center @param order: a numeric vector giving the order of the vertices

(including the center vertex!). If it is C{None}, the vertices will be placed in increasing vertex ID order.

@return: the calculated layout.

vfGraph.layout_sugiyama(layers=None, weights=None, hgap=1, vgap=1, maxiter=100)[source]¶

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.

B{References}:

K Sugiyama, S Tagawa, M Toda: Methods for visual understanding of hierarchical system structures. I{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. I{Information Processing Letters} 47:319-323, 1993.

@param 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 C{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.
@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.

@param hgap: minimum horizontal gap between vertices in the same layer. @param vgap: vertical gap between layers. The layer index will be

multiplied by I{vgap} to obtain the Y coordinate.

@param 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: the calculated layout and an additional list of matrices where the: i-th matrix contains the control points of edge I{i} in the original graph (or an empty matrix if no control points are needed on the edge)

vfGraph.layout_umap(**kwds)[source]¶

Uniform Manifold Approximation and Projection (UMAP).

This layout is a probabilistic algorithm that places vertices that are connected and have a short distance close by in the embedded space.

B{Reference}: L McInnes, J Healy, J Melville: UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. arXiv:1802.03426.

@param dist: distances associated with the graph edges. If None, all edges will: be assumed to convey the same distance between the vertices. Either this argument of the C{weights} argument can be set, but not both. It is fine to set neither.
@param weights: precomputed edge weights if you have them, as an alternative: to setting the C{dist} argument. Zero weights will be ignored if this argument is set, e.g. if you computed the weights via igraph.umap_compute_weights().
@param dim: the desired number of dimensions for the layout. dim=2: means a 2D layout, dim=3 means a 3D layout.
@param seed: if C{None}, uses a random starting layout for the: algorithm. If a matrix (list of lists), uses the given matrix as the starting position.
@param min_dist: the minimal distance in the embedded space beyond which the: probability of being located closeby decreases.
@param epochs: the number of epochs (iterations) the algorithm will iterate: over. Accuracy increases with more epochs, at the cost of longer runtimes. Values between 50 and 1000 are typical. Notice that UMAP does not technically converge for symmetry reasons, but a larger number of epochs should generally give an equivalent or better layout.

@return: the calculated layout.

Please note that if distances are set, the graph is usually directed, whereas if weights are precomputed, the graph will be treated as undirected. A special case is when the graph is directed but the precomputed weights are symmetrized in a way only one of each pair of opposite edges has nonzero weight, e.g. as computed by igraph.umap_compute_weights(). For example: C{weights = igraph.umap_compute_weights(graph, dist)} C{layout = graph.layout_umap(weights=weights)}

@see: igraph.umap_compute_weights()

vfGraph.linegraph()¶

Returns the line graph of the graph.

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

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

Edge M{i} in the original graph will map to vertex M{i} of the line graph.

vfGraph.list_triangles()¶

Lists the triangles of the graph

@return: the list of triangles in the graph; each triangle is represented: by a tuple of length 3, containing the corresponding vertex IDs.

vfGraph.maxdegree(mode='all', loops=False)¶

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

@param vertices: a single vertex ID or a list of vertex IDs, or: C{None} meaning all the vertices in the graph.
@param mode: the type of degree to be returned (C{“out”} for: out-degrees, C{“in”} IN for in-degrees or C{“all”} for the sum of them).

@param loops: whether self-loops should be counted.

vfGraph.maxflow(source, target, capacity=None)[source]¶

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

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

For each edge, the flow (i.e. the assigned number) is not more than the capacity of the edge (see the I{capacity} argument)

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.

@param capacity: the edge capacities (weights). If C{None}, all: edges have equal weight. May also be an attribute name.

@return: a L{Flow} object describing the maximum flow

vfGraph.maxflow_value(target, capacity=None)¶

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

@param source: the source vertex ID @param target: the target vertex ID @param capacity: the capacity of the edges. It must be a list or a valid

attribute name or C{None}. In the latter case, every edge will have the same capacity.

@return: the value of the maximum flow between the given vertices

vfGraph.maximal_cliques(max=0, file=None, max_results=None)¶

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

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

@param min: the minimum size of maximal cliques to be returned. If zero: or negative, no lower bound will be used.
@param max: the maximum size of maximal cliques to be returned. If zero: or negative, no upper bound will be used. If nonzero, the size of every maximal clique found will be compared to this value and a clique will be returned only if its size is smaller than this limit.
@param file: a file object or the name of the file to write the results: to. When this argument is C{None}, the maximal cliques will be returned as a list of lists.
@param max_results: the maximum number of results to return. C{None}: means no limit on the number of results.
@return: the maximal cliques of the graph as a list of lists, or C{None}: if the C{file} argument was given.@see: L{largest_cliques()} for the largest cliques.

vfGraph.maximal_independent_vertex_sets(max=0, max_results=None)¶

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

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

B{Reference}: S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka: A new algorithm for generating all the maximal independent sets. I{SIAM J Computing}, 6:505-517, 1977.

@param min: the minimum size of sets to be returned. If zero or: negative, no lower bound will be used.
@param max: the maximum size of sets to be returned. If zero or: negative, no upper bound will be used.
@param max_results: the maximum number of results to return. C{None}: means no limit on the number of results.
@see: L{largest_independent_vertex_sets()} for the largest independent: vertex sets

vfGraph.maximum_bipartite_matching(types='type', weights=None, eps=None)[source]¶

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.

@param 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 C{False} and C{True}) for the two sides of the bipartite graph. If omitted, it defaults to C{type}, which is the default vertex type attribute for bipartite graphs.
@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.
@param 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 C{None} here, igraph will try to determine an appropriate value automatically.

@return: an instance of L{Matching}.

vfGraph.maximum_cardinality_search()¶

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

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

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

@return: a tuple consisting of the rank vector and its inverse.

vfGraph.mean_degree()¶

Calculates the mean degree of the graph.

@param loops: whether to consider self-loops during the calculation @return: the mean degree of the graph.

vfGraph.mincut(source=None, target=None, capacity=None)[source]¶

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.

@param source: the source vertex ID. If C{None}, the target must also be: C{None} and the calculation will be done for the entire graph (i.e. all possible vertex pairs).
@param target: the target vertex ID. If C{None}, the source must also be: C{None} and the calculation will be done for the entire graph (i.e. all possible vertex pairs).
@param capacity: the edge capacities (weights). If C{None}, all: edges have equal weight. May also be an attribute name.

@return: a L{Cut} object describing the minimum cut

vfGraph.mincut_value(target=-1, capacity=None)¶

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

@param source: the source vertex ID. If negative, the calculation is: done for every vertex except the target and the minimum is returned.
@param target: the target vertex ID. If negative, the calculation is: done for every vertex except the source and the minimum is returned.
@param capacity: the capacity of the edges. It must be a list or a valid: attribute name or C{None}. In the latter case, every edge will have the same capacity.

@return: the value of the minimum cut between the given vertices

vfGraph.minimum_cycle_basis(complete=True, use_cycle_order=True, weights=None)¶

Computes a minimum cycle basis of the graph

@param cutoff: when C{None} or negative, a complete minimum cycle basis is returned.: Otherwise only those cycles in the result will be part of some minimum cycle basis that are of length M{2 * cutoff + 1} or shorter. Cycles longer than this limit may not be of the smallest possible size. This parameter effectively limits the depth of the BFS tree when computing candidate cycles and may speed up the computation substantially.
@param complete: used only when a cutoff is specified, and in this case it: specifies whether a complete basis is returned (C{True}) or the result will be limited to cycles of length M{2 * cutoff + 1} or shorter only. This limits computation time, but the result may not span the entire cycle space.
@param use_cycle_order: if C{True}, every cycle is returned in natural: order: the edge IDs will appear ordered along the cycle. If C{False}, no guarantees are given about the ordering of edge IDs within cycles.
@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.

@return: the cycle basis as a list of tuples containing edge IDs

vfGraph.minimum_size_separators()¶

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

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

B{Reference}: Arkady Kanevsky: Finding all minimum-size separating vertex sets in a graph. I{Networks} 23:533-541, 1993.

@return: a list where each item lists the vertex indices of a given: separator of minimum size.

vfGraph.modularity(membership, weights=None, resolution=1, directed=True)[source]¶

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 M{Q=1/(2m)*sum(Aij-gamma*ki*kj/(2m)delta(ci,cj),i,j)}. M{m} is the number of edges, M{Aij} is the element of the M{A} adjacency matrix in row M{i} and column M{j}, M{ki} is the degree of node M{i}, M{kj} is the degree of node M{j}, and M{Ci} and C{cj} are the types of the two vertices (M{i} and M{j}), and M{gamma} is a resolution parameter that defaults to 1 for the classical definition of modularity. M{delta(x,y)} is one iff M{x=y}, 0 otherwise.

If edge weights are given, the definition of modularity is modified as follows: M{Aij} becomes the weight of the corresponding edge, M{ki} is the total weight of edges adjacent to vertex M{i}, M{kj} is the total weight of edges adjacent to vertex M{j} and M{m} is the total edge weight in the graph.

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

@param membership: a membership list or a L{VertexClustering} object @param weights: optional edge weights or C{None} if all edges are

weighed equally. Attribute names are also allowed.

@param resolution: the resolution parameter I{gamma} in the formula above.: The classical definition of modularity is retrieved when the resolution parameter is set to 1.
@param directed: whether to consider edge directions if the graph is directed.: C{True} will use the directed variant of the modularity measure where the in- and out-degrees of nodes are treated separately; C{False} will treat directed graphs as undirected.

@return: the modularity score

vfGraph.modularity_matrix(resolution=1, directed=True)¶

Calculates the modularity matrix of the graph.

@param weights: optional edge weights or C{None} if all edges are weighed: equally.
@param resolution: the resolution parameter I{gamma} of the modularity: formula. The classical definition of modularity is retrieved when the resolution parameter is set to 1.
@param directed: whether to consider edge directions if the graph is directed.: C{True} will use the directed variant of the modularity measure where the in- and out-degrees of nodes are treated separately; C{False} will treat directed graphs as undirected.

@return: the modularity matrix as a list of lists.

vfGraph.motifs_randesu(cut_prob=None, callback=None)¶

Counts the number of motifs in the graph

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

Currently we support motifs of size 3 and 4 for directed graphs, and motifs of size 3, 4, 5 or 6 for undirected graphs.

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

B{Reference}: S. Wernicke and F. Rasche: FANMOD: a tool for fast network motif detection, I{Bioinformatics} 22(9), 1152–1153, 2006.

@param size: the size of the motifs @param cut_prob: the cut probabilities for different levels of the search

tree. This must be a list of length I{size} or C{None} to find all motifs.

@param callback: C{None} or a callable that will be called for every motif: found in the graph. The callable must accept three parameters: the graph itself, the list of vertices in the motif and the isomorphism class of the motif (see L{isoclass()}). The search will stop when the callback returns an object with a non-zero truth value or raises an exception.

@return: the list of motifs if I{callback} is C{None}, or C{None} otherwise @see: Graph.motifs_randesu_no()

vfGraph.motifs_randesu_estimate(cut_prob=None, sample=None)¶

Counts the total number of motifs in the graph

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

Currently we support motifs of size 3 and 4 for directed graphs, and motifs of size 3, 4, 5 or 6 for undirected graphs.

B{Reference}: S. Wernicke and F. Rasche: FANMOD: a tool for fast network motif detection, I{Bioinformatics} 22(9), 1152–1153, 2006.

@param size: the size of the motifs @param cut_prob: the cut probabilities for different levels of the search

tree. This must be a list of length I{size} or C{None} to find all motifs.

@param sample: the size of the sample or the vertex IDs of the vertices: to be used for sampling.

@see: Graph.motifs_randesu()

vfGraph.motifs_randesu_no(cut_prob=None)¶

Counts the total number of motifs in the graph

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

Currently we support motifs of size 3 and 4 for directed graphs, and motifs of size 3, 4, 5 or 6 for undirected graphs.

B{Reference}: S. Wernicke and F. Rasche: FANMOD: a tool for fast network motif detection, I{Bioinformatics} 22(9), 1152–1153, 2006.

@param size: the size of the motifs @param cut_prob: the cut probabilities for different levels of the search

tree. This must be a list of length I{size} or C{None} to find all motifs.

@see: Graph.motifs_randesu()

vfGraph.multimaxflow(sources, sinks)[source]¶: Multi-source multi-sink maximum flow. Ported from https://github.com/kazumits/ddhodge/blob/master/R/graphConstr.R

vfGraph.neighborhood(order=1, mode='all', mindist=0)¶

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

@param vertices: a single vertex ID or a list of vertex IDs, or: C{None} meaning all the vertices in the graph.
@param order: the order of the neighborhood, i.e. the maximum number of: steps to take from the seed vertex. Negative values are interpreted as an infinite order, i.e. no limit on the number of steps.
@param mode: specifies how to take into account the direction of: the edges if a directed graph is analyzed. C{“out”} means that only the outgoing edges are followed, so all vertices reachable from the source vertex in at most I{order} steps are counted. C{“in”} means that only the incoming edges are followed (in reverse direction of course), so all vertices from which the source vertex is reachable in at most I{order} steps are counted. C{“all”} treats directed edges as undirected.
@param mindist: the minimum distance required to include a vertex in the: result. If this is one, the seed vertex is not included. If this is two, the direct neighbors of the seed vertex are not included either, and so on.
@return: a single list specifying the neighborhood if I{vertices}: was an integer specifying a single vertex index, or a list of lists if I{vertices} was a list or C{None}.

vfGraph.neighborhood_size(order=1, mode='all', mindist=0)¶

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

@param vertices: a single vertex ID or a list of vertex IDs, or: C{None} meaning all the vertices in the graph.
@param order: the order of the neighborhood, i.e. the maximum number of: steps to take from the seed vertex. Negative values are interpreted as an infinite order, i.e. no limit on the number of steps.
@param mode: specifies how to take into account the direction of: the edges if a directed graph is analyzed. C{“out”} means that only the outgoing edges are followed, so all vertices reachable from the source vertex in at most I{order} steps are counted. C{“in”} means that only the incoming edges are followed (in reverse direction of course), so all vertices from which the source vertex is reachable in at most I{order} steps are counted. C{“all”} treats directed edges as undirected.
@param mindist: the minimum distance required to include a vertex in the: result. If this is one, the seed vertex is not counted. If this is two, the direct neighbors of the seed vertex are not counted either, and so on.
@return: a single number specifying the neighborhood size if I{vertices}: was an integer specifying a single vertex index, or a list of sizes if I{vertices} was a list or C{None}.

vfGraph.neighbors(mode='all', loops='twice', multiple=True)¶

Returns adjacent vertices to a given vertex.

@param vertex: a vertex ID @param mode: whether to return only successors (C{“out”}),

predecessors (C{“in”}) or both (C{“all”}). Ignored for undirected graphs.@param loops: whether to return loops in I{undirected} graphs once (C{“once”}), twice (C{“twice”}) or not at all (C{“ignore”}). C{False} is accepted as an alias to C{“ignore”} and C{True} is accepted as an alias to C{“twice”}. For directed graphs, C{“twice”} is equivalent to C{“once”} (except when C{mode} is C{“all”} because the graph is then treated as undirected).

@param multiple: whether to return endpoints of multiple edges as many: times as their multiplicities.

vfGraph.omega()¶

Returns the clique number of the graph.

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

@see: L{largest_cliques()} for the largest cliques.

vfGraph.outdegree(*args, **kwds)[source]¶

Returns the out-degrees in a list.

See L{GraphBase.degree} for possible arguments.

vfGraph.pagerank(vertices=None, directed=True, damping=0.85, weights=None, arpack_options=None, implementation='prpack')[source]¶

Calculates the PageRank values of a graph.

@param vertices: the indices of the vertices being queried.: C{None} means all of the vertices.

@param directed: whether to consider directed paths. @param damping: the damping factor. M{1-damping} is the probability of

resetting the random walk to a uniform distribution in each step.

@param weights: edge weights to be used. Can be a sequence or iterable

or even an edge attribute name.

@param arpack_options: an L{ARPACKOptions} object used to fine-tune

the ARPACK eigenvector calculation. If omitted, the module-level variable called C{arpack_options} is used. This argument is ignored if not the ARPACK implementation is used, see the I{implementation} argument.

@param implementation: which implementation to use to solve the

PageRank eigenproblem. Possible values are:

C{“prpack”}: use the PRPACK library. This is a new implementation in igraph 0.7
C{“arpack”}: use the ARPACK library. This implementation was used from version 0.5, until version 0.7.

@return: a list with the PageRank values of the specified vertices.

vfGraph.path_length_hist(directed=True)[source]¶

Returns the path length histogram of the graph

@param directed: whether to consider directed paths. Ignored for: undirected graphs.
@return: a L{Histogram} object. The object will also have an: C{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 I{very} large.

vfGraph.permute_vertices()¶

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

Vertex M{k} of the new graph will belong to vertex M{permutation[k]} in the original graph. No validity checks are performed on the permutation vector.

@return: the new graph

vfGraph.personalized_pagerank(directed=True, damping=0.85, reset=None, reset_vertices=None, weights=None, arpack_options=None, implementation='prpack')¶

Calculates the personalized PageRank values of a graph.

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

@param vertices: the indices of the vertices being queried.: C{None} means all of the vertices.

@param directed: whether to consider directed paths. @param damping: the damping factor. @param reset: the distribution over the vertices to be used when resetting

the random walk. Can be a sequence, an iterable or a vertex attribute name as long as they return a list of floats whose length is equal to the number of vertices. If C{None}, a uniform distribution is assumed, which makes the method equivalent to the original PageRank algorithm.

@param reset_vertices: an alternative way to specify the distribution

over the vertices to be used when resetting the random walk. Simply supply a list of vertex IDs here, or a L{VertexSeq} or a L{Vertex}. Resetting will take place using a uniform distribution over the specified vertices.

@param weights: edge weights to be used. Can be a sequence or iterable or

even an edge attribute name.

@param arpack_options: an L{ARPACKOptions} object used to fine-tune

@param implementation: which implementation to use to solve the

PageRank eigenproblem. Possible values are:

C{“prpack”}: use the PRPACK library. This is a new implementation in igraph 0.7

C{“arpack”}: use the ARPACK library. This implementation was used from version 0.5, until version 0.7.

@return: a list with the personalized PageRank values of the specified

vertices.

vfGraph.predecessors(vertex, loops=True, multiple=True)[source]¶

Returns the predecessors of a given vertex.

Equivalent to calling the L{Graph.neighbors()} method with mode=C{“in”}.

vfGraph.radius(weights=None)¶

Calculates the radius of the graph.

The radius of a graph is defined as the minimum eccentricity of its vertices (see L{eccentricity()}). @param mode: what kind of paths to consider for the calculation

in case of directed graphs. C{OUT} considers paths that follow edge directions, C{IN} considers paths that follow the opposite edge directions, C{ALL} ignores edge directions. The argument is ignored for undirected graphs.

@param weights: a list containing the edge weights. It can also be: an attribute name (edge weights are retrieved from the given attribute) or C{None} (all edges have equal weight).

@return: the radius @see: L{eccentricity()}

vfGraph.random_walk(steps, mode='out', stuck='return', weights=None, return_type='vertices')¶

Performs a random walk of a given length from a given node.

@param start: the starting vertex of the walk @param steps: the number of steps that the random walk should take @param mode: whether to follow outbound edges only (C{“out”}),

inbound edges only (C{“in”}) or both (C{“all”}). Ignored for undirected graphs.@param stuck: what to do when the random walk gets stuck. C{“return”} returns a partial random walk; C{“error”} throws an exception.

@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.
@param return_type: what to return. It can be C{“vertices”} (default),: then the function returns a list of the vertex ids visited; C{“edges”}, then the function returns a list of edge ids visited; or C{“both”}, then the function return a dictionary with keys C{“vertices”} and C{“edges”}.
@return: a random walk that starts from the given vertex and has at most: the given length (shorter if the random walk got stuck).

vfGraph.reciprocity(mode='default')¶

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

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

@param ignore_loops: whether loop edges should be ignored. @param mode: the algorithm to use to calculate the reciprocity; see

above for more details.

@return: the reciprocity of the graph

vfGraph.reverse_edges()¶

Reverses the direction of some edges in the graph.

This function is a no-op for undirected graphs.

@param es: the list of edges to be reversed. Edges are identifed by: edge IDs. L{EdgeSeq} objects are also accepted here. When omitted, all edges will be reversed.

vfGraph.rewire(n=None, allowed_edge_types='simple', *, mode=None)[source]¶

Randomly rewires the graph while preserving the degree distribution.

The rewiring is done “in-place”, so the original graph will be modified. If you want to preserve the original graph, use the L{copy} method before rewiring.

@param n: the number of rewiring trials. The default is 10 times the number: of edges.
@param allowed_edge_types: the rewiring algorithm to use. It can either be: C{“simple”} or C{“loops”}; the former does not create or destroy loop edges while the latter does.

vfGraph.rewire_edges(allowed_edge_types='simple')¶

Rewires the edges of a graph with constant probability.

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

Please note that the rewiring is done “in-place”, so the original graph will be modified. If you want to preserve the original graph, use the L{cop y} method before.

@param prob: rewiring probability @param allowed_edge_types: controls whether loops or multi-edges are allowed

during the rewiring process. Note that not all combinations are supported for all types of graphs; an exception will be raised for unsupported combinations. Possible values are:

C{“simple”}: simple graphs (no self-loops, no multi-edges)

C{“loops”}: single self-loops allowed, but not multi-edges

C{“multi”}: multi-edges allowed, but not self-loops

C{“all”}: multi-edges and self-loops allowed

vfGraph.save(f, format=None, *args, **kwds)[source]¶

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.

@param f: the file containing the graph to be saved @param 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). C{None} means auto-detection. Possible values are:

C{“adjacency”}: adjacency matrix format

C{“dimacs”}: DIMACS format

C{“dot”}, C{“graphviz”}: GraphViz DOT format

C{“edgelist”}, C{“edges”} or C{“edge”}: numeric edge list format

C{“gml”}: GML format

C{“graphml”} and C{“graphmlz”}: standard and gzipped GraphML format

C{“gw”}, C{“leda”}, C{“lgr”}: LEDA native format

C{“lgl”}: LGL format

C{“ncol”}: NCOL format

C{“net”}, C{“pajek”}: Pajek format

C{“pickle”}, C{“picklez”}: standard and gzipped Python pickled format

C{“svg”}: SVG format

@raises IOError: if the file format can’t be identified and: none was given.

vfGraph.shell_index()¶

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

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

@param mode: whether to compute the in-corenesses (C{“in”}), the: out-corenesses (C{“out”}) or the undirected corenesses (C{“all”}). Ignored and assumed to be C{“all”} for undirected graphs.

@return: the corenesses for each vertex.

vfGraph.shortest_paths(*args, **kwds)[source]¶: Deprecated alias to L{Graph.distances()}.

vfGraph.shortest_paths_dijkstra(*args, **kwds)[source]¶: Deprecated alias to L{Graph.distances()}.

vfGraph.similarity_dice(pairs=None, mode='all', loops=True)¶

Dice similarity coefficient of vertices.

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

@param vertices: the vertices to be analysed. If C{None} and I{pairs} is also: C{None}, all vertices will be considered.
@param pairs: the vertex pairs to be analysed. If this is given, I{vertices}: must be C{None}, and the similarity values will be calculated only for the given pairs. Vertex pairs must be specified as tuples of vertex IDs.
@param mode: which neighbors should be considered for directed graphs.: Can be C{“all”}, C{“in”} or C{“out”}, ignored for undirected graphs.
@param loops: whether vertices should be considered adjacent to: themselves. Setting this to C{True} assumes a loop edge for all vertices even if none is present in the graph. Setting this to C{False} may result in strange results: nonadjacent vertices may have larger similarities compared to the case when an edge is added between them – however, this might be exactly the result you want to get.
@return: the pairwise similarity coefficients for the vertices specified,: in the form of a matrix if C{pairs} is C{None} or in the form of a list if C{pairs} is not C{None}.

vfGraph.similarity_inverse_log_weighted(mode='all')¶

Inverse log-weighted similarity coefficient of vertices.

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

Note that the presence of loop edges may yield counter-intuitive results. A node with a loop edge is considered to be a neighbor of itself I{twice} (because there are two edge stems incident on the node). Adding a loop edge to a node may decrease its similarity to other nodes, but it may also I{increase} it. For instance, if nodes A and B are connected but share no common neighbors, their similarity is zero. However, if a loop edge is added to B, then B itself becomes a common neighbor of A and B and thus the similarity of A and B will be increased. Consider removing loop edges explicitly before invoking this function using L{Graph.simplify()}.

@param vertices: the vertices to be analysed. If C{None}, all vertices: will be considered.
@param mode: which neighbors should be considered for directed graphs.: Can be C{“all”}, C{“in”} or C{“out”}, ignored for undirected graphs. C{“in”} means that the weights are determined by the out-degrees, C{“out”} means that the weights are determined by the in-degrees.
@return: the pairwise similarity coefficients for the vertices specified,: in the form of a matrix (list of lists).

vfGraph.similarity_jaccard(pairs=None, mode='all', loops=True)¶

Jaccard similarity coefficient of vertices.

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

@param vertices: the vertices to be analysed. If C{None} and I{pairs} is also: C{None}, all vertices will be considered.
@param pairs: the vertex pairs to be analysed. If this is given, I{vertices}: must be C{None}, and the similarity values will be calculated only for the given pairs. Vertex pairs must be specified as tuples of vertex IDs.
@param mode: which neighbors should be considered for directed graphs.: Can be C{“all”}, C{“in”} or C{“out”}, ignored for undirected graphs.
@param loops: whether vertices should be considered adjacent to: themselves. Setting this to C{True} assumes a loop edge for all vertices even if none is present in the graph. Setting this to C{False} may result in strange results: nonadjacent vertices may have larger similarities compared to the case when an edge is added between them – however, this might be exactly the result you want to get.
@return: the pairwise similarity coefficients for the vertices specified,: in the form of a matrix if C{pairs} is C{None} or in the form of a list if C{pairs} is not C{None}.

vfGraph.simple_cycles(min=-1, max=-1, output='vpath')¶

Finds simple cycles in a graph

@param mode: for directed graphs, specifies how the edge directions: should be taken into account. C{“all”} means that the edge directions must be ignored, C{“out”} means that the edges must be oriented away from the root, C{“in”} means that the edges must be oriented towards the root. Ignored for undirected graphs.
@param min: the minimum number of vertices in a cycle: for it to be returned.
@param max: the maximum number of vertices in a cycle: for it to be considered.
@param output: determines what should be returned. If this is: C{“vpath”}, a list of tuples of vertex IDs will be returned. If this is C{“epath”}, edge IDs are returned instead of vertex IDs.

@return: see the documentation of the C{output} parameter.

vfGraph.simplify(loops=True, combine_edges=None)¶

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

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

@param multiple: whether to remove multiple edges. @param loops: whether to remove loops. @param combine_edges: specifies how to combine the attributes of

multiple edges between the same pair of vertices into a single attribute. If it is C{None}, only one of the edges will be kept and all the attributes will be lost. If it is a function, the attributes of multiple edges will be collected and passed on to that function which will return the new attribute value that has to be assigned to the single collapsed edge. It can also be one of the following string constants:

C{“ignore”}: all the edge attributes will be ignored.

C{“sum”}: the sum of the edge attribute values will be used for the new edge.

C{“product”}: the product of the edge attribute values will be used for the new edge.

C{“mean”}: the mean of the edge attribute values will be used for the new edge.

C{“median”}: the median of the edge attribute values will be used for the new edge.

C{“min”}: the minimum of the edge attribute values will be used for the new edge.

C{“max”}: the maximum of the edge attribute values will be used for the new edge.

C{“first”}: the attribute value of the first edge in the collapsed set will be used for the new edge.

C{“last”}: the attribute value of the last edge in the collapsed set will be used for the new edge.

C{“random”}: a randomly selected value will be used for the new edge

C{“concat”}: the attribute values will be concatenated for the new edge.

You can also use a dict mapping edge attribute names to functions or the above string constants if you want to make the behaviour of the simplification process depend on the name of the attribute. C{None} is a special key in this dict, its value will be used for all the attributes not specified explicitly in the dictionary.

vfGraph.spanning_tree(weights=None, return_tree=True, method='auto')[source]¶

Calculates a minimum spanning tree for a graph.

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

@param weights: a vector containing weights for every edge in: the graph. C{None} means that the graph is unweighted.
@param return_tree: whether to return the minimum spanning tree (when: C{return_tree} is C{True}) or to return the IDs of the edges in the minimum spanning tree instead (when C{return_tree} is C{False}). The default is C{True} for historical reasons as this argument was introduced in igraph 0.6.
@param method: the algorithm to use. C{“auto”} means that the algorithm: is selected automatically. C{“prim”} means that Prim’s algorithm is used. C{“kruskal”} means that Kruskal’s algorithm is used. C{“unweighted”} assumes that the graph is unweighted even if weights are provided.
@return: the spanning tree as a L{Graph} object if C{return_tree}: is C{True} or the IDs of the edges that constitute the spanning tree if C{return_tree} is C{False}.

vfGraph.st_mincut(source, target, capacity=None)[source]¶

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

@param source: the source vertex ID @param target: the target vertex ID @param capacity: the capacity of the edges. It must be a list or a valid

attribute name or C{None}. In the latter case, every edge will have the same capacity.

@return: 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

vfGraph.strength(mode='all', loops=True, weights=None)¶

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

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

@param vertices: a single vertex ID or a list of vertex IDs @param mode: the type of degree to be returned (C{“out”} for

out-degrees, C{“in”} for in-degrees or C{“all”} for the sum of them).

@param loops: whether self-loops should be counted. @param weights: edge weights to be used. Can be a sequence or iterable or

even an edge attribute name. None means to treat the graph as unweighted, falling back to ordinary degree calculations.

vfGraph.subcomponent(mode='all')¶

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

@param v: the index of the vertex used as the source/destination @param mode: if equals to C{“in”}, returns the vertex IDs from

where the given vertex can be reached. If equals to C{“out”}, returns the vertex IDs which are reachable from the given vertex. If equals to C{“all”}, returns all vertices within the same component as the given vertex, ignoring edge directions. Note that this is not equal to calculating the union of the results of C{“in”} and C{“out”}.

@return: the indices of vertices which are in the same component as a given vertex.

vfGraph.subgraph(implementation='auto')¶

Returns a subgraph spanned by the given vertices.

@param vertices: a list containing the vertex IDs which: should be included in the result.
@param implementation: the implementation to use when constructing: the new subgraph. igraph includes two implementations at the moment. C{“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 (C{“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. C{“auto”} selects between the two implementations automatically, based on the ratio of the size of the subgraph and the size of the original graph.

@return: the subgraph

vfGraph.subgraph_edges(delete_vertices=True)¶

Returns a subgraph spanned by the given edges.

@param edges: a list containing the edge IDs which should: be included in the result.
@param delete_vertices: if C{True}, vertices not incident on: any of the specified edges will be deleted from the result. If C{False}, all vertices will be kept.

@return: the subgraph

vfGraph.subisomorphic_lad(domains=None, induced=False, time_limit=0, return_mapping=False)¶

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

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

@param other: the pattern graph we are looking for in the graph. @param domains: a list of lists, one sublist belonging to each vertex in

the template graph. Sublist M{i} contains the indices of the vertices in the original graph that may match vertex M{i} in the template graph. C{None} means that every vertex may match every other vertex.

@param induced: whether to consider induced subgraphs only. @param time_limit: an optimal time limit in seconds. Only the integral

part of this number is taken into account. If the time limit is exceeded, the method will throw an exception.

@param return_mapping: when C{True}, the function will return a tuple,: where the first element is a boolean denoting whether a subisomorphism has been found or not, and the second element describes the mapping of the vertices from the template graph to the original graph. When C{False}, only the boolean is returned.
@return: if no mapping is calculated, the result is C{True} if the graph: contains a subgraph that is isomorphic to the given template, C{False} otherwise. If the mapping is calculated, the result is a tuple, the first element being the above mentioned boolean, and the second element being the mapping from the target to the original graph.

vfGraph.subisomorphic_vf2(color1=None, color2=None, edge_color1=None, edge_color2=None, return_mapping_12=False, return_mapping_21=False, callback=None, node_compat_fn=None, edge_compat_fn=None)¶

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

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

@param other: the other graph with which we want to compare the graph. @param color1: optional vector storing the coloring of the vertices of

the first graph. If C{None}, all vertices have the same color.

@param color2: optional vector storing the coloring of the vertices of: the second graph. If C{None}, all vertices have the same color.
@param edge_color1: optional vector storing the coloring of the edges of: the first graph. If C{None}, all edges have the same color.
@param edge_color2: optional vector storing the coloring of the edges of: the second graph. If C{None}, all edges have the same color.
@param return_mapping_12: if C{True}, calculates the mapping which maps: the vertices of the first graph to the second. The mapping can contain -1 if a given node is not mapped.
@param return_mapping_21: if C{True}, calculates the mapping which maps: the vertices of the second graph to the first. The mapping can contain -1 if a given node is not mapped.
@param callback: if not C{None}, the subisomorphism search will not stop at: the first match; it will call this callback function instead for every subisomorphism found. The callback function must accept four arguments: the first graph, the second graph, a mapping from the nodes of the first graph to the second, and a mapping from the nodes of the second graph to the first. The function must return C{True} if the search should continue or C{False} otherwise.
@param node_compat_fn: a function that receives the two graphs and two: node indices (one from the first graph, one from the second graph) and returns C{True} if the nodes given by the two indices are compatible (i.e. they could be matched to each other) or C{False} otherwise. This can be used to restrict the set of isomorphisms based on node-specific criteria that are too complicated to be represented by node color vectors (i.e. the C{color1} and C{color2} parameters). C{None} means that every node is compatible with every other node.
@param edge_compat_fn: a function that receives the two graphs and two: edge indices (one from the first graph, one from the second graph) and returns C{True} if the edges given by the two indices are compatible (i.e. they could be matched to each other) or C{False} otherwise. This can be used to restrict the set of isomorphisms based on edge-specific criteria that are too complicated to be represented by edge color vectors (i.e. the C{edge_color1} and C{edge_color2} parameters). C{None} means that every edge is compatible with every other node.
@return: if no mapping is calculated, the result is C{True} if the graph: contains a subgraph that’s isomorphic to the given one, C{False} otherwise. If any or both mappings are calculated, the result is a 3-tuple, the first element being the above mentioned boolean, the second element being the 1 -> 2 mapping and the third element being the 2 -> 1 mapping. If the corresponding mapping was not calculated, C{None} is returned in the appropriate element of the 3-tuple.

vfGraph.successors(vertex, loops=True, multiple=True)[source]¶

Returns the successors of a given vertex.

Equivalent to calling the L{Graph.neighbors()} method with mode=C{“out”}.

vfGraph.summary(verbosity=0, width=None, *args, **kwds)[source]¶

Returns the summary of the graph.

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

Behind the scenes, this method constructs a L{GraphSummary} object and invokes its C{__str__} method.

@param verbosity: if zero, only the header line is returned: (see C{__str__} for more details), otherwise the header line and the full edge list is printed.
@param width: the number of characters to use in one line.: If C{None}, no limit will be enforced on the line lengths.

@return: the summary of the graph.

vfGraph.to_dict_dict(use_vids=True, edge_attrs=None, skip_none=False, vertex_name_attr='name')[source]¶

Export graph to dictionary of dicts of edge attributes

This function is the reverse of Graph.DictDict.

Example

>>> g = Graph.Full(3)
>>> g.es['name'] = ['first_edge', 'second', 'third']
>>> g.to_dict_dict()
{0: {1: {'name': 'first_edge'}, 2: {'name': 'second'}}, 1: {2: {'name': 'third'}}}

@param use_vids: whether to label vertices in the output data: structure by their ids or their vertex_name_attr attribute. If use_vids=False but vertices lack a vertex_name_attr attribute, an AttributeError is raised.
@param edge_attrs: list of edge attributes to export.: None (default) signified all attributes (unlike Graph.to_tuple_list). A string is acceptable to signify a single attribute and will be wrapped in a list internally.
@param skip_none: whether to skip, for each edge, attributes that: have a value of None. This is useful if only some edges are expected to possess an attribute.
@param vertex_name_attr: only used with use_vids=False to choose what: vertex attribute to use to name your vertices in the output data structure.
@return: dictionary of dictionaries of dictionaries, with the outer keys: vertex ids/names, the middle keys ids/names of their neighbors, and the innermost dictionary representing attributes of that edge.

vfGraph.to_dict_list(use_vids=True, skip_none=False, vertex_name_attr='name')[source]¶

Export graph as two lists of dictionaries, for vertices and edges.

This function is the reverse of Graph.DictList.

Example

>>> g = Graph([(0, 1), (1, 2)])
>>> g.vs["name"] = ["apple", "pear", "peach"]
>>> g.es["name"] = ["first_edge", "second"]

>>> g.to_dict_list()
([{"name": "apple"}, {"name": "pear"}, {"name": "peach"}],
 [{"source": 0, "target": 1, "name": "first_edge"},
  {"source" 0, "target": 2, name": "second"}])

>>> g.to_dict_list(use_vids=False)
([{"name": "apple"}, {"name": "pear"}, {"name": "peach"}],
 [{"source": "apple", "target": "pear", "name": "first_edge"},
  {"source" "apple", "target": "peach", name": "second"}])

@param use_vids: whether to label vertices in the output data: structure by their ids or their vertex_name_attr attribute. If use_vids=False but vertices lack a vertex_name_attr attribute, an AttributeError is raised.
@param skip_none: whether to skip, for each edge, attributes that: have a value of None. This is useful if only some edges are expected to possess an attribute.
@param vertex_name_attr: only used with use_vids=False to choose what: vertex attribute to use to name your vertices in the output data structure.
@return: a tuple with two lists of dictionaries, representing the vertices: and the edges, respectively, with their attributes.

vfGraph.to_directed()¶

Converts an undirected graph to directed.

@param mode: specifies how to convert undirected edges into: directed ones. C{True} or C{“mutual”} creates a mutual edge pair for each undirected edge. C{False} or C{“arbitrary”} picks an arbitrary (but deterministic) edge direction for each edge. C{“random”} picks a random direction for each edge. C{“acyclic”} picks the edge directions in a way that the resulting graph will be acyclic if there were no self-loops in the original graph.

vfGraph.to_graph_tool(graph_attributes=None, vertex_attributes=None, edge_attributes=None)[source]¶

Converts the graph to graph-tool

Data types: graph-tool only accepts specific data types. See the following web page for a list:

https://graph-tool.skewed.de/static/doc/quickstart.html

Note: because of the restricted data types in graph-tool, vertex and edge attributes require to be type-consistent across all vertices or edges. If you set the property for only some vertices/edges, the other will be tagged as None in igraph, so they can only be converted to graph-tool with the type ‘object’ and any other conversion will fail.

@param graph_attributes: dictionary of graph attributes to transfer.: Keys are attributes from the graph, values are data types (see below). C{None} means no graph attributes are transferred.
@param vertex_attributes: dictionary of vertex attributes to transfer.: Keys are attributes from the vertices, values are data types (see below). C{None} means no vertex attributes are transferred.
@param edge_attributes: dictionary of edge attributes to transfer.: Keys are attributes from the edges, values are data types (see below). C{None} means no vertex attributes are transferred.

vfGraph.to_list_dict(use_vids=True, sequence_constructor=<class 'list'>, vertex_name_attr='name')[source]¶

Export graph to a dictionary of lists (or other sequences).

This function is the reverse of Graph.ListDict.

Example

>>> g = Graph.Full(3)
>>> g.to_sequence_dict() -> {0: [1, 2], 1: [2]}
>>> g.to_sequence_dict(sequence_constructor=tuple) -> {0: (1, 2), 1: (2,)}
>>> g.vs['name'] = ['apple', 'pear', 'peach']
>>> g.to_sequence_dict(use_vids=False)
{'apple': ['pear', 'peach'], 'pear': ['peach']}

@param use_vids: whether to label vertices in the output data: structure by their ids or their vertex_name_attr attribute. If use_vids=False but vertices lack a vertex_name_attr attribute, an AttributeError is raised.
@param sequence_constructor: constructor for the data structure: to be used as values of the dictionary. The default (list) makes a dict of lists, with each list representing the neighbors of the vertex specified in the respective dictionary key.
@param vertex_name_attr: only used with use_vids=False to choose what: vertex attribute to use to name your vertices in the output data structure.
@return: dictionary of sequences, keyed by vertices, with each value: containing the neighbors of that vertex.

vfGraph.to_networkx(create_using=None, vertex_attr_hashable='_nx_name')[source]¶

Converts the graph to networkx format.

igraph has ordered vertices and edges, but networkx does not. To keep track of the original order, the ‘_igraph_index’ vertex property is added to both vertices and edges.

@param create_using: specifies which NetworkX graph class to use when: constructing the graph. C{None} means to let igraph infer the most appropriate class based on whether the graph is directed and whether it has multi-edges.
@param vertex_attr_hashable: vertex attribute used to name vertices: in the exported network. The default “_nx_name” ensures round trip conversions to/from networkx are lossless.

vfGraph.to_prufer()¶

Converts a tree graph into a Prüfer sequence.

@return: the Prüfer sequence as a list

vfGraph.to_tuple_list(use_vids=True, edge_attrs=None, vertex_name_attr='name')[source]¶

Export graph to a list of edge tuples

This function is the reverse of Graph.TupleList.

Example

>>> g = Graph.Full(3)
>>> g.vs["name"] = ["apple", "pear", "peach"]
>>> g.es["name"] = ["first_edge", "second", "third"]

>>> # Get name of the edge
>>> g.to_tuple_list(edge_attrs=["name"])
[(0, 1, "first_edge"), (0, 2, "second"), (1, 2, "third")]

>>> # Use vertex names, no edge attributes
>>> g.to_tuple_list(use_vids=False)
[("apple", "pear"), ("apple", "peach"), ("pear", "peach")]

@param use_vids: whether to label vertices in the output data: structure by their ids or their vertex_name_attr attribute. If use_vids=False but vertices lack a vertex_name_attr attribute, an AttributeError is raised.
@param edge_attrs: list of edge attributes to export: in addition to source and target vertex, which are always the first two elements of each tuple. None (default) is equivalent to an empty list. A string is acceptable to signify a single attribute and will be wrapped in a list internally.
@param vertex_name_attr: only used with use_vids=False to choose what: vertex attribute to use to name your vertices in the output data structure.

@return: a list of tuples, each representing an edge of the graph.

vfGraph.to_undirected(combine_edges=None)¶

Converts a directed graph to undirected.

@param mode: specifies what to do with multiple directed edges: going between the same vertex pair. C{True} or C{“collapse”} means that only a single edge should be created from multiple directed edges. C{False} or C{“each”} means that every edge will be kept (with the arrowheads removed). C{“mutual”} creates one undirected edge for each mutual directed edge pair.
@param combine_edges: specifies how to combine the attributes of: multiple edges between the same pair of vertices into a single attribute. See L{simplify()} for more details.

vfGraph.topological_sorting()¶

Calculates a possible topological sorting of the graph.

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

@param mode: if C{“out”}, vertices are returned according to the: forward topological order – all vertices come before their successors. If C{“in”}, all vertices come before their ancestors.

@return: a possible topological ordering as a list

vfGraph.transitivity_avglocal_undirected(mode='nan', weights=None)[source]¶

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 I{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 L{transitivity_undirected()}) as it simply takes the average local transitivity across the whole network.

B{References}

Watts DJ and Strogatz S: Collective dynamics of small-world networks. I{Nature} 393(6884):440-442, 1998.

Barrat A, Barthelemy M, Pastor-Satorras R and Vespignani A: The architecture of complex weighted networks. I{PNAS} 101, 3747 (2004). U{https://arxiv.org/abs/cond-mat/0311416}.

@param mode: defines how to treat vertices with degree less than two.: If C{TRANSITIVITY_ZERO} or C{“zero”}, these vertices will have zero transitivity. If C{TRANSITIVITY_NAN} or C{“nan”}, these vertices will be excluded from the average.
@param weights: edge weights to be used. Can be a sequence or iterable: or even an edge attribute name.

@see: L{transitivity_undirected()}, L{transitivity_local_undirected()}

vfGraph.transitivity_local_undirected(mode='nan', weights=None)¶

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

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

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

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

B{References}:

D. J. Watts and S. Strogatz: Collective dynamics of small-world networks. I{Nature} 393(6884):440-442, 1998.

Barrat A, Barthelemy M, Pastor-Satorras R and Vespignani A: The architecture of complex weighted networks. I{PNAS} 101, 3747 (2004). U{https://arxiv.org/abs/cond-mat/0311416}.

@param vertices: a list containing the vertex IDs which should be: included in the result. C{None} means all of the vertices.
@param mode: defines how to treat vertices with degree less than two.: If C{TRANSITIVITT_ZERO} or C{“zero”}, these vertices will have zero transitivity. If C{TRANSITIVITY_NAN} or C{“nan”}, these vertices will have C{NaN} (not a number) as their transitivity.
@param weights: edge weights to be used. Can be a sequence or iterable or: even an edge attribute name.

@return: the transitivities for the given vertices in a list @see: L{transitivity_undirected()}, L{transitivity_avglocal_undirected()}

vfGraph.transitivity_undirected()¶

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

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

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

B{Reference}: S. Wasserman and K. Faust: I{Social Network Analysis: Methods and Applications}. Cambridge: Cambridge University Press, 1994.

@param mode: if C{TRANSITIVITY_ZERO} or C{“zero”}, the result will: be zero if the graph does not have any triplets. If C{“nan”} or C{TRANSITIVITY_NAN}, the result will be C{NaN} (not a number).

@return: the transitivity @see: L{transitivity_local_undirected()}, L{transitivity_avglocal_undirected()}

vfGraph.triad_census(*args, **kwds)[source]¶

Calculates the triad census of the graph.

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

@return: a L{TriadCensus} object.

vfGraph.unfold_tree(mode='out')¶

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

@param sources: the source vertices to start the unfolding from. It should be a: list of vertex indices, preferably one vertex from each connected component. You can use L{topological_sorting()} to determine a suitable set. A single vertex index is also accepted.
@param mode: which edges to follow during the BFS. C{OUT} follows outgoing edges,: C{IN} follows incoming edges, C{ALL} follows both. Ignored for undirected graphs.
@return: the unfolded tree graph and a mapping from the new vertex indices to the: old ones.

vfGraph.union(other, byname='auto')[source]¶

Creates the union of two (or more) graphs.

@param other: graph or list of graphs to be united with the current one. @param byname: whether to use vertex names instead of ids. See

L{igraph.operators.union} for details.

@return: the union graph

vfGraph.vcount()¶

Counts the number of vertices.

@return: the number of vertices in the graph. @rtype: integer

vfGraph.vertex_attributes()¶: @return: the attribute name list of the vertices of the graph

vfGraph.vertex_coloring_greedy()¶

Calculates a greedy vertex coloring for the graph based on some heuristics.

@param method: the heuristics to use. C{colored_neighbors} always picks the: vertex with the largest number of colored neighbors as the next vertex to pick a color for. C{dsatur} picks the vertex with the largest number of I{unique} colors in its neighborhood; this is also known as the DSatur heuristics (hence the name).

vfGraph.vertex_connectivity(target=-1, checks=True, neighbors='error')¶

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

@param source: the source vertex involved in the calculation. @param target: the target vertex involved in the calculation. @param checks: if the whole graph connectivity is calculated and this is

C{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 C{True}. The parameter is ignored if the connectivity between two given vertices is computed.

@param neighbors: tells igraph what to do when the two vertices are: connected. C{“error”} raises an exception, C{“negative”} returns a negative value, C{“number_of_nodes”} or C{“nodes”} returns the number of nodes, or C{“ignore”} ignores the edge.

@return: the vertex connectivity

vfGraph.vertex_disjoint_paths(target=-1, checks=True, neighbors='error')¶

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

@param source: the source vertex involved in the calculation. @param target: the target vertex involved in the calculation. @param checks: if the whole graph connectivity is calculated and this is

C{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 C{True}. The parameter is ignored if the connectivity between two given vertices is computed.

@param neighbors: tells igraph what to do when the two vertices are: connected. C{“error”} raises an exception, C{“negative”} returns a negative value, C{“number_of_nodes”} or C{“nodes”} returns the number of nodes, or C{“ignore”} ignores the edge.

@return: the vertex connectivity

vfGraph.write(f, format=None, *args, **kwds)[source]¶

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.

@param f: the file containing the graph to be saved @param 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). C{None} means auto-detection. Possible values are:

C{“adjacency”}: adjacency matrix format

C{“dimacs”}: DIMACS format

C{“dot”}, C{“graphviz”}: GraphViz DOT format

C{“edgelist”}, C{“edges”} or C{“edge”}: numeric edge list format

C{“gml”}: GML format

C{“graphml”} and C{“graphmlz”}: standard and gzipped GraphML format

C{“gw”}, C{“leda”}, C{“lgr”}: LEDA native format

C{“lgl”}: LGL format

C{“ncol”}: NCOL format

C{“net”}, C{“pajek”}: Pajek format

C{“pickle”}, C{“picklez”}: standard and gzipped Python pickled format

C{“svg”}: SVG format

@raises IOError: if the file format can’t be identified and: none was given.

vfGraph.write_adjacency(f, sep=' ', eol='\n', *args, **kwds)[source]¶

Writes the adjacency matrix of the graph to the given file

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

@param f: the name of the file to be written. @param sep: the string that separates the matrix elements in a row @param 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

vfGraph.write_dimacs(f, source=None, target=None, capacity='capacity')[source]¶

Writes the graph in DIMACS format to the given file.

@param f: the name of the file to be written or a Python file handle. @param source: the source vertex ID. If C{None}, igraph will try to

infer it from the C{source} graph attribute.

@param target: the target vertex ID. If C{None}, igraph will try to: infer it from the C{target} graph attribute.
@param 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.

vfGraph.write_dot()¶

Writes the graph in DOT format to the given file.

DOT is the format used by the U{GraphViz <http://www.graphviz.org>} software package.

@param f: the name of the file to be written or a Python file handle

vfGraph.write_edgelist()¶

Writes the edge list of a graph to a file.

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

@param f: the name of the file to be written or a Python file handle

vfGraph.write_gml(creator=None, ids=None)¶

Writes the graph in GML format to the given file.

@param f: the name of the file to be written or a Python file handle @param creator: optional creator information to be written to the file.

If C{None}, the current date and time is added.

@param ids: optional numeric vertex IDs to use in the file. This must: be a list of integers or C{None}. If C{None}, the C{id} attribute of the vertices are used, or if they don’t exist, numeric vertex IDs will be generated automatically.

vfGraph.write_graphml(prefixattr=True)¶

Writes the graph to a GraphML file.

@param f: the name of the file to be written or a Python file handle @param prefixattr: whether attribute names in the written file should be

prefixed with C{g_}, C{v_} and C{e_} for graph, vertex and edge attributes, respectively. This might be needed to ensure the uniqueness of attribute identifiers in the written GraphML file.

vfGraph.write_graphmlz(f, compresslevel=9)[source]¶

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 C{gunzip} or C{zcat} from Unix command line) or the Python C{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.

@param f: the name of the file to be written. @param compresslevel: the level of compression. 1 is fastest and

produces the least compression, and 9 is slowest and produces the most compression.

vfGraph.write_leda(names='name', weights='weights')¶

Writes the graph to a file in LEDA native format.

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

@param f: the name of the file to be written or a Python file handle @param names: the name of the vertex attribute to be stored along with

the vertices. It is usually used to store the vertex names (hence the name of the keyword argument), but you may also use a numeric attribute. If you don’t want to store any vertex attributes, supply C{None} here.

@param weights: the name of the edge attribute to be stored along with: the edges. It is usually used to store the edge weights (hence the name of the keyword argument), but you may also use a string attribute. If you don’t want to store any edge attributes, supply C{None} here.

vfGraph.write_lgl(names='name', weights='weights', isolates=True)¶

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

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

@param f: the name of the file to be written or a Python file handle @param names: the name of the vertex attribute containing the name

of the vertices. If you don’t want to store vertex names, supply C{None} here.

@param weights: the name of the edge attribute containing the weight: of the vertices. If you don’t want to store weights, supply C{None} here.

@param isolates: whether to include isolated vertices in the output.

vfGraph.write_ncol(names='name', weights='weights')¶

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

@param f: the name of the file to be written or a Python file handle @param names: the name of the vertex attribute containing the name

of the vertices. If you don’t want to store vertex names, supply C{None} here.

@param weights: the name of the edge attribute containing the weight: of the vertices. If you don’t want to store weights, supply C{None} here.

vfGraph.write_pajek()¶

Writes the graph in Pajek format to the given file.

@param f: the name of the file to be written or a Python file handle

vfGraph.write_pickle(fname=None, version=-1)[source]¶

Saves the graph in Python pickled format

@param fname: the name of the file or a stream to save to. If: C{None}, saves the graph to a string and returns the string.
@param version: pickle protocol version to be used. If -1, uses: the highest protocol available
@return: C{None} if the graph was saved successfully to the: given file, or a string if C{fname} was C{None}.

vfGraph.write_picklez(fname=None, version=-1)[source]¶

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.

@param fname: the name of the file or a stream to save to. @param version: pickle protocol version to be used. If -1, uses

the highest protocol available

@return: C{None} if the graph was saved successfully to the: given file.

vfGraph.write_svg(fname, layout='auto', width=None, height=None, labels='label', colors='color', shapes='shape', vertex_size=10, edge_colors='color', edge_stroke_widths='width', font_size=16, *args, **kwds)[source]¶

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.

@param fname: the name of the file or a Python file handle @param 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 L{Graph} object, but without the C{layout_} prefix.

@param width: the preferred width in pixels (default: 400) @param height: the preferred height in pixels (default: 400) @param 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 C{None}.

@param 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.
@param 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.

@param vertex_size: vertex size in pixels @param 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.

@param edge_stroke_widths: the stroke widths of the edges. Either: it is the name of an edge attribute to use, or a list explicitly specifying the stroke widths. The stroke width can be anything acceptable in an SVG file.
@param 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 C{font-size} style). If it is a number, it is interpreted as pixel size and converted to the proper attribute value accordingly.