Graph classes

Graph

A simple graph that has no self-loops or multiple (parallel) edges.

An empty graph is created with

>>> G=Graph()

DiGraph

A directed graph that has no self-loops or multiple (parallel) edges. Subclass of Graph.

An empty digraph is created with

>>> G=DiGraph()

XGraph

A graph that has (optional) self-loops or multiple (parallel) edges and arbitrary data on the edges. Subclass of Graph.

An empty graph is created with

>>> G=XGraph()

XDiGraph

A directed graph that has (optional) self-loops or multiple (parallel) edges and arbitrary data on the edges.

A simple digraph that has no self-loops or multiple (parallel) edges. Subclass of DiGraph which is a subclass of Graph.

An empty digraph is created with

>>> G=DiGraph()

The XGraph and XDiGraph classes extend the Graph and DiGraph classes by allowing (optional) self loops, multiedges and by decorating each edge with an object x.

Each XDiGraph or XGraph edge is a 3-tuple e=(n1,n2,x), representing an edge between nodes n1 and n2 that is decorated with the object x. Here n1 and n2 are (hashable) node objects and x is a (not necessarily hashable) edge object. If multiedges are allowed, G.get_edge(n1,n2) returns a list of edge objects.

Whether an XGraph or XDiGraph allow self-loops or multiple edges is determined initially via parameters selfloops=True/False and multiedges=True/False. For example, the example empty XGraph created above is equivalent to

>>> G=XGraph(selfloops=False, multiedges=False)

Similar defaults hold for XDiGraph. The command

>>> G=XDiGraph(multiedges=True)

creates an empty digraph G that does not allow selfloops but does allow for multiple (parallel) edges. Methods exist for allowing or disallowing each feature after instatiation as well.

Note that if G is an XGraph then G.add_edge(n1,n2) will add the edge (n1,n2,None), and G.delete_edge(n1,n2) will attempt to delete the edge (n1,n2,None). In the case of multiple edges between nodes n1 and n2, one can use G.delete_multiedge(n1,n2) to delete all edges between n1 and n2.

Notation

The following shorthand is used throughout NetworkX documentation and code: (we use mathematical notation n,v,w,... to indicate a node, v=vertex=node).

G,G1,G2,H,etc:

Graphs

n,n1,n2,u,v,v1,v2:

nodes (vertices)

nlist:

a list of nodes (vertices)

nbunch:

a "bunch" of nodes (vertices). An nbunch is either a single node of the graph or any iterable container/iterator of nodes. The distinction is determined by checking if nbunch is in the graph. If you use iterable containers as nodes you should be careful when using nbunch.

e=(n1,n2):

an edge (a python "2-tuple"), also written n1-n2 (if undirected) and n1->n2 (if directed).

e=(n1,n2,x):

an edge triple ("3-tuple") containing the two nodes connected and the edge data/label/object stored associated with the edge. The object x, or a list of objects (if multiedges=True), can be obtained using G.get_edge(n1,n2)

elist:

a list of edges (as 2- or 3-tuples)

ebunch:

a bunch of edges (as 2- or 3-tuples). An ebunch is any iterable (non-string) container of edge-tuples (either 2-tuples, 3-tuples or a mixture).

Warning:

• The ordering of objects within an arbitrary nbunch/ebunch can be machine-dependent.
• Algorithms should treat an arbitrary nbunch/ebunch as once-through-and-exhausted iterable containers.
• len(nbunch) and len(ebunch) need not be defined.

Methods

Each class provides basic graph methods.

Implementation Notes

The graph classes implement graphs using data structures based on an adjacency list implemented as a node-centric dictionary of dictionaries. The dictionary contains keys corresponding to the nodes and the values are dictionaries of neighboring node keys with the value None (the Python None type) for Graph and DiGraph or user specified (default is None) for XGraph and XDiGraph. The dictionary of dictionary structure allows fast addition, deletion and lookup of nodes and neighbors in large graphs.