This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Source code for networkx.generators.classic

Generators for some classic graphs.

The typical graph generator is called as follows:

>>> G=nx.complete_graph(100)

returning the complete graph on n nodes labeled 0,..,99
as a simple graph. Except for empty_graph, all the generators
in this module return a Graph class (i.e. a simple, undirected graph).

#    Copyright (C) 2004-2015 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.
import itertools

from networkx.algorithms.bipartite.generators import complete_bipartite_graph
from networkx.utils import accumulate

__author__ ="""Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)"""

__all__ = [ 'balanced_tree',

#   Some Classic Graphs
import networkx as nx
from networkx.utils import is_list_of_ints, flatten

def _tree_edges(n,r):
    # helper function for trees
    # yields edges in rooted tree at 0 with n nodes and branching ratio r
    parents=[next(nodes)] # stack of max length r
    while parents:
        for i in range(r):
                yield source,target
            except StopIteration:

def full_rary_tree(r, n, create_using=None):
    """Creates a full r-ary tree of n vertices.

    Sometimes called a k-ary, n-ary, or m-ary tree.  "... all non-leaf
    vertices have exactly r children and all levels are full except
    for some rightmost position of the bottom level (if a leaf at the
    bottom level is missing, then so are all of the leaves to its
    right." [1]_

    r : int
        branching factor of the tree
    n : int
        Number of nodes in the tree
    create_using : NetworkX graph type, optional
        Use specified type to construct graph (default = networkx.Graph)

    G : networkx Graph
        An r-ary tree with n nodes

    .. [1] An introduction to data structures and algorithms,
           James Andrew Storer,  Birkhauser Boston 2001, (page 225).
    return G

[docs]def balanced_tree(r, h, create_using=None): """Return the perfectly balanced r-tree of height h. Parameters ---------- r : int Branching factor of the tree h : int Height of the tree create_using : NetworkX graph type, optional Use specified type to construct graph (default = networkx.Graph) Returns ------- G : networkx Graph A tree with n nodes Notes ----- This is the rooted tree where all leaves are at distance h from the root. The root has degree r and all other internal nodes have degree r+1. Node labels are the integers 0 (the root) up to number_of_nodes - 1. Also refered to as a complete r-ary tree. """ # number of nodes is n=1+r+..+r^h if r==1: n=2 else: n = int((1-r**(h+1))/(1-r)) # sum of geometric series r!=1 G=nx.empty_graph(n,create_using) G.add_edges_from(_tree_edges(n,r)) return G return nx.full_rary_tree(r,n,create_using)
[docs]def barbell_graph(m1,m2,create_using=None): """Return the Barbell Graph: two complete graphs connected by a path. For m1 > 1 and m2 >= 0. Two identical complete graphs K_{m1} form the left and right bells, and are connected by a path P_{m2}. The 2*m1+m2 nodes are numbered 0,...,m1-1 for the left barbell, m1,...,m1+m2-1 for the path, and m1+m2,...,2*m1+m2-1 for the right barbell. The 3 subgraphs are joined via the edges (m1-1,m1) and (m1+m2-1,m1+m2). If m2=0, this is merely two complete graphs joined together. This graph is an extremal example in David Aldous and Jim Fill's etext on Random Walks on Graphs. """ if create_using is not None and create_using.is_directed(): raise nx.NetworkXError("Directed Graph not supported") if m1<2: raise nx.NetworkXError(\ "Invalid graph description, m1 should be >=2") if m2<0: raise nx.NetworkXError(\ "Invalid graph description, m2 should be >=0") # left barbell G=complete_graph(m1,create_using) G.name="barbell_graph(%d,%d)"%(m1,m2) # connecting path G.add_nodes_from([v for v in range(m1,m1+m2-1)]) if m2>1: G.add_edges_from([(v,v+1) for v in range(m1,m1+m2-1)]) # right barbell G.add_edges_from( (u,v) for u in range(m1+m2,2*m1+m2) for v in range(u+1,2*m1+m2)) # connect it up G.add_edge(m1-1,m1) if m2>0: G.add_edge(m1+m2-1,m1+m2) return G
[docs]def complete_graph(n,create_using=None): """ Return the complete graph K_n with n nodes. Node labels are the integers 0 to n-1. """ G=empty_graph(n,create_using) G.name="complete_graph(%d)"%(n) if n>1: if G.is_directed(): edges=itertools.permutations(range(n),2) else: edges=itertools.combinations(range(n),2) G.add_edges_from(edges) return G
[docs]def circular_ladder_graph(n,create_using=None): """Return the circular ladder graph CL_n of length n. CL_n consists of two concentric n-cycles in which each of the n pairs of concentric nodes are joined by an edge. Node labels are the integers 0 to n-1 """ G=ladder_graph(n,create_using) G.name="circular_ladder_graph(%d)"%n G.add_edge(0,n-1) G.add_edge(n,2*n-1) return G
def circulant_graph(n, offsets, create_using=None): """Generates the circulant graph Ci_n(x_1, x_2, ..., x_m) with n vertices. Returns ------- The graph Ci_n(x_1, ..., x_m) consisting of n vertices 0, ..., n-1 such that the vertex with label i is connected to the vertices labelled (i + x) and (i - x), for all x in x_1 up to x_m, with the indices taken modulo n. Parameters ---------- n : integer The number of vertices the generated graph is to contain. offsets : list of integers A list of vertex offsets, x_1 up to x_m, as described above. create_using : NetworkX graph type, optional Use specified type to construct graph (default = networkx.Graph) Examples -------- Many well-known graph families are subfamilies of the circulant graphs; for example, to generate the cycle graph on n points, we connect every vertex to every other at offset plus or minus one. For n = 10, >>> import networkx >>> G = networkx.generators.classic.circulant_graph(10, [1]) >>> edges = [ ... (0, 9), (0, 1), (1, 2), (2, 3), (3, 4), ... (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)] ... >>> sorted(edges) == sorted(G.edges()) True Similarly, we can generate the complete graph on 5 points with the set of offsets [1, 2]: >>> G = networkx.generators.classic.circulant_graph(5, [1, 2]) >>> edges = [ ... (0, 1), (0, 2), (0, 3), (0, 4), (1, 2), ... (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] ... >>> sorted(edges) == sorted(G.edges()) True """ G = empty_graph(n, create_using) template = 'circulant_graph(%d, [%s])' G.name = template % (n, ', '.join(str(j) for j in offsets)) for i in range(n): for j in offsets: G.add_edge(i, (i - j) % n) G.add_edge(i, (i + j) % n) return G
[docs]def cycle_graph(n,create_using=None): """Return the cycle graph C_n over n nodes. C_n is the n-path with two end-nodes connected. Node labels are the integers 0 to n-1 If create_using is a DiGraph, the direction is in increasing order. """ G=path_graph(n,create_using) G.name="cycle_graph(%d)"%n if n>1: G.add_edge(n-1,0) return G
[docs]def dorogovtsev_goltsev_mendes_graph(n,create_using=None): """Return the hierarchically constructed Dorogovtsev-Goltsev-Mendes graph. n is the generation. See: arXiv:/cond-mat/0112143 by Dorogovtsev, Goltsev and Mendes. """ if create_using is not None: if create_using.is_directed(): raise nx.NetworkXError("Directed Graph not supported") if create_using.is_multigraph(): raise nx.NetworkXError("Multigraph not supported") G=empty_graph(0,create_using) G.name="Dorogovtsev-Goltsev-Mendes Graph" G.add_edge(0,1) if n==0: return G new_node = 2 # next node to be added for i in range(1,n+1): #iterate over number of generations. last_generation_edges = G.edges() number_of_edges_in_last_generation = len(last_generation_edges) for j in range(0,number_of_edges_in_last_generation): G.add_edge(new_node,last_generation_edges[j][0]) G.add_edge(new_node,last_generation_edges[j][1]) new_node += 1 return G
[docs]def empty_graph(n=0,create_using=None): """Return the empty graph with n nodes and zero edges. Node labels are the integers 0 to n-1 For example: >>> G=nx.empty_graph(10) >>> G.number_of_nodes() 10 >>> G.number_of_edges() 0 The variable create_using should point to a "graph"-like object that will be cleaned (nodes and edges will be removed) and refitted as an empty "graph" with n nodes with integer labels. This capability is useful for specifying the class-nature of the resulting empty "graph" (i.e. Graph, DiGraph, MyWeirdGraphClass, etc.). The variable create_using has two main uses: Firstly, the variable create_using can be used to create an empty digraph, network,etc. For example, >>> n=10 >>> G=nx.empty_graph(n,create_using=nx.DiGraph()) will create an empty digraph on n nodes. Secondly, one can pass an existing graph (digraph, pseudograph, etc.) via create_using. For example, if G is an existing graph (resp. digraph, pseudograph, etc.), then empty_graph(n,create_using=G) will empty G (i.e. delete all nodes and edges using G.clear() in base) and then add n nodes and zero edges, and return the modified graph (resp. digraph, pseudograph, etc.). See also create_empty_copy(G). """ if create_using is None: # default empty graph is a simple graph G=nx.Graph() else: G=create_using G.clear() G.add_nodes_from(range(n)) G.name="empty_graph(%d)"%n return G
[docs]def grid_2d_graph(m,n,periodic=False,create_using=None): """ Return the 2d grid graph of mxn nodes, each connected to its nearest neighbors. Optional argument periodic=True will connect boundary nodes via periodic boundary conditions. """ G=empty_graph(0,create_using) G.name="grid_2d_graph" rows=range(m) columns=range(n) G.add_nodes_from( (i,j) for i in rows for j in columns ) G.add_edges_from( ((i,j),(i-1,j)) for i in rows for j in columns if i>0 ) G.add_edges_from( ((i,j),(i,j-1)) for i in rows for j in columns if j>0 ) if G.is_directed(): G.add_edges_from( ((i,j),(i+1,j)) for i in rows for j in columns if i<m-1 ) G.add_edges_from( ((i,j),(i,j+1)) for i in rows for j in columns if j<n-1 ) if periodic: if n>2: G.add_edges_from( ((i,0),(i,n-1)) for i in rows ) if G.is_directed(): G.add_edges_from( ((i,n-1),(i,0)) for i in rows ) if m>2: G.add_edges_from( ((0,j),(m-1,j)) for j in columns ) if G.is_directed(): G.add_edges_from( ((m-1,j),(0,j)) for j in columns ) G.name="periodic_grid_2d_graph(%d,%d)"%(m,n) return G
[docs]def grid_graph(dim,periodic=False): """ Return the n-dimensional grid graph. The dimension is the length of the list 'dim' and the size in each dimension is the value of the list element. E.g. G=grid_graph(dim=[2,3]) produces a 2x3 grid graph. If periodic=True then join grid edges with periodic boundary conditions. """ dlabel="%s"%dim if dim==[]: G=empty_graph(0) G.name="grid_graph(%s)"%dim return G if not is_list_of_ints(dim): raise nx.NetworkXError("dim is not a list of integers") if min(dim)<=0: raise nx.NetworkXError(\ "dim is not a list of strictly positive integers") if periodic: func=cycle_graph else: func=path_graph dim=list(dim) current_dim=dim.pop() G=func(current_dim) while len(dim)>0: current_dim=dim.pop() # order matters: copy before it is cleared during the creation of Gnew Gold=G.copy() Gnew=func(current_dim) # explicit: create_using=None # This is so that we get a new graph of Gnew's class. G=nx.cartesian_product(Gnew,Gold) # graph G is done but has labels of the form (1,(2,(3,1))) # so relabel H=nx.relabel_nodes(G, flatten) H.name="grid_graph(%s)"%dlabel return H
[docs]def hypercube_graph(n): """Return the n-dimensional hypercube. Node labels are the integers 0 to 2**n - 1. """ dim=n*[2] G=grid_graph(dim) G.name="hypercube_graph_(%d)"%n return G
[docs]def ladder_graph(n,create_using=None): """Return the Ladder graph of length n. This is two rows of n nodes, with each pair connected by a single edge. Node labels are the integers 0 to 2*n - 1. """ if create_using is not None and create_using.is_directed(): raise nx.NetworkXError("Directed Graph not supported") G=empty_graph(2*n,create_using) G.name="ladder_graph_(%d)"%n G.add_edges_from([(v,v+1) for v in range(n-1)]) G.add_edges_from([(v,v+1) for v in range(n,2*n-1)]) G.add_edges_from([(v,v+n) for v in range(n)]) return G
[docs]def lollipop_graph(m,n,create_using=None): """Return the Lollipop Graph; `K_m` connected to `P_n`. This is the Barbell Graph without the right barbell. For m>1 and n>=0, the complete graph K_m is connected to the path P_n. The resulting m+n nodes are labelled 0,...,m-1 for the complete graph and m,...,m+n-1 for the path. The 2 subgraphs are joined via the edge (m-1,m). If n=0, this is merely a complete graph. Node labels are the integers 0 to number_of_nodes - 1. (This graph is an extremal example in David Aldous and Jim Fill's etext on Random Walks on Graphs.) """ if create_using is not None and create_using.is_directed(): raise nx.NetworkXError("Directed Graph not supported") if m<2: raise nx.NetworkXError(\ "Invalid graph description, m should be >=2") if n<0: raise nx.NetworkXError(\ "Invalid graph description, n should be >=0") # the ball G=complete_graph(m,create_using) # the stick G.add_nodes_from([v for v in range(m,m+n)]) if n>1: G.add_edges_from([(v,v+1) for v in range(m,m+n-1)]) # connect ball to stick if m>0: G.add_edge(m-1,m) G.name="lollipop_graph(%d,%d)"%(m,n) return G
[docs]def null_graph(create_using=None): """Return the Null graph with no nodes or edges. See empty_graph for the use of create_using. """ G=empty_graph(0,create_using) G.name="null_graph()" return G
[docs]def path_graph(n,create_using=None): """Return the Path graph P_n of n nodes linearly connected by n-1 edges. Node labels are the integers 0 to n - 1. If create_using is a DiGraph then the edges are directed in increasing order. """ G=empty_graph(n,create_using) G.name="path_graph(%d)"%n G.add_edges_from([(v,v+1) for v in range(n-1)]) return G
[docs]def star_graph(n,create_using=None): """ Return the Star graph with n+1 nodes: one center node, connected to n outer nodes. Node labels are the integers 0 to n. """ G=complete_bipartite_graph(1,n,create_using) G.name="star_graph(%d)"%n return G
[docs]def trivial_graph(create_using=None): """ Return the Trivial graph with one node (with integer label 0) and no edges. """ G=empty_graph(1,create_using) G.name="trivial_graph()" return G
[docs]def wheel_graph(n,create_using=None): """ Return the wheel graph: a single hub node connected to each node of the (n-1)-node cycle graph. Node labels are the integers 0 to n - 1. """ if n == 0: return nx.empty_graph(n, create_using=create_using) G=star_graph(n-1,create_using) G.name="wheel_graph(%d)"%n G.add_edges_from([(v,v+1) for v in range(1,n-1)]) if n>2: G.add_edge(1,n-1) return G
[docs]def complete_multipartite_graph(*block_sizes): """Returns the complete multipartite graph with the specified block sizes. Parameters ---------- block_sizes : tuple of integers The number of vertices in each block of the multipartite graph. The length of this tuple is the number of blocks. Returns ------- G : NetworkX Graph Returns the complete multipartite graph with the specified block sizes. For each node, the node attribute ``'block'`` is an integer indicating which block contains the node. Examples -------- Creating a complete tripartite graph, with blocks of one, two, and three vertices, respectively. >>> import networkx as nx >>> G = nx.complete_multipartite_graph(1, 2, 3) >>> [G.node[u]['block'] for u in G] [0, 1, 1, 2, 2, 2] >>> G.edges(0) [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)] >>> G.edges(2) [(2, 0), (2, 3), (2, 4), (2, 5)] >>> G.edges(4) [(4, 0), (4, 1), (4, 2)] Notes ----- This function generalizes several other graph generator functions. - If no block sizes are given, this returns the null graph. - If a single block size ``n`` is given, this returns the empty graph on ``n`` nodes. - If two block sizes ``m`` and ``n`` are given, this returns the complete bipartite graph on ``m + n`` nodes. - If block sizes ``1`` and ``n`` are given, this returns the star graph on ``n + 1`` nodes. See also -------- complete_bipartite_graph """ G = nx.empty_graph(sum(block_sizes)) # If block_sizes is (n1, n2, n3, ...), create pairs of the form (0, n1), # (n1, n1 + n2), (n1 + n2, n1 + n2 + n3), etc. extents = zip([0] + list(accumulate(block_sizes)), accumulate(block_sizes)) blocks = [range(start, end) for start, end in extents] for (i, block) in enumerate(blocks): G.add_nodes_from(block, block=i) # Across blocks, all vertices should be adjacent. We can use # itertools.combinations() because the complete multipartite graph is an # undirected graph. for block1, block2 in itertools.combinations(blocks, 2): G.add_edges_from(itertools.product(block1, block2)) G.name = 'complete_multiparite_graph{0}'.format(block_sizes) return G