Overview

NetworkX provides

  • tools for the study of the structure and dynamics of social, biological, and infrastructure networks;
  • a standard programming interface and graph implementation that is suitable for many applications;
  • a rapid development environment for collaborative, multidisciplinary projects;
  • an interface to existing numerical algorithms and code written in C, C++, and FORTRAN; and
  • the ability to painlessly work with large nonstandard data sets.

With NetworkX you can load and store networks in standard and nonstandard data formats, generate many types of random and classic networks, analyze network structure, build network models, design new network algorithms, draw networks, and much more.

Audience

The audience for NetworkX includes mathematicians, physicists, biologists, computer scientists, and social scientists. Good reviews of the science of complex networks are presented in Albert and Barabási [BA02], Newman [Newman03], and Dorogovtsev and Mendes [DM03]. See also the classic texts [Bollobas01], [Diestel97] and [West01] for graph theoretic results and terminology. For basic graph algorithms, we recommend the texts of Sedgewick (e.g., [Sedgewick01] and [Sedgewick02]) and the survey of Brandes and Erlebach [BE05].

Python

Python is a powerful programming language that allows simple and flexible representations of networks as well as clear and concise expressions of network algorithms. Python has a vibrant and growing ecosystem of packages that NetworkX uses to provide more features such as numerical linear algebra and drawing. In order to make the most out of NetworkX you will want to know how to write basic programs in Python. Among the many guides to Python, we recommend the Python documentation and the text by Alex Martelli [Martelli03].

Free software

NetworkX is free software; you can redistribute it and/or modify it under the terms of the 3-clause BSD License. We welcome contributions. Join us on GitHub.

History

NetworkX was born in May 2002. The original version was designed and written by Aric Hagberg, Dan Schult, and Pieter Swart in 2002 and 2003. The first public release was in April 2005. Many people have contributed to the success of NetworkX. Some of the contributors are listed in the credits.

Documentation

Release:2.0.dev_20170724193324
Date:Jul 24, 2017

Install

NetworkX requires Python 2.7, 3.3, 3.4, 3.5, or 3.6. If you do not already have a Python environment configured on your computer, please see the instructions for installing the full scientific Python stack.

Note

If you are on Windows and want to install optional packages (e.g., scipy), then you will need to install a Python distribution such as Anaconda, Enthought Canopy, Python(x,y), WinPython, or Pyzo. If you use one of these Python distribution, please refer to their online documentation.

Below we assume you have the default Python environment already configured on your computer and you intend to install networkx inside of it. If you want to create and work with Python virtual environments, please follow instructions on venv and virtual environments.

First, make sure you have the latest version of pip (the Python package manager) installed. If you do not, refer to the Pip documentation and install pip first.

Install the released version

Install the current release of networkx with pip:

$ pip install networkx

To upgrade to a newer release use the --upgrade flag:

$ pip install --upgrade networkx

If you do not have permission to install software systemwide, you can install into your user directory using the --user flag:

$ pip install --user networkx

Alternatively, you can manually download networkx from GitHub or PyPI. To install one of these versions, unpack it and run the following from the top-level source directory using the Terminal:

$ pip install .

Install the development version

If you have Git installed on your system, it is also possible to install the development version of networkx.

Before installing the development version, you may need to uninstall the standard version of networkx using pip:

$ pip uninstall networkx

Then do:

$ git clone https://github.com/networkx/networkx.git
$ cd networkx
$ pip install -e .

The pip install -e . command allows you to follow the development branch as it changes by creating links in the right places and installing the command line scripts to the appropriate locations.

Then, if you want to update networkx at any time, in the same directory do:

$ git pull

Optional packages

Note

Some optional packages (e.g., scipy, gdal) may require compiling C or C++ code. If you have difficulty installing these packages with pip, please review the instructions for installing the full scientific Python stack.

The following optional packages provide additional functionality.

  • NumPy (>= 1.6) provides matrix representation of graphs and is used in some graph algorithms for high-performance matrix computations.
  • SciPy (>= 0.10) provides sparse matrix representation of graphs and many numerical scientific tools.
  • pandas (>= 0.8) provides a DataFrame, which is a tabular data structure with labeled axes.
  • Matplotlib (>= 1.1) provides flexible drawing of graphs.
  • PyGraphviz and pydot (>= 1.2.3) provide graph drawing and graph layout algorithms via GraphViz.
  • PyYAML provides YAML format reading and writing.
  • gdal provides shapefile format reading and writing.

To install networkx and all optional packages, do:

$ pip install networkx[all]

To explicitly install all optional packages, do:

$ pip install numpy scipy pandas matplotlib pygraphviz pydot pyyaml gdal

Or, install any optional package (e.g., numpy) individually:

$ pip install numpy

Testing

NetworkX uses the Python nose testing package. If you don’t already have that package installed, follow the directions on the nose homepage.

Test a source distribution

You can test the complete package from the unpacked source directory with:

nosetests networkx -v
Test an installed package

If you have a file-based (not a Python egg) installation you can test the installed package with:

>>> import networkx as nx
>>> nx.test()

or:

python -c "import networkx as nx; nx.test()"
Testing for developers

You can test any or all of NetworkX by using the nosetests test runner.

First make sure the NetworkX version you want to test is in your PYTHONPATH (either installed or pointing to your unpacked source directory).

Then you can run individual test files with:

nosetests path/to/file

or all tests found in dir and an directories contained in dir:

nosetests path/to/dir

By default nosetests does not test docutils style tests in Python modules but you can turn that on with:

nosetests --with-doctest

For doctests in stand-alone files NetworkX uses the extension txt so you can add:

nosetests --with-doctest --doctest-extension=txt

to also execute those tests.

These options are on by default if you run nosetests from the root of the NetworkX distribution since they are specified in the setup.cfg file found there.

Tutorial

Start here to begin working with NetworkX.

Creating a graph

Create an empty graph with no nodes and no edges.

>>> import networkx as nx
>>> G = nx.Graph()

By definition, a Graph is a collection of nodes (vertices) along with identified pairs of nodes (called edges, links, etc). In NetworkX, nodes can be any hashable object e.g., a text string, an image, an XML object, another Graph, a customized node object, etc.

Note

Python’s None object should not be used as a node as it determines whether optional function arguments have been assigned in many functions.

Nodes

The graph G can be grown in several ways. NetworkX includes many graph generator functions and facilities to read and write graphs in many formats. To get started though we’ll look at simple manipulations. You can add one node at a time,

>>> G.add_node(1)

add a list of nodes,

>>> G.add_nodes_from([2, 3])

or add any nbunch of nodes. An nbunch is any iterable container of nodes that is not itself a node in the graph (e.g., a list, set, graph, file, etc.).

>>> H = nx.path_graph(10)
>>> G.add_nodes_from(H)

Note that G now contains the nodes of H as nodes of G. In contrast, you could use the graph H as a node in G.

>>> G.add_node(H)

The graph G now contains H as a node. This flexibility is very powerful as it allows graphs of graphs, graphs of files, graphs of functions and much more. It is worth thinking about how to structure your application so that the nodes are useful entities. Of course you can always use a unique identifier in G and have a separate dictionary keyed by identifier to the node information if you prefer.

Note

You should not change the node object if the hash depends on its contents.

Edges

G can also be grown by adding one edge at a time,

>>> G.add_edge(1, 2)
>>> e = (2, 3)
>>> G.add_edge(*e)  # unpack edge tuple*

by adding a list of edges,

>>> G.add_edges_from([(1, 2), (1, 3)])

or by adding any ebunch of edges. An ebunch is any iterable container of edge-tuples. An edge-tuple can be a 2-tuple of nodes or a 3-tuple with 2 nodes followed by an edge attribute dictionary, e.g., (2, 3, {'weight': 3.1415}). Edge attributes are discussed further below

>>> G.add_edges_from(H.edges())

One can demolish the graph in a similar fashion; using Graph.remove_node(), Graph.remove_nodes_from(), Graph.remove_edge() and Graph.remove_edges_from(), e.g.

>>> G.remove_node(H)

There are no complaints when adding existing nodes or edges. For example, after removing all nodes and edges,

>>> G.clear()

we add new nodes/edges and NetworkX quietly ignores any that are already present.

>>> G.add_edges_from([(1, 2), (1, 3)])
>>> G.add_node(1)
>>> G.add_edge(1, 2)
>>> G.add_node("spam")        # adds node "spam"
>>> G.add_nodes_from("spam")  # adds 4 nodes: 's', 'p', 'a', 'm'

At this stage the graph G consists of 8 nodes and 2 edges, as can be seen by:

>>> G.number_of_nodes()
8
>>> G.number_of_edges()
2

We can examine the nodes and edges. The methods return iterators of nodes, edges, neighbors, etc. This is typically more memory efficient, but it does mean we need to specify what type of container to put the objects in. Here we use lists, though sets, dicts, tuples and other containers may be better in other contexts.

>>> list(G.nodes())
['a', 1, 2, 3, 'spam', 'm', 'p', 's']
>>> list(G.edges())
[(1, 2), (1, 3)]
>>> list(G.neighbors(1))
[2, 3]

Removing nodes or edges has similar syntax to adding:

>>> G.remove_nodes_from("spam")
>>> list(G.nodes())
[1, 2, 3, 'spam']
>>> G.remove_edge(1, 3)

When creating a graph structure by instantiating one of the graph classes you can specify data in several formats.

>>> H=nx.DiGraph(G)   # create a DiGraph using the connections from G
>>> list(H.edges())
[(1, 2), (2, 1)]
>>> edgelist=[(0, 1), (1, 2), (2, 3)]
>>> H=nx.Graph(edgelist)

What to use as nodes and edges

You might notice that nodes and edges are not specified as NetworkX objects. This leaves you free to use meaningful items as nodes and edges. The most common choices are numbers or strings, but a node can be any hashable object (except None), and an edge can be associated with any object x using G.add_edge(n1, n2, object=x).

As an example, n1 and n2 could be protein objects from the RCSB Protein Data Bank, and x could refer to an XML record of publications detailing experimental observations of their interaction.

We have found this power quite useful, but its abuse can lead to unexpected surprises unless one is familiar with Python. If in doubt, consider using convert_node_labels_to_integers() to obtain a more traditional graph with integer labels.

Accessing edges

In addition to the methods Graph.nodes(), Graph.edges(), and Graph.neighbors(), fast direct access to the graph data structure is also possible using subscript notation.

Warning

Do not change the returned dict—it is part of the graph data structure and direct manipulation may leave the graph in an inconsistent state.

>>> G[1]  # Warning: do not change the resulting dict
{2: {}}
>>> G[1][2]
{}

You can safely set the attributes of an edge using subscript notation if the edge already exists.

>>> G.add_edge(1, 3)
>>> G[1][3]['color'] = "blue"

Fast examination of all edges is achieved using adjacency iterators. Note that for undirected graphs this actually looks at each edge twice.

>>> FG = nx.Graph()
>>> FG.add_weighted_edges_from([(1, 2, 0.125), (1, 3, 0.75), (2, 4, 1.2), (3, 4, 0.375)])
>>> for n, nbrs in FG.adjacency():
...    for nbr, eattr in nbrs.items():
...        data = eattr['weight']
...        if data < 0.5: print('(%d, %d, %.3f)' % (n, nbr, data))
(1, 2, 0.125)
(2, 1, 0.125)
(3, 4, 0.375)
(4, 3, 0.375)

Convenient access to all edges is achieved with the edges method.

>>> for (u, v, d) in FG.edges(data='weight'):
...     if d < 0.5: print('(%d, %d, %.3f)' % (u, v, d))
(1, 2, 0.125)
(3, 4, 0.375)

Adding attributes to graphs, nodes, and edges

Attributes such as weights, labels, colors, or whatever Python object you like, can be attached to graphs, nodes, or edges.

Each graph, node, and edge can hold key/value attribute pairs in an associated attribute dictionary (the keys must be hashable). By default these are empty, but attributes can be added or changed using add_edge, add_node or direct manipulation of the attribute dictionaries named G.graph, G.node, and G.edge for a graph G.

Graph attributes

Assign graph attributes when creating a new graph

>>> G = nx.Graph(day="Friday")
>>> G.graph
{'day': 'Friday'}

Or you can modify attributes later

>>> G.graph['day'] = "Monday"
>>> G.graph
{'day': 'Monday'}
Node attributes

Add node attributes using add_node(), add_nodes_from(), or G.node

>>> G.add_node(1, time='5pm')
>>> G.add_nodes_from([3], time='2pm')
>>> G.node[1]
{'time': '5pm'}
>>> G.node[1]['room'] = 714
>>> list(G.nodes(data=True))
[(1, {'room': 714, 'time': '5pm'}), (3, {'time': '2pm'})]

Note that adding a node to G.node does not add it to the graph, use G.add_node() to add new nodes.

Edge Attributes

Add edge attributes using add_edge(), add_edges_from(), subscript notation, or G.edge.

>>> G.add_edge(1, 2, weight=4.7 )
>>> G.add_edges_from([(3, 4), (4, 5)], color='red')
>>> G.add_edges_from([(1, 2, {'color': 'blue'}), (2, 3, {'weight': 8})])
>>> G[1][2]['weight'] = 4.7
>>> G.edge[1][2]['weight'] = 4

The special attribute weight should be numeric and holds values used by algorithms requiring weighted edges.

Warning

Do not assign anything to G.edge[u] or G.edge[u][v] as it will corrupt the graph data structure. Change the edge dict as shown above.

Directed graphs

The DiGraph class provides additional methods specific to directed edges, e.g., DiGraph.out_edges(), DiGraph.in_degree(), DiGraph.predecessors(), DiGraph.successors() etc. To allow algorithms to work with both classes easily, the directed versions of neighbors() and degree() are equivalent to successors() and the sum of in_degree() and out_degree() respectively even though that may feel inconsistent at times.

>>> DG = nx.DiGraph()
>>> DG.add_weighted_edges_from([(1, 2, 0.5), (3, 1, 0.75)])
>>> DG.out_degree(1, weight='weight')
0.5
>>> DG.degree(1, weight='weight')
1.25
>>> DG.successors(1)
[2]
>>> DG.neighbors(1)
[2]

Some algorithms work only for directed graphs and others are not well defined for directed graphs. Indeed the tendency to lump directed and undirected graphs together is dangerous. If you want to treat a directed graph as undirected for some measurement you should probably convert it using Graph.to_undirected() or with

>>> H = nx.Graph(G)  # convert G to undirected graph

Multigraphs

NetworkX provides classes for graphs which allow multiple edges between any pair of nodes. The MultiGraph and MultiDiGraph classes allow you to add the same edge twice, possibly with different edge data. This can be powerful for some applications, but many algorithms are not well defined on such graphs. Where results are well defined, e.g., MultiGraph.degree() we provide the function. Otherwise you should convert to a standard graph in a way that makes the measurement well defined.

>>> MG = nx.MultiGraph()
>>> MG.add_weighted_edges_from([(1, 2, 0.5), (1, 2, 0.75), (2, 3, 0.5)])
>>> dict(MG.degree(weight='weight'))
{1: 1.25, 2: 1.75, 3: 0.5}
>>> GG = nx.Graph()
>>> for n, nbrs in MG.adjacency_iter():
...    for nbr, edict in nbrs.items():
...        minvalue = min([d['weight'] for d in edict.values()])
...        GG.add_edge(n, nbr, weight = minvalue)
...
>>> nx.shortest_path(GG, 1, 3)
[1, 2, 3]

Graph generators and graph operations

In addition to constructing graphs node-by-node or edge-by-edge, they can also be generated by

  1. Applying classic graph operations, such as:

    subgraph(G, nbunch)      - induce subgraph of G on nodes in nbunch
    union(G1,G2)             - graph union
    disjoint_union(G1,G2)    - graph union assuming all nodes are different
    cartesian_product(G1,G2) - return Cartesian product graph
    compose(G1,G2)           - combine graphs identifying nodes common to both
    complement(G)            - graph complement
    create_empty_copy(G)     - return an empty copy of the same graph class
    convert_to_undirected(G) - return an undirected representation of G
    convert_to_directed(G)   - return a directed representation of G
    
  2. Using a call to one of the classic small graphs, e.g.,

>>> petersen = nx.petersen_graph()
>>> tutte = nx.tutte_graph()
>>> maze = nx.sedgewick_maze_graph()
>>> tet = nx.tetrahedral_graph()
  1. Using a (constructive) generator for a classic graph, e.g.,
>>> K_5 = nx.complete_graph(5)
>>> K_3_5 = nx.complete_bipartite_graph(3, 5)
>>> barbell = nx.barbell_graph(10, 10)
>>> lollipop = nx.lollipop_graph(10, 20)
  1. Using a stochastic graph generator, e.g.,
>>> er = nx.erdos_renyi_graph(100, 0.15)
>>> ws = nx.watts_strogatz_graph(30, 3, 0.1)
>>> ba = nx.barabasi_albert_graph(100, 5)
>>> red = nx.random_lobster(100, 0.9, 0.9)
  1. Reading a graph stored in a file using common graph formats, such as edge lists, adjacency lists, GML, GraphML, pickle, LEDA and others.
>>> nx.write_gml(red, "path.to.file")
>>> mygraph = nx.read_gml("path.to.file")

For details on graph formats see Reading and writing graphs and for graph generator functions see Graph generators

Analyzing graphs

The structure of G can be analyzed using various graph-theoretic functions such as:

>>> G = nx.Graph()
>>> G.add_edges_from([(1, 2), (1, 3)])
>>> G.add_node("spam")       # adds node "spam"
>>> list(nx.connected_components(G))
[{1, 2, 3}, {'spam'}]
>>> sorted(d for n, d in G.degree())
[0, 1, 1, 2]
>>> nx.clustering(G)
{1: 0.0, 2: 0.0, 3: 0.0, 'spam': 0.0}

Functions that return node properties return iterators over node, value 2-tuples. These are easily stored in a dict structure if you desire.

>>> dict(nx.degree(G))
{1: 2, 2: 1, 3: 1, 'spam': 0}

For values of specific nodes, you can provide a single node or an nbunch of nodes as argument. If a single node is specified, then a single value is returned. If an nbunch is specified, then the function will return a dictionary.

>>> nx.degree(G, 1)
2
>>> G.degree(1)
2
>>> dict(G.degree([1, 2]))
{1: 2, 2: 1}
>>> sorted(d for n, d in G.degree([1, 2]))
[1, 2]
>>> sorted(d for n, d in G.degree())
[0, 1, 1, 2]

See Algorithms for details on graph algorithms supported.

Drawing graphs

NetworkX is not primarily a graph drawing package but basic drawing with Matplotlib as well as an interface to use the open source Graphviz software package are included. These are part of the networkx.drawing module and will be imported if possible.

First import Matplotlib’s plot interface (pylab works too)

>>> import matplotlib.pyplot as plt

You may find it useful to interactively test code using ipython -pylab, which combines the power of ipython and matplotlib and provides a convenient interactive mode.

To test if the import of networkx.drawing was successful draw G using one of

>>> nx.draw(G)
>>> nx.draw_random(G)
>>> nx.draw_circular(G)
>>> nx.draw_spectral(G)

when drawing to an interactive display. Note that you may need to issue a Matplotlib

>>> plt.show()

command if you are not using matplotlib in interactive mode (see Matplotlib FAQ ).

To save drawings to a file, use, for example

>>> nx.draw(G)
>>> plt.savefig("path.png")

writes to the file path.png in the local directory. If Graphviz and PyGraphviz or pydot, are available on your system, you can also use nx_agraph.graphviz_layout(G) or nx_pydot.graphviz_layout(G) to get the node positions, or write the graph in dot format for further processing.

>>> from networkx.drawing.nx_pydot import write_dot
>>> pos = nx.nx_agraph.graphviz_layout(G)
>>> nx.draw(G, pos=pos)
>>> nx.write_dot(G, 'file.dot')

See Drawing for additional details.

Reference

Release:2.0.dev20170724193324
Date:Jul 24, 2017

Introduction

The structure of NetworkX can be seen by the organization of its source code. The package provides classes for graph objects, generators to create standard graphs, IO routines for reading in existing datasets, algorithms to analyze the resulting networks and some basic drawing tools.

Most of the NetworkX API is provided by functions which take a graph object as an argument. Methods of the graph object are limited to basic manipulation and reporting. This provides modularity of code and documentation. It also makes it easier for newcomers to learn about the package in stages. The source code for each module is meant to be easy to read and reading this Python code is actually a good way to learn more about network algorithms, but we have put a lot of effort into making the documentation sufficient and friendly. If you have suggestions or questions please contact us by joining the NetworkX Google group.

Classes are named using CamelCase (capital letters at the start of each word). functions, methods and variable names are lower_case_underscore (lowercase with an underscore representing a space between words).

NetworkX Basics

After starting Python, import the networkx module with (the recommended way)

>>> import networkx as nx

To save repetition, in the documentation we assume that NetworkX has been imported this way.

If importing networkx fails, it means that Python cannot find the installed module. Check your installation and your PYTHONPATH.

The following basic graph types are provided as Python classes:

Graph
This class implements an undirected graph. It ignores multiple edges between two nodes. It does allow self-loop edges between a node and itself.
DiGraph
Directed graphs, that is, graphs with directed edges. Operations common to directed graphs, (a subclass of Graph).
MultiGraph
A flexible graph class that allows multiple undirected edges between pairs of nodes. The additional flexibility leads to some degradation in performance, though usually not significant.
MultiDiGraph
A directed version of a MultiGraph.

Empty graph-like objects are created with

>>> G = nx.Graph()
>>> G = nx.DiGraph()
>>> G = nx.MultiGraph()
>>> G = nx.MultiDiGraph()

All graph classes allow any hashable object as a node. Hashable objects include strings, tuples, integers, and more. Arbitrary edge attributes such as weights and labels can be associated with an edge.

The graph internal data structures are based on an adjacency list representation and implemented using Python dictionary datastructures. The graph adjacency structure is implemented as a Python dictionary of dictionaries; the outer dictionary is keyed by nodes to values that are themselves dictionaries keyed by neighboring node to the edge attributes associated with that edge. This “dict-of-dicts” structure allows fast addition, deletion, and lookup of nodes and neighbors in large graphs. The underlying datastructure is accessed directly by methods (the programming interface “API”) in the class definitions. All functions, on the other hand, manipulate graph-like objects solely via those API methods and not by acting directly on the datastructure. This design allows for possible replacement of the ‘dicts-of-dicts’-based datastructure with an alternative datastructure that implements the same methods.

Graphs

The first choice to be made when using NetworkX is what type of graph object to use. A graph (network) is a collection of nodes together with a collection of edges that are pairs of nodes. Attributes are often associated with nodes and/or edges. NetworkX graph objects come in different flavors depending on two main properties of the network:

  • Directed: Are the edges directed? Does the order of the edge pairs (u, v) matter? A directed graph is specified by the “Di” prefix in the class name, e.g. DiGraph(). We make this distinction because many classical graph properties are defined differently for directed graphs.
  • Multi-edges: Are multiple edges allowed between each pair of nodes? As you might imagine, multiple edges requires a different data structure, though tricky users could design edge data objects to support this functionality. We provide a standard data structure and interface for this type of graph using the prefix “Multi”, e.g., MultiGraph().

The basic graph classes are named: Graph, DiGraph, MultiGraph, and MultiDiGraph

Nodes and Edges

The next choice you have to make when specifying a graph is what kinds of nodes and edges to use.

If the topology of the network is all you care about then using integers or strings as the nodes makes sense and you need not worry about edge data. If you have a data structure already in place to describe nodes you can simply use that structure as your nodes provided it is hashable. If it is not hashable you can use a unique identifier to represent the node and assign the data as a node attribute.

Edges often have data associated with them. Arbitrary data can associated with edges as an edge attribute. If the data is numeric and the intent is to represent a weighted graph then use the ‘weight’ keyword for the attribute. Some of the graph algorithms, such as Dijkstra’s shortest path algorithm, use this attribute name to get the weight for each edge.

Other attributes can be assigned to an edge by using keyword/value pairs when adding edges. You can use any keyword except ‘weight’ to name your attribute and can then easily query the edge data by that attribute keyword.

Once you’ve decided how to encode the nodes and edges, and whether you have an undirected/directed graph with or without multiedges you are ready to build your network.

Graph Creation

NetworkX graph objects can be created in one of three ways:

  • Graph generators—standard algorithms to create network topologies.
  • Importing data from pre-existing (usually file) sources.
  • Adding edges and nodes explicitly.

Explicit addition and removal of nodes/edges is the easiest to describe. Each graph object supplies methods to manipulate the graph. For example,

>>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_edge(1, 2)  # default edge data=1
>>> G.add_edge(2, 3, weight=0.9)  # specify edge data

Edge attributes can be anything:

>>> import math
>>> G.add_edge('y', 'x', function=math.cos)
>>> G.add_node(math.cos)  # any hashable can be a node

You can add many edges at one time:

>>> elist = [('a', 'b', 5.0), ('b', 'c', 3.0), ('a', 'c', 1.0), ('c', 'd', 7.3)]
>>> G.add_weighted_edges_from(elist)

See the Tutorial for more examples.

Some basic graph operations such as union and intersection are described in the Operators module documentation.

Graph generators such as binomial_graph and powerlaw_graph are provided in the Graph generators subpackage.

For importing network data from formats such as GML, GraphML, edge list text files see the Reading and writing graphs subpackage.

Graph Reporting

Class methods are used for the basic reporting functions neighbors, edges and degree. Reporting of lists is often needed only to iterate through that list so we supply iterator versions of many property reporting methods. For example edges() and nodes() have corresponding methods edges_iter() and nodes_iter(). Using these methods when you can will save memory and often time as well.

The basic graph relationship of an edge can be obtained in two basic ways. One can look for neighbors of a node or one can look for edges incident to a node. We jokingly refer to people who focus on nodes/neighbors as node-centric and people who focus on edges as edge-centric. The designers of NetworkX tend to be node-centric and view edges as a relationship between nodes. You can see this by our avoidance of notation like G[u,v] in favor of G[u][v]. Most data structures for sparse graphs are essentially adjacency lists and so fit this perspective. In the end, of course, it doesn’t really matter which way you examine the graph. G.edges() removes duplicate representations of each edge while G.neighbors(n) or G[n] is slightly faster but doesn’t remove duplicates.

Any properties that are more complicated than edges, neighbors and degree are provided by functions. For example nx.triangles(G,n) gives the number of triangles which include node n as a vertex. These functions are grouped in the code and documentation under the term algorithms.

Algorithms

A number of graph algorithms are provided with NetworkX. These include shortest path, and breadth first search (see traversal), clustering and isomorphism algorithms and others. There are many that we have not developed yet too. If you implement a graph algorithm that might be useful for others please let us know through the NetworkX Google group or the Github Developer Zone.

As an example here is code to use Dijkstra’s algorithm to find the shortest weighted path:

>>> G = nx.Graph()
>>> e = [('a', 'b', 0.3), ('b', 'c', 0.9), ('a', 'c', 0.5), ('c', 'd', 1.2)]
>>> G.add_weighted_edges_from(e)
>>> print(nx.dijkstra_path(G, 'a', 'd'))
['a', 'c', 'd']

Drawing

While NetworkX is not designed as a network layout tool, we provide a simple interface to drawing packages and some simple layout algorithms. We interface to the excellent Graphviz layout tools like dot and neato with the (suggested) pygraphviz package or the pydot interface. Drawing can be done using external programs or the Matplotlib Python package. Interactive GUI interfaces are possible though not provided. The drawing tools are provided in the module drawing.

The basic drawing functions essentially place the nodes on a scatterplot using the positions in a dictionary or computed with a layout function. The edges are then lines between those dots.

>>> G = nx.cubical_graph()
>>> nx.draw(G)   # default spring_layout
>>> nx.draw(G, pos=nx.spectral_layout(G), nodecolor='r', edge_color='b')

See the examples for more ideas.

Data Structure

NetworkX uses a “dictionary of dictionaries of dictionaries” as the basic network data structure. This allows fast lookup with reasonable storage for large sparse networks. The keys are nodes so G[u] returns an adjacency dictionary keyed by neighbor to the edge attribute dictionary. The expression G[u][v] returns the edge attribute dictionary itself. A dictionary of lists would have also been possible, but not allowed fast edge detection nor convenient storage of edge data.

Advantages of dict-of-dicts-of-dicts data structure:

  • Find edges and remove edges with two dictionary look-ups.
  • Prefer to “lists” because of fast lookup with sparse storage.
  • Prefer to “sets” since data can be attached to edge.
  • G[u][v] returns the edge attribute dictionary.
  • n in G tests if node n is in graph G.
  • for n in G: iterates through the graph.
  • for nbr in G[n]: iterates through neighbors.

As an example, here is a representation of an undirected graph with the edges (‘A’, ‘B’), (‘B’, ‘C’)

>>> G = nx.Graph()
>>> G.add_edge('A', 'B')
>>> G.add_edge('B', 'C')
>>> print(G.adj)
{'A': {'B': {}}, 'C': {'B': {}}, 'B': {'A': {}, 'C': {}}}

The data structure gets morphed slightly for each base graph class. For DiGraph two dict-of-dicts-of-dicts structures are provided, one for successors and one for predecessors. For MultiGraph/MultiDiGraph we use a dict-of-dicts-of-dicts-of-dicts [1] where the third dictionary is keyed by an edge key identifier to the fourth dictionary which contains the edge attributes for that edge between the two nodes.

Graphs use a dictionary of attributes for each edge. We use a dict-of-dicts-of-dicts data structure with the inner dictionary storing “name-value” relationships for that edge.

>>> G = nx.Graph()
>>> G.add_edge(1, 2, color='red', weight=0.84, size=300)
>>> print(G[1][2]['size'])
300

Footnotes

[1]“It’s dictionaries all the way down.”

Graph types

NetworkX provides data structures and methods for storing graphs.

All NetworkX graph classes allow (hashable) Python objects as nodes and any Python object can be assigned as an edge attribute.

The choice of graph class depends on the structure of the graph you want to represent.

Which graph class should I use?
Graph Type NetworkX Class
Undirected Simple Graph
Directed Simple DiGraph
With Self-loops Graph, DiGraph
With Parallel edges MultiGraph, MultiDiGraph
Basic graph types
Graph—Undirected graphs with self loops
Overview
class Graph(data=None, **attr)[source]

Base class for undirected graphs.

A Graph stores nodes and edges with optional data, or attributes.

Graphs hold undirected edges. Self loops are allowed but multiple (parallel) edges are not.

Nodes can be arbitrary (hashable) Python objects with optional key/value attributes.

Edges are represented as links between nodes with optional key/value attributes.

Parameters:
  • data (input graph) – Data to initialize graph. If data=None (default) an empty graph is created. The data can be any format that is supported by the to_networkx_graph() function, currently including edge list, dict of dicts, dict of lists, NetworkX graph, NumPy matrix or 2d ndarray, SciPy sparse matrix, or PyGraphviz graph.
  • attr (keyword arguments, optional (default= no attributes)) – Attributes to add to graph as key=value pairs.

Examples

Create an empty graph structure (a “null graph”) with no nodes and no edges.

>>> G = nx.Graph()

G can be grown in several ways.

Nodes:

Add one node at a time:

>>> G.add_node(1)

Add the nodes from any container (a list, dict, set or even the lines from a file or the nodes from another graph).

>>> G.add_nodes_from([2, 3])
>>> G.add_nodes_from(range(100, 110))
>>> H = nx.path_graph(10)
>>> G.add_nodes_from(H)

In addition to strings and integers any hashable Python object (except None) can represent a node, e.g. a customized node object, or even another Graph.

>>> G.add_node(H)

Edges:

G can also be grown by adding edges.

Add one edge,

>>> G.add_edge(1, 2)

a list of edges,

>>> G.add_edges_from([(1, 2), (1, 3)])

or a collection of edges,

>>> G.add_edges_from(H.edges())

If some edges connect nodes not yet in the graph, the nodes are added automatically. There are no errors when adding nodes or edges that already exist.

Attributes:

Each graph, node, and edge can hold key/value attribute pairs in an associated attribute dictionary (the keys must be hashable). By default these are empty, but can be added or changed using add_edge, add_node or direct manipulation of the attribute dictionaries named graph, node and edge respectively.

>>> G = nx.Graph(day="Friday")
>>> G.graph
{'day': 'Friday'}

Add node attributes using add_node(), add_nodes_from() or G.node

>>> G.add_node(1, time='5pm')
>>> G.add_nodes_from([3], time='2pm')
>>> G.node[1]
{'time': '5pm'}
>>> G.node[1]['room'] = 714
>>> del G.node[1]['room'] # remove attribute
>>> list(G.nodes(data=True))
[(1, {'time': '5pm'}), (3, {'time': '2pm'})]

Warning: adding a node to G.node does not add it to the graph.

Add edge attributes using add_edge(), add_edges_from(), subscript notation, or G.edge.

>>> G.add_edge(1, 2, weight=4.7 )
>>> G.add_edges_from([(3, 4), (4, 5)], color='red')
>>> G.add_edges_from([(1, 2, {'color': 'blue'}), (2, 3, {'weight': 8})])
>>> G[1][2]['weight'] = 4.7
>>> G.edge[1, 2]['weight'] = 4

Warning: assigning to G.edge[u] or G.edge[u][v] will almost certainly corrupt the graph data structure. Use 3 sets of brackets as shown above. (4 for multigraphs: MG.edge[u][v][key][name] = value)

Shortcuts:

Many common graph features allow python syntax to speed reporting.

>>> 1 in G     # check if node in graph
True
>>> [n for n in G if n < 3]   # iterate through nodes
[1, 2]
>>> len(G)  # number of nodes in graph
5

The fastest way to traverse all edges of a graph is via adjacency():

>>> for n, nbrsdict in G.adjacency():
...     for nbr, eattr in nbrsdict.items():
...        if 'weight' in eattr:
...            # Do something useful with the edges
...            pass

But the edges() method is often more convenient:

>>> for u, v, weight in G.edges(data='weight'):
...     if weight is not None:
...         # Do something useful with the edges
...         pass

Reporting:

Simple graph information is obtained using methods. Reporting methods usually return views instead of containers to reduce memory usage. Methods exist for reporting nodes(), edges(), neighbors() and degree() as well as the number of nodes and edges.

For details on these and other miscellaneous methods, see below.

Subclasses (Advanced):

The Graph class uses a dict-of-dict-of-dict data structure. The outer dict (node_dict) holds adjacency information keyed by node. The next dict (adjlist_dict) represents the adjacency information and holds edge data keyed by neighbor. The inner dict (edge_attr_dict) represents the edge data and holds edge attribute values keyed by attribute names.

Each of these three dicts can be replaced in a subclass by a user defined dict-like object. In general, the dict-like features should be maintained but extra features can be added. To replace one of the dicts create a new graph class by changing the class(!) variable holding the factory for that dict-like structure. The variable names are node_dict_factory, adjlist_inner_dict_factory, adjlist_outer_dict_factory, and edge_attr_dict_factory.

node_dict_factory : function, (default: dict)
Factory function to be used to create the dict containing node attributes, keyed by node id. It should require no arguments and return a dict-like object
adjlist_outer_dict_factory : function, (default: dict)
Factory function to be used to create the outer-most dict in the data structure that holds adjacency info keyed by node. It should require no arguments and return a dict-like object.
adjlist_inner_dict_factory : function, (default: dict)
Factory function to be used to create the adjacency list dict which holds edge data keyed by neighbor. It should require no arguments and return a dict-like object
edge_attr_dict_factory : function, (default: dict)
Factory function to be used to create the edge attribute dict which holds attrbute values keyed by attribute name. It should require no arguments and return a dict-like object.

Examples

Create a low memory graph class that effectively disallows edge attributes by using a single attribute dict for all edges. This reduces the memory used, but you lose edge attributes.

>>> class ThinGraph(nx.Graph):
...     all_edge_dict = {'weight': 1}
...     def single_edge_dict(self):
...         return self.all_edge_dict
...     edge_attr_dict_factory = single_edge_dict
>>> G = ThinGraph()
>>> G.add_edge(2, 1)
>>> G[2][1]
{'weight': 1}
>>> G.add_edge(2, 2)
>>> G[2][1] is G[2][2]
True

Please see ordered for more examples of creating graph subclasses by overwriting the base class dict with a dictionary-like object.

Methods
Adding and removing nodes and edges
Graph.__init__([data]) Initialize a graph with edges, name, graph attributes.
Graph.add_node(n, **attr) Add a single node n and update node attributes.
Graph.add_nodes_from(nodes, **attr) Add multiple nodes.
Graph.remove_node(n) Remove node n.
Graph.remove_nodes_from(nodes) Remove multiple nodes.
Graph.add_edge(u, v, **attr) Add an edge between u and v.
Graph.add_edges_from(ebunch, **attr) Add all the edges in ebunch.
Graph.add_weighted_edges_from(ebunch[, weight]) Add all the edges in ebunch as weighted edges with specified weights.
Graph.remove_edge(u, v) Remove the edge between u and v.
Graph.remove_edges_from(ebunch) Remove all edges specified in ebunch.
Graph.clear() Remove all nodes and edges from the graph.
Iterating over nodes and edges
Graph.nodes A NodeView of the Graph as G.nodes or G.nodes().
Graph.__iter__() Iterate over the nodes.
Graph.edges An EdgeView of the Graph as G.edges or G.edges().
Graph.get_edge_data(u, v[, default]) Return the attribute dictionary associated with edge (u, v).
Graph.neighbors(n) Return an iterator over all neighbors of node n.
Graph.__getitem__(n) Return a dict of neighbors of node n.
Graph.adjacency() Return an iterator over (node, adjacency dict) tuples for all nodes.
Graph.nbunch_iter([nbunch]) Return an iterator over nodes contained in nbunch that are also in the graph.
Information about graph structure
Graph.has_node(n) Return True if the graph contains the node n.
Graph.__contains__(n) Return True if n is a node, False otherwise.
Graph.has_edge(u, v) Return True if the edge (u, v) is in the graph.
Graph.order() Return the number of nodes in the graph.
Graph.number_of_nodes() Return the number of nodes in the graph.
Graph.__len__() Return the number of nodes.
Graph.degree A DegreeView for the Graph as G.degree or G.degree().
Graph.size([weight]) Return the number of edges or total of all edge weights.
Graph.number_of_edges([u, v]) Return the number of edges between two nodes.
Graph.nodes_with_selfloops() Returns an iterator over nodes with self loops.
Graph.selfloop_edges([data, default]) Returns an iterator over selfloop edges.
Graph.number_of_selfloops() Return the number of selfloop edges.
Making copies and subgraphs
Graph.copy([with_data]) Return a copy of the graph.
Graph.to_undirected() Return an undirected copy of the graph.
Graph.to_directed() Return a directed representation of the graph.
Graph.subgraph(nbunch) Return the subgraph induced on nodes in nbunch.
Graph.edge_subgraph(edges) Returns the subgraph induced by the specified edges.
DiGraph—Directed graphs with self loops
Overview
class DiGraph(data=None, **attr)[source]

Base class for directed graphs.

A DiGraph stores nodes and edges with optional data, or attributes.

DiGraphs hold directed edges. Self loops are allowed but multiple (parallel) edges are not.

Nodes can be arbitrary (hashable) Python objects with optional key/value attributes.

Edges are represented as links between nodes with optional key/value attributes.

Parameters:
  • data (input graph) – Data to initialize graph. If data=None (default) an empty graph is created. The data can be any format that is supported by the to_networkx_graph() function, currently including edge list, dict of dicts, dict of lists, NetworkX graph, NumPy matrix or 2d ndarray, SciPy sparse matrix, or PyGraphviz graph.
  • attr (keyword arguments, optional (default= no attributes)) – Attributes to add to graph as key=value pairs.

Examples

Create an empty graph structure (a “null graph”) with no nodes and no edges.

>>> G = nx.DiGraph()

G can be grown in several ways.

Nodes:

Add one node at a time:

>>> G.add_node(1)

Add the nodes from any container (a list, dict, set or even the lines from a file or the nodes from another graph).

>>> G.add_nodes_from([2, 3])
>>> G.add_nodes_from(range(100, 110))
>>> H = nx.path_graph(10)
>>> G.add_nodes_from(H)

In addition to strings and integers any hashable Python object (except None) can represent a node, e.g. a customized node object, or even another Graph.

>>> G.add_node(H)

Edges:

G can also be grown by adding edges.

Add one edge,

>>> G.add_edge(1, 2)

a list of edges,

>>> G.add_edges_from([(1, 2), (1, 3)])

or a collection of edges,

>>> G.add_edges_from(H.edges())

If some edges connect nodes not yet in the graph, the nodes are added automatically. There are no errors when adding nodes or edges that already exist.

Attributes:

Each graph, node, and edge can hold key/value attribute pairs in an associated attribute dictionary (the keys must be hashable). By default these are empty, but can be added or changed using add_edge, add_node or direct manipulation of the attribute dictionaries named graph, node and edge respectively.

>>> G = nx.DiGraph(day="Friday")
>>> G.graph
{'day': 'Friday'}

Add node attributes using add_node(), add_nodes_from() or G.node

>>> G.add_node(1, time='5pm')
>>> G.add_nodes_from([3], time='2pm')
>>> G.node[1]
{'time': '5pm'}
>>> G.node[1]['room'] = 714
>>> del G.node[1]['room'] # remove attribute
>>> list(G.nodes(data=True))
[(1, {'time': '5pm'}), (3, {'time': '2pm'})]

Warning: adding a node to G.node does not add it to the graph.

Add edge attributes using add_edge(), add_edges_from(), subscript notation, or G.edge.

>>> G.add_edge(1, 2, weight=4.7 )
>>> G.add_edges_from([(3, 4), (4, 5)], color='red')
>>> G.add_edges_from([(1, 2, {'color':'blue'}), (2, 3, {'weight':8})])
>>> G[1][2]['weight'] = 4.7
>>> G.edge[1, 2]['weight'] = 4

Shortcuts:

Many common graph features allow python syntax to speed reporting.

>>> 1 in G     # check if node in graph
True
>>> [n for n in G if n<3]   # iterate through nodes
[1, 2]
>>> len(G)  # number of nodes in graph
5

The fastest way to traverse all edges of a graph is via adjacency(), but the edges() method is often more convenient.

>>> for n, nbrsdict in G.adjacency():
...     for nbr, eattr in nbrsdict.items():
...        if 'weight' in eattr:
...            # Do something useful with the edges
...            pass

But the edges() method is often more convenient:

>>> for u, v, weight in G.edges(data='weight'):
...     if weight is not None:
...         # Do something useful with the edges
...         pass

Reporting:

Simple graph information is obtained using methods. Reporting methods usually return iterators instead of containers to reduce memory usage. Methods exist for reporting nodes(), edges(), neighbors() and degree() as well as the number of nodes and edges.

For details on these and other miscellaneous methods, see below.

Subclasses (Advanced):

The Graph class uses a dict-of-dict-of-dict data structure. The outer dict (node_dict) holds adjacency information keyed by node. The next dict (adjlist_dict) represents the adjacency information and holds edge data keyed by neighbor. The inner dict (edge_attr_dict) represents the edge data and holds edge attribute values keyed by attribute names.

Each of these three dicts can be replaced in a subclass by a user defined dict-like object. In general, the dict-like features should be maintained but extra features can be added. To replace one of the dicts create a new graph class by changing the class(!) variable holding the factory for that dict-like structure. The variable names are node_dict_factory, adjlist_inner_dict_factory, adjlist_outer_dict_factory, and edge_attr_dict_factory.

node_dict_factory : function, (default: dict)
Factory function to be used to create the dict containing node attributes, keyed by node id. It should require no arguments and return a dict-like object
adjlist_outer_dict_factory : function, (default: dict)
Factory function to be used to create the outer-most dict in the data structure that holds adjacency info keyed by node. It should require no arguments and return a dict-like object.
adjlist_inner_dict_factory : function, optional (default: dict)
Factory function to be used to create the adjacency list dict which holds edge data keyed by neighbor. It should require no arguments and return a dict-like object
edge_attr_dict_factory : function, optional (default: dict)
Factory function to be used to create the edge attribute dict which holds attrbute values keyed by attribute name. It should require no arguments and return a dict-like object.

Examples

Create a low memory graph class that effectively disallows edge attributes by using a single attribute dict for all edges. This reduces the memory used, but you lose edge attributes.

>>> class ThinGraph(nx.Graph):
...     all_edge_dict = {'weight': 1}
...     def single_edge_dict(self):
...         return self.all_edge_dict
...     edge_attr_dict_factory = single_edge_dict
>>> G = ThinGraph()
>>> G.add_edge(2, 1)
>>> G[2][1]
{'weight': 1}
>>> G.add_edge(2, 2)
>>> G[2][1] is G[2][2]
True

Please see ordered for more examples of creating graph subclasses by overwriting the base class dict with a dictionary-like object.

Methods
Adding and removing nodes and edges
DiGraph.__init__([data]) Initialize a graph with edges, name, graph attributes.
DiGraph.add_node(n, **attr) Add a single node n and update node attributes.
DiGraph.add_nodes_from(nodes, **attr) Add multiple nodes.
DiGraph.remove_node(n) Remove node n.
DiGraph.remove_nodes_from(nbunch) Remove multiple nodes.
DiGraph.add_edge(u, v, **attr) Add an edge between u and v.
DiGraph.add_edges_from(ebunch, **attr) Add all the edges in ebunch.
DiGraph.add_weighted_edges_from(ebunch[, weight]) Add all the edges in ebunch as weighted edges with specified weights.
DiGraph.remove_edge(u, v) Remove the edge between u and v.
DiGraph.remove_edges_from(ebunch) Remove all edges specified in ebunch.
DiGraph.clear() Remove all nodes and edges from the graph.
Iterating over nodes and edges
DiGraph.nodes A NodeView of the Graph as G.nodes or G.nodes().
DiGraph.__iter__() Iterate over the nodes.
DiGraph.edges Return an iterator over the edges.
DiGraph.out_edges Return an iterator over the edges.
DiGraph.in_edges Return an iterator over the incoming edges.
DiGraph.get_edge_data(u, v[, default]) Return the attribute dictionary associated with edge (u, v).
DiGraph.neighbors(n) Return an iterator over successor nodes of n.
DiGraph.__getitem__(n) Return a dict of neighbors of node n.
DiGraph.successors(n) Return an iterator over successor nodes of n.
DiGraph.predecessors(n) Return an iterator over predecessor nodes of n.
DiGraph.adjacency() Return an iterator over (node, adjacency dict) tuples for all nodes.
DiGraph.nbunch_iter([nbunch]) Return an iterator over nodes contained in nbunch that are also in the graph.
Information about graph structure
DiGraph.has_node(n) Return True if the graph contains the node n.
DiGraph.__contains__(n) Return True if n is a node, False otherwise.
DiGraph.has_edge(u, v) Return True if the edge (u, v) is in the graph.
DiGraph.order() Return the number of nodes in the graph.
DiGraph.number_of_nodes() Return the number of nodes in the graph.
DiGraph.__len__() Return the number of nodes.
DiGraph.degree Return an iterator for (node, degree) or degree for single node.
DiGraph.in_degree Return an iterator for (node, in-degree) or in-degree for single node.
DiGraph.out_degree Return an iterator for (node, out-degree) or out-degree for single node.
DiGraph.size([weight]) Return the number of edges or total of all edge weights.
DiGraph.number_of_edges([u, v]) Return the number of edges between two nodes.
DiGraph.nodes_with_selfloops() Returns an iterator over nodes with self loops.
DiGraph.selfloop_edges([data, default]) Returns an iterator over selfloop edges.
DiGraph.number_of_selfloops() Return the number of selfloop edges.
Making copies and subgraphs
DiGraph.copy([with_data]) Return a copy of the graph.
DiGraph.to_undirected([reciprocal]) Return an undirected representation of the digraph.
DiGraph.to_directed() Return a directed copy of the graph.
DiGraph.subgraph(nbunch) Return the subgraph induced on nodes in nbunch.
DiGraph.edge_subgraph(edges) Returns the subgraph induced by the specified edges.
DiGraph.reverse([copy]) Return the reverse of the graph.
MultiGraph—Undirected graphs with self loops and parallel edges
Overview
class MultiGraph(data=None, **attr)[source]

An undirected graph class that can store multiedges.

Multiedges are multiple edges between two nodes. Each edge can hold optional data or attributes.

A MultiGraph holds undirected edges. Self loops are allowed.

Nodes can be arbitrary (hashable) Python objects with optional key/value attributes.

Edges are represented as links between nodes with optional key/value attributes.

Parameters:
  • data (input graph) – Data to initialize graph. If data=None (default) an empty graph is created. The data can be any format that is supported by the to_networkx_graph() function, currently including edge list, dict of dicts, dict of lists, NetworkX graph, NumPy matrix or 2d ndarray, SciPy sparse matrix, or PyGraphviz graph.
  • attr (keyword arguments, optional (default= no attributes)) – Attributes to add to graph as key=value pairs.

Examples

Create an empty graph structure (a “null graph”) with no nodes and no edges.

>>> G = nx.MultiGraph()

G can be grown in several ways.

Nodes:

Add one node at a time:

>>> G.add_node(1)

Add the nodes from any container (a list, dict, set or even the lines from a file or the nodes from another graph).

>>> G.add_nodes_from([2, 3])
>>> G.add_nodes_from(range(100, 110))
>>> H = nx.path_graph(10)
>>> G.add_nodes_from(H)

In addition to strings and integers any hashable Python object (except None) can represent a node, e.g. a customized node object, or even another Graph.

>>> G.add_node(H)

Edges:

G can also be grown by adding edges.

Add one edge,

>>> key = G.add_edge(1, 2)

a list of edges,

>>> keys = G.add_edges_from([(1, 2), (1, 3)])

or a collection of edges,

>>> keys = G.add_edges_from(list(H.edges()))

If some edges connect nodes not yet in the graph, the nodes are added automatically. If an edge already exists, an additional edge is created and stored using a key to identify the edge. By default the key is the lowest unused integer.

>>> keys = G.add_edges_from([(4,5,{'route':282}), (4,5,{'route':37})])
>>> G[4]
AtlasView2({3: {0: {}}, 5: {0: {}, 1: {'route': 282}, 2: {'route': 37}}})

Attributes:

Each graph, node, and edge can hold key/value attribute pairs in an associated attribute dictionary (the keys must be hashable). By default these are empty, but can be added or changed using add_edge, add_node or direct manipulation of the attribute dictionaries named graph, node and edge respectively.

>>> G = nx.MultiGraph(day="Friday")
>>> G.graph
{'day': 'Friday'}

Add node attributes using add_node(), add_nodes_from() or G.node

>>> G.add_node(1, time='5pm')
>>> G.add_nodes_from([3], time='2pm')
>>> G.node[1]
{'time': '5pm'}
>>> G.node[1]['room'] = 714
>>> del G.node[1]['room'] # remove attribute
>>> list(G.nodes(data=True))
[(1, {'time': '5pm'}), (3, {'time': '2pm'})]

Warning: adding a node to G.node does not add it to the graph.

Add edge attributes using add_edge(), add_edges_from(), subscript notation, or G.edge.

>>> key = G.add_edge(1, 2, weight=4.7 )
>>> keys = G.add_edges_from([(3, 4), (4, 5)], color='red')
>>> keys = G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])
>>> G[1][2][0]['weight'] = 4.7
>>> G.edge[1, 2, 0]['weight'] = 4

Shortcuts:

Many common graph features allow python syntax to speed reporting.

>>> 1 in G     # check if node in graph
True
>>> [n for n in G if n<3]   # iterate through nodes
[1, 2]
>>> len(G)  # number of nodes in graph
5
>>> G[1] # adjacency dict-like view keyed by neighbor to edge attributes
AtlasView2({2: {0: {'weight': 4}, 1: {'color': 'blue'}}})

The fastest way to traverse all edges of a graph is via adjacency():

>>> for n, nbrsdict in G.adjacency():
...     for nbr, keydict in nbrsdict.items():
...        for key, eattr in keydict.items():
...            if 'weight' in eattr:
...                # Do something useful with the edges
...                pass

But the edges() method is often more convenient:

>>> for u, v, keys, weight in G.edges(data='weight', keys=True):
...     if weight is not None:
...         # Do something useful with the edges
...         pass

Reporting:

Simple graph information is obtained using methods. Reporting methods usually return iterators instead of containers to reduce memory usage. Methods exist for reporting nodes(), edges(), neighbors() and degree() as well as the number of nodes and edges.

For details on these and other miscellaneous methods, see below.

Subclasses (Advanced):

The MultiGraph class uses a dict-of-dict-of-dict-of-dict data structure. The outer dict (node_dict) holds adjacency information keyed by node. The next dict (adjlist_dict) represents the adjacency information and holds edge_key dicts keyed by neighbor. The edge_key dict holds each edge_attr dict keyed by edge key. The inner dict (edge_attr_dict) represents the edge data and holds edge attribute values keyed by attribute names.

Each of these four dicts in the dict-of-dict-of-dict-of-dict structure can be replaced by a user defined dict-like object. In general, the dict-like features should be maintained but extra features can be added. To replace one of the dicts create a new graph class by changing the class(!) variable holding the factory for that dict-like structure. The variable names are node_dict_factory, adjlist_inner_dict_factory, adjlist_outer_dict_factory, and edge_attr_dict_factory.

node_dict_factory : function, (default: dict)
Factory function to be used to create the dict containing node attributes, keyed by node id. It should require no arguments and return a dict-like object
adjlist_outer_dict_factory : function, (default: dict)
Factory function to be used to create the outer-most dict in the data structure that holds adjacency info keyed by node. It should require no arguments and return a dict-like object.
adjlist_inner_dict_factory : function, (default: dict)
Factory function to be used to create the adjacency list dict which holds multiedge key dicts keyed by neighbor. It should require no arguments and return a dict-like object.
edge_key_dict_factory : function, (default: dict)
Factory function to be used to create the edge key dict which holds edge data keyed by edge key. It should require no arguments and return a dict-like object.
edge_attr_dict_factory : function, (default: dict)
Factory function to be used to create the edge attribute dict which holds attrbute values keyed by attribute name. It should require no arguments and return a dict-like object.

Examples

Please see ordered for examples of creating graph subclasses by overwriting the base class dict with a dictionary-like object.

Methods
Adding and removing nodes and edges
MultiGraph.__init__([data])
MultiGraph.add_node(n, **attr) Add a single node n and update node attributes.
MultiGraph.add_nodes_from(nodes, **attr) Add multiple nodes.
MultiGraph.remove_node(n) Remove node n.
MultiGraph.remove_nodes_from(nodes) Remove multiple nodes.
MultiGraph.add_edge(u, v[, key]) Add an edge between u and v.
MultiGraph.add_edges_from(ebunch, **attr) Add all the edges in ebunch.
MultiGraph.add_weighted_edges_from(ebunch[, …]) Add all the edges in ebunch as weighted edges with specified weights.
MultiGraph.new_edge_key(u, v) Return an unused key for edges between nodes u and v.
MultiGraph.remove_edge(u, v[, key]) Remove an edge between u and v.
MultiGraph.remove_edges_from(ebunch) Remove all edges specified in ebunch.
MultiGraph.clear() Remove all nodes and edges from the graph.
Iterating over nodes and edges
MultiGraph.nodes A NodeView of the Graph as G.nodes or G.nodes().
MultiGraph.__iter__() Iterate over the nodes.
MultiGraph.edges Return an iterator over the edges.
MultiGraph.get_edge_data(u, v[, key, default]) Return the attribute dictionary associated with edge (u, v).
MultiGraph.neighbors(n) Return an iterator over all neighbors of node n.
MultiGraph.__getitem__(n) Return a dict of neighbors of node n.
MultiGraph.adjacency() Return an iterator over (node, adjacency dict) tuples for all nodes.
MultiGraph.nbunch_iter([nbunch]) Return an iterator over nodes contained in nbunch that are also in the graph.
Information about graph structure
MultiGraph.has_node(n) Return True if the graph contains the node n.
MultiGraph.__contains__(n) Return True if n is a node, False otherwise.
MultiGraph.has_edge(u, v[, key]) Return True if the graph has an edge between nodes u and v.
MultiGraph.order() Return the number of nodes in the graph.
MultiGraph.number_of_nodes() Return the number of nodes in the graph.
MultiGraph.__len__() Return the number of nodes.
MultiGraph.degree Return an iterator for (node, degree) or degree for single node.
MultiGraph.size([weight]) Return the number of edges or total of all edge weights.
MultiGraph.number_of_edges([u, v]) Return the number of edges between two nodes.
MultiGraph.nodes_with_selfloops() Returns an iterator over nodes with self loops.
MultiGraph.selfloop_edges([data, keys, default]) Return a list of selfloop edges.
MultiGraph.number_of_selfloops() Return the number of selfloop edges.
Making copies and subgraphs
MultiGraph.copy([with_data]) Return a copy of the graph.
MultiGraph.to_undirected() Return an undirected copy of the graph.
MultiGraph.to_directed() Return a directed representation of the graph.
MultiGraph.subgraph(nbunch) Return the subgraph induced on nodes in nbunch.
MultiGraph.edge_subgraph(edges) Returns the subgraph induced by the specified edges.
MultiDiGraph—Directed graphs with self loops and parallel edges
Overview
class MultiDiGraph(data=None, **attr)[source]

A directed graph class that can store multiedges.

Multiedges are multiple edges between two nodes. Each edge can hold optional data or attributes.

A MultiDiGraph holds directed edges. Self loops are allowed.

Nodes can be arbitrary (hashable) Python objects with optional key/value attributes.

Edges are represented as links between nodes with optional key/value attributes.

Parameters:
  • data (input graph) – Data to initialize graph. If data=None (default) an empty graph is created. The data can be any format that is supported by the to_networkx_graph() function, currently including edge list, dict of dicts, dict of lists, NetworkX graph, NumPy matrix or 2d ndarray, SciPy sparse matrix, or PyGraphviz graph.
  • attr (keyword arguments, optional (default= no attributes)) – Attributes to add to graph as key=value pairs.

Examples

Create an empty graph structure (a “null graph”) with no nodes and no edges.

>>> G = nx.MultiDiGraph()

G can be grown in several ways.

Nodes:

Add one node at a time:

>>> G.add_node(1)

Add the nodes from any container (a list, dict, set or even the lines from a file or the nodes from another graph).

>>> G.add_nodes_from([2, 3])
>>> G.add_nodes_from(range(100, 110))
>>> H = nx.path_graph(10)
>>> G.add_nodes_from(H)

In addition to strings and integers any hashable Python object (except None) can represent a node, e.g. a customized node object, or even another Graph.

>>> G.add_node(H)

Edges:

G can also be grown by adding edges.

Add one edge,

>>> key = G.add_edge(1, 2)

a list of edges,

>>> keys = G.add_edges_from([(1, 2), (1, 3)])

or a collection of edges,

>>> keys = G.add_edges_from(H.edges())

If some edges connect nodes not yet in the graph, the nodes are added automatically. If an edge already exists, an additional edge is created and stored using a key to identify the edge. By default the key is the lowest unused integer.

>>> keys = G.add_edges_from([(4,5,dict(route=282)), (4,5,dict(route=37))])
>>> G[4]
AtlasView2({5: {0: {}, 1: {'route': 282}, 2: {'route': 37}}})

Attributes:

Each graph, node, and edge can hold key/value attribute pairs in an associated attribute dictionary (the keys must be hashable). By default these are empty, but can be added or changed using add_edge, add_node or direct manipulation of the attribute dictionaries named graph, node and edge respectively.

>>> G = nx.MultiDiGraph(day="Friday")
>>> G.graph
{'day': 'Friday'}

Add node attributes using add_node(), add_nodes_from() or G.node

>>> G.add_node(1, time='5pm')
>>> G.add_nodes_from([3], time='2pm')
>>> G.node[1]
{'time': '5pm'}
>>> G.node[1]['room'] = 714
>>> del G.node[1]['room'] # remove attribute
>>> list(G.nodes(data=True))
[(1, {'time': '5pm'}), (3, {'time': '2pm'})]

Warning: adding a node to G.node does not add it to the graph.

Add edge attributes using add_edge(), add_edges_from(), subscript notation, or G.edge.

>>> key = G.add_edge(1, 2, weight=4.7 )
>>> keys = G.add_edges_from([(3, 4), (4, 5)], color='red')
>>> keys = G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])
>>> G[1][2][0]['weight'] = 4.7
>>> G.edge[1, 2, 0]['weight'] = 4

Shortcuts:

Many common graph features allow python syntax to speed reporting.

>>> 1 in G     # check if node in graph
True
>>> [n for n in G if n<3]   # iterate through nodes
[1, 2]
>>> len(G)  # number of nodes in graph
5
>>> G[1] # adjacency dict-like view keyed by neighbor to edge attributes
AtlasView2({2: {0: {'weight': 4}, 1: {'color': 'blue'}}})

The fastest way to traverse all edges of a graph is via adjacency():

>>> for n, nbrsdict in G.adjacency():
...     for nbr, keydict in nbrsdict.items():
...        for key, eattr in keydict.items():
...            if 'weight' in eattr:
...                # Do something useful with the edges
...                pass

But the edges() method is often more convenient:

>>> for u, v, keys, weight in G.edges(data='weight', keys=True):
...     if weight is not None:
...         # Do something useful with the edges
...         pass

Reporting:

Simple graph information is obtained using methods. Reporting methods usually return iterators instead of containers to reduce memory usage. Methods exist for reporting nodes(), edges(), neighbors() and degree() as well as the number of nodes and edges.

For details on these and other miscellaneous methods, see below.

Subclasses (Advanced):

The MultiDiGraph class uses a dict-of-dict-of-dict-of-dict structure. The outer dict (node_dict) holds adjacency information keyed by node. The next dict (adjlist_dict) represents the adjacency information and holds edge_key dicts keyed by neighbor. The edge_key dict holds each edge_attr dict keyed by edge key. The inner dict (edge_attr_dict) represents the edge data and holds edge attribute values keyed by attribute names.

Each of these four dicts in the dict-of-dict-of-dict-of-dict structure can be replaced by a user defined dict-like object. In general, the dict-like features should be maintained but extra features can be added. To replace one of the dicts create a new graph class by changing the class(!) variable holding the factory for that dict-like structure. The variable names are node_dict_factory, adjlist_inner_dict_factory, adjlist_outer_dict_factory, and edge_attr_dict_factory.

node_dict_factory : function, (default: dict)
Factory function to be used to create the dict containing node attributes, keyed by node id. It should require no arguments and return a dict-like object
adjlist_outer_dict_factory : function, (default: dict)
Factory function to be used to create the outer-most dict in the data structure that holds adjacency info keyed by node. It should require no arguments and return a dict-like object.
adjlist_inner_dict_factory : function, (default: dict)
Factory function to be used to create the adjacency list dict which holds multiedge key dicts keyed by neighbor. It should require no arguments and return a dict-like object.
edge_key_dict_factory : function, (default: dict)
Factory function to be used to create the edge key dict which holds edge data keyed by edge key. It should require no arguments and return a dict-like object.
edge_attr_dict_factory : function, (default: dict)
Factory function to be used to create the edge attribute dict which holds attrbute values keyed by attribute name. It should require no arguments and return a dict-like object.

Examples

Please see ordered for examples of creating graph subclasses by overwriting the base class dict with a dictionary-like object.

Methods
Adding and Removing Nodes and Edges
MultiDiGraph.__init__([data])
MultiDiGraph.add_node(n, **attr) Add a single node n and update node attributes.
MultiDiGraph.add_nodes_from(nodes, **attr) Add multiple nodes.
MultiDiGraph.remove_node(n) Remove node n.
MultiDiGraph.remove_nodes_from(nbunch) Remove multiple nodes.
MultiDiGraph.add_edge(u, v[, key]) Add an edge between u and v.
MultiDiGraph.add_edges_from(ebunch, **attr) Add all the edges in ebunch.
MultiDiGraph.add_weighted_edges_from(ebunch) Add all the edges in ebunch as weighted edges with specified weights.
MultiDiGraph.new_edge_key(u, v) Return an unused key for edges between nodes u and v.
MultiDiGraph.remove_edge(u, v[, key]) Remove an edge between u and v.
MultiDiGraph.remove_edges_from(ebunch) Remove all edges specified in ebunch.
MultiDiGraph.clear() Remove all nodes and edges from the graph.
Iterating over nodes and edges
MultiDiGraph.nodes A NodeView of the Graph as G.nodes or G.nodes().
MultiDiGraph.__iter__() Iterate over the nodes.
MultiDiGraph.edges Return an iterator over the edges.
MultiDiGraph.out_edges Return an iterator over the edges.
MultiDiGraph.in_edges Return an iterator over the incoming edges.
MultiDiGraph.get_edge_data(u, v[, key, default]) Return the attribute dictionary associated with edge (u, v).
MultiDiGraph.neighbors(n) Return an iterator over successor nodes of n.
MultiDiGraph.__getitem__(n) Return a dict of neighbors of node n.
MultiDiGraph.successors(n) Return an iterator over successor nodes of n.
MultiDiGraph.predecessors(n) Return an iterator over predecessor nodes of n.
MultiDiGraph.adjacency() Return an iterator over (node, adjacency dict) tuples for all nodes.
MultiDiGraph.nbunch_iter([nbunch]) Return an iterator over nodes contained in nbunch that are also in the graph.
Information about graph structure
MultiDiGraph.has_node(n) Return True if the graph contains the node n.
MultiDiGraph.__contains__(n) Return True if n is a node, False otherwise.
MultiDiGraph.has_edge(u, v[, key]) Return True if the graph has an edge between nodes u and v.
MultiDiGraph.order() Return the number of nodes in the graph.
MultiDiGraph.number_of_nodes() Return the number of nodes in the graph.
MultiDiGraph.__len__() Return the number of nodes.
MultiDiGraph.degree Return an iterator for (node, degree) or degree for single node.
MultiDiGraph.in_degree Return an iterator for (node, in-degree) or in-degree for single node.
MultiDiGraph.out_degree Return an iterator for (node, out-degree) or out-degree for single node.
MultiDiGraph.size([weight]) Return the number of edges or total of all edge weights.
MultiDiGraph.number_of_edges([u, v]) Return the number of edges between two nodes.
MultiDiGraph.nodes_with_selfloops() Returns an iterator over nodes with self loops.
MultiDiGraph.selfloop_edges([data, keys, …]) Return a list of selfloop edges.
MultiDiGraph.number_of_selfloops() Return the number of selfloop edges.
Making copies and subgraphs
MultiDiGraph.copy([with_data]) Return a copy of the graph.
MultiDiGraph.to_undirected([reciprocal]) Return an undirected representation of the digraph.
MultiDiGraph.to_directed() Return a directed copy of the graph.
MultiDiGraph.edge_subgraph(edges) Returns the subgraph induced by the specified edges.
MultiDiGraph.subgraph(nbunch) Return the subgraph induced on nodes in nbunch.
MultiDiGraph.reverse([copy]) Return the reverse of the graph.
Ordered Graphs—Consistently ordered graphs

Consistently ordered variants of the default base classes.

The Ordered (Di/Multi/MultiDi) Graphs give a consistent order for reporting of nodes and edges. The order of node reporting agrees with node adding, but for edges, the order is not necessarily the order that the edges were added.

In general, you should use the default (i.e., unordered) graph classes. However, there are times (e.g., when testing) when you may need the order preserved.

class OrderedGraph(data=None, **attr)[source]

Consistently ordered variant of Graph.

class OrderedDiGraph(data=None, **attr)[source]

Consistently ordered variant of DiGraph.

class OrderedMultiGraph(data=None, **attr)[source]

Consistently ordered variant of MultiGraph.

class OrderedMultiDiGraph(data=None, **attr)[source]

Consistently ordered variant of MultiDiGraph.

Note

NetworkX uses dicts to store the nodes and neighbors in a graph. So the reporting of nodes and edges for the base graph classes will not necessarily be consistent across versions and platforms. If you need the order of nodes and edges to be consistent (e.g., when writing automated tests), please see OrderedGraph, OrderedDiGraph, OrderedMultiGraph, or OrderedMultiDiGraph, which behave like the base graph classes but give a consistent order for reporting of nodes and edges.

Algorithms

Approximation

Warning

The approximation submodule is not imported automatically with networkx.

Approximate algorithms can be imported with from networkx.algorithms import approximation.

Connectivity

Fast approximation for node connectivity

all_pairs_node_connectivity(G[, nbunch, cutoff]) Compute node connectivity between all pairs of nodes.
local_node_connectivity(G, source, target[, …]) Compute node connectivity between source and target.
node_connectivity(G[, s, t]) Returns an approximation for node connectivity for a graph or digraph G.
K-components

Fast approximation for k-component structure

k_components(G[, min_density]) Returns the approximate k-component structure of a graph G.
Clique

Cliques.

max_clique(G) Find the Maximum Clique
clique_removal(G) Repeatedly remove cliques from the graph.
Clustering
average_clustering(G[, trials]) Estimates the average clustering coefficient of G.
Dominating Set

Functions for finding node and edge dominating sets.

A dominating set for an undirected graph G with vertex set V and edge set E is a subset D of V such that every vertex not in D is adjacent to at least one member of D. An edge dominating set is a subset F of E such that every edge not in F is incident to an endpoint of at least one edge in F.

min_weighted_dominating_set(G[, weight]) Returns a dominating set that approximates the minimum weight node dominating set.
min_edge_dominating_set(G) Return minimum cardinality edge dominating set.
Independent Set

Independent Set

Independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I. The size of an independent set is the number of vertices it contains.

A maximum independent set is a largest independent set for a given graph G and its size is denoted α(G). The problem of finding such a set is called the maximum independent set problem and is an NP-hard optimization problem. As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph.

Wikipedia: Independent set

Independent set algorithm is based on the following paper:

O(|V|/(log|V|)^2) apx of maximum clique/independent set.

Boppana, R., & Halldórsson, M. M. (1992). Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2), 180–196. Springer. doi:10.1007/BF01994876

maximum_independent_set(G) Return an approximate maximum independent set.
Matching
Graph Matching

Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.

Wikipedia: Matching

min_maximal_matching(G) Returns the minimum maximal matching of G.
Ramsey

Ramsey numbers.

ramsey_R2(G) Approximately computes the Ramsey number R(2;s,t) for graph.
Vertex Cover

Functions for computing an approximate minimum weight vertex cover.

A vertex cover is a subset of nodes such that each edge in the graph is incident to at least one node in the subset.

min_weighted_vertex_cover(G[, weight]) Returns an approximate minimum weighted vertex cover.
Assortativity
Assortativity
degree_assortativity_coefficient(G[, x, y, …]) Compute degree assortativity of graph.
attribute_assortativity_coefficient(G, attribute) Compute assortativity for node attributes.
numeric_assortativity_coefficient(G, attribute) Compute assortativity for numerical node attributes.
degree_pearson_correlation_coefficient(G[, …]) Compute degree assortativity of graph.
Average neighbor degree
average_neighbor_degree(G[, source, target, …]) Returns the average degree of the neighborhood of each node.
Average degree connectivity
average_degree_connectivity(G[, source, …]) Compute the average degree connectivity of graph.
k_nearest_neighbors(G[, source, target, …]) Compute the average degree connectivity of graph.
Mixing
attribute_mixing_matrix(G, attribute[, …]) Return mixing matrix for attribute.
degree_mixing_matrix(G[, x, y, weight, …]) Return mixing matrix for attribute.
degree_mixing_dict(G[, x, y, weight, nodes, …]) Return dictionary representation of mixing matrix for degree.
attribute_mixing_dict(G, attribute[, nodes, …]) Return dictionary representation of mixing matrix for attribute.
Bipartite

This module provides functions and operations for bipartite graphs. Bipartite graphs B = (U, V, E) have two node sets U,V and edges in E that only connect nodes from opposite sets. It is common in the literature to use an spatial analogy referring to the two node sets as top and bottom nodes.

The bipartite algorithms are not imported into the networkx namespace at the top level so the easiest way to use them is with:

>>> import networkx as nx
>>> from networkx.algorithms import bipartite

NetworkX does not have a custom bipartite graph class but the Graph() or DiGraph() classes can be used to represent bipartite graphs. However, you have to keep track of which set each node belongs to, and make sure that there is no edge between nodes of the same set. The convention used in NetworkX is to use a node attribute named bipartite with values 0 or 1 to identify the sets each node belongs to. This convention is not enforced in the source code of bipartite functions, it’s only a recommendation.

For example:

>>> B = nx.Graph()
>>> # Add nodes with the node attribute "bipartite"
>>> B.add_nodes_from([1, 2, 3, 4], bipartite=0)
>>> B.add_nodes_from(['a', 'b', 'c'], bipartite=1)
>>> # Add edges only between nodes of opposite node sets
>>> B.add_edges_from([(1, 'a'), (1, 'b'), (2, 'b'), (2, 'c'), (3, 'c'), (4, 'a')])

Many algorithms of the bipartite module of NetworkX require, as an argument, a container with all the nodes that belong to one set, in addition to the bipartite graph B. The functions in the bipartite package do not check that the node set is actually correct nor that the input graph is actually bipartite. If B is connected, you can find the two node sets using a two-coloring algorithm:

>>> nx.is_connected(B)
True
>>> bottom_nodes, top_nodes = bipartite.sets(B)

However, if the input graph is not connected, there are more than one possible colorations. This is the reason why we require the user to pass a container with all nodes of one bipartite node set as an argument to most bipartite functions. In the face of ambiguity, we refuse the temptation to guess and raise an AmbiguousSolution Exception if the input graph for bipartite.sets is disconnected.

Using the bipartite node attribute, you can easily get the two node sets:

>>> top_nodes = {n for n, d in B.nodes(data=True) if d['bipartite']==0}
>>> bottom_nodes = set(B) - top_nodes

So you can easily use the bipartite algorithms that require, as an argument, a container with all nodes that belong to one node set:

>>> print(round(bipartite.density(B, bottom_nodes), 2))
0.5
>>> G = bipartite.projected_graph(B, top_nodes)

All bipartite graph generators in NetworkX build bipartite graphs with the bipartite node attribute. Thus, you can use the same approach:

>>> RB = bipartite.random_graph(5, 7, 0.2)
>>> RB_top = {n for n, d in RB.nodes(data=True) if d['bipartite']==0}
>>> RB_bottom = set(RB) - RB_top
>>> list(RB_top)
[0, 1, 2, 3, 4]
>>> list(RB_bottom)
[5, 6, 7, 8, 9, 10, 11]

For other bipartite graph generators see Generators.

Basic functions
Bipartite Graph Algorithms
is_bipartite(G) Returns True if graph G is bipartite, False if not.
is_bipartite_node_set(G, nodes) Returns True if nodes and G/nodes are a bipartition of G.
sets(G[, top_nodes]) Returns bipartite node sets of graph G.
color(G) Returns a two-coloring of the graph.
density(B, nodes) Return density of bipartite graph B.
degrees(B, nodes[, weight]) Return the degrees of the two node sets in the bipartite graph B.
Matching

Provides functions for computing a maximum cardinality matching in a bipartite graph.

If you don’t care about the particular implementation of the maximum matching algorithm, simply use the maximum_matching(). If you do care, you can import one of the named maximum matching algorithms directly.

For example, to find a maximum matching in the complete bipartite graph with two vertices on the left and three vertices on the right:

>>> import networkx as nx
>>> G = nx.complete_bipartite_graph(2, 3)
>>> left, right = nx.bipartite.sets(G)
>>> list(left)
[0, 1]
>>> list(right)
[2, 3, 4]
>>> nx.bipartite.maximum_matching(G)
{0: 2, 1: 3, 2: 0, 3: 1}

The dictionary returned by maximum_matching() includes a mapping for vertices in both the left and right vertex sets.

eppstein_matching(G[, top_nodes]) Returns the maximum cardinality matching of the bipartite graph G.
hopcroft_karp_matching(G[, top_nodes]) Returns the maximum cardinality matching of the bipartite graph G.
to_vertex_cover(G, matching[, top_nodes]) Returns the minimum vertex cover corresponding to the given maximum matching of the bipartite graph G.
Matrix
Biadjacency matrices
biadjacency_matrix(G, row_order[, …]) Return the biadjacency matrix of the bipartite graph G.
from_biadjacency_matrix(A[, create_using, …]) Creates a new bipartite graph from a biadjacency matrix given as a SciPy sparse matrix.
Projections

One-mode (unipartite) projections of bipartite graphs.

projected_graph(B, nodes[, multigraph]) Returns the projection of B onto one of its node sets.
weighted_projected_graph(B, nodes[, ratio]) Returns a weighted projection of B onto one of its node sets.
collaboration_weighted_projected_graph(B, nodes) Newman’s weighted projection of B onto one of its node sets.
overlap_weighted_projected_graph(B, nodes[, …]) Overlap weighted projection of B onto one of its node sets.
generic_weighted_projected_graph(B, nodes[, …]) Weighted projection of B with a user-specified weight function.
Spectral

Spectral bipartivity measure.

spectral_bipartivity(G[, nodes, weight]) Returns the spectral bipartivity.
Clustering
clustering(G[, nodes, mode]) Compute a bipartite clustering coefficient for nodes.
average_clustering(G[, nodes, mode]) Compute the average bipartite clustering coefficient.
latapy_clustering(G[, nodes, mode]) Compute a bipartite clustering coefficient for nodes.
robins_alexander_clustering(G) Compute the bipartite clustering of G.
Redundancy

Node redundancy for bipartite graphs.

node_redundancy(G[, nodes]) Computes the node redundancy coefficients for the nodes in the bipartite graph G.
Centrality
closeness_centrality(G, nodes[, normalized]) Compute the closeness centrality for nodes in a bipartite network.
degree_centrality(G, nodes) Compute the degree centrality for nodes in a bipartite network.
betweenness_centrality(G, nodes) Compute betweenness centrality for nodes in a bipartite network.
Generators

Generators and functions for bipartite graphs.

complete_bipartite_graph(n1, n2[, create_using]) Return the complete bipartite graph K_{n_1,n_2}.
configuration_model(aseq, bseq[, …]) Return a random bipartite graph from two given degree sequences.
havel_hakimi_graph(aseq, bseq[, create_using]) Return a bipartite graph from two given degree sequences using a Havel-Hakimi style construction.
reverse_havel_hakimi_graph(aseq, bseq[, …]) Return a bipartite graph from two given degree sequences using a Havel-Hakimi style construction.
alternating_havel_hakimi_graph(aseq, bseq[, …]) Return a bipartite graph from two given degree sequences using an alternating Havel-Hakimi style construction.
preferential_attachment_graph(aseq, p[, …]) Create a bipartite graph with a preferential attachment model from a given single degree sequence.
random_graph(n, m, p[, seed, directed]) Return a bipartite random graph.
gnmk_random_graph(n, m, k[, seed, directed]) Return a random bipartite graph G_{n,m,k}.
Covering

Functions related to graph covers.

min_edge_cover(G[, matching_algorithm]) Returns a set of edges which constitutes the minimum edge cover of the graph.
Boundary

Routines to find the boundary of a set of nodes.

An edge boundary is a set of edges, each of which has exactly one endpoint in a given set of nodes (or, in the case of directed graphs, the set of edges whose source node is in the set).

A node boundary of a set S of nodes is the set of (out-)neighbors of nodes in S that are outside S.

edge_boundary(G, nbunch1[, nbunch2, data, …]) Returns the edge boundary of nbunch1.
node_boundary(G, nbunch1[, nbunch2]) Returns the node boundary of nbunch1.
Bridges

Bridge-finding algorithms.

bridges(G[, root]) Generate all bridges in a graph.
has_bridges(G[, root]) Decide whether a graph has any bridges.
Centrality
Degree
degree_centrality(G) Compute the degree centrality for nodes.
in_degree_centrality(G) Compute the in-degree centrality for nodes.
out_degree_centrality(G) Compute the out-degree centrality for nodes.
Eigenvector
eigenvector_centrality(G[, max_iter, tol, …]) Compute the eigenvector centrality for the graph G.
eigenvector_centrality_numpy(G[, weight, …]) Compute the eigenvector centrality for the graph G.
katz_centrality(G[, alpha, beta, max_iter, …]) Compute the Katz centrality for the nodes of the graph G.
katz_centrality_numpy(G[, alpha, beta, …]) Compute the Katz centrality for the graph G.
Closeness
closeness_centrality(G[, u, distance, …]) Compute closeness centrality for nodes.
Current Flow Closeness
current_flow_closeness_centrality(G[, …]) Compute current-flow closeness centrality for nodes.
(Shortest Path) Betweenness
betweenness_centrality(G[, k, normalized, …]) Compute the shortest-path betweenness centrality for nodes.
edge_betweenness_centrality(G[, k, …]) Compute betweenness centrality for edges.
betweenness_centrality_subset(G, sources, …) Compute betweenness centrality for a subset of nodes.
edge_betweenness_centrality_subset(G, …[, …]) Compute betweenness centrality for edges for a subset of nodes.
Current Flow Betweenness
current_flow_betweenness_centrality(G[, …]) Compute current-flow betweenness centrality for nodes.
edge_current_flow_betweenness_centrality(G) Compute current-flow betweenness centrality for edges.
approximate_current_flow_betweenness_centrality(G) Compute the approximate current-flow betweenness centrality for nodes.
current_flow_betweenness_centrality_subset(G, …) Compute current-flow betweenness centrality for subsets of nodes.
edge_current_flow_betweenness_centrality_subset(G, …) Compute current-flow betweenness centrality for edges using subsets of nodes.
Communicability Betweenness
communicability_betweenness_centrality(G[, …]) Return subgraph communicability for all pairs of nodes in G.
Load
load_centrality(G[, v, cutoff, normalized, …]) Compute load centrality for nodes.
edge_load_centrality(G[, cutoff]) Compute edge load.
Subgraph
subgraph_centrality(G) Return subgraph centrality for each node in G.
subgraph_centrality_exp(G) Return the subgraph centrality for each node of G.
estrada_index(G) Return the Estrada index of a the graph G.
Harmonic Centrality
harmonic_centrality(G[, nbunch, distance]) Compute harmonic centrality for nodes.
Reaching
local_reaching_centrality(G, v[, paths, …]) Returns the local reaching centrality of a node in a directed graph.
global_reaching_centrality(G[, weight, …]) Returns the global reaching centrality of a directed graph.
Chains

Functions for finding chains in a graph.

chain_decomposition(G[, root]) Return the chain decomposition of a graph.
Chordal

Algorithms for chordal graphs.

A graph is chordal if every cycle of length at least 4 has a chord (an edge joining two nodes not adjacent in the cycle). http://en.wikipedia.org/wiki/Chordal_graph

is_chordal(G) Checks whether G is a chordal graph.
chordal_graph_cliques(G) Returns the set of maximal cliques of a chordal graph.
chordal_graph_treewidth(G) Returns the treewidth of the chordal graph G.
find_induced_nodes(G, s, t[, treewidth_bound]) Returns the set of induced nodes in the path from s to t.
Clique

Functions for finding and manipulating cliques.

Finding the largest clique in a graph is NP-complete problem, so most of these algorithms have an exponential running time; for more information, see the Wikipedia article on the clique problem [1].

[1]clique problem:: https://en.wikipedia.org/wiki/Clique_problem
enumerate_all_cliques(G) Returns all cliques in an undirected graph.
find_cliques(G) Returns all maximal cliques in an undirected graph.
make_max_clique_graph(G[, create_using]) Returns the maximal clique graph of the given graph.
make_clique_bipartite(G[, fpos, …]) Returns the bipartite clique graph corresponding to G.
graph_clique_number(G[, cliques]) Returns the clique number of the graph.
graph_number_of_cliques(G[, cliques]) Returns the number of maximal cliques in the graph.
node_clique_number(G[, nodes, cliques]) Returns the size of the largest maximal clique containing each given node.
number_of_cliques(G[, nodes, cliques]) Returns the number of maximal cliques for each node.
cliques_containing_node(G[, nodes, cliques]) Returns a list of cliques containing the given node.
Clustering

Algorithms to characterize the number of triangles in a graph.

triangles(G[, nodes]) Compute the number of triangles.
transitivity(G) Compute graph transitivity, the fraction of all possible triangles present in G.
clustering(G[, nodes, weight]) Compute the clustering coefficient for nodes.
average_clustering(G[, nodes, weight, …]) Compute the average clustering coefficient for the graph G.
square_clustering(G[, nodes]) Compute the squares clustering coefficient for nodes.
generalized_degree(G[, nodes]) Compute the generalized degree for nodes.
Coloring
greedy_color(G[, strategy, interchange]) Color a graph using various strategies of greedy graph coloring.

Some node ordering strategies are provided for use with greedy_color().

strategy_connected_sequential(G, colors[, …]) Returns an iterable over nodes in G in the order given by a breadth-first or depth-first traversal.
strategy_connected_sequential_dfs(G, colors) Returns an iterable over nodes in G in the order given by a depth-first traversal.
strategy_connected_sequential_bfs(G, colors) Returns an iterable over nodes in G in the order given by a breadth-first traversal.
strategy_independent_set(G, colors) Uses a greedy independent set removal strategy to determine the colors.
strategy_largest_first(G, colors) Returns a list of the nodes of G in decreasing order by degree.
strategy_random_sequential(G, colors) Returns a random permutation of the nodes of G as a list.
strategy_saturation_largest_first(G, colors) Iterates over all the nodes of G in “saturation order” (also known as “DSATUR”).
strategy_smallest_last(G, colors) Returns a deque of the nodes of G, “smallest” last.
Communicability

Communicability.

communicability(G) Return communicability between all pairs of nodes in G.
communicability_exp(G) Return communicability between all pairs of nodes in G.
Communities

Functions for computing and measuring community structure.

The functions in this class are not imported into the top-level networkx namespace. You can access these functions by importing the networkx.algorithms.community module, then accessing the functions as attributes of community. For example:

>>> import networkx as nx
>>> from networkx.algorithms import community
>>> G = nx.barbell_graph(5, 1)
>>> communities_generator = community.girvan_newman(G)
>>> top_level_communities = next(communities_generator)
>>> next_level_communities = next(communities_generator)
>>> sorted(map(sorted, next_level_communities))
[[0, 1, 2, 3, 4], [5], [6, 7, 8, 9, 10]]
Bipartitions

Functions for computing the Kernighan–Lin bipartition algorithm.

kernighan_lin_bisection(G[, partition, …]) Partition a graph into two blocks using the Kernighan–Lin algorithm.
Generators

Functions for generating graphs with community structure.

LFR_benchmark_graph(n, tau1, tau2, mu[, …]) Returns the LFR benchmark graph for testing community-finding algorithms.
K-Clique
k_clique_communities(G, k[, cliques]) Find k-clique communities in graph using the percolation method.
Label propagation

Asynchronous label propagation algorithms for community detection.

asyn_lpa_communities(G[, weight]) Returns communities in G as detected by asynchronous label propagation.
Measuring partitions

Functions for measuring the quality of a partition (into communities).

coverage(*args, **kw) Returns the coverage of a partition.
performance(*args, **kw) Returns the performance of a partition.
Partitions via centrality measures

Functions for computing communities based on centrality notions.

girvan_newman(G[, most_valuable_edge]) Finds communities in a graph using the Girvan–Newman method.
Validating partitions

Helper functions for community-finding algorithms.

is_partition(G, communities) Return True if and only if communities is a partition of the nodes of G.
Components
Connectivity
is_connected(G) Return True if the graph is connected, false otherwise.
number_connected_components(G) Return the number of connected components.
connected_components(G) Generate connected components.
connected_component_subgraphs(G[, copy]) Generate connected components as subgraphs.
node_connected_component(G, n) Return the nodes in the component of graph containing node n.
Strong connectivity
is_strongly_connected(G) Test directed graph for strong connectivity.
number_strongly_connected_components(G) Return number of strongly connected components in graph.
strongly_connected_components(G) Generate nodes in strongly connected components of graph.
strongly_connected_component_subgraphs(G[, copy]) Generate strongly connected components as subgraphs.
strongly_connected_components_recursive(G) Generate nodes in strongly connected components of graph.
kosaraju_strongly_connected_components(G[, …]) Generate nodes in strongly connected components of graph.
condensation(G[, scc]) Returns the condensation of G.
Weak connectivity
is_weakly_connected(G) Test directed graph for weak connectivity.
number_weakly_connected_components(G) Return the number of weakly connected components in G.
weakly_connected_components(G) Generate weakly connected components of G.
weakly_connected_component_subgraphs(G[, copy]) Generate weakly connected components as subgraphs.
Attracting components
is_attracting_component(G) Returns True if G consists of a single attracting component.
number_attracting_components(G) Returns the number of attracting components in G.
attracting_components(G) Generates a list of attracting components in G.
attracting_component_subgraphs(G[, copy]) Generates a list of attracting component subgraphs from G.
Biconnected components
is_biconnected(G) Return True if the graph is biconnected, False otherwise.
biconnected_components(G) Return a generator of sets of nodes, one set for each biconnected
biconnected_component_edges(G) Return a generator of lists of edges, one list for each biconnected component of the input graph.
biconnected_component_subgraphs(G[, copy]) Return a generator of graphs, one graph for each biconnected component of the input graph.
articulation_points(G) Yield the articulation points, or cut vertices, of a graph.
Semiconnectedness
is_semiconnected(G) Return True if the graph is semiconnected, False otherwise.
Connectivity

Connectivity and cut algorithms

K-node-components

Moody and White algorithm for k-components

k_components(G[, flow_func]) Returns the k-component structure of a graph G.
K-node-cutsets

Kanevsky all minimum node k cutsets algorithm.

all_node_cuts(G[, k, flow_func]) Returns all minimum k cutsets of an undirected graph G.
Flow-based Connectivity

Flow based connectivity algorithms

average_node_connectivity(G[, flow_func]) Returns the average connectivity of a graph G.
all_pairs_node_connectivity(G[, nbunch, …]) Compute node connectivity between all pairs of nodes of G.
edge_connectivity(G[, s, t, flow_func]) Returns the edge connectivity of the graph or digraph G.
local_edge_connectivity(G, s, t[, …]) Returns local edge connectivity for nodes s and t in G.
local_node_connectivity(G, s, t[, …]) Computes local node connectivity for nodes s and t.
node_connectivity(G[, s, t, flow_func]) Returns node connectivity for a graph or digraph G.
Flow-based Minimum Cuts

Flow based cut algorithms

minimum_edge_cut(G[, s, t, flow_func]) Returns a set of edges of minimum cardinality that disconnects G.
minimum_node_cut(G[, s, t, flow_func]) Returns a set of nodes of minimum cardinality that disconnects G.
minimum_st_edge_cut(G, s, t[, flow_func, …]) Returns the edges of the cut-set of a minimum (s, t)-cut.
minimum_st_node_cut(G, s, t[, flow_func, …]) Returns a set of nodes of minimum cardinality that disconnect source from target in G.
Stoer-Wagner minimum cut

Stoer-Wagner minimum cut algorithm.

stoer_wagner(G[, weight, heap]) Returns the weighted minimum edge cut using the Stoer-Wagner algorithm.
Utils for flow-based connectivity

Utilities for connectivity package

build_auxiliary_edge_connectivity(G) Auxiliary digraph for computing flow based edge connectivity
build_auxiliary_node_connectivity(G) Creates a directed graph D from an undirected graph G to compute flow based node connectivity.
Cores

Find the k-cores of a graph.

The k-core is found by recursively pruning nodes with degrees less than k.

See the following references for details:

An O(m) Algorithm for Cores Decomposition of Networks Vladimir Batagelj and Matjaz Zaversnik, 2003. http://arxiv.org/abs/cs.DS/0310049

Generalized Cores Vladimir Batagelj and Matjaz Zaversnik, 2002. http://arxiv.org/pdf/cs/0202039

For directed graphs a more general notion is that of D-cores which looks at (k, l) restrictions on (in, out) degree. The (k, k) D-core is the k-core.

D-cores: Measuring Collaboration of Directed Graphs Based on Degeneracy Christos Giatsidis, Dimitrios M. Thilikos, Michalis Vazirgiannis, ICDM 2011. http://www.graphdegeneracy.org/dcores_ICDM_2011.pdf

core_number(G) Return the core number for each vertex.
k_core(G[, k, core_number]) Return the k-core of G.
k_shell(G[, k, core_number]) Return the k-shell of G.
k_crust(G[, k, core_number]) Return the k-crust of G.
k_corona(G, k[, core_number]) Return the k-corona of G.
Covering

Functions related to graph covers.

min_edge_cover(G[, matching_algorithm]) Returns a set of edges which constitutes the minimum edge cover of the graph.
is_edge_cover(G, cover) Decides whether a set of edges is a valid edge cover of the graph.
Cycles
Cycle finding algorithms
cycle_basis(G[, root]) Returns a list of cycles which form a basis for cycles of G.
simple_cycles(G) Find simple cycles (elementary circuits) of a directed graph.
find_cycle(G[, source, orientation]) Returns the edges of a cycle found via a directed, depth-first traversal.
Cuts

Functions for finding and evaluating cuts in a graph.

boundary_expansion(G, S) Returns the boundary expansion of the set S.
conductance(G, S[, T, weight]) Returns the conductance of two sets of nodes.
cut_size(G, S[, T, weight]) Returns the size of the cut between two sets of nodes.
edge_expansion(G, S[, T, weight]) Returns the edge expansion between two node sets.
mixing_expansion(G, S[, T, weight]) Returns the mixing expansion between two node sets.
node_expansion(G, S) Returns the node expansion of the set S.
normalized_cut_size(G, S[, T, weight]) Returns the normalized size of the cut between two sets of nodes.
volume(G, S[, weight]) Returns the volume of a set of nodes.
Directed Acyclic Graphs

Algorithms for directed acyclic graphs (DAGs).

Note that most of these functions are only guaranteed to work for DAGs. In general, these functions do not check for acyclic-ness, so it is up to the user to check for that.

ancestors(G, source) Return all nodes having a path to source in G.
descendants(G, source) Return all nodes reachable from source in G.
topological_sort(G) Return a generator of nodes in topologically sorted order.
lexicographical_topological_sort(G[, key]) Return a generator of nodes in lexicographically topologically sorted order.
is_directed_acyclic_graph(G) Return True if the graph G is a directed acyclic graph (DAG) or False if not.
is_aperiodic(G) Return True if G is aperiodic.
transitive_closure(G) Returns transitive closure of a directed graph
transitive_reduction(G) Returns transitive reduction of a directed graph
antichains(G) Generates antichains from a directed acyclic graph (DAG).
dag_longest_path(G[, weight, default_weight]) Returns the longest path in a directed acyclic graph (DAG).
dag_longest_path_length(G[, weight, …]) Returns the longest path length in a DAG
Dispersion
Dispersion
dispersion(G[, u, v, normalized, alpha, b, c]) Calculate dispersion between u and v in G.
Distance Measures

Graph diameter, radius, eccentricity and other properties.

center(G[, e, usebounds]) Return the center of the graph G.
diameter(G[, e, usebounds]) Return the diameter of the graph G.
eccentricity(G[, v, sp]) Return the eccentricity of nodes in G.
periphery(G[, e, usebounds]) Return the periphery of the graph G.
radius(G[, e, usebounds]) Return the radius of the graph G.
Distance-Regular Graphs
Distance-regular graphs
is_distance_regular(G) Returns True if the graph is distance regular, False otherwise.
is_strongly_regular(G) Returns True if and only if the given graph is strongly regular.
intersection_array(G) Returns the intersection array of a distance-regular graph.
global_parameters(b, c) Return global parameters for a given intersection array.
Dominance

Dominance algorithms.

immediate_dominators(G, start) Returns the immediate dominators of all nodes of a directed graph.
dominance_frontiers(G, start) Returns the dominance frontiers of all nodes of a directed graph.
Dominating Sets

Functions for computing dominating sets in a graph.

dominating_set(G[, start_with]) Finds a dominating set for the graph G.
is_dominating_set(G, nbunch) Checks if nbunch is a dominating set for G.
Efficiency

Provides functions for computing the efficiency of nodes and graphs.

efficiency(G, u, v) Returns the efficiency of a pair of nodes in a graph.
local_efficiency(G) Returns the average local efficiency of the graph.
global_efficiency(G) Returns the average global efficiency of the graph.
Eulerian

Eulerian circuits and graphs.

is_eulerian(G) Returns True if and only if G is Eulerian.
eulerian_circuit(G[, source, keys]) Returns an iterator over the edges of an Eulerian circuit in G.
Flows
Maximum Flow
maximum_flow(G, s, t[, capacity, flow_func]) Find a maximum single-commodity flow.
maximum_flow_value(G, s, t[, capacity, …]) Find the value of maximum single-commodity flow.
minimum_cut(G, s, t[, capacity, flow_func]) Compute the value and the node partition of a minimum (s, t)-cut.
minimum_cut_value(G, s, t[, capacity, flow_func]) Compute the value of a minimum (s, t)-cut.
Edmonds-Karp
edmonds_karp(G, s, t[, capacity, residual, …]) Find a maximum single-commodity flow using the Edmonds-Karp algorithm.
Shortest Augmenting Path
shortest_augmenting_path(G, s, t[, …]) Find a maximum single-commodity flow using the shortest augmenting path algorithm.
Preflow-Push
preflow_push(G, s, t[, capacity, residual, …]) Find a maximum single-commodity flow using the highest-label preflow-push algorithm.
Dinitz
dinitz(G, s, t[, capacity, residual, …]) Find a maximum single-commodity flow using Dinitz’ algorithm.
Boykov-Kolmogorov
boykov_kolmogorov(G, s, t[, capacity, …]) Find a maximum single-commodity flow using Boykov-Kolmogorov algorithm.
Gomory-Hu Tree
gomory_hu_tree(G[, capacity, flow_func]) Returns the Gomory-Hu tree of an undirected graph G.
Utils
build_residual_network(G, capacity) Build a residual network and initialize a zero flow.
Network Simplex
network_simplex(G[, demand, capacity, weight]) Find a minimum cost flow satisfying all demands in digraph G.
min_cost_flow_cost(G[, demand, capacity, weight]) Find the cost of a minimum cost flow satisfying all demands in digraph G.
min_cost_flow(G[, demand, capacity, weight]) Return a minimum cost flow satisfying all demands in digraph G.
cost_of_flow(G, flowDict[, weight]) Compute the cost of the flow given by flowDict on graph G.
max_flow_min_cost(G, s, t[, capacity, weight]) Return a maximum (s, t)-flow of minimum cost.
Capacity Scaling Minimum Cost Flow
capacity_scaling(G[, demand, capacity, …]) Find a minimum cost flow satisfying all demands in digraph G.
Graphical degree sequence

Test sequences for graphiness.

is_graphical(sequence[, method]) Returns True if sequence is a valid degree sequence.
is_digraphical(in_sequence, out_sequence) Returns True if some directed graph can realize the in- and out-degree sequences.
is_multigraphical(sequence) Returns True if some multigraph can realize the sequence.
is_pseudographical(sequence) Returns True if some pseudograph can realize the sequence.
is_valid_degree_sequence_havel_hakimi(…) Returns True if deg_sequence can be realized by a simple graph.
is_valid_degree_sequence_erdos_gallai(…) Returns True if deg_sequence can be realized by a simple graph.
Hierarchy

Flow Hierarchy.

flow_hierarchy(G[, weight]) Returns the flow hierarchy of a directed network.
Hybrid

Provides functions for finding and testing for locally (k, l)-connected graphs.

kl_connected_subgraph(G, k, l[, low_memory, …]) Returns the maximum locally (k, l)-connected subgraph of G.
is_kl_connected(G, k, l[, low_memory]) Returns True if and only if G is locally (k, l)-connected.
Isolates

Functions for identifying isolate (degree zero) nodes.

is_isolate(G, n) Determines whether a node is an isolate.
isolates(G) Iterator over isolates in the graph.
Isomorphism
is_isomorphic(G1, G2[, node_match, edge_match]) Returns True if the graphs G1 and G2 are isomorphic and False otherwise.
could_be_isomorphic(G1, G2) Returns False if graphs are definitely not isomorphic.
fast_could_be_isomorphic(G1, G2) Returns False if graphs are definitely not isomorphic.
faster_could_be_isomorphic(G1, G2) Returns False if graphs are definitely not isomorphic.
Advanced Interface to VF2 Algorithm
VF2 Algorithm
VF2 Algorithm

An implementation of VF2 algorithm for graph ismorphism testing.

The simplest interface to use this module is to call networkx.is_isomorphic().

Introduction

The GraphMatcher and DiGraphMatcher are responsible for matching graphs or directed graphs in a predetermined manner. This usually means a check for an isomorphism, though other checks are also possible. For example, a subgraph of one graph can be checked for isomorphism to a second graph.

Matching is done via syntactic feasibility. It is also possible to check for semantic feasibility. Feasibility, then, is defined as the logical AND of the two functions.

To include a semantic check, the (Di)GraphMatcher class should be subclassed, and the semantic_feasibility() function should be redefined. By default, the semantic feasibility function always returns True. The effect of this is that semantics are not considered in the matching of G1 and G2.

Examples

Suppose G1 and G2 are isomorphic graphs. Verification is as follows:

>>> from networkx.algorithms import isomorphism
>>> G1 = nx.path_graph(4)
>>> G2 = nx.path_graph(4)
>>> GM = isomorphism.GraphMatcher(G1,G2)
>>> GM.is_isomorphic()
True

GM.mapping stores the isomorphism mapping from G1 to G2.

>>> GM.mapping
{0: 0, 1: 1, 2: 2, 3: 3}

Suppose G1 and G2 are isomorphic directed graphs graphs. Verification is as follows:

>>> G1 = nx.path_graph(4, create_using=nx.DiGraph())
>>> G2 = nx.path_graph(4, create_using=nx.DiGraph())
>>> DiGM = isomorphism.DiGraphMatcher(G1,G2)
>>> DiGM.is_isomorphic()
True

DiGM.mapping stores the isomorphism mapping from G1 to G2.

>>> DiGM.mapping
{0: 0, 1: 1, 2: 2, 3: 3}
Subgraph Isomorphism

Graph theory literature can be ambiguious about the meaning of the above statement, and we seek to clarify it now.

In the VF2 literature, a mapping M is said to be a graph-subgraph isomorphism iff M is an isomorphism between G2 and a subgraph of G1. Thus, to say that G1 and G2 are graph-subgraph isomorphic is to say that a subgraph of G1 is isomorphic to G2.

Other literature uses the phrase ‘subgraph isomorphic’ as in ‘G1 does not have a subgraph isomorphic to G2’. Another use is as an in adverb for isomorphic. Thus, to say that G1 and G2 are subgraph isomorphic is to say that a subgraph of G1 is isomorphic to G2.

Finally, the term ‘subgraph’ can have multiple meanings. In this context, ‘subgraph’ always means a ‘node-induced subgraph’. Edge-induced subgraph isomorphisms are not directly supported, but one should be able to perform the check by making use of nx.line_graph(). For subgraphs which are not induced, the term ‘monomorphism’ is preferred over ‘isomorphism’. Currently, it is not possible to check for monomorphisms.

Let G=(N,E) be a graph with a set of nodes N and set of edges E.

If G’=(N’,E’) is a subgraph, then:
N’ is a subset of N E’ is a subset of E
If G’=(N’,E’) is a node-induced subgraph, then:
N’ is a subset of N E’ is the subset of edges in E relating nodes in N’
If G’=(N’,E’) is an edge-induced subgraph, then:
N’ is the subset of nodes in N related by edges in E’ E’ is a subset of E

References

[1] Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento,
“A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 10, pp. 1367-1372, Oct., 2004. http://ieeexplore.ieee.org/iel5/34/29305/01323804.pdf
[2] L. P. Cordella, P. Foggia, C. Sansone, M. Vento, “An Improved
Algorithm for Matching Large Graphs”, 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, Cuen, pp. 149-159, 2001. http://amalfi.dis.unina.it/graph/db/papers/vf-algorithm.pdf

See also

syntactic_feasibliity, semantic_feasibility

Notes

The implementation handles both directed and undirected graphs as well as multigraphs. However, it does require that nodes in the graph are orderable (in addition to the general NetworkX requirement that nodes are hashable). If the nodes in your graph are not orderable, you can convert them to an orderable type (int, for example) by using the networkx.relabel() function. You can store the dictionary of old-to-new node labels to retrieve the original node labels after running the isomorphism algorithm:

>>> G = nx.Graph()
>>> node1, node2 = object(), object()
>>> G.add_nodes_from([node1, node2])
>>> mapping = {k: v for v, k in enumerate(G)}
>>> G = nx.relabel_nodes(G, mapping)

In general, the subgraph isomorphism problem is NP-complete whereas the graph isomorphism problem is most likely not NP-complete (although no polynomial-time algorithm is known to exist).

Graph Matcher
GraphMatcher.__init__(G1, G2[, node_match, …]) Initialize graph matcher.
GraphMatcher.initialize() Reinitializes the state of the algorithm.
GraphMatcher.is_isomorphic() Returns True if G1 and G2 are isomorphic graphs.
GraphMatcher.subgraph_is_isomorphic() Returns True if a subgraph of G1 is isomorphic to G2.
GraphMatcher.isomorphisms_iter() Generator over isomorphisms between G1 and G2.
GraphMatcher.subgraph_isomorphisms_iter() Generator over isomorphisms between a subgraph of G1 and G2.
GraphMatcher.candidate_pairs_iter() Iterator over candidate pairs of nodes in G1 and G2.
GraphMatcher.match() Extends the isomorphism mapping.
GraphMatcher.semantic_feasibility(G1_node, …) Returns True if mapping G1_node to G2_node is semantically feasible.
GraphMatcher.syntactic_feasibility(G1_node, …) Returns True if adding (G1_node, G2_node) is syntactically feasible.
DiGraph Matcher
DiGraphMatcher.__init__(G1, G2[, …]) Initialize graph matcher.
DiGraphMatcher.initialize() Reinitializes the state of the algorithm.
DiGraphMatcher.is_isomorphic() Returns True if G1 and G2 are isomorphic graphs.
DiGraphMatcher.subgraph_is_isomorphic() Returns True if a subgraph of G1 is isomorphic to G2.
DiGraphMatcher.isomorphisms_iter() Generator over isomorphisms between G1 and G2.
DiGraphMatcher.subgraph_isomorphisms_iter() Generator over isomorphisms between a subgraph of G1 and G2.
DiGraphMatcher.candidate_pairs_iter() Iterator over candidate pairs of nodes in G1 and G2.
DiGraphMatcher.match() Extends the isomorphism mapping.
DiGraphMatcher.semantic_feasibility(G1_node, …) Returns True if mapping G1_node to G2_node is semantically feasible.
DiGraphMatcher.syntactic_feasibility(…) Returns True if adding (G1_node, G2_node) is syntactically feasible.
Match helpers
categorical_node_match(attr, default) Returns a comparison function for a categorical node attribute.
categorical_edge_match(attr, default) Returns a comparison function for a categorical edge attribute.
categorical_multiedge_match(attr, default) Returns a comparison function for a categorical edge attribute.
numerical_node_match(attr, default[, rtol, atol]) Returns a comparison function for a numerical node attribute.
numerical_edge_match(attr, default[, rtol, atol]) Returns a comparison function for a numerical edge attribute.
numerical_multiedge_match(attr, default[, …]) Returns a comparison function for a numerical edge attribute.
generic_node_match(attr, default, op) Returns a comparison function for a generic attribute.
generic_edge_match(attr, default, op) Returns a comparison function for a generic attribute.
generic_multiedge_match(attr, default, op) Returns a comparison function for a generic attribute.
Matching

Functions for computing and verifying matchings in a graph.

is_matching(G, matching) Decides whether the given set or dictionary represents a valid matching in G.
is_maximal_matching(G, matching) Decides whether the given set or dictionary represents a valid maximal matching in G.
maximal_matching(G) Find a maximal matching in the graph.
max_weight_matching(G[, maxcardinality, weight]) Compute a maximum-weighted matching of G.
Minors

Provides functions for computing minors of a graph.

contracted_edge(G, edge[, self_loops]) Returns the graph that results from contracting the specified edge.
contracted_nodes(G, u, v[, self_loops]) Returns the graph that results from contracting u and v.
identified_nodes(G, u, v[, self_loops]) Returns the graph that results from contracting u and v.
quotient_graph(G, partition[, …]) Returns the quotient graph of G under the specified equivalence relation on nodes.
blockmodel(G, partition[, multigraph]) Returns a reduced graph constructed using the generalized block modeling technique.
Maximal independent set

Algorithm to find a maximal (not maximum) independent set.

maximal_independent_set(G[, nodes]) Return a random maximal independent set guaranteed to contain a given set of nodes.
Operators

Unary operations on graphs

complement(G[, name]) Return the graph complement of G.
reverse(G[, copy]) Return the reverse directed graph of G.

Operations on graphs including union, intersection, difference.

compose(G, H[, name]) Return a new graph of G composed with H.
union(G, H[, rename, name]) Return the union of graphs G and H.
disjoint_union(G, H) Return the disjoint union of graphs G and H.
intersection(G, H) Return a new graph that contains only the edges that exist in both G and H.
difference(G, H) Return a new graph that contains the edges that exist in G but not in H.
symmetric_difference(G, H) Return new graph with edges that exist in either G or H but not both.

Operations on many graphs.

compose_all(graphs[, name]) Return the composition of all graphs.
union_all(graphs[, rename, name]) Return the union of all graphs.
disjoint_union_all(graphs) Return the disjoint union of all graphs.
intersection_all(graphs) Return a new graph that contains only the edges that exist in all graphs.

Graph products.

cartesian_product(G, H) Return the Cartesian product of G and H.
lexicographic_product(G, H) Return the lexicographic product of G and H.
strong_product(G, H) Return the strong product of G and H.
tensor_product(G, H) Return the tensor product of G and H.
power(G, k) Returns the specified power of a graph.
Reciprocity

Algorithms to calculate reciprocity in a directed graph.

reciprocity(G[, nodes]) Compute the reciprocity in a directed graph.
overall_reciprocity(G) Compute the reciprocity for the whole graph.
Rich Club

Functions for computing rich-club coefficients.

rich_club_coefficient(G[, normalized, Q]) Returns the rich-club coefficient of the graph G.
Shortest Paths

Compute the shortest paths and path lengths between nodes in the graph.

These algorithms work with undirected and directed graphs.

shortest_path(G[, source, target, weight]) Compute shortest paths in the graph.
all_shortest_paths(G, source, target[, weight]) Compute all shortest paths in the graph.
shortest_path_length(G[, source, target, weight]) Compute shortest path lengths in the graph.
average_shortest_path_length(G[, weight]) Return the average shortest path length.
has_path(G, source, target) Return True if G has a path from source to target.
Advanced Interface

Shortest path algorithms for unweighted graphs.

single_source_shortest_path(G, source[, cutoff]) Compute shortest path between source and all other nodes reachable from source.
single_source_shortest_path_length(G, source) Compute the shortest path lengths from source to all reachable nodes.
all_pairs_shortest_path(G[, cutoff]) Compute shortest paths between all nodes.
all_pairs_shortest_path_length(G[, cutoff]) Computes the shortest path lengths between all nodes in G.
predecessor(G, source[, target, cutoff, …]) Returns dict of predecessors for the path from source to all nodes in G

Shortest path algorithms for weighed graphs.

dijkstra_predecessor_and_distance(G, source) Compute weighted shortest path length and predecessors.
dijkstra_path(G, source, target[, weight]) Returns the shortest weighted path from source to target in G.
dijkstra_path_length(G, source, target[, weight]) Returns the shortest weighted path length in G from source to target.
single_source_dijkstra(G, source[, target, …]) Find shortest weighted paths and lengths from a source node.
single_source_dijkstra_path(G, source[, …]) Find shortest weighted paths in G from a source node.
single_source_dijkstra_path_length(G, source) Find shortest weighted path lengths in G from a source node.
multi_source_dijkstra_path(G, sources[, …]) Find shortest weighted paths in G from a given set of source nodes.
multi_source_dijkstra_path_length(G, sources) Find shortest weighted path lengths in G from a given set of source nodes.
all_pairs_dijkstra_path(G[, cutoff, weight]) Compute shortest paths between all nodes in a weighted graph.
all_pairs_dijkstra_path_length(G[, cutoff, …]) Compute shortest path lengths between all nodes in a weighted graph.
bidirectional_dijkstra(G, source, target[, …]) Dijkstra’s algorithm for shortest paths using bidirectional search.
bellman_ford_path(G, source, target[, weight]) Returns the shortest path from source to target in a weighted graph G.
bellman_ford_path_length(G, source, target) Returns the shortest path length from source to target in a weighted graph.
single_source_bellman_ford_path(G, source[, …]) Compute shortest path between source and all other reachable nodes for a weighted graph.
single_source_bellman_ford_path_length(G, source) Compute the shortest path length between source and all other reachable nodes for a weighted graph.
all_pairs_bellman_ford_path(G[, cutoff, weight]) Compute shortest paths between all nodes in a weighted graph.
all_pairs_bellman_ford_path_length(G[, …]) Compute shortest path lengths between all nodes in a weighted graph.
single_source_bellman_ford(G, source[, …]) Compute shortest paths and lengths in a weighted graph G.
bellman_ford_predecessor_and_distance(G, source) Compute shortest path lengths and predecessors on shortest paths in weighted graphs.
negative_edge_cycle(G[, weight]) Return True if there exists a negative edge cycle anywhere in G.
johnson(G[, weight]) Uses Johnson’s Algorithm to compute shortest paths.
Dense Graphs

Floyd-Warshall algorithm for shortest paths.

floyd_warshall(G[, weight]) Find all-pairs shortest path lengths using Floyd’s algorithm.
floyd_warshall_predecessor_and_distance(G[, …]) Find all-pairs shortest path lengths using Floyd’s algorithm.
floyd_warshall_numpy(G[, nodelist, weight]) Find all-pairs shortest path lengths using Floyd’s algorithm.
A* Algorithm

Shortest paths and path lengths using the A* (“A star”) algorithm.

astar_path(G, source, target[, heuristic, …]) Return a list of nodes in a shortest path between source and target using the A* (“A-star”) algorithm.
astar_path_length(G, source, target[, …]) Return the length of the shortest path between source and target using the A* (“A-star”) algorithm.
Simple Paths
all_simple_paths(G, source, target[, cutoff]) Generate all simple paths in the graph G from source to target.
is_simple_path(G, nodes) Returns True if and only if the given nodes form a simple path in G.
shortest_simple_paths(G, source, target[, …]) Generate all simple paths in the graph G from source to target, starting from shortest ones.
Structural holes

Functions for computing measures of structural holes.

constraint(G[, nodes, weight]) Returns the constraint on all nodes in the graph G.
effective_size(G[, nodes, weight]) Returns the effective size of all nodes in the graph G.
local_constraint(G, u, v[, weight]) Returns the local constraint on the node u with respect to the node v in the graph G.
Swap

Swap edges in a graph.

double_edge_swap(G[, nswap, max_tries]) Swap two edges in the graph while keeping the node degrees fixed.
connected_double_edge_swap(G[, nswap, …]) Attempts the specified number of double-edge swaps in the graph G.
Tournament

Functions concerning tournament graphs.

A tournament graph is a complete oriented graph. In other words, it is a directed graph in which there is exactly one directed edge joining each pair of distinct nodes. For each function in this module that accepts a graph as input, you must provide a tournament graph. The responsibility is on the caller to ensure that the graph is a tournament graph.

To access the functions in this module, you must access them through the networkx.algorithms.tournament module:

>>> import networkx as nx
>>> from networkx.algorithms import tournament
>>> G = nx.DiGraph([(0, 1), (1, 2), (2, 0)])
>>> tournament.is_tournament(G)
True
hamiltonian_path(G) Returns a Hamiltonian path in the given tournament graph.
is_reachable(G, s, t) Decides whether there is a path from s to t in the tournament.
is_strongly_connected(G) Decides whether the given tournament is strongly connected.
is_tournament(G) Returns True if and only if G is a tournament.
random_tournament(n) Returns a random tournament graph on n nodes.
score_sequence(G) Returns the score sequence for the given tournament graph.
Traversal
Beam search

Basic algorithms for breadth-first searching the nodes of a graph.

bfs_beam_edges(G, source, value[, width]) Iterates over edges in a beam search.
Depth First Search on Edges
Depth First Search on Edges

Algorithms for a depth-first traversal of edges in a graph.

edge_dfs(G[, source, orientation]) A directed, depth-first traversal of edges in G, beginning at source.
Tree
Recognition
Recognition Tests

A forest is an acyclic, undirected graph, and a tree is a connected forest. Depending on the subfield, there are various conventions for generalizing these definitions to directed graphs.

In one convention, directed variants of forest and tree are defined in an identical manner, except that the direction of the edges is ignored. In effect, each directed edge is treated as a single undirected edge. Then, additional restrictions are imposed to define branchings and arborescences.

In another convention, directed variants of forest and tree correspond to the previous convention’s branchings and arborescences, respectively. Then two new terms, polyforest and polytree, are defined to correspond to the other convention’s forest and tree.

Summarizing:

+-----------------------------+
| Convention A | Convention B |
+=============================+
| forest       | polyforest   |
| tree         | polytree     |
| branching    | forest       |
| arborescence | tree         |
+-----------------------------+

Each convention has its reasons. The first convention emphasizes definitional similarity in that directed forests and trees are only concerned with acyclicity and do not have an in-degree constraint, just as their undirected counterparts do not. The second convention emphasizes functional similarity in the sense that the directed analog of a spanning tree is a spanning arborescence. That is, take any spanning tree and choose one node as the root. Then every edge is assigned a direction such there is a directed path from the root to every other node. The result is a spanning arborescence.

NetworkX follows convention “A”. Explicitly, these are:

undirected forest
An undirected graph with no undirected cycles.
undirected tree
A connected, undirected forest.
directed forest
A directed graph with no undirected cycles. Equivalently, the underlying graph structure (which ignores edge orientations) is an undirected forest. In convention B, this is known as a polyforest.
directed tree
A weakly connected, directed forest. Equivalently, the underlying graph structure (which ignores edge orientations) is an undirected tree. In convention B, this is known as a polytree.
branching
A directed forest with each node having, at most, one parent. So the maximum in-degree is equal to 1. In convention B, this is known as a forest.
arborescence
A directed tree with each node having, at most, one parent. So the maximum in-degree is equal to 1. In convention B, this is known as a tree.

For trees and arborescences, the adjective “spanning” may be added to designate that the graph, when considered as a forest/branching, consists of a single tree/arborescence that includes all nodes in the graph. It is true, by definition, that every tree/arborescence is spanning with respect to the nodes that define the tree/arborescence and so, it might seem redundant to introduce the notion of “spanning”. However, the nodes may represent a subset of nodes from a larger graph, and it is in this context that the term “spanning” becomes a useful notion.

is_tree(G) Returns True if G is a tree.
is_forest(G) Returns True if G is a forest.
is_arborescence(G) Returns True if G is an arborescence.
is_branching(G) Returns True if G is a branching.
Branchings and Spanning Arborescences

Algorithms for finding optimum branchings and spanning arborescences.

This implementation is based on:

J. Edmonds, Optimum branchings, J. Res. Natl. Bur. Standards 71B (1967), 233–240. URL: http://archive.org/details/jresv71Bn4p233
branching_weight(G[, attr, default]) Returns the total weight of a branching.
greedy_branching(G[, attr, default, kind]) Returns a branching obtained through a greedy algorithm.
maximum_branching(G[, attr, default]) Returns a maximum branching from G.
minimum_branching(G[, attr, default]) Returns a minimum branching from G.
maximum_spanning_arborescence(G[, attr, default]) Returns a maximum spanning arborescence from G.
minimum_spanning_arborescence(G[, attr, default]) Returns a minimum spanning arborescence from G.
Edmonds(G[, seed]) Edmonds algorithm for finding optimal branchings and spanning arborescences.
Encoding and decoding

Functions for encoding and decoding trees.

Since a tree is a highly restricted form of graph, it can be represented concisely in several ways. This module includes functions for encoding and decoding trees in the form of nested tuples and Prüfer sequences. The former requires a rooted tree, whereas the latter can be applied to unrooted trees. Furthermore, there is a bijection from Prüfer sequences to labeled trees.

from_nested_tuple(sequence[, …]) Returns the rooted tree corresponding to the given nested tuple.
to_nested_tuple(T, root[, canonical_form]) Returns a nested tuple representation of the given tree.
from_prufer_sequence(sequence) Returns the tree corresponding to the given Prüfer sequence.
to_prufer_sequence(T) Returns the Prüfer sequence of the given tree.
Operations

Operations on trees.

join(rooted_trees[, label_attribute]) Returns a new rooted tree with a root node joined with the roots of each of the given rooted trees.
Spanning Trees

Algorithms for calculating min/max spanning trees/forests.

minimum_spanning_tree(G[, weight, algorithm]) Returns a minimum spanning tree or forest on an undirected graph G.
maximum_spanning_tree(G[, weight, algorithm]) Returns a maximum spanning tree or forest on an undirected graph G.
minimum_spanning_edges(G[, algorithm, …]) Generate edges in a minimum spanning forest of an undirected weighted graph.
maximum_spanning_edges(G[, algorithm, …]) Generate edges in a maximum spanning forest of an undirected weighted graph.
Exceptions

Functions for encoding and decoding trees.

Since a tree is a highly restricted form of graph, it can be represented concisely in several ways. This module includes functions for encoding and decoding trees in the form of nested tuples and Prüfer sequences. The former requires a rooted tree, whereas the latter can be applied to unrooted trees. Furthermore, there is a bijection from Prüfer sequences to labeled trees.

NotATree Raised when a function expects a tree (that is, a connected undirected graph with no cycles) but gets a non-tree graph as input instead.
Triads

Functions for analyzing triads of a graph.

triadic_census(G) Determines the triadic census of a directed graph.
Vitality

Vitality measures.

closeness_vitality(G[, node, weight, …]) Returns the closeness vitality for nodes in the graph.
Voronoi cells

Functions for computing the Voronoi cells of a graph.

voronoi_cells(G, center_nodes[, weight]) Returns the Voronoi cells centered at center_nodes with respect to the shortest-path distance metric.
Wiener index

Functions related to the Wiener index of a graph.

wiener_index(G[, weight]) Returns the Wiener index of the given graph.

Functions

Functional interface to graph methods and assorted utilities.

Graph
degree(G[, nbunch, weight]) Return degree of single node or of nbunch of nodes.
degree_histogram(G) Return a list of the frequency of each degree value.
density(G) Return the density of a graph.
info(G[, n]) Print short summary of information for the graph G or the node n.
create_empty_copy(G[, with_data]) Return a copy of the graph G with all of the edges removed.
is_directed(G) Return True if graph is directed.
add_star(G, nodes, **attr) Add a star to Graph G.
add_path(G, nodes, **attr) Add a path to the Graph G.
add_cycle(G, nodes, **attr) Add a cycle to the Graph G.
Nodes
nodes(G) Return an iterator over the graph nodes.
number_of_nodes(G) Return the number of nodes in the graph.
all_neighbors(graph, node) Returns all of the neighbors of a node in the graph.
non_neighbors(graph, node) Returns the non-neighbors of the node in the graph.
common_neighbors(G, u, v) Return the common neighbors of two nodes in a graph.
Edges
edges(G[, nbunch]) Return iterator over edges incident to nodes in nbunch.
number_of_edges(G) Return the number of edges in the graph.
non_edges(graph) Returns the non-existent edges in the graph.
Attributes
set_node_attributes(G, name, values) Sets node attributes from a given value or dictionary of values.
get_node_attributes(G, name) Get node attributes from graph
set_edge_attributes(G, name, values) Sets edge attributes from a given value or dictionary of values.
get_edge_attributes(G, name) Get edge attributes from graph
Freezing graph structure
freeze(G) Modify graph to prevent further change by adding or removing nodes or edges.
is_frozen(G) Return True if graph is frozen.

Graph generators

Atlas

Generators for the small graph atlas.

graph_atlas(i) Returns graph number i from the Graph Atlas.
graph_atlas_g() Return the list of all graphs with up to seven nodes named in the Graph Atlas.
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).

balanced_tree(r, h[, create_using]) Return the perfectly balanced r-ary tree of height h.
barbell_graph(m1, m2[, create_using]) Return the Barbell Graph: two complete graphs connected by a path.
complete_graph(n[, create_using]) Return the complete graph K_n with n nodes.
complete_multipartite_graph(*subset_sizes) Returns the complete multipartite graph with the specified subset sizes.
circular_ladder_graph(n[, create_using]) Return the circular ladder graph CL_n of length n.
cycle_graph(n[, create_using]) Return the cycle graph C_n of cyclicly connected nodes.
dorogovtsev_goltsev_mendes_graph(n[, …]) Return the hierarchically constructed Dorogovtsev-Goltsev-Mendes graph.
empty_graph([n, create_using]) Return the empty graph with n nodes and zero edges.
ladder_graph(n[, create_using]) Return the Ladder graph of length n.
lollipop_graph(m, n[, create_using]) Return the Lollipop Graph; K_m connected to P_n.
null_graph([create_using]) Return the Null graph with no nodes or edges.
path_graph(n[, create_using]) Return the Path graph P_n of linearly connected nodes.
star_graph(n[, create_using]) Return the star graph
trivial_graph([create_using]) Return the Trivial graph with one node (with label 0) and no edges.
turan_graph(n, r) Return the Turan Graph
wheel_graph(n[, create_using]) Return the wheel graph
Expanders

Provides explicit constructions of expander graphs.

margulis_gabber_galil_graph(n[, create_using]) Return the Margulis-Gabber-Galil undirected MultiGraph on n^2 nodes.
chordal_cycle_graph(p[, create_using]) Return the chordal cycle graph on p nodes.
Lattice

Functions for generating grid graphs and lattices

The grid_2d_graph(), triangular_lattice_graph(), and hexagonal_lattice_graph() functions correspond to the three regular tilings of the plane, the square, triangular, and hexagonal tilings, respectively. grid_graph() and hypercube_graph() are similar for arbitrary dimensions. Useful relevent discussion can be found about Triangular Tiling, and Square, Hex and Triangle Grids

grid_2d_graph(m, n[, periodic, create_using]) Returns the two-dimensional grid graph.
grid_graph(dim[, periodic]) Returns the n-dimensional grid graph.
hexagonal_lattice_graph(m, n[, periodic, …]) Returns an m by n hexagonal lattice graph.
hypercube_graph(n) Returns the n-dimensional hypercube graph.
triangular_lattice_graph(m, n[, periodic, …]) Returns the m by n triangular lattice graph.
Small

Various small and named graphs, together with some compact generators.

make_small_graph(graph_description[, …]) Return the small graph described by graph_description.
LCF_graph(n, shift_list, repeats[, create_using]) Return the cubic graph specified in LCF notation.
bull_graph([create_using]) Return the Bull graph.
chvatal_graph([create_using]) Return the Chvátal graph.
cubical_graph([create_using]) Return the 3-regular Platonic Cubical graph.
desargues_graph([create_using]) Return the Desargues graph.
diamond_graph([create_using]) Return the Diamond graph.
dodecahedral_graph([create_using]) Return the Platonic Dodecahedral graph.
frucht_graph([create_using]) Return the Frucht Graph.
heawood_graph([create_using]) Return the Heawood graph, a (3,6) cage.
house_graph([create_using]) Return the House graph (square with triangle on top).
house_x_graph([create_using]) Return the House graph with a cross inside the house square.
icosahedral_graph([create_using]) Return the Platonic Icosahedral graph.
krackhardt_kite_graph([create_using]) Return the Krackhardt Kite Social Network.
moebius_kantor_graph([create_using]) Return the Moebius-Kantor graph.
octahedral_graph([create_using]) Return the Platonic Octahedral graph.
pappus_graph() Return the Pappus graph.
petersen_graph([create_using]) Return the Petersen graph.
sedgewick_maze_graph([create_using]) Return a small maze with a cycle.
tetrahedral_graph([create_using]) Return the 3-regular Platonic Tetrahedral graph.
truncated_cube_graph([create_using]) Return the skeleton of the truncated cube.
truncated_tetrahedron_graph([create_using]) Return the skeleton of the truncated Platonic tetrahedron.
tutte_graph([create_using]) Return the Tutte graph.
Random Graphs

Generators for random graphs.

fast_gnp_random_graph(n, p[, seed, directed]) Returns a G_{n,p} random graph, also known as an Erdős-Rényi graph or a binomial graph.
gnp_random_graph(n, p[, seed, directed]) Returns a G_{n,p} random graph, also known as an Erdős-Rényi graph or a binomial graph.
dense_gnm_random_graph(n, m[, seed]) Returns a G_{n,m} random graph.
gnm_random_graph(n, m[, seed, directed]) Returns a G_{n,m} random graph.
erdos_renyi_graph(n, p[, seed, directed]) Returns a G_{n,p} random graph, also known as an Erdős-Rényi graph or a binomial graph.
binomial_graph(n, p[, seed, directed]) Returns a G_{n,p} random graph, also known as an Erdős-Rényi graph or a binomial graph.
newman_watts_strogatz_graph(n, k, p[, seed]) Return a Newman–Watts–Strogatz small-world graph.
watts_strogatz_graph(n, k, p[, seed]) Return a Watts–Strogatz small-world graph.
connected_watts_strogatz_graph(n, k, p[, …]) Returns a connected Watts–Strogatz small-world graph.
random_regular_graph(d, n[, seed]) Returns a random d-regular graph on n nodes.
barabasi_albert_graph(n, m[, seed]) Returns a random graph according to the Barabási–Albert preferential attachment model.
powerlaw_cluster_graph(n, m, p[, seed]) Holme and Kim algorithm for growing graphs with powerlaw degree distribution and approximate average clustering.
random_kernel_graph(n, kernel_integral[, …]) Return an random graph based on the specified kernel.
random_lobster(n, p1, p2[, seed]) Returns a random lobster graph.
random_shell_graph(constructor[, seed]) Returns a random shell graph for the constructor given.
random_powerlaw_tree(n[, gamma, seed, tries]) Returns a tree with a power law degree distribution.
random_powerlaw_tree_sequence(n[, gamma, …]) Returns a degree sequence for a tree with a power law distribution.
Duplication Divergence

Functions for generating graphs based on the “duplication” method.

These graph generators start with a small initial graph then duplicate nodes and (partially) duplicate their edges. These functions are generally inspired by biological networks.

duplication_divergence_graph(n, p[, seed]) Returns an undirected graph using the duplication-divergence model.
partial_duplication_graph(N, n, p, q[, seed]) Return a random graph using the partial duplication model.
Degree Sequence

Generate graphs with a given degree sequence or expected degree sequence.

configuration_model(deg_sequence[, …]) Return a random graph with the given degree sequence.
directed_configuration_model(…[, …]) Return a directed_random graph with the given degree sequences.
expected_degree_graph(w[, seed, selfloops]) Return a random graph with given expected degrees.
havel_hakimi_graph(deg_sequence[, create_using]) Return a simple graph with given degree sequence constructed using the Havel-Hakimi algorithm.
directed_havel_hakimi_graph(in_deg_sequence, …) Return a directed graph with the given degree sequences.
degree_sequence_tree(deg_sequence[, …]) Make a tree for the given degree sequence.
random_degree_sequence_graph(sequence[, …]) Return a simple random graph with the given degree sequence.
Random Clustered

Generate graphs with given degree and triangle sequence.

random_clustered_graph(joint_degree_sequence) Generate a random graph with the given joint independent edge degree and triangle degree sequence.
Directed

Generators for some directed graphs, including growing network (GN) graphs and scale-free graphs.

gn_graph(n[, kernel, create_using, seed]) Return the growing network (GN) digraph with n nodes.
gnr_graph(n, p[, create_using, seed]) Return the growing network with redirection (GNR) digraph with n nodes and redirection probability p.
gnc_graph(n[, create_using, seed]) Return the growing network with copying (GNC) digraph with n nodes.
random_k_out_graph(n, k, alpha[, …]) Returns a random k-out graph with preferential attachment.
scale_free_graph(n[, alpha, beta, gamma, …]) Returns a scale-free directed graph.
Geometric

Generators for geometric graphs.

random_geometric_graph(n, radius[, dim, pos, p]) Returns a random geometric graph in the unit cube.
geographical_threshold_graph(n, theta[, …]) Returns a geographical threshold graph.
waxman_graph(n[, beta, alpha, L, domain, metric]) Return a Waxman random graph.
navigable_small_world_graph(n[, p, q, r, …]) Return a navigable small-world graph.
Line Graph

Functions for generating line graphs.

line_graph(G[, create_using]) Returns the line graph of the graph or digraph G.
Ego Graph

Ego graph.

ego_graph(G, n[, radius, center, …]) Returns induced subgraph of neighbors centered at node n within a given radius.
Stochastic

Functions for generating stochastic graphs from a given weighted directed graph.

stochastic_graph(G[, copy, weight]) Returns a right-stochastic representation of directed graph G.
Intersection

Generators for random intersection graphs.

uniform_random_intersection_graph(n, m, p[, …]) Return a uniform random intersection graph.
k_random_intersection_graph(n, m, k) Return a intersection graph with randomly chosen attribute sets for each node that are of equal size (k).
general_random_intersection_graph(n, m, p) Return a random intersection graph with independent probabilities for connections between node and attribute sets.
Social Networks

Famous social networks.

karate_club_graph() Return Zachary’s Karate Club graph.
davis_southern_women_graph() Return Davis Southern women social network.
florentine_families_graph() Return Florentine families graph.
Community

Generators for classes of graphs used in studying social networks.

caveman_graph(l, k) Returns a caveman graph of l cliques of size k.
connected_caveman_graph(l, k) Returns a connected caveman graph of l cliques of size k.
relaxed_caveman_graph(l, k, p[, seed]) Return a relaxed caveman graph.
random_partition_graph(sizes, p_in, p_out[, …]) Return the random partition graph with a partition of sizes.
planted_partition_graph(l, k, p_in, p_out[, …]) Return the planted l-partition graph.
gaussian_random_partition_graph(n, s, v, …) Generate a Gaussian random partition graph.
ring_of_cliques(num_cliques, clique_size) Defines a “ring of cliques” graph.
windmill_graph(n, k) Generate a windmill graph.
Trees

Functions for generating trees.

random_tree(n[, seed]) Returns a uniformly random tree on n nodes.
Non Isomorphic Trees

Implementation of the Wright, Richmond, Odlyzko and McKay (WROM) algorithm for the enumeration of all non-isomorphic free trees of a given order. Rooted trees are represented by level sequences, i.e., lists in which the i-th element specifies the distance of vertex i to the root.

nonisomorphic_trees(order[, create]) Returns a list of nonisomporphic trees
number_of_nonisomorphic_trees(order) Returns the number of nonisomorphic trees
Triads

Functions that generate the triad graphs, that is, the possible digraphs on three nodes.

triad_graph(triad_name) Returns the triad graph with the given name.
Joint Degree Sequence

Generate graphs with a given joint degree

is_valid_joint_degree(joint_degrees) Checks whether the given joint degree dictionary is realizable as a simple graph.
joint_degree_graph(joint_degrees[, seed]) Generates a random simple graph with the given joint degree dictionary.

Linear algebra

Graph Matrix

Adjacency matrix and incidence matrix of graphs.

adjacency_matrix(G[, nodelist, weight]) Return adjacency matrix of G.
incidence_matrix(G[, nodelist, edgelist, …]) Return incidence matrix of G.
Laplacian Matrix

Laplacian matrix of graphs.

laplacian_matrix(G[, nodelist, weight]) Return the Laplacian matrix of G.
normalized_laplacian_matrix(G[, nodelist, …]) Return the normalized Laplacian matrix of G.
directed_laplacian_matrix(G[, nodelist, …]) Return the directed Laplacian matrix of G.
Spectrum

Eigenvalue spectrum of graphs.

laplacian_spectrum(G[, weight]) Return eigenvalues of the Laplacian of G
adjacency_spectrum(G[, weight]) Return eigenvalues of the adjacency matrix of G.
Algebraic Connectivity

Algebraic connectivity and Fiedler vectors of undirected graphs.

algebraic_connectivity(G[, weight, …]) Return the algebraic connectivity of an undirected graph.
fiedler_vector(G[, weight, normalized, tol, …]) Return the Fiedler vector of a connected undirected graph.
spectral_ordering(G[, weight, normalized, …]) Compute the spectral_ordering of a graph.
Attribute Matrices

Functions for constructing matrix-like objects from graph attributes.

attr_matrix(G[, edge_attr, node_attr, …]) Returns a NumPy matrix using attributes from G.
attr_sparse_matrix(G[, edge_attr, …]) Returns a SciPy sparse matrix using attributes from G.

Converting to and from other data formats

To NetworkX Graph

Functions to convert NetworkX graphs to and from other formats.

The preferred way of converting data to a NetworkX graph is through the graph constuctor. The constructor calls the to_networkx_graph() function which attempts to guess the input type and convert it automatically.

Examples

Create a graph with a single edge from a dictionary of dictionaries

>>> d={0: {1: 1}} # dict-of-dicts single edge (0,1)
>>> G=nx.Graph(d)

See also

nx_agraph, nx_pydot

to_networkx_graph(data[, create_using, …]) Make a NetworkX graph from a known data structure.
Dictionaries
to_dict_of_dicts(G[, nodelist, edge_data]) Return adjacency representation of graph as a dictionary of dictionaries.
from_dict_of_dicts(d[, create_using, …]) Return a graph from a dictionary of dictionaries.
Lists
to_dict_of_lists(G[, nodelist]) Return adjacency representation of graph as a dictionary of lists.
from_dict_of_lists(d[, create_using]) Return a graph from a dictionary of lists.
to_edgelist(G[, nodelist]) Return a list of edges in the graph.
from_edgelist(edgelist[, create_using]) Return a graph from a list of edges.
Numpy

Functions to convert NetworkX graphs to and from numpy/scipy matrices.

The preferred way of converting data to a NetworkX graph is through the graph constuctor. The constructor calls the to_networkx_graph() function which attempts to guess the input type and convert it automatically.

Examples

Create a 10 node random graph from a numpy matrix

>>> import numpy
>>> a = numpy.reshape(numpy.random.random_integers(0,1,size=100),(10,10))
>>> D = nx.DiGraph(a)

or equivalently

>>> D = nx.to_networkx_graph(a,create_using=nx.DiGraph())

See also

nx_agraph, nx_pydot

to_numpy_matrix(G[, nodelist, dtype, order, …]) Return the graph adjacency matrix as a NumPy matrix.
to_numpy_recarray(G[, nodelist, dtype, order]) Return the graph adjacency matrix as a NumPy recarray.
from_numpy_matrix(A[, parallel_edges, …]) Return a graph from numpy matrix.
Scipy
to_scipy_sparse_matrix(G[, nodelist, dtype, …]) Return the graph adjacency matrix as a SciPy sparse matrix.
from_scipy_sparse_matrix(A[, …]) Creates a new graph from an adjacency matrix given as a SciPy sparse matrix.
Pandas
to_pandas_dataframe(G[, nodelist, dtype, …]) Return the graph adjacency matrix as a Pandas DataFrame.
from_pandas_dataframe(df[, source, target, …]) Return a graph from Pandas DataFrame containing an edge list.

Relabeling nodes

Relabeling
convert_node_labels_to_integers(G[, …]) Return a copy of the graph G with the nodes relabeled using consecutive integers.
relabel_nodes(G, mapping[, copy]) Relabel the nodes of the graph G.

Reading and writing graphs

Adjacency List
Adjacency List

Read and write NetworkX graphs as adjacency lists.

Adjacency list format is useful for graphs without data associated with nodes or edges and for nodes that can be meaningfully represented as strings.

Format

The adjacency list format consists of lines with node labels. The first label in a line is the source node. Further labels in the line are considered target nodes and are added to the graph along with an edge between the source node and target node.

The graph with edges a-b, a-c, d-e can be represented as the following adjacency list (anything following the # in a line is a comment):

a b c # source target target
d e
read_adjlist(path[, comments, delimiter, …]) Read graph in adjacency list format from path.
write_adjlist(G, path[, comments, …]) Write graph G in single-line adjacency-list format to path.
parse_adjlist(lines[, comments, delimiter, …]) Parse lines of a graph adjacency list representation.
generate_adjlist(G[, delimiter]) Generate a single line of the graph G in adjacency list format.
Multiline Adjacency List
Multi-line Adjacency List

Read and write NetworkX graphs as multi-line adjacency lists.

The multi-line adjacency list format is useful for graphs with nodes that can be meaningfully represented as strings. With this format simple edge data can be stored but node or graph data is not.

Format

The first label in a line is the source node label followed by the node degree d. The next d lines are target node labels and optional edge data. That pattern repeats for all nodes in the graph.

The graph with edges a-b, a-c, d-e can be represented as the following adjacency list (anything following the # in a line is a comment):

# example.multiline-adjlist
a 2
b
c
d 1
e
read_multiline_adjlist(path[, comments, …]) Read graph in multi-line adjacency list format from path.
write_multiline_adjlist(G, path[, …]) Write the graph G in multiline adjacency list format to path
parse_multiline_adjlist(lines[, comments, …]) Parse lines of a multiline adjacency list representation of a graph.
generate_multiline_adjlist(G[, delimiter]) Generate a single line of the graph G in multiline adjacency list format.
Edge List
Edge Lists

Read and write NetworkX graphs as edge lists.

The multi-line adjacency list format is useful for graphs with nodes that can be meaningfully represented as strings. With the edgelist format simple edge data can be stored but node or graph data is not. There is no way of representing isolated nodes unless the node has a self-loop edge.

Format

You can read or write three formats of edge lists with these functions.

Node pairs with no data:

1 2

Python dictionary as data:

1 2 {'weight':7, 'color':'green'}

Arbitrary data:

1 2 7 green
read_edgelist(path[, comments, delimiter, …]) Read a graph from a list of edges.
write_edgelist(G, path[, comments, …]) Write graph as a list of edges.
read_weighted_edgelist(path[, comments, …]) Read a graph as list of edges with numeric weights.
write_weighted_edgelist(G, path[, comments, …]) Write graph G as a list of edges with numeric weights.
generate_edgelist(G[, delimiter, data]) Generate a single line of the graph G in edge list format.
parse_edgelist(lines[, comments, delimiter, …]) Parse lines of an edge list representation of a graph.
GEXF

Read and write graphs in GEXF format.

GEXF (Graph Exchange XML Format) is a language for describing complex network structures, their associated data and dynamics.

This implementation does not support mixed graphs (directed and undirected edges together).

Format

GEXF is an XML format. See http://gephi.org/gexf/format/schema.html for the specification and http://gephi.org/gexf/format/basic.html for examples.

read_gexf(path[, node_type, relabel, version]) Read graph in GEXF format from path.
write_gexf(G, path[, encoding, prettyprint, …]) Write G in GEXF format to path.
relabel_gexf_graph(G) Relabel graph using “label” node keyword for node label.
GML

Read graphs in GML format.

“GML, the G>raph Modelling Language, is our proposal for a portable file format for graphs. GML’s key features are portability, simple syntax, extensibility and flexibility. A GML file consists of a hierarchical key-value lists. Graphs can be annotated with arbitrary data structures. The idea for a common file format was born at the GD‘95; this proposal is the outcome of many discussions. GML is the standard file format in the Graphlet graph editor system. It has been overtaken and adapted by several other systems for drawing graphs.”

GML files are stored using a 7-bit ASCII encoding with any extended ASCII characters (iso8859-1) appearing as HTML character entities. You will need to give some thought into how the exported data should interact with different languages and even different Python versions. Re-importing from gml is also a concern.

Without specifying a stringizer/destringizer, the code is capable of handling int/float/str/dict/list data as required by the GML specification. For other data types, you need to explicitly supply a stringizer/destringizer.

For better interoperability of data generated by Python 2 and Python 3, we’ve provided literal_stringizer and literal_destringizer.

For additional documentation on the GML file format, please see the GML website.

Several example graphs in GML format may be found on Mark Newman’s Network data page.

read_gml(path[, label, destringizer]) Read graph in GML format from path.
write_gml(G, path[, stringizer]) Write a graph G in GML format to the file or file handle path.
parse_gml(lines[, label, destringizer]) Parse GML graph from a string or iterable.
generate_gml(G[, stringizer]) Generate a single entry of the graph G in GML format.
literal_destringizer(rep) Convert a Python literal to the value it represents.
literal_stringizer(value) Convert a value to a Python literal in GML representation.
Pickle
Pickled Graphs

Read and write NetworkX graphs as Python pickles.

“The pickle module implements a fundamental, but powerful algorithm for serializing and de-serializing a Python object structure. “Pickling” is the process whereby a Python object hierarchy is converted into a byte stream, and “unpickling” is the inverse operation, whereby a byte stream is converted back into an object hierarchy.”

Note that NetworkX graphs can contain any hashable Python object as node (not just integers and strings). For arbitrary data types it may be difficult to represent the data as text. In that case using Python pickles to store the graph data can be used.

read_gpickle(path) Read graph object in Python pickle format.
write_gpickle(G, path[, protocol]) Write graph in Python pickle format.
GraphML
GraphML

Read and write graphs in GraphML format.

This implementation does not support mixed graphs (directed and unidirected edges together), hyperedges, nested graphs, or ports.

“GraphML is a comprehensive and easy-to-use file format for graphs. It consists of a language core to describe the structural properties of a graph and a flexible extension mechanism to add application-specific data. Its main features include support of

  • directed, undirected, and mixed graphs,
  • hypergraphs,
  • hierarchical graphs,
  • graphical representations,
  • references to external data,
  • application-specific attribute data, and
  • light-weight parsers.

Unlike many other file formats for graphs, GraphML does not use a custom syntax. Instead, it is based on XML and hence ideally suited as a common denominator for all kinds of services generating, archiving, or processing graphs.”

http://graphml.graphdrawing.org/

Format

GraphML is an XML format. See http://graphml.graphdrawing.org/specification.html for the specification and http://graphml.graphdrawing.org/primer/graphml-primer.html for examples.

read_graphml(path[, node_type]) Read graph in GraphML format from path.
write_graphml(G, path[, encoding, …]) Write G in GraphML XML format to path
JSON
JSON data

Generate and parse JSON serializable data for NetworkX graphs.

These formats are suitable for use with the d3.js examples http://d3js.org/

The three formats that you can generate with NetworkX are:

node_link_data(G[, attrs]) Return data in node-link format that is suitable for JSON serialization and use in Javascript documents.
node_link_graph(data[, directed, …]) Return graph from node-link data format.
adjacency_data(G[, attrs]) Return data in adjacency format that is suitable for JSON serialization and use in Javascript documents.
adjacency_graph(data[, directed, …]) Return graph from adjacency data format.
tree_data(G, root[, attrs]) Return data in tree format that is suitable for JSON serialization and use in Javascript documents.
tree_graph(data[, attrs]) Return graph from tree data format.
jit_data(G[, indent]) Return data in JIT JSON format.
jit_graph(data) Read a graph from JIT JSON.
LEDA

Read graphs in LEDA format.

LEDA is a C++ class library for efficient data types and algorithms.

read_leda(path[, encoding]) Read graph in LEDA format from path.
parse_leda(lines) Read graph in LEDA format from string or iterable.
YAML
YAML

Read and write NetworkX graphs in YAML format.

“YAML is a data serialization format designed for human readability and interaction with scripting languages.” See http://www.yaml.org for documentation.

read_yaml(path) Read graph in YAML format from path.
write_yaml(G, path[, encoding]) Write graph G in YAML format to path.
SparseGraph6

Functions for reading and writing graphs in the graph6 or sparse6 file formats.

According to the author of these formats,

graph6 and sparse6 are formats for storing undirected graphs in a compact manner, using only printable ASCII characters. Files in these formats have text type and contain one line per graph.

graph6 is suitable for small graphs, or large dense graphs. sparse6 is more space-efficient for large sparse graphs.

graph6 and sparse6 homepage

Graph6

Functions for reading and writing graphs in the graph6 format.

The graph6 file format is suitable for small graphs or large dense graphs. For large sparse graphs, use the sparse6 format.

For more information, see the graph6 homepage.

parse_graph6(string) Read a simple undirected graph in graph6 format from string.
read_graph6(path) Read simple undirected graphs in graph6 format from path.
generate_graph6(G[, nodes, header]) Generate graph6 format string from a simple undirected graph.
write_graph6(G, path[, nodes, header]) Write a simple undirected graph to path in graph6 format.
Sparse6

Functions for reading and writing graphs in the sparse6 format.

The sparse6 file format is a space-efficient format for large sparse graphs. For small graphs or large dense graphs, use the graph6 file format.

For more information, see the sparse6 homepage.

parse_sparse6(string) Read an undirected graph in sparse6 format from string.
read_sparse6(path) Read an undirected graph in sparse6 format from path.
generate_sparse6(G[, nodes, header]) Generate sparse6 format string from an undirected graph.
write_sparse6(G, path[, nodes, header]) Write graph G to given path in sparse6 format.
Pajek
Pajek

Read graphs in Pajek format.

This implementation handles directed and undirected graphs including those with self loops and parallel edges.

read_pajek(path[, encoding]) Read graph in Pajek format from path.
write_pajek(G, path[, encoding]) Write graph in Pajek format to path.
parse_pajek(lines) Parse Pajek format graph from string or iterable.
GIS Shapefile
Shapefile

Generates a networkx.DiGraph from point and line shapefiles.

“The Esri Shapefile or simply a shapefile is a popular geospatial vector data format for geographic information systems software. It is developed and regulated by Esri as a (mostly) open specification for data interoperability among Esri and other software products.” See http://en.wikipedia.org/wiki/Shapefile for additional information.

read_shp(path[, simplify, geom_attrs]) Generates a networkx.DiGraph from shapefiles.
write_shp(G, outdir) Writes a networkx.DiGraph to two shapefiles, edges and nodes.

Drawing

NetworkX provides basic functionality for visualizing graphs, but its main goal is to enable graph analysis rather than perform graph visualization. In the future, graph visualization functionality may be removed from NetworkX or only available as an add-on package.

Proper graph visualization is hard, and we highly recommend that people visualize their graphs with tools dedicated to that task. Notable examples of dedicated and fully-featured graph visualization tools are Cytoscape, Gephi, Graphviz and, for LaTeX typesetting, PGF/TikZ. To use these and other such tools, you should export your NetworkX graph into a format that can be read by those tools. For example, Cytoscape can read the GraphML format, and so, networkx.write_graphml(G) might be an appropriate choice.

Matplotlib
Matplotlib

Draw networks with matplotlib.

See also

matplotlib
http://matplotlib.org/
pygraphviz
http://pygraphviz.github.io/
draw(G[, pos, ax]) Draw the graph G with Matplotlib.
draw_networkx(G[, pos, arrows, with_labels]) Draw the graph G using Matplotlib.
draw_networkx_nodes(G, pos[, nodelist, …]) Draw the nodes of the graph G.
draw_networkx_edges(G, pos[, edgelist, …]) Draw the edges of the graph G.
draw_networkx_labels(G, pos[, labels, …]) Draw node labels on the graph G.
draw_networkx_edge_labels(G, pos[, …]) Draw edge labels.
draw_circular(G, **kwargs) Draw the graph G with a circular layout.
draw_random(G, **kwargs) Draw the graph G with a random layout.
draw_spectral(G, **kwargs) Draw the graph G with a spectral layout.
draw_spring(G, **kwargs) Draw the graph G with a spring layout.
draw_shell(G, **kwargs) Draw networkx graph with shell layout.
Graphviz AGraph (dot)
Graphviz AGraph

Interface to pygraphviz AGraph class.

Examples

>>> G = nx.complete_graph(5)
>>> A = nx.nx_agraph.to_agraph(G)
>>> H = nx.nx_agraph.from_agraph(A)

See also

Pygraphviz
http://pygraphviz.github.io/
from_agraph(A[, create_using]) Return a NetworkX Graph or DiGraph from a PyGraphviz graph.
to_agraph(N) Return a pygraphviz graph from a NetworkX graph N.
write_dot(G, path) Write NetworkX graph G to Graphviz dot format on path.
read_dot(path) Return a NetworkX graph from a dot file on path.
graphviz_layout(G[, prog, root, args]) Create node positions for G using Graphviz.
pygraphviz_layout(G[, prog, root, args]) Create node positions for G using Graphviz.
Graphviz with pydot
Pydot

Import and export NetworkX graphs in Graphviz dot format using pydot.

Either this module or nx_agraph can be used to interface with graphviz.

from_pydot(P) Return a NetworkX graph from a Pydot graph.
to_pydot(N[, strict]) Return a pydot graph from a NetworkX graph N.
write_dot(G, path) Write NetworkX graph G to Graphviz dot format on path.
read_dot(path) Return a NetworkX MultiGraph or MultiDiGraph from the dot file with the passed path.
graphviz_layout(G[, prog, root]) Create node positions using Pydot and Graphviz.
pydot_layout(G[, prog, root]) Create node positions using pydot and Graphviz.
Graph Layout
Layout

Node positioning algorithms for graph drawing.

For random_layout() the possible resulting shape is a square of side [0, scale] (default: [0, 1]) Changing center shifts the layout by that amount.

For the other layout routines, the extent is [center - scale, center + scale] (default: [-1, 1]).

Warning: Most layout routines have only been tested in 2-dimensions.

circular_layout(G[, scale, center, dim]) Position nodes on a circle.
random_layout(G[, center, dim]) Position nodes uniformly at random in the unit square.
rescale_layout(pos[, scale]) Return scaled position array to (-scale, scale) in all axes.
shell_layout(G[, nlist, scale, center, dim]) Position nodes in concentric circles.
spring_layout(G[, k, pos, fixed, …]) Position nodes using Fruchterman-Reingold force-directed algorithm.
spectral_layout(G[, weight, scale, center, dim]) Position nodes using the eigenvectors of the graph Laplacian.

Exceptions

Exceptions

Base exceptions and errors for NetworkX.

class NetworkXException[source]

Base class for exceptions in NetworkX.

class NetworkXError[source]

Exception for a serious error in NetworkX

class NetworkXPointlessConcept[source]

Harary, F. and Read, R. “Is the Null Graph a Pointless Concept?” In Graphs and Combinatorics Conference, George Washington University. New York: Springer-Verlag, 1973.

class NetworkXAlgorithmError[source]

Exception for unexpected termination of algorithms.

class NetworkXUnfeasible[source]

Exception raised by algorithms trying to solve a problem instance that has no feasible solution.

class NetworkXNoPath[source]

Exception for algorithms that should return a path when running on graphs where such a path does not exist.

class NetworkXNoCycle[source]

Exception for algorithms that should return a cycle when running on graphs where such a cycle does not exist.

class NodeNotFound[source]

Exception raised if requested node is not present in the graph

class NetworkXUnbounded[source]

Exception raised by algorithms trying to solve a maximization or a minimization problem instance that is unbounded.

class NetworkXNotImplemented[source]

Exception raised by algorithms not implemented for a type of graph.

class AmbiguousSolution[source]

Raised if more than one valid solution exists for an intermediary step of an algorithm.

In the face of ambiguity, refuse the temptation to guess. This may occur, for example, when trying to determine the bipartite node sets in a disconnected bipartite graph when computing bipartite matchings.

class ExceededMaxIterations[source]

Raised if a loop iterates too many times without breaking.

This may occur, for example, in an algorithm that computes progressively better approximations to a value but exceeds an iteration bound specified by the user.

class PowerIterationFailedConvergence(num_iterations, *args, **kw)[source]

Raised when the power iteration method fails to converge within a specified iteration limit.

num_iterations is the number of iterations that have been completed when this exception was raised.

Utilities

Helper Functions

Miscellaneous Helpers for NetworkX.

These are not imported into the base networkx namespace but can be accessed, for example, as

>>> import networkx
>>> networkx.utils.is_string_like('spam')
True
is_string_like(obj) Check if obj is string.
flatten(obj[, result]) Return flattened version of (possibly nested) iterable object.
iterable(obj) Return True if obj is iterable with a well-defined len().
is_list_of_ints(intlist) Return True if list is a list of ints.
make_str(x) Return the string representation of t.
generate_unique_node() Generate a unique node label.
default_opener(filename) Opens filename using system’s default program.
pairwise(iterable[, cyclic]) s -> (s0, s1), (s1, s2), (s2, s3), …
groups(many_to_one) Converts a many-to-one mapping into a one-to-many mapping.
Data Structures and Algorithms

Union-find data structure.

UnionFind.union(*objects) Find the sets containing the objects and merge them all.
Random Sequence Generators

Utilities for generating random numbers, random sequences, and random selections.

create_degree_sequence(n[, sfunction, max_tries])
pareto_sequence(n[, exponent]) Return sample sequence of length n from a Pareto distribution.
powerlaw_sequence(n[, exponent]) Return sample sequence of length n from a power law distribution.
uniform_sequence(n) Return sample sequence of length n from a uniform distribution.
cumulative_distribution(distribution) Return normalized cumulative distribution from discrete distribution.
discrete_sequence(n[, distribution, …]) Return sample sequence of length n from a given discrete distribution or discrete cumulative distribution.
zipf_sequence(n[, alpha, xmin]) Return a sample sequence of length n from a Zipf distribution with exponent parameter alpha and minimum value xmin.
zipf_rv(alpha[, xmin, seed]) Return a random value chosen from the Zipf distribution.
random_weighted_sample(mapping, k) Return k items without replacement from a weighted sample.
weighted_choice(mapping) Return a single element from a weighted sample.
Decorators
open_file(path_arg[, mode]) Decorator to ensure clean opening and closing of files.
Cuthill-Mckee Ordering

Cuthill-McKee ordering of graph nodes to produce sparse matrices

cuthill_mckee_ordering(G[, heuristic]) Generate an ordering (permutation) of the graph nodes to make a sparse matrix.
reverse_cuthill_mckee_ordering(G[, heuristic]) Generate an ordering (permutation) of the graph nodes to make a sparse matrix.
Context Managers
reversed(*args, **kwds) A context manager for temporarily reversing a directed graph in place.

Glossary

dictionary
A Python dictionary maps keys to values. Also known as “hashes”, or “associative arrays” in other programming languages. See http://docs.python.org/tutorial/datastructures.html#dictionaries
edge
Edges are either two-tuples of nodes (u, v) or three tuples of nodes with an edge attribute dictionary (u, v, dict).
ebunch
An iteratable container of edge tuples like a list, iterator, or file.
edge attribute
Edges can have arbitrary Python objects assigned as attributes by using keyword/value pairs when adding an edge assigning to the G.edge[u][v] attribute dictionary for the specified edge u-v.
hashable

An object is hashable if it has a hash value which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__() or __cmp__() method). Hashable objects which compare equal must have the same hash value.

Hashability makes an object usable as a dictionary key and a set member, because these data structures use the hash value internally.

All of Python’s immutable built-in objects are hashable, while no mutable containers (such as lists or dictionaries) are. Objects which are instances of user-defined classes are hashable by default; they all compare unequal, and their hash value is their id().

Definition from http://docs.python.org/glossary.html

nbunch
An nbunch is any iterable container of nodes that is not itself a node in the graph. It can be an iterable or an iterator, e.g. a list, set, graph, file, etc..
node
A node can be any hashable Python object except None.
node attribute
Nodes can have arbitrary Python objects assigned as attributes by using keyword/value pairs when adding a node or assigning to the G.node[n] attribute dictionary for the specified node n.

Developer Guide

Developer overview

  1. If you are a first-time contributor:

    • Go to https://github.com/networkx/networkx and click the “fork” button to create your own copy of the project.

    • Clone the project to your local computer:

      git clone git@github.com:your-username/networkx.git
      
    • Add the upstream repository:

      git remote add upstream git@github.com:networkx/networkx.git
      
    • Now, you have remote repositories named:

      • upstream, which refers to the networkx repository
      • origin, which refers to your personal fork
  2. Develop your contribution:

    • Pull the latest changes from upstream:

      git checkout master
      git pull upstream master
      
    • Create a branch for the feature you want to work on. Since the branch name will appear in the merge message, use a sensible name such as ‘bugfix-for-issue-1480’:

      git checkout -b bugfix-for-issue-1480
      
    • Commit locally as you progress (git add and git commit)

  3. To submit your contribution:

    • Push your changes back to your fork on GitHub:

      git push origin bugfix-for-issue-1480
      
    • Go to GitHub. The new branch will show up with a green Pull Request button—click it.

    • If you want, post on the mailing list to explain your changes or to ask for review.

For a more detailed discussion, read these detailed documents on how to use Git with networkx (https://networkx.readthedocs.io/en/stable/developer/gitwash/index.html).

  1. Review process:

    • Reviewers (the other developers and interested community members) will write inline and/or general comments on your Pull Request (PR) to help you improve its implementation, documentation, and style. Every single developer working on the project has their code reviewed, and we’ve come to see it as friendly conversation from which we all learn and the overall code quality benefits. Therefore, please don’t let the review discourage you from contributing: its only aim is to improve the quality of project, not to criticize (we are, after all, very grateful for the time you’re donating!).
    • To update your pull request, make your changes on your local repository and commit. As soon as those changes are pushed up (to the same branch as before) the pull request will update automatically.
    • Travis-CI, a continuous integration service, is triggered after each Pull Request update to build the code and run unit tests of your branch. The Travis tests must pass before your PR can be merged. If Travis fails, you can find out why by clicking on the “failed” icon (red cross) and inspecting the build and test log.
    • AppVeyor, is another continuous integration service, which we use. You will also need to make sure that the AppVeyor tests pass.

Note

If closing a bug, also add “Fixes #1480” where 1480 is the issue number.

Divergence between upstream master and your feature branch

Never merge the main branch into yours. If GitHub indicates that the branch of your Pull Request can no longer be merged automatically, rebase onto master:

git checkout master
git pull upstream master
git checkout bugfix-for-issue-1480
git rebase master

If any conflicts occur, fix the according files and continue:

git add conflict-file1 conflict-file2
git rebase --continue

However, you should only rebase your own branches and must generally not rebase any branch which you collaborate on with someone else.

Finally, you must push your rebased branch:

git push --force origin bugfix-for-issue-1480

(If you are curious, here’s a further discussion on the dangers of rebasing. Also see this LWN article.)

Guidelines
  • All code should have tests.
  • All code should be documented, to the same standard as NumPy and SciPy.
  • All changes are reviewed. Ask on the mailing list if you get no response to your pull request.
Stylistic Guidelines
  • Set up your editor to remove trailing whitespace. Follow PEP08. Check code with pyflakes / flake8.

  • Use the following import conventions:

    import numpy as np
    import scipy as sp
    import matplotlib as mpl
    import matplotlib.pyplot as plt
    import networkx as nx
    
    cimport numpy as cnp # in Cython code
    
Pull request codes

When you submit a pull request to GitHub, GitHub will ask you for a summary. If your code is not ready to merge, but you want to get feedback, please consider using WIP: experimental optimization or similar for the title of your pull request. That way we will all know that it’s not yet ready to merge and that you may be interested in more fundamental comments about design.

When you think the pull request is ready to merge, change the title (using the Edit button) to remove the WIP:.

Developer Notes

For additional information about contributing to NetworkX, please see the Developer Notes.

Working with networkx source code

Contents:

Introduction

These pages describe a git and github workflow for the networkx project.

There are several different workflows here, for different ways of working with networkx.

This is not a comprehensive git reference, it’s just a workflow for our own project. It’s tailored to the github hosting service. You may well find better or quicker ways of getting stuff done with git, but these should get you started.

For general resources for learning git, see git resources.

Install git
Overview
Debian / Ubuntu sudo apt-get install git
Fedora sudo dnf install git
Windows Download and install msysGit
OS X Use the git-osx-installer
In detail

See the git page for the most recent information.

Have a look at the github install help pages available from github help

There are good instructions here: https://git-scm.com/book/en/v2/Getting-Started-Installing-Git

Following the latest source

These are the instructions if you just want to follow the latest networkx source, but you don’t need to do any development for now.

The steps are:

Get the local copy of the code

From the command line:

git clone git://github.com/networkx/networkx.git

You now have a copy of the code tree in the new networkx directory.

Updating the code

From time to time you may want to pull down the latest code. Do this with:

cd networkx
git pull

The tree in networkx will now have the latest changes from the initial repository.

Making a patch

You’ve discovered a bug or something else you want to change in networkx .. — excellent!

You’ve worked out a way to fix it — even better!

You want to tell us about it — best of all!

The easiest way is to make a patch or set of patches. Here we explain how. Making a patch is the simplest and quickest, but if you’re going to be doing anything more than simple quick things, please consider following the Git for development model instead.

Making patches
Overview
# tell git who you are
git config --global user.email you@yourdomain.example.com
git config --global user.name "Your Name Comes Here"
# get the repository if you don't have it
git clone git://github.com/networkx/networkx.git
# make a branch for your patching
cd networkx
git branch the-fix-im-thinking-of
git checkout the-fix-im-thinking-of
# hack, hack, hack
# Tell git about any new files you've made
git add somewhere/tests/test_my_bug.py
# commit work in progress as you go
git commit -am 'BF - added tests for Funny bug'
# hack hack, hack
git commit -am 'BF - added fix for Funny bug'
# make the patch files
git format-patch -M -C master

Then, send the generated patch files to the networkx mailing list — where we will thank you warmly.

In detail
  1. Tell git who you are so it can label the commits you’ve made:

    git config --global user.email you@yourdomain.example.com
    git config --global user.name "Your Name Comes Here"
    
  2. If you don’t already have one, clone a copy of the networkx repository:

    git clone git://github.com/networkx/networkx.git
    cd networkx
    
  3. Make a ‘feature branch’. This will be where you work on your bug fix. It’s nice and safe and leaves you with access to an unmodified copy of the code in the main branch:

    git branch the-fix-im-thinking-of
    git checkout the-fix-im-thinking-of
    
  4. Do some edits, and commit them as you go:

    # hack, hack, hack
    # Tell git about any new files you've made
    git add somewhere/tests/test_my_bug.py
    # commit work in progress as you go
    git commit -am 'BF - added tests for Funny bug'
    # hack hack, hack
    git commit -am 'BF - added fix for Funny bug'
    

    Note the -am options to commit. The m flag just signals that you’re going to type a message on the command line. The a flag — you can just take on faith — or see why the -a flag?.

  5. When you have finished, check you have committed all your changes:

    git status
    
  6. Finally, make your commits into patches. You want all the commits since you branched from the master branch:

    git format-patch -M -C master
    

    You will now have several files named for the commits:

    0001-BF-added-tests-for-Funny-bug.patch
    0002-BF-added-fix-for-Funny-bug.patch
    

    Send these files to the networkx mailing list.

When you are done, to switch back to the main copy of the code, just return to the master branch:

git checkout master
Moving from patching to development

If you find you have done some patches, and you have one or more feature branches, you will probably want to switch to development mode. You can do this with the repository you have.

Fork the networkx repository on github — Making your own copy (fork) of networkx. Then:

# checkout and refresh master branch from main repo
git checkout master
git pull origin master
# rename pointer to main repository to 'upstream'
git remote rename origin upstream
# point your repo to default read / write to your fork on github
git remote add origin git@github.com:your-user-name/networkx.git
# push up any branches you've made and want to keep
git push origin the-fix-im-thinking-of

Then you can, if you want, follow the Development workflow.

Git for development

Contents:

Making your own copy (fork) of networkx

You need to do this only once. The instructions here are very similar to the instructions at https://help.github.com/forking/ — please see that page for more detail. We’re repeating some of it here just to give the specifics for the networkx project, and to suggest some default names.

Set up and configure a github account

If you don’t have a github account, go to the github page, and make one.

You then need to configure your account to allow write access — see the Generating SSH keys help on github help.

Create your own forked copy of networkx
  1. Log into your github account.

  2. Go to the networkx github home at networkx github.

  3. Click on the fork button:

    _images/forking_button.png

    Now, after a short pause, you should find yourself at the home page for your own forked copy of networkx.

Set up your fork

First you follow the instructions for Making your own copy (fork) of networkx.

Overview
git clone git@github.com:your-user-name/networkx.git
cd networkx
git remote add upstream git://github.com/networkx/networkx.git
In detail
Clone your fork
  1. Clone your fork to the local computer with git clone git@github.com:your-user-name/networkx.git

  2. Investigate. Change directory to your new repo: cd networkx. Then git branch -a to show you all branches. You’ll get something like:

    * master
    remotes/origin/master
    

    This tells you that you are currently on the master branch, and that you also have a remote connection to origin/master. What remote repository is remote/origin? Try git remote -v to see the URLs for the remote. They will point to your github fork.

    Now you want to connect to the upstream networkx github repository, so you can merge in changes from trunk.

Linking your repository to the upstream repo
cd networkx
git remote add upstream git://github.com/networkx/networkx.git

upstream here is just the arbitrary name we’re using to refer to the main networkx repository at networkx github.

Note that we’ve used git:// for the URL rather than git@. The git:// URL is read only. This means we that we can’t accidentally (or deliberately) write to the upstream repo, and we are only going to use it to merge into our own code.

Just for your own satisfaction, show yourself that you now have a new ‘remote’, with git remote -v show, giving you something like:

upstream     git://github.com/networkx/networkx.git (fetch)
upstream     git://github.com/networkx/networkx.git (push)
origin       git@github.com:your-user-name/networkx.git (fetch)
origin       git@github.com:your-user-name/networkx.git (push)
Configure git
Overview

Your personal git configurations are saved in the .gitconfig file in your home directory.

Here is an example .gitconfig file:

[user]
        name = Your Name
        email = you@yourdomain.example.com

[alias]
        ci = commit -a
        co = checkout
        st = status
        stat = status
        br = branch
        wdiff = diff --color-words

[core]
        editor = vim

[merge]
        summary = true

You can edit this file directly or you can use the git config --global command:

git config --global user.name "Your Name"
git config --global user.email you@yourdomain.example.com
git config --global alias.ci "commit -a"
git config --global alias.co checkout
git config --global alias.st "status -a"
git config --global alias.stat "status -a"
git config --global alias.br branch
git config --global alias.wdiff "diff --color-words"
git config --global core.editor vim
git config --global merge.summary true

To set up on another computer, you can copy your ~/.gitconfig file, or run the commands above.

In detail
user.name and user.email

It is good practice to tell git who you are, for labeling any changes you make to the code. The simplest way to do this is from the command line:

git config --global user.name "Your Name"
git config --global user.email you@yourdomain.example.com

This will write the settings into your git configuration file, which should now contain a user section with your name and email:

[user]
      name = Your Name
      email = you@yourdomain.example.com

Of course you’ll need to replace Your Name and you@yourdomain.example.com with your actual name and email address.

Aliases

You might well benefit from some aliases to common commands.

For example, you might well want to be able to shorten git checkout to git co. Or you may want to alias git diff --color-words (which gives a nicely formatted output of the diff) to git wdiff

The following git config --global commands:

git config --global alias.ci "commit -a"
git config --global alias.co checkout
git config --global alias.st "status -a"
git config --global alias.stat "status -a"
git config --global alias.br branch
git config --global alias.wdiff "diff --color-words"

will create an alias section in your .gitconfig file with contents like this:

[alias]
        ci = commit -a
        co = checkout
        st = status -a
        stat = status -a
        br = branch
        wdiff = diff --color-words
Editor

You may also want to make sure that your editor of choice is used

git config --global core.editor vim
Merging

To enforce summaries when doing merges (~/.gitconfig file again):

[merge]
   log = true

Or from the command line:

git config --global merge.log true
Fancy log output

This is a very nice alias to get a fancy log output; it should go in the alias section of your .gitconfig file:

lg = log --graph --pretty=format:'%Cred%h%Creset -%C(yellow)%d%Creset %s %Cgreen(%cr) %C(bold blue)[%an]%Creset' --abbrev-commit --date=relative

You use the alias with:

git lg

and it gives graph / text output something like this (but with color!):

* 6d8e1ee - (HEAD, origin/my-fancy-feature, my-fancy-feature) NF - a fancy file (45 minutes ago) [Matthew Brett]
*   d304a73 - (origin/placeholder, placeholder) Merge pull request #48 from hhuuggoo/master (2 weeks ago) [Jonathan Terhorst]
|\
| * 4aff2a8 - fixed bug 35, and added a test in test_bugfixes (2 weeks ago) [Hugo]
|/
* a7ff2e5 - Added notes on discussion/proposal made during Data Array Summit. (2 weeks ago) [Corran Webster]
* 68f6752 - Initial implimentation of AxisIndexer - uses 'index_by' which needs to be changed to a call on an Axes object - this is all very sketchy right now. (2 weeks ago) [Corr
*   376adbd - Merge pull request #46 from terhorst/master (2 weeks ago) [Jonathan Terhorst]
|\
| * b605216 - updated joshu example to current api (3 weeks ago) [Jonathan Terhorst]
| * 2e991e8 - add testing for outer ufunc (3 weeks ago) [Jonathan Terhorst]
| * 7beda5a - prevent axis from throwing an exception if testing equality with non-axis object (3 weeks ago) [Jonathan Terhorst]
| * 65af65e - convert unit testing code to assertions (3 weeks ago) [Jonathan Terhorst]
| *   956fbab - Merge remote-tracking branch 'upstream/master' (3 weeks ago) [Jonathan Terhorst]
| |\
| |/

Thanks to Yury V. Zaytsev for posting it.

Development workflow

You already have your own forked copy of the networkx repository, by following Making your own copy (fork) of networkx. You have Set up your fork. You have configured git by following Configure git. Now you are ready for some real work.

Workflow summary

In what follows we’ll refer to the upstream networkx master branch, as “trunk”.

  • Don’t use your master branch for anything. Consider deleting it.
  • When you are starting a new set of changes, fetch any changes from trunk, and start a new feature branch from that.
  • Make a new branch for each separable set of changes — “one task, one branch” (ipython git workflow).
  • Name your branch for the purpose of the changes - e.g. bugfix-for-issue-14 or refactor-database-code.
  • If you can possibly avoid it, avoid merging trunk or any other branches into your feature branch while you are working.
  • If you do find yourself merging from trunk, consider Rebasing on trunk
  • Ask on the networkx mailing list if you get stuck.
  • Check that your code meets the requirements as outlined in our wiki.
  • Ask for code review!

This way of working helps to keep work well organized, with readable history. This in turn makes it easier for project maintainers (that might be you) to see what you’ve done, and why you did it.

See linux git workflow and ipython git workflow for some explanation.

Consider deleting your master branch

It may sound strange, but deleting your own master branch can help reduce confusion about which branch you are on. See deleting master on github for details.

Update the mirror of trunk

First make sure you have done Linking your repository to the upstream repo.

From time to time you should fetch the upstream (trunk) changes from github:

git fetch upstream

This will pull down any commits you don’t have, and set the remote branches to point to the right commit. For example, ‘trunk’ is the branch referred to by (remote/branchname) upstream/master - and if there have been commits since you last checked, upstream/master will change after you do the fetch.

Make a new feature branch

When you are ready to make some changes to the code, you should start a new branch. Branches that are for a collection of related edits are often called ‘feature branches’.

Making an new branch for each set of related changes will make it easier for someone reviewing your branch to see what you are doing.

Choose an informative name for the branch to remind yourself and the rest of us what the changes in the branch are for. For example add-ability-to-fly, or buxfix-for-issue-42.

# Update the mirror of trunk
git fetch upstream
# Make new feature branch starting at current trunk
git branch my-new-feature upstream/master
git checkout my-new-feature

Generally, you will want to keep your feature branches on your public github fork of networkx. To do this, you git push this new branch up to your github repo. Generally (if you followed the instructions in these pages, and by default), git will have a link to your github repo, called origin. You push up to your own repo on github with:

git push origin my-new-feature

In git >= 1.7 you can ensure that the link is correctly set by using the --set-upstream option:

git push --set-upstream origin my-new-feature

From now on git will know that my-new-feature is related to the my-new-feature branch in the github repo.

The editing workflow
Overview
# hack hack
git add my_new_file
git commit -am 'NF - some message'
git push
In more detail
  1. Make some changes

  2. See which files have changed with git status (see git status). You’ll see a listing like this one:

    # On branch ny-new-feature
    # Changed but not updated:
    #   (use "git add <file>..." to update what will be committed)
    #   (use "git checkout -- <file>..." to discard changes in working directory)
    #
    #  modified:   README
    #
    # Untracked files:
    #   (use "git add <file>..." to include in what will be committed)
    #
    #  INSTALL
    no changes added to commit (use "git add" and/or "git commit -a")
    
  3. Check what the actual changes are with git diff (git diff).

  4. Add any new files to version control git add new_file_name (see git add).

  5. To commit all modified files into the local copy of your repo,, do git commit -am 'A commit message'. Note the -am options to commit. The m flag just signals that you’re going to type a message on the command line. The a flag — you can just take on faith — or see why the -a flag? — and the helpful use-case description in the tangled working copy problem. The git commit manual page might also be useful.

  6. To push the changes up to your forked repo on github, do a git push (see git push).

Ask for your changes to be reviewed or merged

When you are ready to ask for someone to review your code and consider a merge:

  1. Go to the URL of your forked repo, say https://github.com/your-user-name/networkx.

  2. Use the ‘Switch Branches’ dropdown menu near the top left of the page to select the branch with your changes:

    _images/branch_dropdown.png
  3. Click on the ‘Pull request’ button:

    _images/pull_button.png

    Enter a title for the set of changes, and some explanation of what you’ve done. Say if there is anything you’d like particular attention for - like a complicated change or some code you are not happy with.

    If you don’t think your request is ready to be merged, just say so in your pull request message. This is still a good way of getting some preliminary code review.

Some other things you might want to do
Delete a branch on github
git checkout master
# delete branch locally
git branch -D my-unwanted-branch
# delete branch on github
git push origin :my-unwanted-branch

Note the colon : before my-unwanted-branch. See also: https://help.github.com/articles/pushing-to-a-remote/#deleting-a-remote-branch-or-tag

Several people sharing a single repository

If you want to work on some stuff with other people, where you are all committing into the same repository, or even the same branch, then just share it via github.

First fork networkx into your account, as from Making your own copy (fork) of networkx.

Then, go to your forked repository github page, say https://github.com/your-user-name/networkx

Click on the ‘Admin’ button, and add anyone else to the repo as a collaborator:

_images/pull_button.png

Now all those people can do:

git clone git@githhub.com:your-user-name/networkx.git

Remember that links starting with git@ use the ssh protocol and are read-write; links starting with git:// are read-only.

Your collaborators can then commit directly into that repo with the usual:

git commit -am 'ENH - much better code'
git push origin master # pushes directly into your repo
Explore your repository

To see a graphical representation of the repository branches and commits:

gitk --all

To see a linear list of commits for this branch:

git log

You can also look at the network graph visualizer for your github repo.

Finally the Fancy log output lg alias will give you a reasonable text-based graph of the repository.

Rebasing on trunk

Let’s say you thought of some work you’d like to do. You Update the mirror of trunk and Make a new feature branch called cool-feature. At this stage trunk is at some commit, let’s call it E. Now you make some new commits on your cool-feature branch, let’s call them A, B, C. Maybe your changes take a while, or you come back to them after a while. In the meantime, trunk has progressed from commit E to commit (say) G:

      A---B---C cool-feature
     /
D---E---F---G trunk

At this stage you consider merging trunk into your feature branch, and you remember that this here page sternly advises you not to do that, because the history will get messy. Most of the time you can just ask for a review, and not worry that trunk has got a little ahead. But sometimes, the changes in trunk might affect your changes, and you need to harmonize them. In this situation you may prefer to do a rebase.

rebase takes your changes (A, B, C) and replays them as if they had been made to the current state of trunk. In other words, in this case, it takes the changes represented by A, B, C and replays them on top of G. After the rebase, your history will look like this:

              A'--B'--C' cool-feature
             /
D---E---F---G trunk

See rebase without tears for more detail.

To do a rebase on trunk:

# Update the mirror of trunk
git fetch upstream
# go to the feature branch
git checkout cool-feature
# make a backup in case you mess up
git branch tmp cool-feature
# rebase cool-feature onto trunk
git rebase --onto upstream/master upstream/master cool-feature

In this situation, where you are already on branch cool-feature, the last command can be written more succinctly as:

git rebase upstream/master

When all looks good you can delete your backup branch:

git branch -D tmp

If it doesn’t look good you may need to have a look at Recovering from mess-ups.

If you have made changes to files that have also changed in trunk, this may generate merge conflicts that you need to resolve - see the git rebase man page for some instructions at the end of the “Description” section. There is some related help on merging in the git user manual - see resolving a merge.

Recovering from mess-ups

Sometimes, you mess up merges or rebases. Luckily, in git it is relatively straightforward to recover from such mistakes.

If you mess up during a rebase:

git rebase --abort

If you notice you messed up after the rebase:

# reset branch back to the saved point
git reset --hard tmp

If you forgot to make a backup branch:

# look at the reflog of the branch
git reflog show cool-feature

8630830 cool-feature@{0}: commit: BUG: io: close file handles immediately
278dd2a cool-feature@{1}: rebase finished: refs/heads/my-feature-branch onto 11ee694744f2552d
26aa21a cool-feature@{2}: commit: BUG: lib: make seek_gzip_factory not leak gzip obj
...

# reset the branch to where it was before the botched rebase
git reset --hard cool-feature@{2}
Rewriting commit history

Note

Do this only for your own feature branches.

There’s an embarrassing typo in a commit you made? Or perhaps the you made several false starts you would like the posterity not to see.

This can be done via interactive rebasing.

Suppose that the commit history looks like this:

git log --oneline
eadc391 Fix some remaining bugs
a815645 Modify it so that it works
2dec1ac Fix a few bugs + disable
13d7934 First implementation
6ad92e5 * masked is now an instance of a new object, MaskedConstant
29001ed Add pre-nep for a copule of structured_array_extensions.
...

and 6ad92e5 is the last commit in the cool-feature branch. Suppose we want to make the following changes:

  • Rewrite the commit message for 13d7934 to something more sensible.
  • Combine the commits 2dec1ac, a815645, eadc391 into a single one.

We do as follows:

# make a backup of the current state
git branch tmp HEAD
# interactive rebase
git rebase -i 6ad92e5

This will open an editor with the following text in it:

pick 13d7934 First implementation
pick 2dec1ac Fix a few bugs + disable
pick a815645 Modify it so that it works
pick eadc391 Fix some remaining bugs

# Rebase 6ad92e5..eadc391 onto 6ad92e5
#
# Commands:
#  p, pick = use commit
#  r, reword = use commit, but edit the commit message
#  e, edit = use commit, but stop for amending
#  s, squash = use commit, but meld into previous commit
#  f, fixup = like "squash", but discard this commit's log message
#
# If you remove a line here THAT COMMIT WILL BE LOST.
# However, if you remove everything, the rebase will be aborted.
#

To achieve what we want, we will make the following changes to it:

r 13d7934 First implementation
pick 2dec1ac Fix a few bugs + disable
f a815645 Modify it so that it works
f eadc391 Fix some remaining bugs

This means that (i) we want to edit the commit message for 13d7934, and (ii) collapse the last three commits into one. Now we save and quit the editor.

Git will then immediately bring up an editor for editing the commit message. After revising it, we get the output:

[detached HEAD 721fc64] FOO: First implementation
 2 files changed, 199 insertions(+), 66 deletions(-)
[detached HEAD 0f22701] Fix a few bugs + disable
 1 files changed, 79 insertions(+), 61 deletions(-)
Successfully rebased and updated refs/heads/my-feature-branch.

and the history looks now like this:

0f22701 Fix a few bugs + disable
721fc64 ENH: Sophisticated feature
6ad92e5 * masked is now an instance of a new object, MaskedConstant

If it went wrong, recovery is again possible as explained above.

Maintainer workflow

This page is for maintainers — those of us who merge our own or other peoples’ changes into the upstream repository.

Being as how you’re a maintainer, you are completely on top of the basic stuff in Development workflow.

The instructions in Linking your repository to the upstream repo add a remote that has read-only access to the upstream repo. Being a maintainer, you’ve got read-write access.

It’s good to have your upstream remote have a scary name, to remind you that it’s a read-write remote:

git remote add upstream-rw git@github.com:networkx/networkx.git
git fetch upstream-rw
Integrating changes

Let’s say you have some changes that need to go into trunk (upstream-rw/master).

The changes are in some branch that you are currently on. For example, you are looking at someone’s changes like this:

git remote add someone git://github.com/someone/networkx.git
git fetch someone
git branch cool-feature --track someone/cool-feature
git checkout cool-feature

So now you are on the branch with the changes to be incorporated upstream. The rest of this section assumes you are on this branch.

A few commits

If there are only a few commits, consider rebasing to upstream:

# Fetch upstream changes
git fetch upstream-rw
# rebase
git rebase upstream-rw/master

Remember that, if you do a rebase, and push that, you’ll have to close any github pull requests manually, because github will not be able to detect the changes have already been merged.

A long series of commits

If there are a longer series of related commits, consider a merge instead:

git fetch upstream-rw
git merge --no-ff upstream-rw/master

The merge will be detected by github, and should close any related pull requests automatically.

Note the --no-ff above. This forces git to make a merge commit, rather than doing a fast-forward, so that these set of commits branch off trunk then rejoin the main history with a merge, rather than appearing to have been made directly on top of trunk.

Check the history

Now, in either case, you should check that the history is sensible and you have the right commits:

git log --oneline --graph
git log -p upstream-rw/master..

The first line above just shows the history in a compact way, with a text representation of the history graph. The second line shows the log of commits excluding those that can be reached from trunk (upstream-rw/master), and including those that can be reached from current HEAD (implied with the .. at the end). So, it shows the commits unique to this branch compared to trunk. The -p option shows the diff for these commits in patch form.

Push to trunk
git push upstream-rw my-new-feature:master

This pushes the my-new-feature branch in this repository to the master branch in the upstream-rw repository.

git resources
Tutorials and summaries
Advanced git workflow

There are many ways of working with git; here are some posts on the rules of thumb that other projects have come up with:

  • Linus Torvalds on git management
  • Linus Torvalds on linux git workflow . Summary; use the git tools to make the history of your edits as clean as possible; merge from upstream edits as little as possible in branches where you are doing active development.
Manual pages online

You can get these on your own machine with (e.g) git help push or (same thing) git push --help, but, for convenience, here are the online manual pages for some common commands:

Release Log

NetworkX 2.0

Release date: TBD

See Migration guide from 1.X to 2.0.

Release notes

See release/release_2.0.

NetworkX 1.11

Release date: 30 January 2016

Support for Python 3.5 added, drop support for Python 3.2.

Highlights

Pydot features now use pydotplus. Fixes installation on some machines and test with appveyor. Restores default center and scale of layout routines. Fixes various docs including no symbolic links in examples. Docs can now build using autosummary on readthedocs.org.

NetworkX 1.10

Release date: 2 August 2015

Support for Python 2.6 is dropped in this release.

Highlights
  • Connected components now return generators
  • new functions including
    • enumerate_all_cliques, greedy_coloring, edge_dfs, find_cycle immediate_dominators, harmonic_centrality
    • Hopcraft–Karp algorithm for maximum matchings
    • optimum branchings and arborescences.
    • all_simple_paths
  • pyparsing dependence removed from GML reader/parser
  • improve flow algorithms
  • new generators releated to expander graphs.
  • new generators for multipartite graphs, nonisomorphic trees, circulant graphs
  • allow graph subclasses to use dict-like objects in place of dicts
  • added ordered graph subclasses
  • pandas dataframe read/write added.
  • data keyword in G.edges() allows requesting edge attribute directly
  • expanded layout flexibility for node subsets
  • Kanesky’s algorithm for cut sets and k_components
  • power function for graphs
  • approximation of node connectivity
  • transitive closure, triadic census and antichains
  • quotient graphs and minors
  • longest_path for DAGS
  • modularity matrix routines

NetworkX 1.9.1

Release date: 13 September 2014

Bugfix release for minor installation and documentation issues.

NetworkX 1.9

Release date: 21 June 2014

Support for Python 3.1 is dropped in this release.

Highlights
  • Completely rewritten maximum flow and flow-based connectivity algorithms with backwards incompatible interfaces
  • Community graph generators
  • Stoer–Wagner minimum cut algorithm
  • Linear-time Eulerian circuit algorithm
  • Linear algebra package changed to use SciPy sparse matrices
  • Algebraic connectivity, Fiedler vector, spectral ordering algorithms
  • Link prediction algorithms
  • Goldberg–Radzik shortest path algorithm
  • Semiconnected graph and tree recognition algorithms

NetworkX 1.8.1

Release date: 4 August 2013

Bugfix release for missing files in source packaging.

NetworkX 1.8

Release date: 28 July 2013

Highlights
  • Faster (linear-time) graphicality tests and Havel-Hakimi graph generators
  • Directed Laplacian matrix generator
  • Katz centrality algorithm
  • Functions to generate all simple paths
  • Improved shapefile reader
  • More flexible weighted projection of bipartite graphs
  • Faster topological sort, decendents and ancestors of DAGs
  • Scaling parameter for force-directed layout
Bug fixes
  • Error with average weighted connectivity for digraphs, correct normalized laplacian with self-loops, load betweenness for single node graphs, isolated nodes missing from dfs/bfs trees, normalize HITS using l1, handle density of graphs with self loops
  • Cleaner handling of current figure status with Matplotlib, Pajek files now don’t write troublesome header line, default alpha value for GEXF files, read curved edges from yEd GraphML

For full details of the issues closed for this release (added features and bug fixes) see: https://github.com/networkx/networkx/issues?milestone=1&page=1&state=closed

NetworkX 1.7

Release date: 4 July 2012

Highlights
  • New functions for k-clique community finding, flow hierarchy, union, disjoint union, compose, and intersection operators that work on lists of graphs, and creating the biadjacency matrix of a bipartite graph.
  • New approximation algorithms for dominating set, edge dominating set, independent set, max clique, and min-weighted vertex cover.
  • Many bug fixes and other improvements.

For full details of the tickets closed for this release (added features and bug fixes) see: https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx-1.7

NetworkX 1.6

Release date: 20 November 2011

Highlights

New functions for finding articulation points, generating random bipartite graphs, constructing adjacency matrix representations, forming graph products, computing assortativity coefficients, measuring subgraph centrality and communicability, finding k-clique communities, and writing JSON format output.

New examples for drawing with D3 Javascript library, and ordering matrices with the Cuthill-McKee algorithm.

More memory efficient implementation of current-flow betweenness and new approximation algorithms for current-flow betweenness and shortest-path betweenness.

Simplified handling of “weight” attributes for algorithms that use weights/costs/values. See Version 1.6 notes and API changes.

Updated all code to work with the PyPy Python implementation http://pypy.org which produces faster performance on many algorithms.

For full details of the tickets closed for this release (added features and bug fixes) see: https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx-1.6

NetworkX 1.5

Release date: 4 June 2011

For full details of the tickets closed for this release see: https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx-1.5

Highlights
New features
Bug fixes

NetworkX 1.4

Release date: 23 January 2011

API changes

NetworkX 1.3

Release date: 28 August 2010

See: https://networkx.lanl.gov/trac/timeline

New features
API changes
  • minimum_spanning_tree() now returns a NetworkX Graph (a tree or forest)

NetworkX 1.2

Release date: 28 July 2010

See: https://networkx.lanl.gov/trac/timeline

New features

NetworkX 1.1

Release date: 21 April 2010

See: https://networkx.lanl.gov/trac/timeline

New features
API changes
Returning dictionaries

Several of the algorithms and the degree() method now return dictionaries keyed by node instead of lists. In some cases there was a with_labels keyword which is no longer necessary. For example,

>>> G=nx.Graph()
>>> G.add_edge('a','b')
>>> G.degree() # returns dictionary of degree keyed by node
{'a': 1, 'b': 1}

Asking for the degree of a single node still returns a single number

>>> G.degree('a')
1

The following now return dictionaries by default (instead of lists) and the with_labels keyword has been removed:

The following now return dictionaries by default (instead of lists)

  • pagerank()
  • hits()
Adding nodes

add_nodes_from now accepts (node, attrdict) two-tuples

>>> G = nx.Graph()
>>> G.add_nodes_from([(1, {'color': 'red'})])
Bug fixes
  • Support graph attributes with union, intersection, and other graph operations
  • Improve subgraph speed (and related algorithms such as connected_components_subgraphs())
  • Handle multigraphs in more operators (e.g. union)
  • Handle double-quoted labels with pydot
  • Normalize betweenness_centrality for undirected graphs correctly
  • Normalize eigenvector_centrality by l2 norm
  • read_gml() now returns multigraphs

NetworkX 1.0.1

Release date: 11 Jan 2010

See: https://networkx.lanl.gov/trac/timeline

Bug fix release for missing setup.py in manifest.

NetworkX 1.0

Release date: 8 Jan 2010

See: https://networkx.lanl.gov/trac/timeline

New features

This release has significant changes to parts of the graph API to allow graph, node, and edge attributes. See http://networkx.lanl.gov/reference/api_changes.html

  • Update Graph, DiGraph, and MultiGraph classes to allow attributes.
  • Default edge data is now an empty dictionary (was the integer 1)
  • Difference and intersection operators
  • Average shortest path
  • A* (A-Star) algorithm
  • PageRank, HITS, and eigenvector centrality
  • Read Pajek files
  • Line graphs
  • Minimum spanning tree (Kruskal’s algorithm)
  • Dense and sparse Fruchterman-Reingold layout
  • Random clustered graph generator
  • Directed scale-free graph generator
  • Faster random regular graph generator
  • Improved edge color and label drawing with Matplotlib
  • and much more, see https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx-1.0
Examples
  • Update to work with networkx-1.0 API
  • Graph subclass example

NetworkX 0.99

Release date: 18 November 2008

See: https://networkx.lanl.gov/trac/timeline

New features

This release has significant changes to parts of the graph API. See http://networkx.lanl.gov/reference/api_changes.html

  • Update Graph and DiGraph classes to use weighted graphs as default Change in API for performance and code simplicity.
  • New MultiGraph and MultiDiGraph classes (replace XGraph and XDiGraph)
  • Update to use Sphinx documentation system http://networkx.lanl.gov/
  • Developer site at https://networkx.lanl.gov/trac/
  • Experimental LabeledGraph and LabeledDiGraph
  • Moved package and file layout to subdirectories.
Bug fixes
  • handle root= option to draw_graphviz correctly
Examples
  • Update to work with networkx-0.99 API
  • Drawing examples now use matplotlib.pyplot interface
  • Improved drawings in many examples
  • New examples - see http://networkx.lanl.gov/examples/

NetworkX 0.37

Release date: 17 August 2008

See: https://networkx.lanl.gov/trac/timeline

NetworkX now requires Python 2.4 or later for full functionality.

New features
  • Edge coloring and node line widths with Matplotlib drawings
  • Update pydot functions to work with pydot-1.0.2
  • Maximum-weight matching algorithm
  • Ubigraph interface for 3D OpenGL layout and drawing
  • Pajek graph file format reader and writer
  • p2g graph file format reader and writer
  • Secondary sort in topological sort
Bug fixes
  • Better edge data handling with GML writer
  • Edge betweenness fix for XGraph with default data of None
  • Handle Matplotlib version strings (allow “pre”)
  • Interface to PyGraphviz (to_agraph()) now handles parallel edges
  • Fix bug in copy from XGraph to XGraph with multiedges
  • Use SciPy sparse lil matrix format instead of coo format
  • Clear up ambiguous cases for Barabasi-Albert model
  • Better care of color maps with Matplotlib when drawing colored nodes and edges
  • Fix error handling in layout.py
Examples
  • Ubigraph examples showing 3D drawing

NetworkX 0.36

Release date: 13 January 2008

See: https://networkx.lanl.gov/trac/timeline

New features
  • GML format graph reader, tests, and example (football.py)
  • edge_betweenness() and load_betweenness()
Bug fixes
  • remove obsolete parts of pygraphviz interface
  • improve handling of Matplotlib version strings
  • write_dot() now writes parallel edges and self loops
  • is_bipartite() and bipartite_color() fixes
  • configuration model speedup using random.shuffle()
  • convert with specified nodelist now works correctly
  • vf2 isomorphism checker updates

NetworkX 0.35.1

Release date: 27 July 2007

See: https://networkx.lanl.gov/trac/timeline

Small update to fix import readwrite problem and maintain Python2.3 compatibility.

NetworkX 0.35

Release date: 22 July 2007

See: https://networkx.lanl.gov/trac/timeline

New features
  • algorithms for strongly connected components.
  • Brandes betweenness centrality algorithm (weighted and unweighted versions)
  • closeness centrality for weighted graphs
  • dfs_preorder, dfs_postorder, dfs_tree, dfs_successor, dfs_predecessor
  • readers for GraphML, LEDA, sparse6, and graph6 formats.
  • allow arguments in graphviz_layout to be passed directly to graphviz
Bug fixes
  • more detailed installation instructions
  • replaced dfs_preorder,dfs_postorder (see search.py)
  • allow initial node positions in spectral_layout
  • report no error on attempting to draw empty graph
  • report errors correctly when using tuples as nodes #114
  • handle conversions from incomplete dict-of-dict data

NetworkX 0.34

Release date: 12 April 2007

See: https://networkx.lanl.gov/trac/timeline

New features
  • benchmarks for graph classes
  • Brandes betweenness centrality algorithm
  • Dijkstra predecessor and distance algorithm
  • xslt to convert DIA graphs to NetworkX
  • number_of_edges(u,v) counts edges between nodes u and v
  • run tests with python setup_egg.py test (needs setuptools) else use python -c “import networkx; networkx.test()”
  • is_isomorphic() that uses vf2 algorithm
Bug fixes
  • speedups of neighbors()
  • simplified Dijkstra’s algorithm code
  • better exception handling for shortest paths
  • get_edge(u,v) returns None (instead of exception) if no edge u-v
  • floyd_warshall_array fixes for negative weights
  • bad G467, docs, and unittest fixes for graph atlas
  • don’t put nans in numpy or scipy sparse adjacency matrix
  • handle get_edge() exception (return None if no edge)
  • remove extra kwds arguments in many places
  • no multi counting edges in conversion to dict of lists for multigraphs
  • allow passing tuple to get_edge()
  • bad parameter order in node/edge betweenness
  • edge betweenness doesn’t fail with XGraph
  • don’t throw exceptions for nodes not in graph (silently ignore instead) in edges_* and degree_*

NetworkX 0.33

Release date: 27 November 2006

See: https://networkx.lanl.gov/trac/timeline

New features
  • draw edges with specified colormap

  • more efficient version of Floyd’s algorithm for all pairs shortest path

  • use numpy only, Numeric is deprecated

  • include tests in source package (networkx/tests)

  • include documentation in source package (doc)

  • tests can now be run with
    >>> import networkx
    >>> networkx.test()
    
Bug fixes
  • read_gpickle now works correctly with Windows
  • refactored large modules into smaller code files
  • degree(nbunch) now returns degrees in same order as nbunch
  • degree() now works for multiedges=True
  • update node_boundary and edge_boundary for efficiency
  • edited documentation for graph classes, now mostly in info.py
Examples
  • Draw edges with colormap

NetworkX 0.32

Release date: 29 September 2006

See: https://networkx.lanl.gov/trac/timeline

New features
  • Update to work with numpy-1.0x
  • Make egg usage optional: use python setup_egg.py bdist_egg to build egg
  • Generators and functions for bipartite graphs
  • Experimental classes for trees and forests
  • Support for new pygraphviz update (in nx_agraph.py) , see http://networkx.lanl.gov/pygraphviz/ for pygraphviz details
Bug fixes
  • Handle special cases correctly in triangles function
  • Typos in documentation
  • Handle special cases in shortest_path and shortest_path_length, allow cutoff parameter for maximum depth to search
  • Update examples: erdos_renyi.py, miles.py, roget,py, eigenvalues.py
Examples
  • Expected degree sequence
  • New pygraphviz interface

NetworkX 0.31

Release date: 20 July 2006

See: https://networkx.lanl.gov/trac/timeline

New features
  • arbitrary node relabeling (use relabel_nodes)
  • conversion of NetworkX graphs to/from Python dict/list types, numpy matrix or array types, and scipy_sparse_matrix types
  • generator for random graphs with given expected degree sequence
Bug fixes
  • Allow drawing graphs with no edges using pylab
  • Use faster heapq in dijkstra
  • Don’t complain if X windows is not available
Examples
  • update drawing examples

NetworkX 0.30

Release date: 23 June 2006

See: https://networkx.lanl.gov/trac/timeline

New features
  • update to work with Python 2.5
  • bidirectional version of shortest_path and Dijkstra
  • single_source_shortest_path and all_pairs_shortest_path
  • s-metric and experimental code to generate maximal s-metric graph
  • double_edge_swap and connected_double_edge_swap
  • Floyd’s algorithm for all pairs shortest path
  • read and write unicode graph data to text files
  • read and write YAML format text files, http://yaml.org
Bug fixes
  • speed improvements (faster version of subgraph, is_connected)
  • added cumulative distribution and modified discrete distribution utilities
  • report error if DiGraphs are sent to connected_components routines
  • removed with_labels keywords for many functions where it was causing confusion
  • function name changes in shortest_path routines
  • saner internal handling of nbunch (node bunches), raise an exception if an nbunch isn’t a node or iterable
  • better keyword handling in io.py allows reading multiple graphs
  • don’t mix Numeric and numpy arrays in graph layouts and drawing
  • avoid automatically rescaling matplotlib axes when redrawing graph layout
Examples
  • unicode node labels

NetworkX 0.29

Release date: 28 April 2006

See: https://networkx.lanl.gov/trac/timeline

New features
  • Algorithms for betweenness, eigenvalues, eigenvectors, and spectral projection for threshold graphs
  • Use numpy when available
  • dense_gnm_random_graph generator
  • Generators for some directed graphs: GN, GNR, and GNC by Krapivsky and Redner
  • Grid graph generators now label by index tuples. Helper functions for manipulating labels.
  • relabel_nodes_with_function
Bug fixes
  • Betweenness centrality now correctly uses Brandes definition and has normalization option outside main loop
  • Empty graph now labeled as empty_graph(n)
  • shortest_path_length used python2.4 generator feature
  • degree_sequence_tree off by one error caused nonconsecutive labeling
  • periodic_grid_2d_graph removed in favor of grid_2d_graph with periodic=True

NetworkX 0.28

Release date: 13 March 2006

See: https://networkx.lanl.gov/trac/timeline

New features
  • Option to construct Laplacian with rows and columns in specified order
  • Option in convert_node_labels_to_integers to use sorted order
  • predecessor(G,n) function that returns dictionary of nodes with predecessors from breadth-first search of G starting at node n. https://networkx.lanl.gov/trac/ticket/26
Examples
Bug fixes
  • Adjusted names for random graphs.
    • erdos_renyi_graph=binomial_graph=gnp_graph: n nodes with edge probability p
    • gnm_graph: n nodes and m edges
    • fast_gnp_random_graph: gnp for sparse graphs (small p)
  • Documentation contains correct spelling of Barabási, Bollobás, Erdős, and Rényi in UTF-8 encoding
  • Increased speed of connected_components and related functions by using faster BFS algorithm in networkx.paths https://networkx.lanl.gov/trac/ticket/27
  • XGraph and XDiGraph with multiedges=True produced error on delete_edge
  • Cleaned up docstring errors
  • Normalize names of some graphs to produce strings that represent calling sequence

NetworkX 0.27

Release date: 5 February 2006

See: https://networkx.lanl.gov/trac/timeline

New features
  • sparse_binomial_graph: faster graph generator for sparse random graphs
  • read/write routines in io.py now handle XGraph() type and gzip and bzip2 files
  • optional mapping of type for read/write routine to allow on-the-fly conversion of node and edge datatype on read
  • Substantial changes related to digraphs and definitions of neighbors() and edges(). For digraphs edges=out_edges. Neighbors now returns a list of neighboring nodes with possible duplicates for graphs with parallel edges See https://networkx.lanl.gov/trac/ticket/24
  • Addition of out_edges, in_edges and corresponding out_neighbors and in_neighbors for digraphs. For digraphs edges=out_edges.
Examples
  • Minard’s data for Napoleon’s Russian campaign
Bug fixes
  • XGraph(multiedges=True) returns a copy of the list of edges for get_edge()

NetworkX 0.26

Release date: 6 January 2006

New features
  • Simpler interface to drawing with pylab
  • G.info(node=None) function returns short information about graph or node
  • adj_matrix now takes optional nodelist to force ordering of rows/columns in matrix
  • optional pygraphviz and pydot interface to graphviz is now callable as “graphviz” with pygraphviz preferred. Use draw_graphviz(G).
Examples
  • Several new examples showing how draw to graphs with various properties of nodes, edges, and labels
Bug fixes
  • Default data type for all graphs is now None (was the integer 1)
  • add_nodes_from now won’t delete edges if nodes added already exist
  • Added missing names to generated graphs
  • Indexes for nodes in graphs start at zero by default (was 1)

NetworkX 0.25

Release date: 5 December 2005

New features
Examples
  • Email example shows how to use XDiGraph with Python objects as edge data
Documentation
  • Reformat menu, minor changes to Readme, better stylesheet
Bug fixes
  • use create_using= instead of result= keywords for graph types in all cases
  • missing weights for degree 0 and 1 nodes in clustering
  • configuration model now uses XGraph, returns graph with identical degree sequence as input sequence
  • fixed Dijkstra priority queue
  • fixed non-recursive toposort and is_directed_acyclic graph

NetworkX 0.24

Release date: 20 August 2005

Bug fixes
  • Update of Dijkstra algorithm code
  • dfs_successor now calls proper search method
  • Changed to list comprehension in DiGraph.reverse() for python2.3 compatibility
  • Barabasi-Albert graph generator fixed
  • Attempt to add self loop should add node even if parallel edges not allowed

NetworkX 0.23

Release date: 14 July 2005

The NetworkX web locations have changed:

http://networkx.lanl.gov/ - main documentation site http://networkx.lanl.gov/svn/ - subversion source code repository https://networkx.lanl.gov/trac/ - bug tracking and info

Important Change

The naming conventions in NetworkX have changed. The package name “NX” is now “networkx”.

The suggested ways to import the NetworkX package are

  • import networkx
  • import networkx as NX
  • from networkx import *
New features
  • DiGraph reverse
  • Graph generators
    • watts_strogatz_graph now does rewiring method
    • old watts_strogatz_graph->newman_watts_strogatz_graph
Examples
Documentation
Bug fixes
  • Fixed logic in io.py for reading DiGraphs.
  • Path based centrality measures (betweenness, closeness) modified so they work on graphs that are not connected and produce the same result as if each connected component were considered separately.

NetworkX 0.22

Release date: 17 June 2005

New features
  • Topological sort, testing for directed acyclic graphs (DAGs)
  • Dijkstra’s algorithm for shortest paths in weighted graphs
  • Multidimensional layout with dim=n for drawing
  • 3d rendering demonstration with vtk
  • Graph generators
    • random_powerlaw_tree
    • dorogovtsev_goltsev_mendes_graph
Examples
  • Kevin Bacon movie actor graph: Examples/kevin_bacon.py
  • Compute eigenvalues of graph Laplacian: Examples/eigenvalues.py
  • Atlas of small graphs: Examples/atlas.py
Documentation
  • Rewrite of setup scripts to install documentation and tests in documentation directory specified
Bug fixes
  • Handle calls to edges() with non-node, non-iterable items.
  • truncated_tetrahedral_graph was just plain wrong
  • Speedup of betweenness_centrality code
  • bfs_path_length now returns correct lengths
  • Catch error if target of search not in connected component of source
  • Code cleanup to label internal functions with _name
  • Changed import statement lines to always use “import NX” to protect name-spaces
  • Other minor bug-fixes and testing added

License

NetworkX is distributed with the 3-clause BSD license.

Copyright (C) 2004-2017, NetworkX Developers
Aric Hagberg <hagberg@lanl.gov>
Dan Schult <dschult@colgate.edu>
Pieter Swart <swart@lanl.gov>
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

  * Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.

  * Redistributions in binary form must reproduce the above
    copyright notice, this list of conditions and the following
    disclaimer in the documentation and/or other materials provided
    with the distribution.

  * Neither the name of the NetworkX Developers nor the names of its
    contributors may be used to endorse or promote products derived
    from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Credits

NetworkX was originally written by Aric Hagberg, Dan Schult, and Pieter Swart, and has been developed with the help of many others. Thanks to everyone who has improved NetworkX by contributing code, bug reports (and fixes), documentation, and input on design, features, and the future of NetworkX.

Contributions

This section aims to provide a list of people and projects that have contributed to networkx. It is intended to be an inclusive list, and anyone who has contributed and wishes to make that contribution known is welcome to add an entry into this file. Generally, no name should be added to this list without the approval of the person associated with that name.

Creating a comprehensive list of contributors can be difficult, and the list within this file is almost certainly incomplete. Contributors include testers, bug reporters, contributors who wish to remain anonymous, funding sources, academic advisors, end users, and even build/integration systems (such as TravisCI, coveralls, and readthedocs).

Do you want to make your contribution known? If you have commit access, edit this file and add your name. If you do not have commit access, feel free to open an issue, submit a pull request, or get in contact with one of the official team members.

A supplementary (but still incomplete) list of contributors is given by the list of names that have commits in networkx’s git repository. This can be obtained via:

git log --raw | grep "^Author: " | sort | uniq

A historical, partial listing of contributors and their contributions to some of the earlier versions of NetworkX can be found here.

Original Authors
Aric Hagberg
Dan Schult
Pieter Swart

Contributors

Optionally, add your desired name and include a few relevant links. The order is partially historical, and now, mostly arbitrary.

  • Aric Hagberg, GitHub: hagberg
  • Dan Schult, GitHub: dschult
  • Pieter Swart
  • Katy Bold
  • Hernan Rozenfeld
  • Brendt Wohlberg
  • Jim Bagrow
  • Holly Johnsen
  • Arnar Flatberg
  • Chris Myers
  • Joel Miller
  • Keith Briggs
  • Ignacio Rozada
  • Phillipp Pagel
  • Sverre Sundsdal
  • Ross M. Richardson
  • Eben Kenah
  • Sasha Gutfriend
  • Udi Weinsberg
  • Matteo Dell’Amico
  • Andrew Conway
  • Raf Guns
  • Salim Fadhley
  • Fabrice Desclaux
  • Arpad Horvath
  • Minh Van Nguyen
  • Willem Ligtenberg
  • Loïc Séguin-C.
  • Paul McGuire
  • Jesus Cerquides
  • Ben Edwards
  • Jon Olav Vik
  • Hugh Brown
  • Ben Reilly
  • Leo Lopes
  • Jordi Torrents, GitHub: jtorrents
  • Dheeraj M R
  • Franck Kalala
  • Simon Knight
  • Conrad Lee
  • Sérgio Nery Simões
  • Robert King
  • Nick Mancuso
  • Brian Cloteaux
  • Alejandro Weinstein
  • Dustin Smith
  • Mathieu Larose
  • Vincent Gauthier
  • chebee7i, GitHub: chebee7i
  • Jeffrey Finkelstein
  • Jean-Gabriel Young, Github: jg-you
  • Andrey Paramonov, http://aparamon.msk.ru
  • Mridul Seth, GitHub: MridulS
  • Thodoris Sotiropoulos, GitHub: theosotr
  • Konstantinos Karakatsanis, GitHub: k-karakatsanis
  • Ryan Nelson, GitHub: rnelsonchem
  • Niels van Adrichem, GitHub: NvanAdrichem
  • Michael E. Rose, GitHub: Michael-E-Rose
  • Jarrod Millman, GitHub: jarrodmillman

Support

networkx and those who have contributed to networkx have received support throughout the years from a variety of sources. We list them below. If you have provided support to networkx and a support acknowledgment does not appear below, please help us remedy the situation, and similarly, please let us know if you’d like something modified or corrected.

Research Groups

networkx acknowledges support from the following:

Funding

networkx acknowledges support from the following:

  • Google Summer of Code via Python Software Foundation
  • U.S. Army Research Office grant W911NF-12-1-0288
  • DARPA Physical Intelligence Subcontract No. 9060-000709
  • NSF Grant No. PHY-0748828
  • John Templeton Foundation through a grant to the Santa Fe Institute to study complexity
  • U.S. Army Research Laboratory and the U.S. Army Research Office under contract number W911NF-13-1-0340

Citing

To cite NetworkX please use the following publication:

Aric A. Hagberg, Daniel A. Schult and Pieter J. Swart, “Exploring network structure, dynamics, and function using NetworkX”, in Proceedings of the 7th Python in Science Conference (SciPy2008), Gäel Varoquaux, Travis Vaught, and Jarrod Millman (Eds), (Pasadena, CA USA), pp. 11–15, Aug 2008

PDF BibTeX

Bibliography

[BA02]R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks”, Reviews of Modern Physics, 74, pp. 47-97, 2002. http://arxiv.org/abs/cond-mat/0106096
[Bollobas01]B. Bollobás, “Random Graphs”, Second Edition, Cambridge University Press, 2001.
[BE05]U. Brandes and T. Erlebach, “Network Analysis: Methodological Foundations”, Lecture Notes in Computer Science, Volume 3418, Springer-Verlag, 2005.
[CL1996]G. Chartrand and L. Lesniak, “Graphs and Digraphs”, Chapman and Hall/CRC, 1996.
[choudum1986]S.A. Choudum. “A simple proof of the Erdős-Gallai theorem on graph sequences.” Bulletin of the Australian Mathematical Society, 33, pp 67-70, 1986. http://dx.doi.org/10.1017/S0004972700002872
[Diestel97]R. Diestel, “Graph Theory”, Springer-Verlag, 1997. http://diestel-graph-theory.com/index.html
[DM03]S.N. Dorogovtsev and J.F.F. Mendes, “Evolution of Networks”, Oxford University Press, 2003.
[EppsteinPads]David Eppstein. PADS, A library of Python Algorithms and Data Structures. http://www.ics.uci.edu/~eppstein/PADS
[EG1960]Erdős and Gallai, Mat. Lapok 11 264, 1960.
[hakimi1962]Hakimi, S. “On the Realizability of a Set of Integers as Degrees of the Vertices of a Graph.” SIAM J. Appl. Math. 10, 496-506, 1962.
[havel1955]Havel, V. “A Remark on the Existence of Finite Graphs” Casopis Pest. Mat. 80, 477-480, 1955.
[Langtangen04]H.P. Langtangen, “Python Scripting for Computational Science.”, Springer Verlag Series in Computational Science and Engineering, 2004.
[Martelli03]A. Martelli, “Python in a Nutshell”, O’Reilly Media Inc, 2003.
[Newman03]M.E.J. Newman, “The Structure and Function of Complex Networks”, SIAM Review, 45, pp. 167-256, 2003. http://epubs.siam.org/doi/abs/10.1137/S003614450342480
[Sedgewick02]R. Sedgewick, “Algorithms in C: Parts 1-4: Fundamentals, Data Structure, Sorting, Searching”, Addison Wesley Professional, 3rd ed., 2002.
[Sedgewick01]R. Sedgewick, “Algorithms in C, Part 5: Graph Algorithms”, Addison Wesley Professional, 3rd ed., 2001.
[West01]D. B. West, “Introduction to Graph Theory”, Prentice Hall, 2nd ed., 2001.
[vanRossum98]Guido van Rossum. Python Patterns - Implementing Graphs, 1998. http://www.python.org/doc/essays/graphs

Examples

General-purpose and introductory examples for NetworkX. The tutorial introduces conventions and basic graph manipulations.

3D Drawing

Mayavi2

This is

# needs mayavi2
# run with ipython -wthread
import networkx as nx
import numpy as np
from mayavi import mlab
mlab.options.offscreen = True

# some graphs to try
# H=nx.krackhardt_kite_graph()
# H=nx.Graph();H.add_edge('a','b');H.add_edge('a','c');H.add_edge('a','d')
# H=nx.grid_2d_graph(4,5)
H = nx.cycle_graph(20)

# reorder nodes from 0,len(G)-1
G = nx.convert_node_labels_to_integers(H)
# 3d spring layout
pos = nx.spring_layout(G, dim=3)
# numpy array of x,y,z positions in sorted node order
xyz = np.array([pos[v] for v in sorted(G)])
# scalar colors
scalars = np.array(list(G.nodes())) + 5

mlab.figure(1, bgcolor=(0, 0, 0))
mlab.clf()

pts = mlab.points3d(xyz[:, 0], xyz[:, 1], xyz[:, 2],
                    scalars,
                    scale_factor=0.1,
                    scale_mode='none',
                    colormap='Blues',
                    resolution=20)

pts.mlab_source.dataset.lines = np.array(list(G.edges()))
tube = mlab.pipeline.tube(pts, tube_radius=0.01)
mlab.pipeline.surface(tube, color=(0.8, 0.8, 0.8))

mlab.savefig('mayavi2_spring.png')
# mlab.show() # interactive window

Total running time of the script: ( 0 minutes 0.000 seconds)

Generated by Sphinx-Gallery

Advanced

Eigenvalues

Create an G{n,m} random graph and compute the eigenvalues.

_images/sphx_glr_plot_eigenvalues_001.png

Out:

Largest eigenvalue: 1.59960251352
Smallest eigenvalue: -1.29986895434e-16

import matplotlib.pyplot as plt
import networkx as nx
import numpy.linalg

n = 1000  # 1000 nodes
m = 5000  # 5000 edges
G = nx.gnm_random_graph(n, m)

L = nx.normalized_laplacian_matrix(G)
e = numpy.linalg.eigvals(L.A)
print("Largest eigenvalue:", max(e))
print("Smallest eigenvalue:", min(e))
plt.hist(e, bins=100)  # histogram with 100 bins
plt.xlim(0, 2)  # eigenvalues between 0 and 2
plt.show()

Total running time of the script: ( 0 minutes 3.662 seconds)

Generated by Sphinx-Gallery

Heavy Metal Umlaut

Example using unicode strings as graph labels.

Also shows creative use of the Heavy Metal Umlaut: https://en.wikipedia.org/wiki/Heavy_metal_umlaut

_images/sphx_glr_plot_heavy_metal_umlaut_001.png

Out:

[u'Blue \xd6yster Cult', u'Mot\xf6rhead', u'H\xfcsker D\xfc', u'M\xf6tley Cr\xfce', u'Sp\u0131n\u0308al Tap', u'Deatht\xf6ngue', u'Queensr\xffche']

# Author: Aric Hagberg (hagberg@lanl.gov)

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

import matplotlib.pyplot as plt
import networkx as nx

try:
    hd = 'H' + unichr(252) + 'sker D' + unichr(252)
    mh = 'Mot' + unichr(246) + 'rhead'
    mc = 'M' + unichr(246) + 'tley Cr' + unichr(252) + 'e'
    st = 'Sp' + unichr(305) + 'n' + unichr(776) + 'al Tap'
    q = 'Queensr' + unichr(255) + 'che'
    boc = 'Blue ' + unichr(214) + 'yster Cult'
    dt = 'Deatht' + unichr(246) + 'ngue'
except NameError:
    hd = 'H' + chr(252) + 'sker D' + chr(252)
    mh = 'Mot' + chr(246) + 'rhead'
    mc = 'M' + chr(246) + 'tley Cr' + chr(252) + 'e'
    st = 'Sp' + chr(305) + 'n' + chr(776) + 'al Tap'
    q = 'Queensr' + chr(255) + 'che'
    boc = 'Blue ' + chr(214) + 'yster Cult'
    dt = 'Deatht' + chr(246) + 'ngue'

G = nx.Graph()
G.add_edge(hd, mh)
G.add_edge(mc, st)
G.add_edge(boc, mc)
G.add_edge(boc, dt)
G.add_edge(st, dt)
G.add_edge(q, st)
G.add_edge(dt, mh)
G.add_edge(st, mh)

# write in UTF-8 encoding
fh = open('edgelist.utf-8', 'wb')
fh.write('# -*- coding: utf-8 -*-\n'.encode('utf-8'))  # encoding hint for emacs
nx.write_multiline_adjlist(G, fh, delimiter='\t', encoding='utf-8')

# read and store in UTF-8
fh = open('edgelist.utf-8', 'rb')
H = nx.read_multiline_adjlist(fh, delimiter='\t', encoding='utf-8')

for n in G.nodes():
    if n not in H:
        print(False)

print(list(G.nodes()))

pos = nx.spring_layout(G)
nx.draw(G, pos, font_size=16, with_labels=False)
for p in pos:  # raise text positions
    pos[p][1] += 0.07
nx.draw_networkx_labels(G, pos)
plt.show()

Total running time of the script: ( 0 minutes 0.085 seconds)

Generated by Sphinx-Gallery

Parallel Betweenness

Example of parallel implementation of betweenness centrality using the multiprocessing module from Python Standard Library.

The function betweenness centrality accepts a bunch of nodes and computes the contribution of those nodes to the betweenness centrality of the whole network. Here we divide the network in chunks of nodes and we compute their contribution to the betweenness centrality of the whole network.

This doesn’t work in python2.7.13. It does work in 3.6, 3.5, 3.4, and 3.3.

It may be related to this: https://stackoverflow.com/questions/1816958/cant-pickle-type-instancemethod-when-using-multiprocessing-pool-map

Traceback (most recent call last):
  File "/home/docs/checkouts/readthedocs.org/user_builds/mriduls-networkx/envs/latest/local/lib/python2.7/site-packages/sphinx_gallery/gen_rst.py", line 472, in execute_code_block
    exec(code_block, example_globals)
  File "<string>", line 59, in <module>
  File "<string>", line 39, in betweenness_centrality_parallel
  File "/usr/lib/python2.7/multiprocessing/pool.py", line 251, in map
    return self.map_async(func, iterable, chunksize).get()
  File "/usr/lib/python2.7/multiprocessing/pool.py", line 567, in get
    raise self._value
PicklingError: Can't pickle <type 'function'>: attribute lookup __builtin__.function failed
from multiprocessing import Pool
import time
import itertools

import matplotlib.pyplot as plt
import networkx as nx


def chunks(l, n):
    """Divide a list of nodes `l` in `n` chunks"""
    l_c = iter(l)
    while 1:
        x = tuple(itertools.islice(l_c, n))
        if not x:
            return
        yield x


def _betmap(G_normalized_weight_sources_tuple):
    """Pool for multiprocess only accepts functions with one argument.
    This function uses a tuple as its only argument. We use a named tuple for
    python 3 compatibility, and then unpack it when we send it to
    `betweenness_centrality_source`
    """
    return nx.betweenness_centrality_source(*G_normalized_weight_sources_tuple)


def betweenness_centrality_parallel(G, processes=None):
    """Parallel betweenness centrality  function"""
    p = Pool(processes=processes)
    node_divisor = len(p._pool) * 4
    node_chunks = list(chunks(G.nodes(), int(G.order() / node_divisor)))
    num_chunks = len(node_chunks)
    bt_sc = p.map(_betmap,
                  zip([G] * num_chunks,
                      [True] * num_chunks,
                      [None] * num_chunks,
                      node_chunks))

    # Reduce the partial solutions
    bt_c = bt_sc[0]
    for bt in bt_sc[1:]:
        for n in bt:
            bt_c[n] += bt[n]
    return bt_c


if __name__ == "__main__":
    G_ba = nx.barabasi_albert_graph(1000, 3)
    G_er = nx.gnp_random_graph(1000, 0.01)
    G_ws = nx.connected_watts_strogatz_graph(1000, 4, 0.1)
    for G in [G_ba, G_er, G_ws]:
        print("")
        print("Computing betweenness centrality for:")
        print(nx.info(G))
        print("\tParallel version")
        start = time.time()
        bt = betweenness_centrality_parallel(G)
        print("\t\tTime: %.4F" % (time.time() - start))
        print("\t\tBetweenness centrality for node 0: %.5f" % (bt[0]))
        print("\tNon-Parallel version")
        start = time.time()
        bt = nx.betweenness_centrality(G)
        print("\t\tTime: %.4F seconds" % (time.time() - start))
        print("\t\tBetweenness centrality for node 0: %.5f" % (bt[0]))
    print("")

    nx.draw(G_ba)
    plt.show()

Total running time of the script: ( 0 minutes 0.000 seconds)

Generated by Sphinx-Gallery

Iterated Dynamical Systems

Digraphs from Integer-valued Iterated Functions

Sums of cubes on 3N

The number 153 has a curious property.

Let 3N={3,6,9,12,…} be the set of positive multiples of 3. Define an iterative process f:3N->3N as follows: for a given n, take each digit of n (in base 10), cube it and then sum the cubes to obtain f(n).

When this process is repeated, the resulting series n, f(n), f(f(n)),… terminate in 153 after a finite number of iterations (the process ends because 153 = 1**3 + 5**3 + 3**3).

In the language of discrete dynamical systems, 153 is the global attractor for the iterated map f restricted to the set 3N.

For example: take the number 108

f(108) = 1**3 + 0**3 + 8**3 = 513

and

f(513) = 5**3 + 1**3 + 3**3 = 153

So, starting at 108 we reach 153 in two iterations, represented as:

108->513->153

Computing all orbits of 3N up to 10**5 reveals that the attractor 153 is reached in a maximum of 14 iterations. In this code we show that 13 cycles is the maximum required for all integers (in 3N) less than 10,000.

The smallest number that requires 13 iterations to reach 153, is 177, i.e.,

177->687->1071->345->216->225->141->66->432->99->1458->702->351->153

The resulting large digraphs are useful for testing network software.

The general problem

Given numbers n, a power p and base b, define F(n; p, b) as the sum of the digits of n (in base b) raised to the power p. The above example corresponds to f(n)=F(n; 3,10), and below F(n; p, b) is implemented as the function powersum(n,p,b). The iterative dynamical system defined by the mapping n:->f(n) above (over 3N) converges to a single fixed point; 153. Applying the map to all positive integers N, leads to a discrete dynamical process with 5 fixed points: 1, 153, 370, 371, 407. Modulo 3 those numbers are 1, 0, 1, 2, 2. The function f above has the added property that it maps a multiple of 3 to another multiple of 3; i.e. it is invariant on the subset 3N.

The squaring of digits (in base 10) result in cycles and the single fixed point 1. I.e., from a certain point on, the process starts repeating itself.

keywords: “Recurring Digital Invariant”, “Narcissistic Number”, “Happy Number”

The 3n+1 problem

There is a rich history of mathematical recreations associated with discrete dynamical systems. The most famous is the Collatz 3n+1 problem. See the function collatz_problem_digraph below. The Collatz conjecture — that every orbit returrns to the fixed point 1 in finite time — is still unproven. Even the great Paul Erdos said “Mathematics is not yet ready for such problems”, and offered $500 for its solution.

keywords: “3n+1”, “3x+1”, “Collatz problem”, “Thwaite’s conjecture”

import networkx as nx

nmax = 10000
p = 3


def digitsrep(n, b=10):
    """Return list of digits comprising n represented in base b.
    n must be a nonnegative integer"""

    if n <= 0:
        return [0]

    dlist = []
    while (n > 0):
        # Prepend next least-significant digit
        dlist = [n % b] + dlist
        # Floor-division
        n = n // b
    return dlist


def powersum(n, p, b=10):
    """Return sum of digits of n (in base b) raised to the power p."""
    dlist = digitsrep(n, b)
    sum = 0
    for k in dlist:
        sum += k**p
    return sum


def attractor153_graph(n, p, multiple=3, b=10):
    """Return digraph of iterations of powersum(n,3,10)."""
    G = nx.DiGraph()
    for k in range(1, n + 1):
        if k % multiple == 0 and k not in G:
            k1 = k
            knext = powersum(k1, p, b)
            while k1 != knext:
                G.add_edge(k1, knext)
                k1 = knext
                knext = powersum(k1, p, b)
    return G


def squaring_cycle_graph_old(n, b=10):
    """Return digraph of iterations of powersum(n,2,10)."""
    G = nx.DiGraph()
    for k in range(1, n + 1):
        k1 = k
        G.add_node(k1)  # case k1==knext, at least add node
        knext = powersum(k1, 2, b)
        G.add_edge(k1, knext)
        while k1 != knext:  # stop if fixed point
            k1 = knext
            knext = powersum(k1, 2, b)
            G.add_edge(k1, knext)
            if G.out_degree(knext) >= 1:
                # knext has already been iterated in and out
                break
    return G


def sum_of_digits_graph(nmax, b=10):
    def f(n): return powersum(n, 1, b)
    return discrete_dynamics_digraph(nmax, f)


def squaring_cycle_digraph(nmax, b=10):
    def f(n): return powersum(n, 2, b)
    return discrete_dynamics_digraph(nmax, f)


def cubing_153_digraph(nmax):
    def f(n): return powersum(n, 3, 10)
    return discrete_dynamics_digraph(nmax, f)


def discrete_dynamics_digraph(nmax, f, itermax=50000):
    G = nx.DiGraph()
    for k in range(1, nmax + 1):
        kold = k
        G.add_node(kold)
        knew = f(kold)
        G.add_edge(kold, knew)
        while kold != knew and kold << itermax:
            # iterate until fixed point reached or itermax is exceeded
            kold = knew
            knew = f(kold)
            G.add_edge(kold, knew)
            if G.out_degree(knew) >= 1:
                # knew has already been iterated in and out
                break
    return G


def collatz_problem_digraph(nmax):
    def f(n):
        if n % 2 == 0:
            return n // 2
        else:
            return 3 * n + 1
    return discrete_dynamics_digraph(nmax, f)


def fixed_points(G):
    """Return a list of fixed points for the discrete dynamical
    system represented by the digraph G.
    """
    return [n for n in G if G.out_degree(n) == 0]


if __name__ == "__main__":
    nmax = 10000
    print("Building cubing_153_digraph(%d)" % nmax)
    G = cubing_153_digraph(nmax)
    print("Resulting digraph has", len(G), "nodes and",
          G.size(), " edges")
    print("Shortest path from 177 to 153 is:")
    print(nx.shortest_path(G, 177, 153))
    print("fixed points are %s" % fixed_points(G))

Total running time of the script: ( 0 minutes 0.000 seconds)

Generated by Sphinx-Gallery

Algorithms

Krackhardt Centrality

Centrality measures of Krackhardt social network.

_images/sphx_glr_plot_krackhardt_centrality_001.png

Out:

Betweenness
00 0.023
01 0.023
02 0.000
03 0.102
04 0.000
05 0.231
06 0.231
07 0.389
08 0.222
09 0.000
Degree centrality
00 0.444
01 0.444
02 0.333
03 0.667
04 0.333
05 0.556
06 0.556
07 0.333
08 0.222
09 0.111
Closeness centrality
00 0.529
01 0.529
02 0.500
03 0.600
04 0.500
05 0.643
06 0.643
07 0.600
08 0.429
09 0.310

# Author: Aric Hagberg (hagberg@lanl.gov)
# Date: 2005-05-12 14:33:11 -0600 (Thu, 12 May 2005)
# Revision: 998

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

import matplotlib.pyplot as plt
import networkx as nx

G = nx.krackhardt_kite_graph()

print("Betweenness")
b = nx.betweenness_centrality(G)
for v in G.nodes():
    print("%0.2d %5.3f" % (v, b[v]))

print("Degree centrality")
d = nx.degree_centrality(G)
for v in G.nodes():
    print("%0.2d %5.3f" % (v, d[v]))

print("Closeness centrality")
c = nx.closeness_centrality(G)
for v in G.nodes():
    print("%0.2d %5.3f" % (v, c[v]))

nx.draw(G)
plt.show()

Total running time of the script: ( 0 minutes 0.079 seconds)

Generated by Sphinx-Gallery

Davis Club

Davis Southern Club Women

Shows how to make unipartite projections of the graph and compute the properties of those graphs.

These data were collected by Davis et al. in the 1930s. They represent observed attendance at 14 social events by 18 Southern women. The graph is bipartite (clubs, women).

_images/sphx_glr_plot_davis_club_001.png

Out:

Biadjacency matrix
  (0, 0)        1
  (0, 1)        1
  (0, 2)        1
  (0, 3)        1
  (0, 4)        1
  (0, 5)        1
  (0, 7)        1
  (0, 8)        1
  (1, 0)        1
  (1, 1)        1
  (1, 2)        1
  (1, 4)        1
  (1, 5)        1
  (1, 6)        1
  (1, 7)        1
  (2, 1)        1
  (2, 2)        1
  (2, 3)        1
  (2, 4)        1
  (2, 5)        1
  (2, 6)        1
  (2, 7)        1
  (2, 8)        1
  (3, 0)        1
  (3, 2)        1
  :     :
  (12, 7)       1
  (12, 8)       1
  (12, 9)       1
  (12, 11)      1
  (12, 12)      1
  (12, 13)      1
  (13, 5)       1
  (13, 6)       1
  (13, 8)       1
  (13, 9)       1
  (13, 10)      1
  (13, 11)      1
  (13, 12)      1
  (13, 13)      1
  (14, 6)       1
  (14, 7)       1
  (14, 9)       1
  (14, 10)      1
  (14, 11)      1
  (15, 7)       1
  (15, 8)       1
  (16, 8)       1
  (16, 10)      1
  (17, 8)       1
  (17, 10)      1

#Friends, Member
17 Evelyn Jefferson
15 Laura Mandeville
17 Theresa Anderson
15 Brenda Rogers
11 Charlotte McDowd
15 Frances Anderson
15 Eleanor Nye
16 Pearl Oglethorpe
17 Ruth DeSand
17 Verne Sanderson
16 Myra Liddel
16 Katherina Rogers
17 Sylvia Avondale
17 Nora Fayette
17 Helen Lloyd
16 Dorothy Murchison
12 Olivia Carleton
12 Flora Price

#Friend meetings, Member
50 Evelyn Jefferson
45 Laura Mandeville
57 Theresa Anderson
46 Brenda Rogers
24 Charlotte McDowd
32 Frances Anderson
36 Eleanor Nye
31 Pearl Oglethorpe
40 Ruth DeSand
38 Verne Sanderson
33 Myra Liddel
37 Katherina Rogers
46 Sylvia Avondale
43 Nora Fayette
34 Helen Lloyd
24 Dorothy Murchison
14 Olivia Carleton
14 Flora Price

import matplotlib.pyplot as plt
import networkx as nx
import networkx.algorithms.bipartite as bipartite

G = nx.davis_southern_women_graph()
women = G.graph['top']
clubs = G.graph['bottom']

print("Biadjacency matrix")
print(bipartite.biadjacency_matrix(G, women, clubs))

# project bipartite graph onto women nodes
W = bipartite.projected_graph(G, women)
print('')
print("#Friends, Member")
for w in women:
    print('%d %s' % (W.degree(w), w))

# project bipartite graph onto women nodes keeping number of co-occurence
# the degree computed is weighted and counts the total number of shared contacts
W = bipartite.weighted_projected_graph(G, women)
print('')
print("#Friend meetings, Member")
for w in women:
    print('%d %s' % (W.degree(w, weight='weight'), w))

nx.draw(G)
plt.show()

Total running time of the script: ( 0 minutes 0.088 seconds)

Generated by Sphinx-Gallery

_images/sphx_glr_rcm_thumb.png

Rcm

Rcm

Cuthill-McKee ordering of matrices

The reverse Cuthill-McKee algorithm gives a sparse matrix ordering that reduces the matrix bandwidth.

# Copyright (C) 2011-2017 by
# Author:    Aric Hagberg <aric.hagberg@gmail.com>
# BSD License
import networkx as nx
from networkx.utils import reverse_cuthill_mckee_ordering
import numpy as np

# build low-bandwidth numpy matrix
G = nx.grid_2d_graph(3, 3)
rcm = list(reverse_cuthill_mckee_ordering(G))
print("ordering", rcm)

print("unordered Laplacian matrix")
A = nx.laplacian_matrix(G)
x, y = np.nonzero(A)
#print("lower bandwidth:",(y-x).max())
#print("upper bandwidth:",(x-y).max())
print("bandwidth: %d" % ((y - x).max() + (x - y).max() + 1))
print(A)

B = nx.laplacian_matrix(G, nodelist=rcm)
print("low-bandwidth Laplacian matrix")
x, y = np.nonzero(B)
#print("lower bandwidth:",(y-x).max())
#print("upper bandwidth:",(x-y).max())
print("bandwidth: %d" % ((y - x).max() + (x - y).max() + 1))
print(B)

Total running time of the script: ( 0 minutes 0.000 seconds)

Generated by Sphinx-Gallery

Blockmodel

Example of creating a block model using the blockmodel function in NX. Data used is the Hartford, CT drug users network:

@article{weeks2002social,
  title={Social networks of drug users in high-risk sites: Finding the connections},
  url = {http://dx.doi.org/10.1023/A:1015457400897},
  doi = {10.1023/A:1015457400897},
  author={Weeks, Margaret R and Clair, Scott and Borgatti, Stephen P and Radda, Kim and Schensul, Jean J},
  journal={{AIDS and Behavior}},
  volume={6},
  number={2},
  pages={193--206},
  year={2002},
  publisher={Springer}
}
_images/sphx_glr_plot_blockmodel_001.png
# Authors:  Drew Conway <drew.conway@nyu.edu>, Aric Hagberg <hagberg@lanl.gov>

from collections import defaultdict

import matplotlib.pyplot as plt
import networkx as nx
import numpy
from scipy.cluster import hierarchy
from scipy.spatial import distance


def create_hc(G):
    """Creates hierarchical cluster of graph G from distance matrix"""
    path_length = nx.all_pairs_shortest_path_length(G)
    distances = numpy.zeros((len(G), len(G)))
    for u, p in path_length:
        for v, d in p.items():
            distances[u][v] = d
    # Create hierarchical cluster
    Y = distance.squareform(distances)
    Z = hierarchy.complete(Y)  # Creates HC using farthest point linkage
    # This partition selection is arbitrary, for illustrive purposes
    membership = list(hierarchy.fcluster(Z, t=1.15))
    # Create collection of lists for blockmodel
    partition = defaultdict(list)
    for n, p in zip(list(range(len(G))), membership):
        partition[p].append(n)
    return list(partition.values())


if __name__ == '__main__':
    G = nx.read_edgelist("hartford_drug.edgelist")

    # Extract largest connected component into graph H
    H = next(nx.connected_component_subgraphs(G))
    # Makes life easier to have consecutively labeled integer nodes
    H = nx.convert_node_labels_to_integers(H)
    # Create parititions with hierarchical clustering
    partitions = create_hc(H)
    # Build blockmodel graph
    BM = nx.blockmodel(H, partitions)

    # Draw original graph
    pos = nx.spring_layout(H, iterations=100)
    plt.subplot(211)
    nx.draw(H, pos, with_labels=False, node_size=10)

    # Draw block model with weighted edges and nodes sized by number of internal nodes
    node_size = [BM.node[x]['nnodes'] * 10 for x in BM.nodes()]
    edge_width = [(2 * d['weight']) for (u, v, d) in BM.edges(data=True)]
    # Set positions to mean of positions of internal nodes from original graph
    posBM = {}
    for n in BM:
        xy = numpy.array([pos[u] for u in BM.node[n]['graph']])
        posBM[n] = xy.mean(axis=0)
    plt.subplot(212)
    nx.draw(BM, posBM, node_size=node_size, width=edge_width, with_labels=False)
    plt.axis('off')
    plt.show()

Total running time of the script: ( 0 minutes 0.299 seconds)

Generated by Sphinx-Gallery

Basic

Read and write graphs.

Read and write graphs.

_images/sphx_glr_plot_read_write_001.png

Out:

#/home/docs/checkouts/readthedocs.org/user_builds/mriduls-networkx/envs/latest/bin/sphinx-build -T -E -b readthedocs -d _build/doctrees-readthedocs -D language=en . _build/html
# GMT Mon Jul 24 19:33:46 2017
# grid_2d_graph(5, 5)
(1, 3) (1, 2) (0, 3) (2, 3) (1, 4)
(3, 0) (2, 0) (3, 1) (4, 0)
(2, 1) (2, 0) (3, 1) (1, 1) (2, 2)
(0, 3) (0, 2) (0, 4)
(4, 0) (4, 1)
(1, 2) (1, 1) (0, 2) (2, 2)
(3, 3) (3, 4) (3, 2) (2, 3) (4, 3)
(4, 4) (3, 4) (4, 3)
(2, 2) (3, 2) (2, 3)
(4, 1) (4, 2) (3, 1)
(1, 1) (0, 1) (1, 0)
(3, 2) (4, 2) (3, 1)
(0, 0) (0, 1) (1, 0)
(0, 4) (1, 4)
(1, 4) (2, 4)
(2, 3) (2, 4)
(4, 2) (4, 3)
(1, 0) (2, 0)
(0, 1) (0, 2)
(3, 1)
(2, 4) (3, 4)
(2, 0)
(4, 3)
(3, 4)
(0, 2)

# Author: Aric Hagberg (hagberg@lanl.gov)

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

import sys

import matplotlib.pyplot as plt
import networkx as nx

G = nx.grid_2d_graph(5, 5)  # 5x5 grid
try:  # Python 2.6+
    nx.write_adjlist(G, sys.stdout)  # write adjacency list to screen
except TypeError:  # Python 3.x
    nx.write_adjlist(G, sys.stdout.buffer)  # write adjacency list to screen
# write edgelist to grid.edgelist
nx. write_edgelist(G, path="grid.edgelist", delimiter=":")
# read edgelist from grid.edgelist
H = nx.read_edgelist(path="grid.edgelist", delimiter=":")

nx.draw(H)
plt.show()

Total running time of the script: ( 0 minutes 0.083 seconds)

Generated by Sphinx-Gallery

Properties

Compute some network properties for the lollipop graph.

_images/sphx_glr_plot_properties_001.png

Out:

source vertex {target:length, }
0 {0: 0, 1: 1, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4, 7: 5, 8: 6, 9: 7}
1 {0: 1, 1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4, 7: 5, 8: 6, 9: 7}
2 {0: 1, 1: 1, 2: 0, 3: 1, 4: 2, 5: 3, 6: 4, 7: 5, 8: 6, 9: 7}
3 {0: 1, 1: 1, 2: 1, 3: 0, 4: 1, 5: 2, 6: 3, 7: 4, 8: 5, 9: 6}
4 {0: 2, 1: 2, 2: 2, 3: 1, 4: 0, 5: 1, 6: 2, 7: 3, 8: 4, 9: 5}
5 {0: 3, 1: 3, 2: 3, 3: 2, 4: 1, 5: 0, 6: 1, 7: 2, 8: 3, 9: 4}
6 {0: 4, 1: 4, 2: 4, 3: 3, 4: 2, 5: 1, 6: 0, 7: 1, 8: 2, 9: 3}
7 {0: 5, 1: 5, 2: 5, 3: 4, 4: 3, 5: 2, 6: 1, 7: 0, 8: 1, 9: 2}
8 {0: 6, 1: 6, 2: 6, 3: 5, 4: 4, 5: 3, 6: 2, 7: 1, 8: 0, 9: 1}
9 {0: 7, 1: 7, 2: 7, 3: 6, 4: 5, 5: 4, 6: 3, 7: 2, 8: 1, 9: 0}

average shortest path length 2.86

length #paths
0 10
1 24
2 16
3 14
4 12
5 10
6 8
7 6
radius: 4
diameter: 7
eccentricity: {0: 7, 1: 7, 2: 7, 3: 6, 4: 5, 5: 4, 6: 4, 7: 5, 8: 6, 9: 7}
center: [5, 6]
periphery: [0, 1, 2, 9]
density: 0.266666666667

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

import matplotlib.pyplot as plt
from networkx import nx

G = nx.lollipop_graph(4, 6)

pathlengths = []

print("source vertex {target:length, }")
for v in G.nodes():
    spl = dict(nx.single_source_shortest_path_length(G, v))
    print('{} {} '.format(v, spl))
    for p in spl:
        pathlengths.append(spl[p])

print('')
print("average shortest path length %s" % (sum(pathlengths) / len(pathlengths)))

# histogram of path lengths
dist = {}
for p in pathlengths:
    if p in dist:
        dist[p] += 1
    else:
        dist[p] = 1

print('')
print("length #paths")
verts = dist.keys()
for d in sorted(verts):
    print('%s %d' % (d, dist[d]))

print("radius: %d" % nx.radius(G))
print("diameter: %d" % nx.diameter(G))
print("eccentricity: %s" % nx.eccentricity(G))
print("center: %s" % nx.center(G))
print("periphery: %s" % nx.periphery(G))
print("density: %s" % nx.density(G))

nx.draw(G, with_labels=True)
plt.show()

Total running time of the script: ( 0 minutes 0.087 seconds)

Generated by Sphinx-Gallery

Drawing

Simple Path

Draw a graph with matplotlib.

_images/sphx_glr_plot_simple_path_001.png
import matplotlib.pyplot as plt
import networkx as nx

G = nx.path_graph(8)
nx.draw(G)
plt.show()

Total running time of the script: ( 0 minutes 0.086 seconds)

Generated by Sphinx-Gallery

Node Colormap

Draw a graph with matplotlib, color by degree. You must have matplotlib for this to work.

_images/sphx_glr_plot_node_colormap_001.png
# Author: Aric Hagberg (hagberg@lanl.gov)

import matplotlib.pyplot as plt
import networkx as nx

G = nx.cycle_graph(24)
pos = nx.spring_layout(G, iterations=200)
nx.draw(G, pos, node_color=range(24), node_size=800, cmap=plt.cm.Blues)
plt.show()

Total running time of the script: ( 0 minutes 0.109 seconds)

Generated by Sphinx-Gallery

Edge Colormap

Draw a graph with matplotlib, color edges. You must have matplotlib>=87.7 for this to work.

_images/sphx_glr_plot_edge_colormap_001.png
# Author: Aric Hagberg (hagberg@lanl.gov)

import matplotlib.pyplot as plt
import networkx as nx

G = nx.star_graph(20)
pos = nx.spring_layout(G)
colors = range(20)
nx.draw(G, pos, node_color='#A0CBE2', edge_color=colors,
        width=4, edge_cmap=plt.cm.Blues, with_labels=False)
plt.show()

Total running time of the script: ( 0 minutes 0.084 seconds)

Generated by Sphinx-Gallery

House With Colors

Draw a graph with matplotlib. You must have matplotlib for this to work.

_images/sphx_glr_plot_house_with_colors_001.png
# Author: Aric Hagberg (hagberg@lanl.gov)
import matplotlib.pyplot as plt
import networkx as nx

G = nx.house_graph()
# explicitly set positions
pos = {0: (0, 0),
       1: (1, 0),
       2: (0, 1),
       3: (1, 1),
       4: (0.5, 2.0)}

nx.draw_networkx_nodes(G, pos, node_size=2000, nodelist=[4])
nx.draw_networkx_nodes(G, pos, node_size=3000, nodelist=[0, 1, 2, 3], node_color='b')
nx.draw_networkx_edges(G, pos, alpha=0.5, width=6)
plt.axis('off')
plt.show()

Total running time of the script: ( 0 minutes 0.076 seconds)

Generated by Sphinx-Gallery

Circular Tree

This

_images/sphx_glr_plot_circular_tree_001.png
import matplotlib.pyplot as plt
import networkx as nx

try:
    import pygraphviz
    from networkx.drawing.nx_agraph import graphviz_layout
except ImportError:
    try:
        import pydot
        from networkx.drawing.nx_pydot import graphviz_layout
    except ImportError:
        raise ImportError("This example needs Graphviz and either "
                          "PyGraphviz or pydot")

G = nx.balanced_tree(3, 5)
pos = graphviz_layout(G, prog='twopi', args='')
plt.figure(figsize=(8, 8))
nx.draw(G, pos, node_size=20, alpha=0.5, node_color="blue", with_labels=False)
plt.axis('equal')
plt.show()

Total running time of the script: ( 0 minutes 0.186 seconds)

Generated by Sphinx-Gallery

Degree Rank

Random graph from given degree sequence. Draw degree rank plot and graph with matplotlib.

_images/sphx_glr_plot_degree_rank_001.png
# Author: Aric Hagberg <aric.hagberg@gmail.com>
import networkx as nx
import matplotlib.pyplot as plt

G = nx.gnp_random_graph(100, 0.02)

degree_sequence = sorted([d for n, d in G.degree()], reverse=True)
# print "Degree sequence", degree_sequence
dmax = max(degree_sequence)

plt.loglog(degree_sequence, 'b-', marker='o')
plt.title("Degree rank plot")
plt.ylabel("degree")
plt.xlabel("rank")

# draw graph in inset
plt.axes([0.45, 0.45, 0.45, 0.45])
Gcc = sorted(nx.connected_component_subgraphs(G), key=len, reverse=True)[0]
pos = nx.spring_layout(Gcc)
plt.axis('off')
nx.draw_networkx_nodes(Gcc, pos, node_size=20)
nx.draw_networkx_edges(Gcc, pos, alpha=0.4)

plt.show()

Total running time of the script: ( 0 minutes 0.178 seconds)

Generated by Sphinx-Gallery

Four Grids

Draw a graph with matplotlib. You must have matplotlib for this to work.

_images/sphx_glr_plot_four_grids_001.png
# Author: Aric Hagberg (hagberg@lanl.gov)

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

import matplotlib.pyplot as plt
import networkx as nx

G = nx.grid_2d_graph(4, 4)  # 4x4 grid

pos = nx.spring_layout(G, iterations=100)

plt.subplot(221)
nx.draw(G, pos, font_size=8)

plt.subplot(222)
nx.draw(G, pos, node_color='k', node_size=0, with_labels=False)

plt.subplot(223)
nx.draw(G, pos, node_color='g', node_size=250, with_labels=False, width=6)

plt.subplot(224)
H = G.to_directed()
nx.draw(H, pos, node_color='b', node_size=20, with_labels=False)

plt.show()

Total running time of the script: ( 0 minutes 0.403 seconds)

Generated by Sphinx-Gallery

Ego Graph

Example using the NetworkX ego_graph() function to return the main egonet of the largest hub in a Barabási-Albert network.

_images/sphx_glr_plot_ego_graph_001.png
# Author:  Drew Conway (drew.conway@nyu.edu)

from operator import itemgetter

import matplotlib.pyplot as plt
import networkx as nx

if __name__ == '__main__':
    # Create a BA model graph
    n = 1000
    m = 2
    G = nx.generators.barabasi_albert_graph(n, m)
    # find node with largest degree
    node_and_degree = G.degree()
    (largest_hub, degree) = sorted(node_and_degree, key=itemgetter(1))[-1]
    # Create ego graph of main hub
    hub_ego = nx.ego_graph(G, largest_hub)
    # Draw graph
    pos = nx.spring_layout(hub_ego)
    nx.draw(hub_ego, pos, node_color='b', node_size=50, with_labels=False)
    # Draw ego as large and red
    nx.draw_networkx_nodes(hub_ego, pos, nodelist=[largest_hub], node_size=300, node_color='r')
    plt.show()

Total running time of the script: ( 0 minutes 0.110 seconds)

Generated by Sphinx-Gallery

Degree histogram

Draw degree histogram with matplotlib. Random graph shown as inset

_images/sphx_glr_plot_degree_histogram_001.png
import collections
import matplotlib.pyplot as plt
import networkx as nx

G = nx.gnp_random_graph(100, 0.02)

degree_sequence = sorted([d for n, d in G.degree()], reverse=True)  # degree sequence
# print "Degree sequence", degree_sequence
degreeCount = collections.Counter(degree_sequence)
deg, cnt = zip(*degreeCount.items())

fig, ax = plt.subplots()
plt.bar(deg, cnt, width=0.80, color='b')

plt.title("Degree Histogram")
plt.ylabel("Count")
plt.xlabel("Degree")
ax.set_xticks([d + 0.4 for d in deg])
ax.set_xticklabels(deg)

# draw graph in inset
plt.axes([0.4, 0.4, 0.5, 0.5])
Gcc = sorted(nx.connected_component_subgraphs(G), key=len, reverse=True)[0]
pos = nx.spring_layout(G)
plt.axis('off')
nx.draw_networkx_nodes(G, pos, node_size=20)
nx.draw_networkx_edges(G, pos, alpha=0.4)

plt.show()

Total running time of the script: ( 0 minutes 0.202 seconds)

Generated by Sphinx-Gallery

Random Geometric Graph

Example

_images/sphx_glr_plot_random_geometric_graph_001.png
import matplotlib.pyplot as plt
import networkx as nx

G = nx.random_geometric_graph(200, 0.125)
# position is stored as node attribute data for random_geometric_graph
pos = nx.get_node_attributes(G, 'pos')

# find node near center (0.5,0.5)
dmin = 1
ncenter = 0
for n in pos:
    x, y = pos[n]
    d = (x - 0.5)**2 + (y - 0.5)**2
    if d < dmin:
        ncenter = n
        dmin = d

# color by path length from node near center
p = dict(nx.single_source_shortest_path_length(G, ncenter))

plt.figure(figsize=(8, 8))
nx.draw_networkx_edges(G, pos, nodelist=[ncenter], alpha=0.4)
nx.draw_networkx_nodes(G, pos, nodelist=p.keys(),
                       node_size=80,
                       node_color=p.values(),
                       cmap=plt.cm.Reds_r)

plt.xlim(-0.05, 1.05)
plt.ylim(-0.05, 1.05)
plt.axis('off')
plt.show()

Total running time of the script: ( 0 minutes 0.110 seconds)

Generated by Sphinx-Gallery

Weighted Graph

An example using Graph as a weighted network.

_images/sphx_glr_plot_weighted_graph_001.png
# Author: Aric Hagberg (hagberg@lanl.gov)
import matplotlib.pyplot as plt
import networkx as nx

G = nx.Graph()

G.add_edge('a', 'b', weight=0.6)
G.add_edge('a', 'c', weight=0.2)
G.add_edge('c', 'd', weight=0.1)
G.add_edge('c', 'e', weight=0.7)
G.add_edge('c', 'f', weight=0.9)
G.add_edge('a', 'd', weight=0.3)

elarge = [(u, v) for (u, v, d) in G.edges(data=True) if d['weight'] > 0.5]
esmall = [(u, v) for (u, v, d) in G.edges(data=True) if d['weight'] <= 0.5]

pos = nx.spring_layout(G)  # positions for all nodes

# nodes
nx.draw_networkx_nodes(G, pos, node_size=700)

# edges
nx.draw_networkx_edges(G, pos, edgelist=elarge,
                       width=6)
nx.draw_networkx_edges(G, pos, edgelist=esmall,
                       width=6, alpha=0.5, edge_color='b', style='dashed')

# labels
nx.draw_networkx_labels(G, pos, font_size=20, font_family='sans-serif')

plt.axis('off')
plt.show()

Total running time of the script: ( 0 minutes 0.089 seconds)

Generated by Sphinx-Gallery

Labels And Colors

Draw a graph with matplotlib, color by degree.

You must have matplotlib for this to work.

_images/sphx_glr_plot_labels_and_colors_001.png
# Author: Aric Hagberg (hagberg@lanl.gov)
import matplotlib.pyplot as plt
import networkx as nx

G = nx.cubical_graph()
pos = nx.spring_layout(G)  # positions for all nodes

# nodes
nx.draw_networkx_nodes(G, pos,
                       nodelist=[0, 1, 2, 3],
                       node_color='r',
                       node_size=500,
                       alpha=0.8)
nx.draw_networkx_nodes(G, pos,
                       nodelist=[4, 5, 6, 7],
                       node_color='b',
                       node_size=500,
                       alpha=0.8)

# edges
nx.draw_networkx_edges(G, pos, width=1.0, alpha=0.5)
nx.draw_networkx_edges(G, pos,
                       edgelist=[(0, 1), (1, 2), (2, 3), (3, 0)],
                       width=8, alpha=0.5, edge_color='r')
nx.draw_networkx_edges(G, pos,
                       edgelist=[(4, 5), (5, 6), (6, 7), (7, 4)],
                       width=8, alpha=0.5, edge_color='b')


# some math labels
labels = {}
labels[0] = r'$a$'
labels[1] = r'$b$'
labels[2] = r'$c$'
labels[3] = r'$d$'
labels[4] = r'$\alpha$'
labels[5] = r'$\beta$'
labels[6] = r'$\gamma$'
labels[7] = r'$\delta$'
nx.draw_networkx_labels(G, pos, labels, font_size=16)

plt.axis('off')
plt.show()

Total running time of the script: ( 0 minutes 0.095 seconds)

Generated by Sphinx-Gallery

Sampson

Sampson’s monastery data.

Shows how to read data from a zip file and plot multiple frames.

_images/sphx_glr_plot_sampson_001.png
# Author: Aric Hagberg (hagberg@lanl.gov)

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

import zipfile
import cStringIO

import matplotlib.pyplot as plt
import networkx as nx

zf = zipfile.ZipFile('sampson_data.zip')  # zipfile object
e1 = cStringIO.StringIO(zf.read('samplike1.txt'))  # read info file
e2 = cStringIO.StringIO(zf.read('samplike2.txt'))  # read info file
e3 = cStringIO.StringIO(zf.read('samplike3.txt'))  # read info file
G1 = nx.read_edgelist(e1, delimiter='\t')
G2 = nx.read_edgelist(e2, delimiter='\t')
G3 = nx.read_edgelist(e3, delimiter='\t')
pos = nx.spring_layout(G3, iterations=100)
plt.clf()

plt.subplot(221)
plt.title('samplike1')
nx.draw(G1, pos, node_size=50, with_labels=False)
plt.subplot(222)
plt.title('samplike2')
nx.draw(G2, pos, node_size=50, with_labels=False)
plt.subplot(223)
plt.title('samplike3')
nx.draw(G3, pos, node_size=50, with_labels=False)
plt.subplot(224)
plt.title('samplike1,2,3')
nx.draw(G3, pos, edgelist=list(G3.edges()), node_size=50, with_labels=False)
nx.draw_networkx_edges(G1, pos, alpha=0.25)
nx.draw_networkx_edges(G2, pos, alpha=0.25)
plt.show()

Total running time of the script: ( 0 minutes 0.334 seconds)

Generated by Sphinx-Gallery

Unix Email

Create a directed graph, allowing multiple edges and self loops, from a unix mailbox. The nodes are email addresses with links that point from the sender to the recievers. The edge data is a Python email.Message object which contains all of the email message data.

This example shows the power of DiGraph to hold edge data of arbitrary Python objects (in this case a list of email messages).

The sample unix email mailbox called “unix_email.mbox” may be found here: https://raw.githubusercontent.com/networkx/networkx/master/examples/drawing/unix_email.mbox

_images/sphx_glr_plot_unix_email_001.png

Out:

From: ted@com To: carol@gov Subject: get together for lunch to discuss Networks?
From: ted@com To: alice@edu Subject: get together for lunch to discuss Networks?
From: ted@com To: bob@gov Subject: Graph package in Python?
From: ted@com To: bob@gov Subject: get together for lunch to discuss Networks?
From: alice@edu To: bob@gov Subject: NetworkX
From: bob@gov To: ted@com Subject: Re: Graph package in Python?
From: bob@gov To: alice@edu Subject: Re: NetworkX

# Author: Aric Hagberg (hagberg@lanl.gov)

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

import email
from email.utils import getaddresses, parseaddr
import mailbox
import sys

import matplotlib.pyplot as plt
import networkx as nx

# unix mailbox recipe
# see http://www.python.org/doc/current/lib/module-mailbox.html

def mbox_graph():
    try:
        fh = open("unix_email.mbox", 'rb')
    except IOError:
        print("unix_email.mbox not found")
        raise

    mbox = mailbox.UnixMailbox(fh, email.message_from_file)  # parse unix mailbox

    G = nx.MultiDiGraph()  # create empty graph

    # parse each messages and build graph
    for msg in mbox:  # msg is python email.Message.Message object
        (source_name, source_addr) = parseaddr(msg['From'])  # sender
        # get all recipients
        # see http://www.python.org/doc/current/lib/module-email.Utils.html
        tos = msg.get_all('to', [])
        ccs = msg.get_all('cc', [])
        resent_tos = msg.get_all('resent-to', [])
        resent_ccs = msg.get_all('resent-cc', [])
        all_recipients = getaddresses(tos + ccs + resent_tos + resent_ccs)
        # now add the edges for this mail message
        for (target_name, target_addr) in all_recipients:
            G.add_edge(source_addr, target_addr, message=msg)

    return G

if __name__ == '__main__':

    G = mbox_graph()

    # print edges with message subject
    for (u, v, d) in G.edges(data=True):
        print("From: %s To: %s Subject: %s" % (u, v, d['message']["Subject"]))

    pos = nx.spring_layout(G, iterations=10)
    nx.draw(G, pos, node_size=0, alpha=0.4, edge_color='r', font_size=16, with_labels=True)
    plt.show()

Total running time of the script: ( 0 minutes 0.097 seconds)

Generated by Sphinx-Gallery

Lanl Routes

Routes to LANL from 186 sites on the Internet.

This uses Graphviz for layout so you need PyGraphviz or pydot.

_images/sphx_glr_plot_lanl_routes_001.png

Out:

graph has 1281 nodes with 1296 edges
1 connected components

# Author: Aric Hagberg (hagberg@lanl.gov)

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


import matplotlib.pyplot as plt
import networkx as nx
try:
    import pygraphviz
    from networkx.drawing.nx_agraph import graphviz_layout
except ImportError:
    try:
        import pydot
        from networkx.drawing.nx_pydot import graphviz_layout
    except ImportError:
        raise ImportError("This example needs Graphviz and either "
                          "PyGraphviz or pydot")

def lanl_graph():
    """ Return the lanl internet view graph from lanl.edges
    """
    try:
        fh = open('lanl_routes.edgelist', 'r')
    except IOError:
        print("lanl.edges not found")
        raise

    G = nx.Graph()

    time = {}
    time[0] = 0  # assign 0 to center node
    for line in fh.readlines():
        (head, tail, rtt) = line.split()
        G.add_edge(int(head), int(tail))
        time[int(head)] = float(rtt)

    # get largest component and assign ping times to G0time dictionary
    G0 = sorted(nx.connected_component_subgraphs(G), key=len, reverse=True)[0]
    G0.rtt = {}
    for n in G0:
        G0.rtt[n] = time[n]

    return G0


if __name__ == '__main__':

    G = lanl_graph()

    print("graph has %d nodes with %d edges"
          % (nx.number_of_nodes(G), nx.number_of_edges(G)))
    print(nx.number_connected_components(G), "connected components")

    plt.figure(figsize=(8, 8))
    # use graphviz to find radial layout
    pos = graphviz_layout(G, prog="twopi", root=0)
    # draw nodes, coloring by rtt ping time
    nx.draw(G, pos,
            node_color=[G.rtt[v] for v in G],
            with_labels=False,
            alpha=0.5,
            node_size=15)
    # adjust the plot limits
    xmax = 1.02 * max(xx for xx, yy in pos.values())
    ymax = 1.02 * max(yy for xx, yy in pos.values())
    plt.xlim(0, xmax)
    plt.ylim(0, ymax)
    plt.show()

Total running time of the script: ( 0 minutes 0.486 seconds)

Generated by Sphinx-Gallery

Giant Component

This example illustrates the sudden appearance of a giant connected component in a binomial random graph.

_images/sphx_glr_plot_giant_component_001.png
#    Copyright (C) 2006-2016
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.

import math

import matplotlib.pyplot as plt
import networkx as nx

try:
    import pygraphviz
    from networkx.drawing.nx_agraph import graphviz_layout
    layout = graphviz_layout
except ImportError:
    try:
        import pydot
        from networkx.drawing.nx_pydot import graphviz_layout
        layout = graphviz_layout
    except ImportError:
        print("PyGraphviz and pydot not found;\n"
              "drawing with spring layout;\n"
              "will be slow.")
        layout = nx.spring_layout


n = 150  # 150 nodes
# p value at which giant component (of size log(n) nodes) is expected
p_giant = 1.0 / (n - 1)
# p value at which graph is expected to become completely connected
p_conn = math.log(n) / float(n)

# the following range of p values should be close to the threshold
pvals = [0.003, 0.006, 0.008, 0.015]

region = 220  # for pylab 2x2 subplot layout
plt.subplots_adjust(left=0, right=1, bottom=0, top=0.95, wspace=0.01, hspace=0.01)
for p in pvals:
    G = nx.binomial_graph(n, p)
    pos = layout(G)
    region += 1
    plt.subplot(region)
    plt.title("p = %6.3f" % (p))
    nx.draw(G, pos,
            with_labels=False,
            node_size=10
           )
    # identify largest connected component
    Gcc = sorted(nx.connected_component_subgraphs(G), key=len, reverse=True)
    G0 = Gcc[0]
    nx.draw_networkx_edges(G0, pos,
                           with_labels=False,
                           edge_color='r',
                           width=6.0
                          )
    # show other connected components
    for Gi in Gcc[1:]:
        if len(Gi) > 1:
            nx.draw_networkx_edges(Gi, pos,
                                   with_labels=False,
                                   edge_color='r',
                                   alpha=0.3,
                                   width=5.0
                                  )
plt.show()

Total running time of the script: ( 0 minutes 1.085 seconds)

Generated by Sphinx-Gallery

Knuth Miles

miles_graph() returns an undirected graph over the 128 US cities from the datafile miles_dat.txt. The cities each have location and population data. The edges are labeled with the distance betwen the two cities.

This example is described in Section 1.1 in Knuth’s book (see [1] and [2]).

References.
[1]Donald E. Knuth, “The Stanford GraphBase: A Platform for Combinatorial Computing”, ACM Press, New York, 1993.
[2]http://www-cs-faculty.stanford.edu/~knuth/sgb.html
_images/sphx_glr_plot_knuth_miles_001.png

Out:

Loaded miles_dat.txt containing 128 cities.
digraph has 128 nodes with 8128 edges

# Author: Aric Hagberg (hagberg@lanl.gov)

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

import re
import sys

import matplotlib.pyplot as plt
import networkx as nx


def miles_graph():
    """ Return the cites example graph in miles_dat.txt
        from the Stanford GraphBase.
    """
    # open file miles_dat.txt.gz (or miles_dat.txt)
    import gzip
    fh = gzip.open('knuth_miles.txt.gz', 'r')

    G = nx.Graph()
    G.position = {}
    G.population = {}

    cities = []
    for line in fh.readlines():
        line = line.decode()
        if line.startswith("*"):  # skip comments
            continue

        numfind = re.compile("^\d+")

        if numfind.match(line):  # this line is distances
            dist = line.split()
            for d in dist:
                G.add_edge(city, cities[i], weight=int(d))
                i = i + 1
        else:  # this line is a city, position, population
            i = 1
            (city, coordpop) = line.split("[")
            cities.insert(0, city)
            (coord, pop) = coordpop.split("]")
            (y, x) = coord.split(",")

            G.add_node(city)
            # assign position - flip x axis for matplotlib, shift origin
            G.position[city] = (-int(x) + 7500, int(y) - 3000)
            G.population[city] = float(pop) / 1000.0
    return G


if __name__ == '__main__':

    G = miles_graph()

    print("Loaded miles_dat.txt containing 128 cities.")
    print("digraph has %d nodes with %d edges"
          % (nx.number_of_nodes(G), nx.number_of_edges(G)))

    # make new graph of cites, edge if less then 300 miles between them
    H = nx.Graph()
    for v in G:
        H.add_node(v)
    for (u, v, d) in G.edges(data=True):
        if d['weight'] < 300:
            H.add_edge(u, v)

    # draw with matplotlib/pylab
    plt.figure(figsize=(8, 8))
    # with nodes colored by degree sized by population
    node_color = [float(H.degree(v)) for v in H]
    nx.draw(H, G.position,
            node_size=[G.population[v] for v in H],
            node_color=node_color,
            with_labels=False)

    # scale the axes equally
    plt.xlim(-5000, 500)
    plt.ylim(-2000, 3500)

    plt.show()

Total running time of the script: ( 0 minutes 0.134 seconds)

Generated by Sphinx-Gallery

Atlas

Atlas of all graphs of 6 nodes or less.

_images/sphx_glr_plot_atlas_001.png

Out:

graph has 779 nodes with 1073 edges
137 connected components

# Author: Aric Hagberg (hagberg@lanl.gov)

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

import random

try:
    import pygraphviz
    from networkx.drawing.nx_agraph import graphviz_layout
except ImportError:
    try:
        import pydot
        from networkx.drawing.nx_pydot import graphviz_layout
    except ImportError:
        raise ImportError("This example needs Graphviz and either "
                          "PyGraphviz or pydot.")

import matplotlib.pyplot as plt

import networkx as nx
from networkx.algorithms.isomorphism.isomorph import graph_could_be_isomorphic as isomorphic
from networkx.generators.atlas import graph_atlas_g


def atlas6():
    """ Return the atlas of all connected graphs of 6 nodes or less.
        Attempt to check for isomorphisms and remove.
    """

    Atlas = graph_atlas_g()[0:208]  # 208
    # remove isolated nodes, only connected graphs are left
    U = nx.Graph()  # graph for union of all graphs in atlas
    for G in Atlas:
        zerodegree = [n for n in G if G.degree(n) == 0]
        for n in zerodegree:
            G.remove_node(n)
        U = nx.disjoint_union(U, G)

    # list of graphs of all connected components
    C = nx.connected_component_subgraphs(U)

    UU = nx.Graph()
    # do quick isomorphic-like check, not a true isomorphism checker
    nlist = []  # list of nonisomorphic graphs
    for G in C:
        # check against all nonisomorphic graphs so far
        if not iso(G, nlist):
            nlist.append(G)
            UU = nx.disjoint_union(UU, G)  # union the nonisomorphic graphs
    return UU


def iso(G1, glist):
    """Quick and dirty nonisomorphism checker used to check isomorphisms."""
    for G2 in glist:
        if isomorphic(G1, G2):
            return True
    return False


if __name__ == '__main__':
    G = atlas6()

    print("graph has %d nodes with %d edges"
          % (nx.number_of_nodes(G), nx.number_of_edges(G)))
    print(nx.number_connected_components(G), "connected components")

    plt.figure(1, figsize=(8, 8))
    # layout graphs with positions using graphviz neato
    pos = graphviz_layout(G, prog="neato")
    # color nodes the same in each connected subgraph
    C = nx.connected_component_subgraphs(G)
    for g in C:
        c = [random.random()] * nx.number_of_nodes(g)  # random color...
        nx.draw(g,
                pos,
                node_size=40,
                node_color=c,
                vmin=0.0,
                vmax=1.0,
                with_labels=False
               )
    plt.show()

Total running time of the script: ( 0 minutes 7.738 seconds)

Generated by Sphinx-Gallery

Chess Masters

An example of the MultiDiGraph clas

The function chess_pgn_graph reads a collection of chess matches stored in the specified PGN file (PGN =”Portable Game Notation”). Here the (compressed) default file:

chess_masters_WCC.pgn.bz2

contains all 685 World Chess Championship matches from 1886–1985. (data from http://chessproblem.my-free-games.com/chess/games/Download-PGN.php)

The chess_pgn_graph() function returns a MultiDiGraph with multiple edges. Each node is the last name of a chess master. Each edge is directed from white to black and contains selected game info.

The key statement in chess_pgn_graph below is:

G.add_edge(white, black, game_info)

where game_info is a dict describing each game.

_images/sphx_glr_plot_chess_masters_001.png

Out:

Loaded 685 chess games between 25 players

Note the disconnected component consisting of:
NodeView((u'Karpov, Anatoly', u'Korchnoi, Viktor L', u'Kasparov, Gary'))

From a total of 237 different openings,
the following games used the Sicilian opening
with the Najdorff 7...Qb6 "Poisoned Pawn" variation.

Spassky, Boris V vs Fischer, Robert J
    ECO :  B97
    WhiteElo :  2660
    Site :  Reykjavik ISL
    BlackElo :  2785
    EventDate :  1972.07.11
    Result :  1/2-1/2
    Date :  1972.07.25
    Round :  7
    Event :  World Championship 28th


Spassky, Boris V vs Fischer, Robert J
    ECO :  B97
    WhiteElo :  2660
    Site :  Reykjavik ISL
    BlackElo :  2785
    EventDate :  1972.07.11
    Result :  1-0
    Date :  1972.08.06
    Round :  11
    Event :  World Championship 28th

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

import matplotlib.pyplot as plt
import networkx as nx

# tag names specifying what game info should be
# stored in the dict on each digraph edge
game_details = ["Event",
                "Date",
                "Result",
                "ECO",
                "Site"]


def chess_pgn_graph(pgn_file="chess_masters_WCC.pgn.bz2"):
    """Read chess games in pgn format in pgn_file.

    Filenames ending in .gz or .bz2 will be uncompressed.

    Return the MultiDiGraph of players connected by a chess game.
    Edges contain game data in a dict.

    """
    import bz2
    G = nx.MultiDiGraph()
    game = {}
    datafile = bz2.BZ2File(pgn_file)
    lines = (line.decode().rstrip('\r\n') for line in datafile)
    for line in lines:
        if line.startswith('['):
            tag, value = line[1:-1].split(' ', 1)
            game[str(tag)] = value.strip('"')
        else:
            # empty line after tag set indicates
            # we finished reading game info
            if game:
                white = game.pop('White')
                black = game.pop('Black')
                G.add_edge(white, black, **game)
                game = {}
    return G


if __name__ == '__main__':
    G = chess_pgn_graph()

    ngames = G.number_of_edges()
    nplayers = G.number_of_nodes()

    print("Loaded %d chess games between %d players\n"
          % (ngames, nplayers))

    # identify connected components
    # of the undirected version
    Gcc = list(nx.connected_component_subgraphs(G.to_undirected()))
    if len(Gcc) > 1:
        print("Note the disconnected component consisting of:")
        print(Gcc[1].nodes())

    # find all games with B97 opening (as described in ECO)
    openings = set([game_info['ECO']
                    for (white, black, game_info) in G.edges(data=True)])
    print("\nFrom a total of %d different openings," % len(openings))
    print('the following games used the Sicilian opening')
    print('with the Najdorff 7...Qb6 "Poisoned Pawn" variation.\n')

    for (white, black, game_info) in G.edges(data=True):
        if game_info['ECO'] == 'B97':
            print(white, "vs", black)
            for k, v in game_info.items():
                print("   ", k, ": ", v)
            print("\n")

    # make new undirected graph H without multi-edges
    H = nx.Graph(G)

    # edge width is proportional number of games played
    edgewidth = []
    for (u, v, d) in H.edges(data=True):
        edgewidth.append(len(G.get_edge_data(u, v)))

    # node size is proportional to number of games won
    wins = dict.fromkeys(G.nodes(), 0.0)
    for (u, v, d) in G.edges(data=True):
        r = d['Result'].split('-')
        if r[0] == '1':
            wins[u] += 1.0
        elif r[0] == '1/2':
            wins[u] += 0.5
            wins[v] += 0.5
        else:
            wins[v] += 1.0
    try:
        pos = nx.nx_agraph.graphviz_layout(H)
    except:
        pos = nx.spring_layout(H, iterations=20)

    plt.rcParams['text.usetex'] = False
    plt.figure(figsize=(8, 8))
    nx.draw_networkx_edges(H, pos, alpha=0.3, width=edgewidth, edge_color='m')
    nodesize = [wins[v] * 50 for v in H]
    nx.draw_networkx_nodes(H, pos, node_size=nodesize, node_color='w', alpha=0.4)
    nx.draw_networkx_edges(H, pos, alpha=0.4, node_size=0, width=1, edge_color='k')
    nx.draw_networkx_labels(H, pos, fontsize=14)
    font = {'fontname': 'Helvetica',
            'color': 'k',
            'fontweight': 'bold',
            'fontsize': 14}
    plt.title("World Chess Championship Games: 1886 - 1985", font)

    # change font and write text (using data coordinates)
    font = {'fontname': 'Helvetica',
            'color': 'r',
            'fontweight': 'bold',
            'fontsize': 14}

    plt.text(0.5, 0.97, "edge width = # games played",
             horizontalalignment='center',
             transform=plt.gca().transAxes)
    plt.text(0.5, 0.94, "node size = # games won",
             horizontalalignment='center',
             transform=plt.gca().transAxes)

    plt.axis('off')
    plt.show()

Total running time of the script: ( 0 minutes 0.263 seconds)

Generated by Sphinx-Gallery

Graph

Karate Club

Zachary’s Karate Club graph

Data file from: http://vlado.fmf.uni-lj.si/pub/networks/data/Ucinet/UciData.htm

Reference: Zachary W. (1977). An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33, 452-473.

_images/sphx_glr_plot_karate_club_001.png

Out:

Node Degree
0 16
1 9
2 10
3 6
4 3
5 4
6 4
7 4
8 5
9 2
10 3
11 1
12 2
13 5
14 2
15 2
16 2
17 2
18 2
19 3
20 2
21 2
22 2
23 5
24 3
25 3
26 2
27 4
28 3
29 4
30 4
31 6
32 12
33 17

import matplotlib.pyplot as plt
import networkx as nx

G = nx.karate_club_graph()
print("Node Degree")
for v in G:
    print('%s %s' % (v, G.degree(v)))

nx.draw_circular(G, with_labels=True)
plt.show()

Total running time of the script: ( 0 minutes 0.093 seconds)

Generated by Sphinx-Gallery

Erdos Renyi

Create an G{n,m} random graph with n nodes and m edges and report some properties.

This graph is sometimes called the Erdős-Rényi graph but is different from G{n,p} or binomial_graph which is also sometimes called the Erdős-Rényi graph.

_images/sphx_glr_plot_erdos_renyi_001.png

Out:

node degree clustering
0 5 0.300000
1 2 0.000000
2 3 0.666667
3 2 1.000000
4 4 0.666667
5 4 0.333333
6 6 0.466667
7 4 0.166667
8 4 0.666667
9 6 0.200000
#/home/docs/checkouts/readthedocs.org/user_builds/mriduls-networkx/envs/latest/bin/sphinx-build -T -E -b readthedocs -d _build/doctrees-readthedocs -D language=en . _build/html
# GMT Mon Jul 24 19:34:02 2017
# gnm_random_graph(10,20)
0 8 1 4 6 7
1 9
2 9 5 6
3 9 7
4 8 5 6
5 6 7
6 8 9
7 9
8 9
9

# Author: Aric Hagberg (hagberg@lanl.gov)

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

import sys

import matplotlib.pyplot as plt
from networkx import nx

n = 10  # 10 nodes
m = 20  # 20 edges

G = nx.gnm_random_graph(n, m)

# some properties
print("node degree clustering")
for v in nx.nodes(G):
    print('%s %d %f' % (v, nx.degree(G, v), nx.clustering(G, v)))

# print the adjacency list to terminal
try:
    nx.write_adjlist(G, sys.stdout)
except TypeError:  # Python 3.x
    nx.write_adjlist(G, sys.stdout.buffer)

nx.draw(G)
plt.show()

Total running time of the script: ( 0 minutes 0.084 seconds)

Generated by Sphinx-Gallery

Expected Degree Sequence

Random graph from given degree sequence.

# Author: Aric Hagberg (hagberg@lanl.gov)

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

import networkx as nx
from networkx.generators.degree_seq import expected_degree_graph

# make a random graph of 500 nodes with expected degrees of 50
n = 500  # n nodes
p = 0.1
w = [p * n for i in range(n)]  # w = p*n for all nodes
G = expected_degree_graph(w)  # configuration model
print("Degree histogram")
print("degree (#nodes) ****")
dh = nx.degree_histogram(G)
low = min(nx.degree(G))
for i in range(low, len(dh)):
    bar = ''.join(dh[i] * ['*'])
    print("%2s (%2s) %s" % (i, dh[i], bar))

Total running time of the script: ( 0 minutes 0.000 seconds)

Generated by Sphinx-Gallery

Atlas2

Write first 20 graphs from the graph atlas as graphviz dot files Gn.dot where n=0,19.

# Author: Aric Hagberg (hagberg@lanl.gov)
# Date: 2005-05-19 14:23:02 -0600 (Thu, 19 May 2005)

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

import networkx as nx
from networkx.generators.atlas import graph_atlas_g

atlas = graph_atlas_g()[0:20]

for G in atlas:
    print("graph %s has %d nodes with %d edges"
          % (G.name, nx.number_of_nodes(G), nx.number_of_edges(G)))
    A = nx.nx_agraph.to_agraph(G)
    A.graph_attr['label'] = G.name
    # set default node attributes
    A.node_attr['color'] = 'red'
    A.node_attr['style'] = 'filled'
    A.node_attr['shape'] = 'circle'
    A.write(G.name + '.dot')

Total running time of the script: ( 0 minutes 0.000 seconds)

Generated by Sphinx-Gallery

Degree Sequence

Random graph from given degree sequence.

_images/sphx_glr_plot_degree_sequence_001.png

Out:

True
Configuration model
Degree sequence [5, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1]
Degree histogram
degree #nodes
1 3
2 3
3 4
5 1

# Author: Aric Hagberg (hagberg@lanl.gov)
# Date: 2004-11-03 08:11:09 -0700 (Wed, 03 Nov 2004)
# Revision: 503

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

import matplotlib.pyplot as plt
from networkx import nx

z = [5, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1]
print(nx.is_valid_degree_sequence(z))

print("Configuration model")
G = nx.configuration_model(z)  # configuration model
degree_sequence = [d for n, d in G.degree()]  # degree sequence
print("Degree sequence %s" % degree_sequence)
print("Degree histogram")
hist = {}
for d in degree_sequence:
    if d in hist:
        hist[d] += 1
    else:
        hist[d] = 1
print("degree #nodes")
for d in hist:
    print('%d %d' % (d, hist[d]))

nx.draw(G)
plt.show()

Total running time of the script: ( 0 minutes 0.170 seconds)

Generated by Sphinx-Gallery

Football

Load football network in GML format and compute some network statistcs.

Shows how to download GML graph in a zipped file, unpack it, and load into a NetworkX graph.

Requires Internet connection to download the URL http://www-personal.umich.edu/~mejn/netdata/football.zip

_images/sphx_glr_plot_football_001.png

Out:

The file football.gml contains the network of American football games
between Division IA colleges during regular season Fall 2000, as compiled
by M. Girvan and M. Newman.  The nodes have values that indicate to which
conferences they belong.  The values are as follows:

  0 = Atlantic Coast
  1 = Big East
  2 = Big Ten
  3 = Big Twelve
  4 = Conference USA
  5 = Independents
  6 = Mid-American
  7 = Mountain West
  8 = Pacific Ten
  9 = Southeastern
 10 = Sun Belt
 11 = Western Athletic

If you make use of these data, please cite M. Girvan and M. E. J. Newman,
Community structure in social and biological networks,
Proc. Natl. Acad. Sci. USA 99, 7821-7826 (2002).

Correction: Two edges were erroneously duplicated in this data set, and
have been removed (21 SEP 2014)

Mississippi 11
OregonState 10
NotreDame 11
Wyoming 11
Minnesota 11
Illinois 11
Kent 10
Toledo 9
Indiana 11
TexasChristian 11
Texas 11
BostonCollege 11
MississippiState 11
Tulsa 12
Kansas 10
SouthernMethodist 12
Connecticut 7
Tulane 11
PennState 12
FresnoState 11
Clemson 10
LouisianaState 10
CentralFlorida 8
Cincinnati 11
Missouri 10
Washington 11
OklahomaState 10
Marshall 10
IowaState 11
Army 11
LouisianaTech 10
AlabamaBirmingham 10
UCLA 11
MiddleTennesseeState 9
Maryland 11
Rice 11
SanJoseState 11
NorthCarolinaState 11
Arizona 11
Iowa 12
Pittsburgh 11
Michigan 11
Stanford 11
Oregon 11
Syracuse 11
SouthernCalifornia 12
Northwestern 11
SanDiegoState 11
Florida 11
BowlingGreenState 11
NewMexicoState 11
Baylor 10
MichiganState 11
Ohio 10
Buffalo 11
SouthernMississippi 10
WashingtonState 11
BoiseState 9
WakeForest 10
NorthernIllinois 10
KansasState 12
WesternMichigan 10
Navy 11
VirginiaTech 11
UtahState 9
Oklahoma 11
GeorgiaTech 11
Louisville 10
Arkansas 10
Temple 11
BallState 10
Vanderbilt 11
LouisianaLafayette 8
California 11
ColoradoState 10
Akron 11
Memphis 11
Georgia 10
TexasA&M 11
FloridaState 12
Rutgers 10
NevadaLasVegas 12
Duke 11
LouisianaMonroe 8
Colorado 11
ArizonaState 11
BrighamYoung 12
MiamiOhio 11
Auburn 11
Nevada 12
ArkansasState 10
EasternMichigan 11
SouthCarolina 11
MiamiFlorida 10
Idaho 9
OhioState 11
Utah 11
Virginia 10
TexasElPaso 11
TexasTech 12
NewMexico 11
CentralMichigan 11
Purdue 11
EastCarolina 11
NorthCarolina 11
Hawaii 11
Kentucky 10
Nebraska 11
WestVirginia 11
Wisconsin 12
Alabama 11
Houston 11
NorthTexas 10
AirForce 10
Tennessee 11

# Author: Aric Hagberg (hagberg@lanl.gov)

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

try:  # Python 3.x
    import urllib.request as urllib
except ImportError:  # Python 2.x
    import urllib
import io
import zipfile

import matplotlib.pyplot as plt
import networkx as nx

url = "http://www-personal.umich.edu/~mejn/netdata/football.zip"

sock = urllib.urlopen(url)  # open URL
s = io.BytesIO(sock.read())  # read into BytesIO "file"
sock.close()

zf = zipfile.ZipFile(s)  # zipfile object
txt = zf.read('football.txt').decode()  # read info file
gml = zf.read('football.gml').decode()  # read gml data
# throw away bogus first line with # from mejn files
gml = gml.split('\n')[1:]
G = nx.parse_gml(gml)  # parse gml data

print(txt)
# print degree for each team - number of games
for n, d in G.degree():
    print('%s %d' % (n, d))

nx.draw(G)
plt.show()

Total running time of the script: ( 0 minutes 0.287 seconds)

Generated by Sphinx-Gallery

Roget

Build a directed graph of 1022 categories and 5075 cross-references as defined in the 1879 version of Roget’s Thesaurus contained in the datafile roget_dat.txt. This example is described in Section 1.2 in Knuth’s book (see [1] and [2]).

Note that one of the 5075 cross references is a self loop yet it is included in the graph built here because the standard networkx DiGraph class allows self loops. (cf. 400pungency:400 401 403 405).

References
[1]Donald E. Knuth, “The Stanford GraphBase: A Platform for Combinatorial Computing”, ACM Press, New York, 1993.
[2]http://www-cs-faculty.stanford.edu/~knuth/sgb.html
_images/sphx_glr_plot_roget_001.png

Out:

Loaded roget_dat.txt containing 1022 categories.
digraph has 1022 nodes with 5075 edges
21 connected components

from __future__ import print_function

# Authors: Brendt Wohlberg, Aric Hagberg (hagberg@lanl.gov)
# Date: 2005-04-01 07:56:22 -0700 (Fri, 01 Apr 2005)

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

import gzip
import re
import sys

import matplotlib.pyplot as plt
from networkx import nx

def roget_graph():
    """ Return the thesaurus graph from the roget.dat example in
    the Stanford Graph Base.
    """
    # open file roget_dat.txt.gz (or roget_dat.txt)
    fh = gzip.open('roget_dat.txt.gz', 'r')

    G = nx.DiGraph()

    for line in fh.readlines():
        line = line.decode()
        if line.startswith("*"):  # skip comments
            continue
        if line.startswith(" "):  # this is a continuation line, append
            line = oldline + line
        if line.endswith("\\\n"):  # continuation line, buffer, goto next
            oldline = line.strip("\\\n")
            continue

        (headname, tails) = line.split(":")

        # head
        numfind = re.compile("^\d+")  # re to find the number of this word
        head = numfind.findall(headname)[0]  # get the number

        G.add_node(head)

        for tail in tails.split():
            if head == tail:
                print("skipping self loop", head, tail, file=sys.stderr)
            G.add_edge(head, tail)

    return G


if __name__ == '__main__':
    G = roget_graph()
    print("Loaded roget_dat.txt containing 1022 categories.")
    print("digraph has %d nodes with %d edges"
          % (nx.number_of_nodes(G), nx.number_of_edges(G)))
    UG = G.to_undirected()
    print(nx.number_connected_components(UG), "connected components")

    nx.draw_circular(UG)
    plt.show()

Total running time of the script: ( 0 minutes 0.260 seconds)

Generated by Sphinx-Gallery

Words
Words/Ladder Graph

Generate an undirected graph over the 5757 5-letter words in the datafile words_dat.txt.gz. Two words are connected by an edge if they differ in one letter, resulting in 14,135 edges. This example is described in Section 1.1 in Knuth’s book (see [1] and [2]).

References
[1]Donald E. Knuth, “The Stanford GraphBase: A Platform for Combinatorial Computing”, ACM Press, New York, 1993.
[2]http://www-cs-faculty.stanford.edu/~knuth/sgb.html
# Authors: Aric Hagberg (hagberg@lanl.gov),
#          Brendt Wohlberg,
#          hughdbrown@yahoo.com

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

import gzip
from string import ascii_lowercase as lowercase

import networkx as nx

#-------------------------------------------------------------------
#   The Words/Ladder graph of Section 1.1
#-------------------------------------------------------------------


def generate_graph(words):
    G = nx.Graph(name="words")
    lookup = dict((c, lowercase.index(c)) for c in lowercase)

    def edit_distance_one(word):
        for i in range(len(word)):
            left, c, right = word[0:i], word[i], word[i + 1:]
            j = lookup[c]  # lowercase.index(c)
            for cc in lowercase[j + 1:]:
                yield left + cc + right
    candgen = ((word, cand) for word in sorted(words)
               for cand in edit_distance_one(word) if cand in words)
    G.add_nodes_from(words)
    for word, cand in candgen:
        G.add_edge(word, cand)
    return G


def words_graph():
    """Return the words example graph from the Stanford GraphBase"""
    fh = gzip.open('words_dat.txt.gz', 'r')
    words = set()
    for line in fh.readlines():
        line = line.decode()
        if line.startswith('*'):
            continue
        w = str(line[0:5])
        words.add(w)
    return generate_graph(words)


if __name__ == '__main__':
    G = words_graph()
    print("Loaded words_dat.txt containing 5757 five-letter English words.")
    print("Two words are connected if they differ in one letter.")
    print("Graph has %d nodes with %d edges"
          % (nx.number_of_nodes(G), nx.number_of_edges(G)))
    print("%d connected components" % nx.number_connected_components(G))

    for (source, target) in [('chaos', 'order'),
                             ('nodes', 'graph'),
                             ('pound', 'marks')]:
        print("Shortest path between %s and %s is" % (source, target))
        try:
            sp = nx.shortest_path(G, source, target)
            for n in sp:
                print(n)
        except nx.NetworkXNoPath:
            print("None")

Total running time of the script: ( 0 minutes 0.000 seconds)

Generated by Sphinx-Gallery

Napoleon Russian Campaign

Minard’s data from Napoleon’s 1812-1813 Russian Campaign. http://www.math.yorku.ca/SCS/Gallery/minard/minard.txt

_images/sphx_glr_plot_napoleon_russian_campaign_001.png
# Author: Aric Hagberg (hagberg@lanl.gov)

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

import matplotlib.pyplot as plt
import networkx as nx


def minard_graph():
    data1 = """\
24.0,54.9,340000,A,1
24.5,55.0,340000,A,1
25.5,54.5,340000,A,1
26.0,54.7,320000,A,1
27.0,54.8,300000,A,1
28.0,54.9,280000,A,1
28.5,55.0,240000,A,1
29.0,55.1,210000,A,1
30.0,55.2,180000,A,1
30.3,55.3,175000,A,1
32.0,54.8,145000,A,1
33.2,54.9,140000,A,1
34.4,55.5,127100,A,1
35.5,55.4,100000,A,1
36.0,55.5,100000,A,1
37.6,55.8,100000,A,1
37.7,55.7,100000,R,1
37.5,55.7,98000,R,1
37.0,55.0,97000,R,1
36.8,55.0,96000,R,1
35.4,55.3,87000,R,1
34.3,55.2,55000,R,1
33.3,54.8,37000,R,1
32.0,54.6,24000,R,1
30.4,54.4,20000,R,1
29.2,54.3,20000,R,1
28.5,54.2,20000,R,1
28.3,54.3,20000,R,1
27.5,54.5,20000,R,1
26.8,54.3,12000,R,1
26.4,54.4,14000,R,1
25.0,54.4,8000,R,1
24.4,54.4,4000,R,1
24.2,54.4,4000,R,1
24.1,54.4,4000,R,1"""
    data2 = """\
24.0,55.1,60000,A,2
24.5,55.2,60000,A,2
25.5,54.7,60000,A,2
26.6,55.7,40000,A,2
27.4,55.6,33000,A,2
28.7,55.5,33000,R,2
29.2,54.2,30000,R,2
28.5,54.1,30000,R,2
28.3,54.2,28000,R,2"""
    data3 = """\
24.0,55.2,22000,A,3
24.5,55.3,22000,A,3
24.6,55.8,6000,A,3
24.6,55.8,6000,R,3
24.2,54.4,6000,R,3
24.1,54.4,6000,R,3"""
    cities = """\
24.0,55.0,Kowno
25.3,54.7,Wilna
26.4,54.4,Smorgoni
26.8,54.3,Moiodexno
27.7,55.2,Gloubokoe
27.6,53.9,Minsk
28.5,54.3,Studienska
28.7,55.5,Polotzk
29.2,54.4,Bobr
30.2,55.3,Witebsk
30.4,54.5,Orscha
30.4,53.9,Mohilow
32.0,54.8,Smolensk
33.2,54.9,Dorogobouge
34.3,55.2,Wixma
34.4,55.5,Chjat
36.0,55.5,Mojaisk
37.6,55.8,Moscou
36.6,55.3,Tarantino
36.5,55.0,Malo-Jarosewii"""

    c = {}
    for line in cities.split('\n'):
        x, y, name = line.split(',')
        c[name] = (float(x), float(y))

    g = []

    for data in [data1, data2, data3]:
        G = nx.Graph()
        i = 0
        G.pos = {}  # location
        G.pop = {}  # size
        last = None
        for line in data.split('\n'):
            x, y, p, r, n = line.split(',')
            G.pos[i] = (float(x), float(y))
            G.pop[i] = int(p)
            if last is None:
                last = i
            else:
                G.add_edge(i, last, **{r: int(n)})
                last = i
            i = i + 1
        g.append(G)

    return g, c


if __name__ == "__main__":

    (g, city) = minard_graph()

    plt.figure(1, figsize=(11, 5))
    plt.clf()
    colors = ['b', 'g', 'r']
    for G in g:
        c = colors.pop(0)
        node_size = [int(G.pop[n] / 300.0) for n in G]
        nx.draw_networkx_edges(G, G.pos, edge_color=c, width=4, alpha=0.5)
        nx.draw_networkx_nodes(G, G.pos, node_size=node_size, node_color=c, alpha=0.5)
        nx.draw_networkx_nodes(G, G.pos, node_size=5, node_color='k')

    for c in city:
        x, y = city[c]
        plt.text(x, y + 0.1, c)
    plt.show()

Total running time of the script: ( 0 minutes 0.103 seconds)

Generated by Sphinx-Gallery

Javascript

Javascript

Example of writing JSON format graph data and using the D3 Javascript library to produce an HTML/Javascript drawing.

# Author: Aric Hagberg <aric.hagberg@gmail.com>

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

import flask
import networkx as nx
from networkx.readwrite import json_graph

G = nx.barbell_graph(6, 3)
# this d3 example uses the name attribute for the mouse-hover value,
# so add a name to each node
for n in G:
    G.node[n]['name'] = n
# write json formatted data
d = json_graph.node_link_data(G)  # node-link format to serialize
# write json
json.dump(d, open('force/force.json', 'w'))
print('Wrote node-link JSON data to force/force.json')

# Serve the file over http to allow for cross origin requests
app = flask.Flask(__name__, static_folder="force")

@app.route('/<path:path>')
def static_proxy(path):
    return app.send_static_file(path)

print('\nGo to http://localhost:8000/force.html to see the example\n')
app.run(port=8000)

Total running time of the script: ( 0 minutes 0.000 seconds)

Generated by Sphinx-Gallery

JIT

Rgraph

An example showing how to use the JavaScript InfoVis Toolkit (JIT) JSON export

See the JIT documentation and examples at http://thejit.org

_images/sphx_glr_plot_rgraph_001.png

Out:

[
    {
        "data": {},
        "id": "solo",
        "name": "solo"
    },
    {
        "adjacencies": [
            {
                "nodeTo": "two",
                "data": {
                    "type": "extra special"
                }
            }
        ],
        "data": {},
        "id": 3,
        "name": 3
    },
    {
        "adjacencies": [
            {
                "nodeTo": 3,
                "data": {
                    "type": "extra special"
                }
            },
            {
                "nodeTo": "one",
                "data": {}
            }
        ],
        "data": {
            "type": "special"
        },
        "id": "two",
        "name": "two"
    },
    {
        "adjacencies": [
            {
                "nodeTo": "two",
                "data": {}
            }
        ],
        "data": {
            "type": "normal"
        },
        "id": "one",
        "name": "one"
    }
]
Nodes: [(u'solo', {}), (3, {}), (u'two', {u'type': u'special'}), (u'one', {u'type': u'normal'})]
Edges: [(3, u'two', {u'type': u'extra special'}), (u'two', u'one', {})]

__author__ = """Ollie Glass (ollieglaskovik@gmail.com)"""

import json

import matplotlib.pyplot as plt
import networkx as nx
from networkx.readwrite.json_graph import jit_data, jit_graph

# add some nodes to a graph
G = nx.Graph()

G.add_node("one", type="normal")
G.add_node("two", type="special")
G.add_node("solo")

# add edges
G.add_edge("one", "two")
G.add_edge("two", 3, type="extra special")

# convert to JIT JSON
jit_json = jit_data(G, indent=4)
print(jit_json)

X = jit_graph(json.loads(jit_json))
print("Nodes: %s" % list(X.nodes(data=True)))
print("Edges: %s" % list(X.edges(data=True)))

nx.draw(G, with_labels=True)
plt.show()

Total running time of the script: ( 0 minutes 0.154 seconds)

Generated by Sphinx-Gallery

Pygraphviz

Pygraphviz Draw

An example showing how to use the interface to the pygraphviz AGraph class to draw a graph.

Also see the pygraphviz documentation and examples at http://pygraphviz.github.io/

# Author: Aric Hagberg (hagberg@lanl.gov)

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

import networkx as nx

# plain graph

G = nx.complete_graph(5)   # start with K5 in networkx
A = nx.nx_agraph.to_agraph(G)        # convert to a graphviz graph
A.layout()            # neato layout
A.draw("k5.ps")       # write postscript in k5.ps with neato layout

Total running time of the script: ( 0 minutes 0.000 seconds)

Generated by Sphinx-Gallery

Pygraphviz Simple

An example showing how to use the interface to the pygraphviz AGraph class to convert to and from graphviz.

Also see the pygraphviz documentation and examples at http://pygraphviz.github.io/

# Author: Aric Hagberg (hagberg@lanl.gov)

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

import networkx as nx

# plain graph

G = nx.complete_graph(5)   # start with K5 in networkx
A = nx.nx_agraph.to_agraph(G)        # convert to a graphviz graph
X1 = nx.nx_agraph.from_agraph(A)     # convert back to networkx (but as Graph)
X2 = nx.Graph(A)          # fancy way to do conversion
G1 = nx.Graph(X1)          # now make it a Graph

A.write('k5.dot')     # write to dot file
X3 = nx.nx_agraph.read_dot('k5.dot')  # read from dotfile

Total running time of the script: ( 0 minutes 0.000 seconds)

Generated by Sphinx-Gallery

Pygraphviz Attributes

An example showing how to use the interface to the pygraphviz AGraph class to convert to and from graphviz.

Also see the pygraphviz documentation and examples at http://pygraphviz.github.io/

# Author: Aric Hagberg (hagberg@lanl.gov)

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

import networkx as nx

# networkx graph
G = nx.Graph()
# ad edges with red color
G.add_edge(1, 2, color='red')
G.add_edge(2, 3, color='red')
# add nodes 3 and 4
G.add_node(3)
G.add_node(4)

# convert to a graphviz agraph
A = nx.nx_agraph.to_agraph(G)

# write to dot file
A.write('k5_attributes.dot')

# convert back to networkx Graph with attributes on edges and
# default attributes as dictionary data
X = nx.nx_agraph.from_agraph(A)
print("edges")
print(list(X.edges(data=True)))
print("default graph attributes")
print(X.graph)
print("node node attributes")
print(X.node)

Total running time of the script: ( 0 minutes 0.000 seconds)

Generated by Sphinx-Gallery

Write Dotfile

Write a dot file from a networkx graph for further processing with graphviz.

You need to have either pygraphviz or pydot for this example.

See http://networkx.readthedocs.io/en/latest/reference/drawing.html for more info.

# Author: Aric Hagberg (hagberg@lanl.gov)

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

import networkx as nx

# and the following code block is not needed
# but we want to see which module is used and
# if and why it fails
try:
    import pygraphviz
    from networkx.drawing.nx_agraph import write_dot
    print("using package pygraphviz")
except ImportError:
    try:
        import pydot
        from networkx.drawing.nx_pydot import write_dot
        print("using package pydot")
    except ImportError:
        print()
        print("Both pygraphviz and pydot were not found ")
        print("see  http://networkx.readthedocs.io/en"
              "/latest/reference/drawing.html for info")
        print()
        raise

G = nx.grid_2d_graph(5, 5)  # 5x5 grid
write_dot(G, "grid.dot")
print("Now run: neato -Tps grid.dot >grid.ps")

Total running time of the script: ( 0 minutes 0.000 seconds)

Generated by Sphinx-Gallery

Subclass

Antigraph

Complement graph class for small footprint when working on dense graphs.

This class allows you to add the edges that do not exist in the dense graph. However, when applying algorithms to this complement graph data structure, it behaves as if it were the dense version. So it can be used directly in several NetworkX algorithms.

This subclass has only been tested for k-core, connected_components, and biconnected_components algorithms but might also work for other algorithms.

_images/sphx_glr_plot_antigraph_001.png
# Author: Jordi Torrents <jtorrents@milnou.net>

#    Copyright (C) 2015-2017 by
#    Jordi Torrents <jtorrents@milnou.net>
#    All rights reserved.
#    BSD license.
import networkx as nx
from networkx.exception import NetworkXError
import matplotlib.pyplot as plt

__all__ = ['AntiGraph']


class AntiGraph(nx.Graph):
    """
    Class for complement graphs.

    The main goal is to be able to work with big and dense graphs with
    a low memory foodprint.

    In this class you add the edges that *do not exist* in the dense graph,
    the report methods of the class return the neighbors, the edges and
    the degree as if it was the dense graph. Thus it's possible to use
    an instance of this class with some of NetworkX functions.
    """

    all_edge_dict = {'weight': 1}

    def single_edge_dict(self):
        return self.all_edge_dict
    edge_attr_dict_factory = single_edge_dict

    def __getitem__(self, n):
        """Return a dict of neighbors of node n in the dense graph.

        Parameters
        ----------
        n : node
           A node in the graph.

        Returns
        -------
        adj_dict : dictionary
           The adjacency dictionary for nodes connected to n.

        """
        return dict((node, self.all_edge_dict) for node in
                    set(self.adj) - set(self.adj[n]) - set([n]))

    def neighbors(self, n):
        """Return an iterator over all neighbors of node n in the
           dense graph.

        """
        try:
            return iter(set(self.adj) - set(self.adj[n]) - set([n]))
        except KeyError:
            raise NetworkXError("The node %s is not in the graph." % (n,))

    def degree(self, nbunch=None, weight=None):
        """Return an iterator for (node, degree) in the dense graph.

        The node degree is the number of edges adjacent to the node.

        Parameters
        ----------
        nbunch : iterable container, optional (default=all nodes)
            A container of nodes.  The container will be iterated
            through once.

        weight : string or None, optional (default=None)
           The edge attribute that holds the numerical value used
           as a weight.  If None, then each edge has weight 1.
           The degree is the sum of the edge weights adjacent to the node.

        Returns
        -------
        nd_iter : iterator
            The iterator returns two-tuples of (node, degree).

        See Also
        --------
        degree

        Examples
        --------
        >>> G = nx.path_graph(4) # or DiGraph, MultiGraph, MultiDiGraph, etc
        >>> list(G.degree(0)) # node 0 with degree 1
        [(0, 1)]
        >>> list(G.degree([0,1]))
        [(0, 1), (1, 2)]

        """
        if nbunch is None:
            nodes_nbrs = ((n, {v: self.all_edge_dict for v in
                               set(self.adj) - set(self.adj[n]) - set([n])})
                          for n in self.nodes())
        elif nbunch in self:
            nbrs = set(self.nodes()) - set(self.adj[nbunch]) - {nbunch}
            return len(nbrs)
        else:
            nodes_nbrs = ((n, {v: self.all_edge_dict for v in
                               set(self.nodes()) - set(self.adj[n]) - set([n])})
                          for n in self.nbunch_iter(nbunch))

        if weight is None:
            return ((n, len(nbrs)) for n, nbrs in nodes_nbrs)
        else:
            # AntiGraph is a ThinGraph so all edges have weight 1
            return ((n, sum((nbrs[nbr].get(weight, 1)) for nbr in nbrs))
                    for n, nbrs in nodes_nbrs)

    def adjacency_iter(self):
        """Return an iterator of (node, adjacency set) tuples for all nodes
           in the dense graph.

        This is the fastest way to look at every edge.
        For directed graphs, only outgoing adjacencies are included.

        Returns
        -------
        adj_iter : iterator
           An iterator of (node, adjacency set) for all nodes in
           the graph.

        """
        for n in self.adj:
            yield (n, set(self.adj) - set(self.adj[n]) - set([n]))


if __name__ == '__main__':
    # Build several pairs of graphs, a regular graph
    # and the AntiGraph of it's complement, which behaves
    # as if it were the original graph.
    Gnp = nx.gnp_random_graph(20, 0.8)
    Anp = AntiGraph(nx.complement(Gnp))
    Gd = nx.davis_southern_women_graph()
    Ad = AntiGraph(nx.complement(Gd))
    Gk = nx.karate_club_graph()
    Ak = AntiGraph(nx.complement(Gk))
    pairs = [(Gnp, Anp), (Gd, Ad), (Gk, Ak)]
    # test connected components
    for G, A in pairs:
        gc = [set(c) for c in nx.connected_components(G)]
        ac = [set(c) for c in nx.connected_components(A)]
        for comp in ac:
            assert comp in gc
    # test biconnected components
    for G, A in pairs:
        gc = [set(c) for c in nx.biconnected_components(G)]
        ac = [set(c) for c in nx.biconnected_components(A)]
        for comp in ac:
            assert comp in gc
    # test degree
    for G, A in pairs:
        node = list(G.nodes())[0]
        nodes = list(G.nodes())[1:4]
        assert G.degree(node) == A.degree(node)
        assert sum(d for n, d in G.degree()) == sum(d for n, d in A.degree())
        # AntiGraph is a ThinGraph, so all the weights are 1
        assert sum(d for n, d in A.degree()) == sum(d for n, d in A.degree(weight='weight'))
        assert sum(d for n, d in G.degree(nodes)) == sum(d for n, d in A.degree(nodes))

    nx.draw(Gnp)
    plt.show()

Total running time of the script: ( 0 minutes 0.108 seconds)

Generated by Sphinx-Gallery

Generated by Sphinx-Gallery