Release:  2.0.dev_20170518025222 

Date:  May 18, 2017 
NetworkX is a Python language software package for the creation, manipulation, and study of the structure, dynamics, and function of complex networks.
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.
The potential audience for NetworkX includes mathematicians, physicists, biologists, computer scientists, and social scientists. Good reviews of the stateoftheart in 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].
NetworkX is intended to provide
Python is a powerful programming language that allows simple and flexible representations of networks, and clear and concise expressions of network algorithms (and other algorithms too). Python has a vibrant and growing ecosystem of packages that NetworkX uses to provide more features such as numerical linear algebra and drawing. In addition Python is also an excellent âglueâ language for putting together pieces of software from other languages which allows reuse of legacy code and engineering of highperformance algorithms [Langtangen04].
Equally important, Python is free, wellsupported, and a joy to use.
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 documentation at http://www.python.org and the text by Alex Martelli [Martelli03].
NetworkX is free software; you can redistribute it and/or modify it under the terms of the BSD License. We welcome contributions from the community. Information on NetworkX development is found at the NetworkX Developer Zone at Github https://github.com/networkx/networkx
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.
Source and binary releases: http://pypi.python.org/pypi/networkx/
Github (latest development): https://github.com/networkx/networkx/
As .pdf file: https://media.readthedocs.org/pdf/networkx/stable/networkx.pdf
As html in .zip file: https://readthedocs.org/projects/networkx/downloads/htmlzip/stable/
Try to install it with
pip install networkx
and an attempt will be made to find and install an appropriate version that matches your operating system and Python version.
You can also get NetworkX from the Python Package Index manually at http://pypi.python.org/pypi/networkx To use pip, you need to have setuptools installed.
You can install the development version (at github.com) with
pip install git://github.com/networkx/networkx.git#egg=networkx
More download file options are at http://networkx.github.io/download.html.
If you are using Ananconda/Miniconda distribution of Python then you can update/install NetworkX to the latest version with
conda install networkx
or to update an existing installation
conda update networkx
You can install from source by downloading a source archive file (tar.gz or zip) or by checking out the source files from the Git source code repository.
NetworkX is a pure Python package; you donât need a compiler to build or install it.
 Download the source (tar.gz or zip file) from https://pypi.python.org/pypi/networkx/ or get the latest development version from https://github.com/networkx/networkx/
 Unpack and change directory to the source directory (it should have the files README.txt and setup.py).
 Run
python setup.py install
to build and install (Optional) Run
nosetests
to execute the tests if you have nose installed.
Clone the networkx repository (see https://github.com/networkx/networkx/ for options)
git clone https://github.com/networkx/networkx.gitChange directory to
networkx
Run
python setup.py install
to build and install(Optional) Run
nosetests
to execute the tests if you have nose installed.
If you donât have permission to install software on your
system, you can install into another directory using
the user
, prefix
, or home
flags to setup.py.
For example
python setup.py install prefix=/home/username/python
or
python setup.py install home=~
or
python setup.py install user
If you didnât install in the standard Python sitepackages directory you will need to set your PYTHONPATH variable to the alternate location. See http://docs.python.org/2/install/index.html#searchpath for further details.
To use NetworkX you need Python 2.7, 3.3 or later.
The easiest way to get Python and most optional packages is to install the Enthought Python distribution âCanopyâ.
There are several other distributions that contain the key packages you need for scientific computing. See http://scipy.org/install.html for a list.
The following are optional packages that NetworkX can use to provide additional functions.
Provides matrix representation of graphs and is used in some graph algorithms for highperformance matrix computations.
 Download: http://scipy.org/Download
Provides sparse matrix representation of graphs and many numerical scientific tools.
 Download: http://scipy.org/Download
In conjunction with either
provides graph drawing and graph layout algorithms.
 Download: http://graphviz.org/
These are extra packages you may consider using with NetworkX
 IPython, interactive Python shell, http://ipython.scipy.org/
Start here to begin working with NetworkX.
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.)
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.)
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 edgetuples. An edgetuple can be a 2tuple of nodes or a 3tuple 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)
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.
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)
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.
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'}
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.
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.
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
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. Shortest path is one
example. 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,.5), (1,2,.75), (2,3,.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]
In addition to constructing graphs nodebynode or edgebyedge, they can also be generated by
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
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()
>>> 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)
>>> 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)
>>> nx.write_gml(red,"path.to.file")
>>> mygraph=nx.read_gml("path.to.file")
Details on graph formats: Reading and writing graphs
Details on graph generator functions: Graph generators
The structure of G can be analyzed using various graphtheoretic 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 2tuples. 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]
Details on graph algorithms supported: Algorithms
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 package and will be imported if possible. See Drawing for details.
Note that the drawing package in NetworkX is not yet compatible with Python versions 3.0 and above.
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.
>>> pos = nx.nx_agraph.graphviz_layout(G)
>>> nx.draw(G, pos=pos)
>>> nx.write_dot(G,'file.dot')
Details on drawing graphs: Drawing
What Next
Now that you have an idea of what the NetworkX package provides, you should investigate the parts of the package most useful for you.
Reference Section provides details on NetworkX.
NetworkX Examples provides some example programs written using NetworkX.
Release: 2.0.dev20170518025222 Date: May 18, 2017
NetworkX provides data structures for graphs (or networks) along with graph algorithms, generators, and drawing tools.
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 analyse 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).
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
DiGraph
MultiGraph
MultiDiGraph
Empty graphlike 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 adjaceny 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 âdictofdictsâ 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 graphlike objects solely via those API methods and not by acting directly on the datastructure. This design allows for possible replacement of the âdictsofdictsâbased datastructure with an alternative datastructure that implements the same methods.
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.
 Multiedges: 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
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.
NetworkX graph objects can be created in one of three ways:
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.
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 nodecentric and people who focus on edges as edgecentric. The designers of NetworkX tend to be nodecentric 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.
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']
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.
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 dictofdictsofdicts data structure:
 Find edges and remove edges with two dictionary lookups.
 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 noden
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 dictofdictsofdicts structures are provided, one for successors and one for predecessors. For MultiGraph/MultiDiGraph we use a dictofdictsofdictsofdicts [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 dictofdictsofdicts data structure with the inner dictionary storing ânamevalueâ 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.â 
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.
Graph Type  NetworkX Class 

Undirected Simple  Graph 
Directed Simple  DiGraph 
With Selfloops  Graph, DiGraph 
With Parallel edges  MultiGraph, MultiDiGraph 
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: 


See also
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
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 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 dictofdictofdict 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 dictlike object. In general, the dictlike 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 dictlike structure. The variable names are node_dict_factory, adjlist_inner_dict_factory, adjlist_outer_dict_factory, and edge_attr_dict_factory.
Examples
Create a graph subclass that tracks the order nodes are added.
>>> from collections import OrderedDict
>>> class OrderedNodeGraph(nx.Graph):
... node_dict_factory=OrderedDict
... adjlist_outer_dict_factory=OrderedDict
>>> G=OrderedNodeGraph()
>>> G.add_nodes_from((2, 1))
>>> list(G.nodes())
[2, 1]
>>> G.add_edges_from(((2, 2), (2, 1), (1, 1)))
>>> # Edge addition order is not preserved
Create a graph object that tracks the order nodes are added and for each node track the order that neighbors are added.
>>> class OrderedGraph(nx.Graph):
... node_dict_factory = OrderedDict
... adjlist_outer_dict_factory = OrderedDict
... adjlist_inner_dict_factory = OrderedDict
>>> G = OrderedGraph()
>>> G.add_nodes_from((2, 1))
>>> list(G.nodes())
[2, 1]
>>> G.add_edges_from(((2, 2), (2, 1), (1, 1)))
>>> list(G.edges())
[(2, 2), (2, 1), (1, 1)]
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
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. 
Graph.nodes ([data, default]) 
Returns an iterator over the nodes. 
Graph.__iter__ () 
Iterate over the nodes. 
Graph.edges ([nbunch, data, default]) 
Return an iterator over the 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. 
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 ([nbunch, weight]) 
Return an iterator for (node, degree) or degree for single node. 
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. 
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
(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: 


See also
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 dictofdictofdict 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 dictlike object. In general, the dictlike 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 dictlike structure. The variable names are node_dict_factory, adjlist_inner_dict_factory, adjlist_outer_dict_factory, and edge_attr_dict_factory.
Examples
Create a graph subclass that tracks the order nodes are added.
>>> from collections import OrderedDict
>>> class OrderedNodeGraph(nx.Graph):
... node_dict_factory=OrderedDict
... adjlist_outer_dict_factory=OrderedDict
>>> G=OrderedNodeGraph()
>>> G.add_nodes_from((2, 1))
>>> list(G.nodes())
[2, 1]
>>> G.add_edges_from(((2, 2), (2, 1), (1, 1)))
>>> # Edge addition order is not preserved
Create a graph object that tracks the order nodes are added and for each node track the order that neighbors are added.
>>> class OrderedGraph(nx.Graph):
... node_dict_factory = OrderedDict
... adjlist_outer_dict_factory=OrderedDict
... adjlist_inner_dict_factory = OrderedDict
>>> G = OrderedGraph()
>>> G.add_nodes_from((2, 1))
>>> list(G.nodes())
[2, 1]
>>> G.add_edges_from(((2, 2), (2, 1), (1, 1)))
>>> list(G.edges())
[(2, 2), (2, 1), (1, 1)]
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
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. 
DiGraph.nodes ([data, default]) 
Returns an iterator over the nodes. 
DiGraph.__iter__ () 
Iterate over the nodes. 
DiGraph.edges ([nbunch, data, default]) 
Return an iterator over the edges. 
DiGraph.out_edges ([nbunch, data, default]) 
Return an iterator over the edges. 
DiGraph.in_edges ([nbunch, data, default]) 
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. 
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 ([nbunch, weight]) 
Return an iterator for (node, degree) or degree for single node. 
DiGraph.in_degree ([nbunch, weight]) 
Return an iterator for (node, indegree) or indegree for single node. 
DiGraph.out_degree ([nbunch, weight]) 
Return an iterator for (node, outdegree) or outdegree 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. 
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
(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: 


See also
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,dict(route=282)), (4,5,dict(route=37))])
>>> G[4]
{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 keyed by neighbor to edge attributes
... # Note: you should not change this dict manually!
{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 dictofdictofdictofdict 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 dictofdictofdictofdict structure can be replaced by a user defined dictlike object. In general, the dictlike 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 dictlike structure. The variable names are node_dict_factory, adjlist_inner_dict_factory, adjlist_outer_dict_factory, and edge_attr_dict_factory.
Examples
Create a multigraph subclass that tracks the order nodes are added.
>>> from collections import OrderedDict
>>> class OrderedGraph(nx.MultiGraph):
... node_dict_factory = OrderedDict
... adjlist_outer_dict_factory = OrderedDict
>>> G = OrderedGraph()
>>> G.add_nodes_from((2, 1))
>>> list(G.nodes())
[2, 1]
>>> keys = G.add_edges_from(((2, 2), (2, 1), (2, 1), (1, 1)))
>>> # Edge addition order is not preserved
Create a multgraph object that tracks the order nodes are added and for each node track the order that neighbors are added and for each neighbor tracks the order that multiedges are added.
>>> class OrderedGraph(nx.MultiGraph):
... node_dict_factory = OrderedDict
... adjlist_outer_dict_factory = OrderedDict
... adjlist_inner_dict_factory = OrderedDict
... edge_key_dict_factory = OrderedDict
>>> G = OrderedGraph()
>>> G.add_nodes_from((2, 1))
>>> list(G.nodes())
[2, 1]
>>> elist = ((2, 2), (2, 1, 2, {'weight': 0.1}), (2, 1, 1, {'weight': 0.2}), (1, 1))
>>> keys = G.add_edges_from(elist)
>>> list(G.edges(keys=True))
[(2, 2, 0), (2, 1, 2), (2, 1, 1), (1, 1, 0)]
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. 
MultiGraph.nodes ([data, default]) 
Returns an iterator over the nodes. 
MultiGraph.__iter__ () 
Iterate over the nodes. 
MultiGraph.edges ([nbunch, data, keys, default]) 
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. 
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 ([nbunch, weight]) 
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. 
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
(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: 


See also
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]
{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 keyed by neighbor to edge attributes
... # Note: you should not change this dict manually!
{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 dictofdictofdictofdict 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 dictofdictofdictofdict structure can be replaced by a user defined dictlike object. In general, the dictlike 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 dictlike structure. The variable names are node_dict_factory, adjlist_inner_dict_factory, adjlist_outer_dict_factory, and edge_attr_dict_factory.
Examples
Create a multigraph subclass that tracks the order nodes are added.
>>> from collections import OrderedDict
>>> class OrderedGraph(nx.MultiDiGraph):
... node_dict_factory = OrderedDict
... adjlist_outer_dict_factory = OrderedDict
>>> G = OrderedGraph()
>>> G.add_nodes_from((2, 1))
>>> list(G.nodes())
[2, 1]
>>> keys = G.add_edges_from(((2, 2), (2, 1), (2, 1), (1, 1)))
>>> # Edge addition order is not preserved
Create a multdigraph object that tracks the order nodes are added and for each node track the order that neighbors are added and for each neighbor tracks the order that multiedges are added.
>>> class OrderedGraph(nx.MultiDiGraph):
... node_dict_factory = OrderedDict
... adjlist_outer_dict_factory = OrderedDict
... adjlist_inner_dict_factory = OrderedDict
... edge_key_dict_factory = OrderedDict
>>> G = OrderedGraph()
>>> G.add_nodes_from((2, 1))
>>> list(G.nodes())
[2, 1]
>>> elist = ((2, 2), (2, 1, 2, {'weight': 0.1}), (2, 1, 1, {'weight': 0.2}), (1, 1))
>>> keys = G.add_edges_from(elist)
>>> list(G.edges(keys=True))
[(2, 2, 0), (2, 1, 2), (2, 1, 1), (1, 1, 0)]
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. 
MultiDiGraph.nodes ([data, default]) 
Returns an iterator over the nodes. 
MultiDiGraph.__iter__ () 
Iterate over the nodes. 
MultiDiGraph.edges ([nbunch, data, keys, default]) 
Return an iterator over the edges. 
MultiDiGraph.out_edges ([nbunch, data, keys, âŠ]) 
Return an iterator over the edges. 
MultiDiGraph.in_edges ([nbunch, data, keys, âŠ]) 
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. 
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 ([nbunch, weight]) 
Return an iterator for (node, degree) or degree for single node. 
MultiDiGraph.in_degree ([nbunch, weight]) 
Return an iterator for (node, indegree) or indegree for single node. 
MultiDiGraph.out_degree ([nbunch, weight]) 
Return an iterator for (node, outdegree) or outdegree 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. 
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. 
Warning
The approximation submodule is not imported automatically with networkx.
Approximate algorithms can be imported with from networkx.algorithms import approximation
.
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. 
Fast approximation for kcomponent structure
k_components (G[, min_density]) 
Returns the approximate kcomponent structure of a graph G. 
Cliques.
max_clique (G) 
Find the Maximum Clique 
clique_removal (G) 
Repeatedly remove cliques from the graph. 
average_clustering (G[, trials]) 
Estimates the average clustering coefficient of G. 
Functions for finding node and edge dominating sets.
A `dominating set`_[1] 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`_[2] 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.
[1]  dominating set: https://en.wikipedia.org/wiki/Dominating_set 
[2]  edge dominating set: https://en.wikipedia.org/wiki/Edge_dominating_set 
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 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 NPhard optimization problem. As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph.
http://en.wikipedia.org/wiki/Independent_set_(graph_theory)
Independent set algorithm is based on the following paper:
O(V/(logV)^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. 
Given a graph G = (V,E), a matching M in G is a set of pairwise nonadjacent edges; that is, no two edges share a common vertex.
min_maximal_matching (G) 
Returns the minimum maximal matching of G. 
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. 
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 (G[, source, target, âŠ]) 
Returns the average degree of the neighborhood of each node. 
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. 
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. 
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 twocoloring
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
.
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 twocoloring 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. 
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 . 
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. 
Onemode (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 userspecified weight function. 
Spectral bipartivity measure.
spectral_bipartivity (G[, nodes, weight]) 
Returns the spectral bipartivity. 
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. 
Node redundancy for bipartite graphs.
node_redundancy (G[, nodes]) 
Computes the node redundancy coefficients for the nodes in the bipartite graph G . 
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 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 HavelHakimi style construction. 
reverse_havel_hakimi_graph (aseq, bseq[, âŠ]) 
Return a bipartite graph from two given degree sequences using a HavelHakimi style construction. 
alternating_havel_hakimi_graph (aseq, bseq[, âŠ]) 
Return a bipartite graph from two given degree sequences using an alternating HavelHakimi 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}. 
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. 
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 . 
degree_centrality (G) 
Compute the degree centrality for nodes. 
in_degree_centrality (G) 
Compute the indegree centrality for nodes. 
out_degree_centrality (G) 
Compute the outdegree centrality for nodes. 
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_centrality (G[, u, distance, âŠ]) 
Compute closeness centrality for nodes. 
current_flow_closeness_centrality (G[, âŠ]) 
Compute currentflow closeness centrality for nodes. 
betweenness_centrality (G[, k, normalized, âŠ]) 
Compute the shortestpath 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_centrality (G[, âŠ]) 
Compute currentflow betweenness centrality for nodes. 
edge_current_flow_betweenness_centrality (G) 
Compute currentflow betweenness centrality for edges. 
approximate_current_flow_betweenness_centrality (G) 
Compute the approximate currentflow betweenness centrality for nodes. 
current_flow_betweenness_centrality_subset (G, âŠ) 
Compute currentflow betweenness centrality for subsets of nodes. 
edge_current_flow_betweenness_centrality_subset (G, âŠ) 
Compute currentflow betweenness centrality for edges using subsets of nodes. 
communicability_betweenness_centrality (G[, âŠ]) 
Return subgraph communicability for all pairs of nodes in G. 
load_centrality (G[, v, cutoff, normalized, âŠ]) 
Compute load centrality for nodes. 
edge_load_centrality (G[, cutoff]) 
Compute edge load. 
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 (G[, nbunch, distance]) 
Compute harmonic centrality for nodes. 
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. 
Functions for finding chains in a graph.
chain_decomposition (G[, root]) 
Return the chain decomposition of a graph. 
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. 
Functions for finding and manipulating cliques.
Finding the largest clique in a graph is NPcomplete 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. 
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. 
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 breadthfirst or depthfirst traversal. 
strategy_connected_sequential_dfs (G, colors) 
Returns an iterable over nodes in G in the order given by a depthfirst traversal. 
strategy_connected_sequential_bfs (G, colors) 
Returns an iterable over nodes in G in the order given by a breadthfirst 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 (G) 
Return communicability between all pairs of nodes in G. 
communicability_exp (G) 
Return communicability between all pairs of nodes in G. 
Functions for computing the KernighanâLin bipartition algorithm.
kernighan_lin_bisection (G[, partition, âŠ]) 
Partition a graph into two blocks using the KernighanâLin algorithm. 
LFR_benchmark_graph 
k_clique_communities (G, k[, cliques]) 
Find kclique communities in graph using the percolation method. 
Asynchronous label propagation algorithms for community detection.
asyn_lpa_communities (G[, weight]) 
Returns communities in G as detected by asynchronous label propagation. 
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. 
Functions for computing communities based on centrality notions.
girvan_newman (G[, most_valuable_edge]) 
Finds communities in a graph using the GirvanâNewman method. 
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. 
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. 
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. 
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 . 
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. 
is_semiconnected (G) 
Return True if the graph is semiconnected, False otherwise. 
Connectivity and cut algorithms
Moody and White algorithm for kcomponents
k_components (G[, flow_func]) 
Returns the kcomponent structure of a graph G. 
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 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, u, v[, âŠ]) 
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 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 cutset 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. 
StoerWagner minimum cut algorithm.
stoer_wagner (G[, weight, heap]) 
Returns the weighted minimum edge cut using the StoerWagner algorithm. 
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. 
Find the kcores of a graph.
The kcore 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 Dcores which looks at (k, l) restrictions on (in, out) degree. The (k, k) Dcore is the kcore.
Dcores: 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 kcore of G. 
k_shell (G[, k, core_number]) 
Return the kshell of G. 
k_crust (G[, k, core_number]) 
Return the kcrust of G. 
k_corona (G, k[, core_number]) 
Return the kcorona of G. 
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. 
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, depthfirst traversal. 
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. 
Algorithms for directed acyclic graphs (DAGs).
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 DAG. 
dag_longest_path (G[, weight, default_weight]) 
Returns the longest path in a DAG If G has edges with âweightâ attribute the edge data are used as weight values. 
dag_longest_path_length (G[, weight, âŠ]) 
Returns the longest path length in a DAG 
dispersion
Graph diameter, radius, eccentricity and other properties.
center (G[, e]) 
Return the center of the graph G. 
diameter (G[, e]) 
Return the diameter of the graph G. 
eccentricity (G[, v, sp]) 
Return the eccentricity of nodes in G. 
periphery (G[, e]) 
Return the periphery of the graph G. 
radius (G[, e]) 
Return the radius of the graph G. 
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 distanceregular graph. 
global_parameters (b, c) 
Return global parameters for a given intersection array. 
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. 
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 . 
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 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 . 
maximum_flow (G, s, t[, capacity, flow_func]) 
Find a maximum singlecommodity flow. 
maximum_flow_value (G, s, t[, capacity, âŠ]) 
Find the value of maximum singlecommodity 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 (G, s, t[, capacity, residual, âŠ]) 
Find a maximum singlecommodity flow using the EdmondsKarp algorithm. 
shortest_augmenting_path (G, s, t[, âŠ]) 
Find a maximum singlecommodity flow using the shortest augmenting path algorithm. 
preflow_push (G, s, t[, capacity, residual, âŠ]) 
Find a maximum singlecommodity flow using the highestlabel preflowpush algorithm. 
dinitz (G, s, t[, capacity, residual, âŠ]) 
Find a maximum singlecommodity flow using Dinitzâ algorithm. 
boykov_kolmogorov (G, s, t[, capacity, âŠ]) 
Find a maximum singlecommodity flow using BoykovKolmogorov algorithm. 
build_residual_network (G, capacity) 
Build a residual network and initialize a zero flow. 
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 (G[, demand, capacity, âŠ]) 
Find a minimum cost flow satisfying all demands in digraph G. 
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 outdegree 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. 
Flow Hierarchy.
flow_hierarchy (G[, weight]) 
Returns the flow hierarchy of a directed network. 
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. 
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. 
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. 
An implementation of VF2 algorithm for graph ismorphism testing.
The simplest interface to use this module is to call networkx.is_isomorphic().
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}
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 graphsubgraph isomorphism iff M is an isomorphism between G2 and a subgraph of G1. Thus, to say that G1 and G2 are graphsubgraph 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 ânodeinduced subgraphâ. Edgeinduced 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.
References
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
oldtonew 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 NPcomplete whereas the graph isomorphism problem is most likely not NPcomplete (although no polynomialtime algorithm is known to exist).
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. 
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. 
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. 
PageRank analysis of graph structure.
pagerank (G[, alpha, personalization, âŠ]) 
Return the PageRank of the nodes in the graph. 
pagerank_numpy (G[, alpha, personalization, âŠ]) 
Return the PageRank of the nodes in the graph. 
pagerank_scipy (G[, alpha, personalization, âŠ]) 
Return the PageRank of the nodes in the graph. 
google_matrix (G[, alpha, personalization, âŠ]) 
Return the Google matrix of the graph. 
Hubs and authorities analysis of graph structure.
hits (G[, max_iter, tol, nstart, normalized]) 
Return HITS hubs and authorities values for nodes. 
hits_numpy (G[, normalized]) 
Return HITS hubs and authorities values for nodes. 
hits_scipy (G[, max_iter, tol, normalized]) 
Return HITS hubs and authorities values for nodes. 
hub_matrix (G[, nodelist]) 
Return the HITS hub matrix. 
authority_matrix (G[, nodelist]) 
Return the HITS authority matrix. 
Link prediction algorithms.
resource_allocation_index (G[, ebunch]) 
Compute the resource allocation index of all node pairs in ebunch. 
jaccard_coefficient (G[, ebunch]) 
Compute the Jaccard coefficient of all node pairs in ebunch. 
adamic_adar_index (G[, ebunch]) 
Compute the AdamicAdar index of all node pairs in ebunch. 
preferential_attachment (G[, ebunch]) 
Compute the preferential attachment score of all node pairs in ebunch. 
cn_soundarajan_hopcroft (G[, ebunch, community]) 
Count the number of common neighbors of all node pairs in ebunch using community information. 
ra_index_soundarajan_hopcroft (G[, ebunch, âŠ]) 
Compute the resource allocation index of all node pairs in ebunch using community information. 
within_inter_cluster (G[, ebunch, delta, âŠ]) 
Compute the ratio of within and intercluster common neighbors of all node pairs in ebunch. 
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 maximumweighted matching of G. 
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. 
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. 
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. 
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. 
Functions for computing richclub coefficients.
rich_club_coefficient (G[, normalized, Q]) 
Returns the richclub coefficient of the graph G . 
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. 
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 dictionary 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. 
FloydWarshall algorithm for shortest paths.
floyd_warshall (G[, weight]) 
Find allpairs shortest path lengths using Floydâs algorithm. 
floyd_warshall_predecessor_and_distance (G[, âŠ]) 
Find allpairs shortest path lengths using Floydâs algorithm. 
floyd_warshall_numpy (G[, nodelist, weight]) 
Find allpairs shortest path lengths using Floydâs 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* (âAstarâ) algorithm. 
astar_path_length (G, source, target[, âŠ]) 
Return the length of the shortest path between source and target using the A* (âAstarâ) algorithm. 
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. 
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 doubleedge swaps in the graph G . 
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. 
Basic algorithms for depthfirst searching the nodes of a graph.
Based on http://www.ics.uci.edu/~eppstein/PADS/DFS.py by D. Eppstein, July 2004.
dfs_edges (G[, source]) 
Produce edges in a depthfirstsearch (DFS). 
dfs_tree (G[, source]) 
Return oriented tree constructed from a depthfirstsearch from source. 
dfs_predecessors (G[, source]) 
Return dictionary of predecessors in depthfirstsearch from source. 
dfs_successors (G[, source]) 
Return dictionary of successors in depthfirstsearch from source. 
dfs_preorder_nodes (G[, source]) 
Produce nodes in a depthfirstsearch preordering starting from source. 
dfs_postorder_nodes (G[, source]) 
Produce nodes in a depthfirstsearch postordering starting from source. 
dfs_labeled_edges (G[, source]) 
Produce edges in a depthfirstsearch (DFS) labeled by type. 
Basic algorithms for breadthfirst searching the nodes of a graph.
bfs_edges (G, source[, reverse]) 
Produce edges in a breadthfirstsearch starting at source. 
bfs_tree (G, source[, reverse]) 
Return an oriented tree constructed from of a breadthfirstsearch starting at source. 
bfs_predecessors (G, source) 
Returns an iterator of predecessors in breadthfirstsearch from source. 
bfs_successors (G, source) 
Returns an iterator of successors in breadthfirstsearch from source. 
Basic algorithms for breadthfirst searching the nodes of a graph.
bfs_beam_edges (G, source, value[, width]) 
Iterates over edges in a beam search. 
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 indegree 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:
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. 
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. 
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 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. 
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. 
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 nontree graph as input instead. 
Functions for analyzing triads of a graph.
triadic_census (G) 
Determines the triadic census of a directed graph. 
Vitality measures.
closeness_vitality (G[, node, weight, âŠ]) 
Returns the closeness vitality for nodes in the graph. 
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 shortestpath distance metric. 
Functions related to the Wiener index of a graph.
wiener_index (G[, weight]) 
Returns the Wiener index of the given graph. 
Functional interface to graph methods and assorted utilities.
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 (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 nonneighbors of the node in the graph. 
common_neighbors (G, u, v) 
Return the common neighbors of two nodes in a graph. 
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 nonexistent edges in the graph. 
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 
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. 
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 DorogovtsevGoltsevMendes graph. 
empty_graph ([n, create_using]) 
Return the empty graph with n nodes and zero edges. 
grid_2d_graph (m, n[, periodic, create_using]) 
Return the 2d grid graph of mxn nodes 
grid_graph (dim[, periodic]) 
Return the ndimensional grid graph. 
hypercube_graph (n) 
Return the ndimensional hypercube. 
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 
Provides explicit constructions of expander graphs.
margulis_gabber_galil_graph (n[, create_using]) 
Return the MargulisGabberGalil undirected MultiGraph on n^2 nodes. 
chordal_cycle_graph (p[, create_using]) 
Return the chordal cycle graph on p nodes. 
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 3regular 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 MoebiusKantor 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 3regular 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. 
Generators for random graphs.
fast_gnp_random_graph (n, p[, seed, directed]) 
Returns a G_{n,p} random graph, also known as an ErdĆsRĂ©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ĆsRĂ©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ĆsRĂ©nyi graph or a binomial graph. 
binomial_graph (n, p[, seed, directed]) 
Returns a G_{n,p} random graph, also known as an ErdĆsRĂ©nyi graph or a binomial graph. 
newman_watts_strogatz_graph (n, k, p[, seed]) 
Return a NewmanâWattsâStrogatz smallworld graph. 
watts_strogatz_graph (n, k, p[, seed]) 
Return a WattsâStrogatz smallworld graph. 
connected_watts_strogatz_graph (n, k, p[, âŠ]) 
Returns a connected WattsâStrogatz smallworld 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. 
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 duplicationdivergence model. 
partial_duplication_graph (N, n, p, q[, seed]) 
Return a random graph using the partial duplication model. 
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 HavelHakimi 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. 
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. 
Generators for some directed graphs, including growing network (GN) graphs and scalefree 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 scalefree directed graph. 
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[, alpha, beta, L, domain, metric]) 
Return a Waxman random graph. 
navigable_small_world_graph (n[, p, q, r, âŠ]) 
Return a navigable smallworld 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 (G, n[, radius, center, âŠ]) 
Returns induced subgraph of neighbors centered at node n within a given radius. 
Functions for generating stochastic graphs from a given weighted directed graph.
stochastic_graph (G[, copy, weight]) 
Returns a rightstochastic representation of directed graph G . 
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. 
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. 
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 lpartition 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. 
Functions for generating trees.
random_tree (n[, seed]) 
Returns a uniformly random tree on n nodes. 
Implementation of the Wright, Richmond, Odlyzko and McKay (WROM) algorithm for the enumeration of all nonisomorphic free trees of a given order. Rooted trees are represented by level sequences, i.e., lists in which the ith 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 
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. 
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. 
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 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. 
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 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. 
Functions for constructing matrixlike 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. 
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}} # dictofdicts 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. 
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. 
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. 
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. 
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. 
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. 
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. 
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.
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 ab, ac, de 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 singleline adjacencylist 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. 
Read and write NetworkX graphs as multiline adjacency lists.
The multiline 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.
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 ab, ac, de can be represented as the following adjacency list (anything following the # in a line is a comment):
# example.multilineadjlist
a 2
b
c
d 1
e
read_multiline_adjlist (path[, comments, âŠ]) 
Read graph in multiline 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. 
Read and write NetworkX graphs as edge lists.
The multiline 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 selfloop edge.
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. 
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).
GEXF is an XML format. See http://gexf.net/format/schema.html for the specification and http://gexf.net/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. 
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 keyvalue 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.â
See http://www.infosun.fim.unipassau.de/Graphlet/GML/gmltr.html
See http://www.infosun.fim.unipassau.de/Graphlet/GML/gmltr.html for format specification.
Example graphs in GML format http://wwwpersonal.umich.edu/~mejn/netdata/
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. 
Read and write NetworkX graphs as Python pickles.
âThe pickle module implements a fundamental, but powerful algorithm for serializing and deserializing 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. 
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 easytouse 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 applicationspecific data. Its main features include support of
 directed, undirected, and mixed graphs,
 hypergraphs,
 hierarchical graphs,
 graphical representations,
 references to external data,
 applicationspecific attribute data, and
 lightweight 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/
GraphML is an XML format. See http://graphml.graphdrawing.org/specification.html for the specification and http://graphml.graphdrawing.org/primer/graphmlprimer.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 
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:
 nodelink like in the d3.js example http://bl.ocks.org/mbostock/4062045
 tree like in the d3.js example http://bl.ocks.org/mbostock/4063550
 adjacency like in the d3.js example http://bost.ocks.org/mike/miserables/
node_link_data (G[, attrs]) 
Return data in nodelink format that is suitable for JSON serialization and use in Javascript documents. 
node_link_graph (data[, directed, âŠ]) 
Return graph from nodelink 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. 
Read graphs in LEDA format.
LEDA is a C++ class library for efficient data types and algorithms.
See http://www.algorithmicsolutions.info/leda_guide/graphs/leda_native_graph_fileformat.html
read_leda (path[, encoding]) 
Read graph in LEDA format from path. 
parse_leda (lines) 
Read graph in LEDA format from string or iterable. 
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. 
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 spaceefficient for large sparse graphs.
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. 
Functions for reading and writing graphs in the sparse6 format.
The sparse6 file format is a spaceefficient 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. 
Read graphs in Pajek format.
This implementation handles directed and undirected graphs including those with self loops and parallel edges.
See http://vlado.fmf.unilj.si/pub/networks/pajek/doc/draweps.htm for format information.
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. 
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. 
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 addon 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 fullyfeatured 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.
Draw networks with matplotlib.
See also
matplotlib
pygraphviz
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. 
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
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. 
Import and export NetworkX graphs in Graphviz dot format using pydot.
Either this module or nx_agraph can be used to interface with graphviz.
See also
DOT
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. 
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 2dimensions.
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 FruchtermanReingold forcedirected algorithm. 
spectral_layout (G[, weight, scale, center, dim]) 
Position nodes using the eigenvectors of the graph Laplacian. 
Base exceptions and errors for NetworkX.
NetworkXPointlessConcept
[source]Â¶Harary, F. and Read, R. âIs the Null Graph a Pointless Concept?â In Graphs and Combinatorics Conference, George Washington University. New York: SpringerVerlag, 1973.
NetworkXUnfeasible
[source]Â¶Exception raised by algorithms trying to solve a problem instance that has no feasible solution.
NetworkXNoPath
[source]Â¶Exception for algorithms that should return a path when running on graphs where such a path does not exist.
NetworkXNoCycle
[source]Â¶Exception for algorithms that should return a cycle when running on graphs where such a cycle does not exist.
NetworkXUnbounded
[source]Â¶Exception raised by algorithms trying to solve a maximization or a minimization problem instance that is unbounded.
NetworkXNotImplemented
[source]Â¶Exception raised by algorithms not implemented for a type of graph.
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.
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 welldefined 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 manytoone mapping into a onetomany mapping. 
Unionfind data structure.
UnionFind.union (*objects) 
Find the sets containing the objects and merge them all. 
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. 
CuthillMcKee 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. 
NetworkX is distributed with the BSD license.
Copyright (C) 20042016, 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.
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
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.
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.
Optionally, add your desired name and include a few relevant links. The order is partially historical, and now, mostly arbitrary.
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.
networkx
acknowledges support from the following:
networkx
acknowledges support from the following:
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 builtin objects are hashable, while no mutable containers (such as lists or dictionaries) are. Objects which are instances of userdefined classes are hashable by default; they all compare unequal, and their hash value is their id().
Definition from http://docs.python.org/glossary.html
NetworkX uses the Python nose testing package. If you donât already have that package installed, follow the directions on the nose homepage.
You can test the complete package from the unpacked source directory with:
python setup_egg.py nosetests
If you have a filebased (not a Python egg) installation you can test the installed package with
>>> import networkx
>>> networkx.test()
or:
python c "import networkx; networkx.test()"
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 doesnât test docutils style tests in Python modules but you can turn that on with:
nosetests withdoctest
For doctests in standalone files NetworkX uses the extension txt so you can add:
nosetests withdoctest doctestextension=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.
Contents:
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.
Debian / Ubuntu  sudo aptget install git 
Fedora  sudo yum install gitcore 
Windows  Download and install msysGit 
OS X  Use the gitosxinstaller 
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: http://book.gitscm.com/2_installing_git.html
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:
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.
From time to time you may want to pull down the latest code. It is necessary to add the networkx repository as a remote to your configuration file. We call it upstream.
git remote seturl upstream https://github.com/networkx/networkx.git
Now git knows where to fetch updates from.
cd networkx git fetch upstream
The tree in networkx
will now have the latest changes from the initial
repository, unless you have made local changes in the meantime. In this
case, you have to merge.
git merge upstream/master
It is also possible to update your local fork directly from GitHub:
 Open your fork on GitHub.
 Click on âPull Requestsâ.
3. Click on âNew Pull Requestâ. By default, GitHub will compare the original with your fork. If you didnât make any changes, there is nothing to compare. 4. Click on âSwitching the baseâ or click âEditâ and switch the base manually. Now GitHub will compare your fork with the original, and you should see all the latest changes. 5. Click on âClick to create a pull request for this comparisonâ and name your pull request. 6. Click on Send pull request. 7. Scroll down and click âMerge pull requestâ and finally âConfirm mergeâ. You will be able to merge it automatically unless you did not change you local repo.
Contents:
You need to do this only once. The instructions here are very similar to the instructions at https://help.github.com/articles/forkarepo/ â 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.
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.
Log into your github account.
Go to the networkx github home at networkx github.
Click on the fork button:
Now, after a short pause and some âHardcore forking actionâ, you should find yourself at the home page for your own forked copy of networkx.
First you follow the instructions for Making your own copy (fork) of networkx.
git clone git@github.com:yourusername/networkx.git
cd networkx
git remote add upstream git://github.com/networkx/networkx.git
Clone your fork to the local computer with git clone
git@github.com:yourusername/networkx.git
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.
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:yourusername/networkx.git (fetch)
origin git@github.com:yourusername/networkx.git (push)
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 colorwords
[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 colorwords"
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.
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.
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 colorwords
(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 colorwords"
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 colorwords
You may also want to make sure that your editor of choice is used
git config global core.editor vim
To enforce summaries when doing merges (~/.gitconfig
file again):
[merge]
log = true
Or from the command line:
git config global merge.log true
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' abbrevcommit date=relative
You use the alias with:
git lg
and it gives graph / text output something like this (but with color!):
* 6d8e1ee  (HEAD, origin/myfancyfeature, myfancyfeature) 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 nonaxis object (3 weeks ago) [Jonathan Terhorst]
 * 65af65e  convert unit testing code to assertions (3 weeks ago) [Jonathan Terhorst]
 * 956fbab  Merge remotetracking branch 'upstream/master' (3 weeks ago) [Jonathan Terhorst]
 \
 /
Thanks to Yury V. Zaytsev for posting it.
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.
In what follows weâll refer to the upstream networkx master
branch, as
âtrunkâ.
master
branch for anything. Consider deleting it.bugfixforissue14
or refactordatabasecode
.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 ipython git workflow for some explanation.
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.
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.
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 addabilitytofly
, or
buxfixforissue42
.
# Update the mirror of trunk
git fetch upstream
# Make new feature branch starting at current trunk
git branch mynewfeature upstream/master
git checkout mynewfeature
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 mynewfeature
In git >= 1.7 you can ensure that the link is correctly set by using the
setupstream
option:
git push setupstream origin mynewfeature
From now on git will know that mynewfeature
is related to the
mynewfeature
branch in the github repo.
# hack hack
git add my_new_file
git commit am 'NF  some message'
git push
Make some changes
See which files have changed with git status
(see git status).
Youâll see a listing like this one:
# On branch nynewfeature
# 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")
Check what the actual changes are with git diff
(git diff).
Add any new files to version control git add new_file_name
(see
git add).
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 usecase
description in the tangled working copy problem. The git commit manual
page might also be useful.
To push the changes up to your forked repo on github, do a git
push
(see git push).
When you are ready to ask for someone to review your code and consider a merge:
Go to the URL of your forked repo, say
http://github.com/yourusername/networkx
.
Use the âSwitch Branchesâ dropdown menu near the top left of the page to select the branch with your changes:
Click on the âPull requestâ button:
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.
git checkout master
# delete branch locally
git branch D myunwantedbranch
# delete branch on github
git push origin :myunwantedbranch
(Note the colon :
before testbranch
. See also:
http://github.com/guides/removearemotebranch
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
http://github.com/yourusername/networkx
Click on the âAdminâ button, and add anyone else to the repo as a collaborator:
Now all those people can do:
git clone git@githhub.com:yourusername/networkx.git
Remember that links starting with git@
use the ssh protocol and are
readwrite; links starting with git://
are readonly.
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
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 textbased
graph of the repository.
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
coolfeature
. At this stage trunk is at some commit, letâs call it E. Now
you make some new commits on your coolfeature
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:
ABC coolfeature
/
DEFG 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' coolfeature
/
DEFG 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 coolfeature
# make a backup in case you mess up
git branch tmp coolfeature
# rebase coolfeature onto trunk
git rebase onto upstream/master upstream/master coolfeature
In this situation, where you are already on branch coolfeature
, 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 messups.
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.
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 coolfeature
8630830 coolfeature@{0}: commit: BUG: io: close file handles immediately
278dd2a coolfeature@{1}: rebase finished: refs/heads/myfeaturebranch onto 11ee694744f2552d
26aa21a coolfeature@{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 coolfeature@{2}
Note
Do this only for your own feature branches.
Thereâs an embarassing 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 prenep for a copule of structured_array_extensions.
...
and 6ad92e5
is the last commit in the coolfeature
branch. Suppose we
want to make the following changes:
13d7934
to something more sensible.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/myfeaturebranch.
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.
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 readonly access to the upstream repo. Being a maintainer, youâve got readwrite access.
Itâs good to have your upstream remote have a scary name, to remind you that itâs a readwrite remote:
git remote add upstreamrw git@github.com:networkx/networkx.git
git fetch upstreamrw
Letâs say you have some changes that need to go into trunk
(upstreamrw/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 coolfeature track someone/coolfeature
git checkout coolfeature
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.
If there are only a few commits, consider rebasing to upstream:
# Fetch upstream changes
git fetch upstreamrw
# rebase
git rebase upstreamrw/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.
If there are a longer series of related commits, consider a merge instead:
git fetch upstreamrw
git merge noff upstreamrw/master
The merge will be detected by github, and should close any related pull requests automatically.
Note the noff
above. This forces git to make a merge commit, rather than
doing a fastforward, 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.
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 upstreamrw/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 (upstreamrw/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.
git push upstreamrw mynewfeature:master
This pushes the mynewfeature
branch in this repository to the master
branch in the upstreamrw
repository.
github help is Gitâs own help and tutorial site. github more help lists more resources for learning Git and GitHub, including YouTube channels. The list is constantly updated. In case you are used to subversion , you can directly consult the git svn crash course.
To make full use of Git, you need to understand the concept behind Git. The following pages might help you:
Other than that, many devlopers list their personal tips and tricks. Among others there are Fernando Perez, Nick Quaranto and Linus Torvalds.
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:
Original Creators:
Aric Hagberg, hagberg@lanl.gov
Pieter Swart, swart@lanl.gov
Dan Schult, dschult@colgate.edu
This page includes more detailed release information and API changes from NetworkX 1.10 to NetworkX 2.0.
There is a [migration guide for people moving from 1.X to 2.0](http://networkx.readthedocs.org/en/latest/reference/migration_guide_from_1.x_to_2.0.html)
Please send comments and questions to the networkxdiscuss [mailing list](http://groups.google.com/group/networkxdiscuss).
Base Graph Class Changes
With the release of NetworkX 2.0 we are moving towards an iterator reporting API.
We used to have two methods for the same property of the graph, one that returns a
list and one that returns an iterator. With 2.0 we have removed the one that returns
a list and renamed the iterator returning method as the original one. For example,
G.nodes()
used to return a list and G.nodes_iter()
used to return an iterator, now
G.nodes()
returns an iterator and G.nodes_iter()
is removed. Routines that used to
return a dict now return an iterator of (key,value) 2tuples, so that dict(G.degree())
returns a dict keyed by node with degree as value.
The old behavior
>>> G = nx.complete_graph(5)
>>> G.nodes()
[0, 1, 2, 3, 4]
>>> G.nodes_iter()
<dictionarykeyiterator at 0x10898f470>
has changed to
>>> G = nx.complete_graph(5)
>>> G.nodes()
<dictionarykeyiterator at 0x10898f470>
>>> list(G.nodes())
[0, 1, 2, 3, 4]
G.nodes()
G.edges()
G.neighbors()
G.adjacency_list()
and G.adjacency_iter()
to G.adjacency()
G.degree()
G.nodes_with_selfloops()
G.selfloop_edges()
G.nodes()
G.edges()
G.in_edges()
G.out_edges()
G.degree()
G.in_degree()
G.out_degree()
[#2107]
The Graph class methods add_edge
and add_edges_from
no longer
allow the use of the attr_dict
parameter. Instead use keyword arguments.
Thus G.add_edge(1, 2, {'color': 'red'})
becomes
G.add_edge(1, 2, color='red')
.
Note that this only works if the attribute name is a string. For nonstring
attributes you will need to add the edge and then update manually using
e.g. G.adj[1][2].update({0: "zero"})
.
[#1577]
In addition to minimum spanning trees, a new function for calculating maximum
spanning trees is now provided. The new API consists of four functions:
minimum_spanning_edges
, maximum_spanning_edges
,
minimum_spanning_tree
, and maximum_spanning_tree
.
All of these functions accept an algorithm
parameter which specifies the
algorithm to use when finding the minimum or maximum spanning tree. Currently,
Kruskalâs and Primâs algorithms are implemented, defined as âkruskalâ and
âprimâ, respectively. If nothing is specified, Kruskalâs algorithm is used.
For example, to calculate the maximum spanning tree of a graph using Kruskalâs
algorithm, the function maximum_spanning_tree
has to be called like:
>>> nx.maximum_spanning_tree(G, algorithm='kruskal')
The algorithm
parameter is new and appears before the existing weight
parameter. So existing code that did not explicitly name the optional
weight
parameter will need to be updated:
>>> nx.minimum_spanning_tree(G, 'mass') # old
>>> nx.minimum_spanning_tree(G, weight='mass') # new
In the above, we are still relying on the the functions being imported into the toplevel namespace. We do not have immediate plans to deprecate this approach, but we recommend the following instead:
>>> from networkx.algorithms import tree
# recommended
>>> tree.minimum_spanning_tree(G, algorithm='kruskal', weight='mass')
>>> tree.minimum_spanning_edges(G, algorithm='prim', weight='mass')
Most of the shortest_path algorithms now raise a NodeNotFound exception when a source or a target are not present in the graph.
This page includes more detailed release information and API changes from NetworkX 1.9 to NetworkX 1.10.
Please send comments and questions to the networkxdiscuss mailing list: <http://groups.google.com/group/networkxdiscuss>.
connected_components
, weakly_connected_components
, and
strongly_connected_components
return now a generator of sets of
nodes. Previously the generator was of lists of nodes. This PR also
refactored the connected_components
and weakly_connected_components
implementations making them faster, especially for large graphs.func_iter
functions in Di/Multi/Graphs classes are slated for
removal in NetworkX 2.0 release. func
will behave like func_iter
and return an iterator instead of list. These functions are deprecated in
NetworkX 1.10 release.enumerate_all_cliques
function is added in the clique package
(networkx.algorithms.clique
) for enumerating all cliques (including
nonmaximal ones) of undirected graphs.networkx.algorithms.coloring
) is created for
graph coloring algorithms. Initially, a greedy_color
function is
provided for coloring graphs using various greedy heuristics.edge_dfs
, added to networkx.algorithms.traversal
,
implements a depthfirst traversal of the edges in a graph. This complements
functionality provided by a depthfirst traversal of the nodes in a graph.
For multigraphs, it allows the user to know precisely which edges were
followed in a traversal. All NetworkX graph types are supported. A traversal
can also reverse edge orientations or ignore them.find_cycle
function is added to the networkx.algorithms.cycles
package to find a cycle in a graph. Edge orientations can be optionally
reversed or ignored.networkx.algorithms.dominance
package is added for
dominance/dominator algorithms on directed graphs. It contains a
immediate_dominators
function for computing immediate
dominators/dominator trees and a dominance_frontiers
function for
computing dominance frontiers.networkx.algorithms.flow
package is
rewritten to improve its performance and support multi and disconnected
networks. For some cases, the new implementation is two or three orders of
magnitude faster than the old implementation.networkx.generators
.networkx.generators.expanders
.to_pandas_dataframe
and from_pandas_dataframe
.from_pandas_dataframe
function that accepts Pandas DataFrames
and returns a new graph object. At a minimum, the DataFrame must have two
columns, which define the nodes that make up an edge. However, the function
can also process an arbitrary number of additional columns as edge
attributes, such as âweightâ.network.algorithms.centrality
.generators.bipartite
have been moved to
algorithms.bipartite.generators
. The functions are not imported in the
main namespace, so to use it, the bipartite package has to be imported.algorithms.dag
. The antichains function was contributed
by Peter Jipsen and Franco Saliola and originally developed for the
SAGE project.networkx.generators.classic
module.networkx.algorithms.minors
.networkx.algorithms.minors
.networkx.linalg
,
and associated spectrum functions to the networkx.linalg.spectrum
module.algorithms.simple_paths
.networkx.linalg.modularity_matrix
module.triadic_census
function; also creates a new module,
networkx.algorithms.triads
.is_weighted
, is_negatively_weighted
, and is_empty
.johnson
at
algorithms.shortest_paths
k_components
in a
graph, which is based on Kanevskyâs algorithm for finding all minimumsize
node cutsets (implemented in all_node_cuts
#1391).k_components
to the
networkx.approximation
package. This is based on White and Newman
approximation algorithm for finding node independent paths between two
nodes (see #1405).This page reflects API changes from NetworkX 1.8 to NetworkX 1.9.
Please send comments and questions to the networkxdiscuss mailing list: <http://groups.google.com/group/networkxdiscuss>.
The flow package (networkx.algorithms.flow
) is completely rewritten
with backward incompatible changes. It introduces a new interface to flow
algorithms. Existing code that uses the flow package will not work unmodified
with NetworkX 1.9.
preflow_push
and
shortest_augmenting_path
) and rewrote the EdmondsâKarp algorithm in
flow_fulkerson
which is now in edmonds_karp
.
@ysitu contributed implementations of all new
maximum flow algorithms. The legacy EdmondsâKarp algorithm implementation in
ford_fulkerson
is still available but will be removed in the next
release.ford_fulkerson
) output now a residual network (i.e., a
DiGraph
) after computing the maximum flow. See maximum_flow
documentation for the details on the conventions that NetworkX uses for
defining a residual network.max_flow
and min_cut
functions. The main
entry points to flow algorithms are now the functions maximum_flow
,
maximum_flow_value
, minimum_cut
and
minimum_cut_value
, which have new parameters that control maximum
flow computation: flow_func
for specifying the algorithm that will
do the actual computation (it accepts a function as argument that implements
a maximum flow algorithm), cutoff
for suggesting a maximum flow
value at which the algorithm stops, value_only
for stopping the
computation as soon as we have the value of the flow, and residual
that accepts as argument a residual network to be reused in repeated maximum
flow computation.preflow_push
algorithm can stop after the preflow phase without
computing a maximum flow if we only need the flow value, but both
edmonds_karp
and shortest_augmenting_path
always compute a
maximum flow to obtain the flow value.minimum_cut
returns the cut value and a node
partition that defines the minimum cut. The function
minimum_cut_value
returns only the value of the cut, which is what
the removed min_cut
function used to return before 1.9.preflow_push
,
edmonds_karp
, shortest_augmenting_path
and
ford_fulkerson
) are not imported to the base NetworkX namespace. You
have to explicitly import them from the flow package:>>> from networkx.algorithms.flow import (ford_fulkerson, preflow_push,
... edmonds_karp, shortest_augmenting_path)
capacity_scaling
. It supports MultiDiGraph
and disconnected
networks.Below are some small examples illustrating how to obtain the same output than in NetworkX 1.8.1 using the new interface to flow algorithms introduced in 1.9:
>>> import networkx as nx
>>> G = nx.icosahedral_graph()
>>> nx.set_edge_attributes(G, 'capacity', 1)
With NetworkX 1.8:
>>> flow_value = nx.max_flow(G, 0, 6)
>>> cut_value = nx.min_cut(G, 0, 6)
>>> flow_value == cut_value
True
>>> flow_value, flow_dict = nx.ford_fulkerson(G, 0, 6)
With NetworkX 1.9:
>>> from networkx.algorithms.flow import (ford_fulkerson, preflow_push,
... edmonds_karp, shortest_augmenting_path)
>>> flow_value = nx.maximum_flow_value(G, 0, 6)
>>> cut_value = nx.minimum_cut_value(G, 0, 6)
>>> flow_value == cut_value
True
>>> # Legacy: this returns the exact same output than ford_fulkerson in 1.8.1
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=ford_fulkerson)
>>> # We strongly recommend to use the new algorithms:
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6)
>>> # If no flow_func is passed as argument, the default flow_func
>>> # (preflowpush) is used. Therefore this is the same than:
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=preflow_push)
>>> # You can also use alternative maximum flow algorithms:
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=shortest_augmenting_path)
>>> flow_value, flow_dict = nx.maximum_flow(G, 0, 6, flow_func=edmonds_karp)
The flowbased connecitivity and cut algorithms from the connectivity
package (networkx.algorithms.connectivity
) are adapted to take
advantage of the new interface to flow algorithms. As a result, flowbased
connectivity algorithms are up to 10x faster than in NetworkX 1.8 for some
problems, such as sparse networks with highly skewed degree distributions.
A few backwards incompatible changes were introduced.
flow_func
for defining the algorithm that will perform the
underlying maximum flow computations, residual
that accepts
as argument a residual network to be reused in repeated maximum
flow computations, and cutoff
for defining a maximum flow
value at which the underlying maximum flow algorithm stops. The big
speed improvement with respect to 1.8 comes mainly from the reuse
of the residual network and the use of cutoff
.edge_connectivity
,
node_connectivity
, minimum_edge_cut
, and
minimum_node_cut
. All these functions accept a couple of nodes
as optional arguments for computing local connectivity and cuts.mapping
parameter from the local versions of connectivity and cut
functions. We also changed the parameter name for the auxuliary digraph
from aux_digraph
to auxiliary
.all_pairs_node_connectiviy_matrix
to all_pairs_node_connectivity
. This function now returns a dictionary
instead of a NumPy 2D array. We added a new parameter nbunch
for
computing node connectivity only among pairs of nodes in nbunch
.stoer_wagner
function is added to the connectivity package
for computing the weighted minimum cuts of undirected graphs using
the StoerâWagner algorithm. This algorithm is not based on maximum flows.
Several heap implementations are also added in the utility package
(networkx.utils
) for use in this function.
BinaryHeap
is recommeded over PairingHeap
for Python
implementations without optimized attribute accesses (e.g., CPython)
despite a slower asymptotic running time. For Python implementations
with optimized attribute accesses (e.g., PyPy), PairingHeap
provides better performance.disperson
function is added in the centrality package
(networkx.algorithms.centrality
) for computing the dispersion of
graphs.networkx.generators.community
) is added for
generating community graphs.is_semiconnected
function is added in the connectivity package
(networkx.algorithms.connectivity
) for recognizing semiconnected
graphs.eulerian_circuit
function in the Euler package
(networkx.algorithm.euler
) is changed to use a lineartime algorithm.non_edges
function in added in the function package
(networkx.functions
) for enumerating nonexistent edges between
existing nodes of graphs.networkx.linalg
) is changed to use SciPy
sparse matrices.algebraic_connectivity
, fiedler_vector
and
spectral_ordering
are added in the linear algebra package
(networkx.linalg
) for computing the algebraic connectivity, Fiedler
vectors and spectral orderings of undirected graphs.networkx.algorithms.link_prediction
) is
added to provide link predictionrelated functionalities.networx.readwrite
).goldberg_radzik
function is added in the shortest path package
(networkx.algorithms.shortest_paths
) for computing shortest paths
using the GoldbergâRadzik algorithm.networkx.tree
) is added to provide tree recognition
functionalities.reversed
is added in the utility package
(networkx.utils
) for temporary inplace reversal of graphs.networkx.algorithms.components
) such as connected_components
,
connected_components_subgraph
now return generators instead of lists.
To recover the earlier behavior, use list(connected_components(G))
.networkx.readwrite.json_graph
)
are removed. Use functions from the standard library (e.g.,
json.dumps
) instead.This page reflects API changes from networkx1.7 to networkx1.8.
Please send comments and questions to the networkxdiscuss mailing list: http://groups.google.com/group/networkxdiscuss .
This page reflects API changes from networkx1.6 to networkx1.7.
Please send comments and questions to the networkxdiscuss mailing list: http://groups.google.com/group/networkxdiscuss .
This page reflects API changes from networkx1.5 to networkx1.6.
Please send comments and questions to the networkxdiscuss mailing list: http://groups.google.com/group/networkxdiscuss .
The degree* methods in the graph classes (Graph, DiGraph, MultiGraph, MultiDiGraph) now take an optional weight= keyword that allows computing weighted degree with arbitrary (numerical) edge attributes. Setting weight=None is equivalent to the previous weighted=False.
Many âweightedâ graph algorithms now take optional parameter to specifiy which edge attribute should be used for the weight (default=âweightâ) (ticket https://networkx.lanl.gov/trac/ticket/573)
In some cases the parameter name was changed from weighted, to weight. Here is how to specify which edge attribute will be used in the algorithms:
Algorithms affected are:
to_scipy_sparse_matrix, clustering, average_clustering, bipartite.degree, spectral_layout, neighbor_degree, is_isomorphic, betweenness_centrality, betweenness_centrality_subset, vitality, load_centrality, mincost, shortest_path, shortest_path_length, average_shortest_path_length
Node and edge attributes are now more easily incorporated into isomorphism checks via the ânode_matchâ and âedge_matchâ parameters. As part of this change, the following classes were removed:
WeightedGraphMatcher
WeightedDiGraphMatcher
WeightedMultiGraphMatcher
WeightedMultiDiGraphMatcher
The function signature for âis_isomorphicâ is now simply:
is_isomorphic(g1, g2, node_match=None, edge_match=None)
See its docstring for more details. To aid in the creation of ânode_matchâ and âedge_matchâ functions, users are encouraged to work with:
categorical_node_match
categorical_edge_match
categroical_multiedge_match
numerical_node_match
numerical_edge_match
numerical_multiedge_match
generic_node_match
generic_edge_match
generic_multiedge_match
These functions construct functions which can be passed to âis_isomorphicâ. Finally, note that the above functions are not imported into the toplevel namespace and should be accessed from ânetworkx.algorithms.isomorphismâ. A useful import statement that will be repeated throughout documentation is:
import networkx.algorithms.isomorphism as iso
attracting_components
A list of lists is returned instead of a list of tuples.
condensation
The condensation algorithm now takes a second argument (scc) and returns a graph with nodes labeled as integers instead of node tuples.
degree connectivity
average_in_degree_connectivity and average_out_degree_connectivity have have been replaced with
average_degree_connectivity(G, source=âinâ, target=âinâ)
and
average_degree_connectivity(G, source=âoutâ, target=âoutâ)
neighbor degree
average_neighbor_in_degree and average_neighbor_out_degreey have have been replaced with
average_neighbor_degree(G, source=âinâ, target=âinâ)
and
average_neighbor_degree(G, source=âoutâ, target=âoutâ)
This page reflects API changes from networkx1.4 to networkx1.5.
Please send comments and questions to the networkxdiscuss mailing list: http://groups.google.com/group/networkxdiscuss .
Many âweightedâ graph algorithms now take optional parameter to specifiy which edge attribute should be used for the weight (default=âweightâ) (ticket https://networkx.lanl.gov/trac/ticket/509)
In some cases the parameter name was changed from weighted_edges, or weighted, to weight. Here is how to specify which edge attribute will be used in the algorithms:
Algorithms affected are:
betweenness_centrality, closeness_centrality, edge_bewteeness_centrality, betweeness_centrality_subset, edge_betweenness_centrality_subset, betweenness_centrality_source, load, closness_vitality, weiner_index, spectral_bipartivity current_flow_betweenness_centrality, edge_current_flow_betweenness_centrality, current_flow_betweenness_centrality_subset, edge_current_flow_betweenness_centrality_subset, laplacian, normalized_laplacian, adj_matrix, adjacency_spectrum, shortest_path, shortest_path_length, average_shortest_path_length, single_source_dijkstra_path_basic, astar_path, astar_path_length
The random geometric graph generator has been simplified. It no longer supports the create_using, repel, or verbose parameters. An optional pos keyword was added to allow specification of node positions.
We have made some API changes, detailed below, to add clarity. This page reflects changes from networkx1.3 to networkx1.4. For changes from earlier versions to networkx1.0 see Version 1.0 API changes.
Please send comments and questions to the networkxdiscuss mailing list: http://groups.google.com/group/networkxdiscuss .
These algorithms now raise an exception when a source and a target are specified and no path exist between these two nodes. The exception is a NetworkXNoPath exception.
We have made some significant API changes, detailed below, to add functionality and clarity. This page reflects changes from networkx0.99 to networkx1.0. For changes from earlier versions to networkx0.99 see Version 0.99 API changes.
Version 1.0 requires Python 2.4 or greater.
Please send comments and questions to the networkxdiscuss mailing list: http://groups.google.com/group/networkxdiscuss .
In the future we will use a more standard release numbering system with major.minor[build] labels where major and minor are numbers and [build] is a label such as âdev1379â to indicate a development version or ârc1â to indicate a release candidate.
We plan on sticking closer to a timebased release schedule with smaller incremental changes released on a roughly quarterly basis. The graph classes API will remain fixed, unless we determine there are serious bugs or other defects in the existing classes, until networkx2.0 is released at some time in the future.
The most significant changes in are in the graph classes. All of the graph classes now allow optional graph, node, and edge attributes. Those attributes are stored internally in the graph classes as dictionaries and can be accessed simply like Python dictionaries in most cases.
Each graph keeps a dictionary of key=value attributes in the member G.graph. These attributes can be accessed directly using G.graph or added at instantiation using keyword arguments.
>>> G=nx.Graph(region='Africa')
>>> G.graph['color']='green'
>>> G.graph
{'color': 'green', 'region': 'Africa'}
Each node has a corresponding dictionary of attributes. Adding attributes to nodes is optional.
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
>>> G.nodes(data=True)
[(1, {'room': 714, 'time': '5pm'}), (3, {'time': '2pm'})]
Each edge has a corresponding dictionary of attributes. The default edge data is now an empty dictionary of attributes and adding attributes to edges is optional.
A common use case is to add a weight attribute to an edge:
>>> G.add_edge(1,2,weight=3.14159)
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
Now takes optional keyword=value attributes on initialization.
>>> G=nx.Graph(year='2009',city='New York')
Now takes optional keyword=value attributes or a dictionary of attributes.
>>> G.add_node(1,room=714)
Now takes optional keyword=value attributes or a dictionary of attributes applied to all affected nodes.
>>> G.add_nodes_from([1,2],time='2pm') # all nodes have same attribute
Now takes optional keyword=value attributes or a dictionary of attributes.
>>> G.add_edge(1, 2, weight=4.7 )
Now takes optional keyword=value attributes or a dictionary of attributes applied to all affected edges.
>>> G.add_edges_from([(3,4),(4,5)], color='red') >>> G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])
New keyword data=TrueFalse keyword determines whether to return twotuples (n,dict) (True) with node attribution dictionary
>>> G=nx.Graph([(1,2),(3,4)]) >>> G.nodes(data=True) [(1, {}), (2, {}), (3, {}), (4, {})]
Now returns a deep copy of the graph (copies all underlying data and attributes for nodes and edges). Use the class initializer to make a shallow copy:
>>> G=nx.Graph() >>> G_shallow=nx.Graph(G) # shallow copy >>> G_deep=G.copy() # deep copy
Now returns a deep copy of the graph (copies all underlying data and attributes for nodes and edges). Use the class initializer to make a shallow copy:
>>> G=nx.Graph() >>> D_shallow=nx.DiGraph(G) # shallow copy >>> D_deep=G.to_directed() # deep copy
With copy=True now returns a deep copy of the graph (copies all underlying data and attributes for nodes and edges).
>>> G=nx.Graph() >>> # note: copy keyword deprecated in networkx>1.0 >>> # H=G.subgraph([],copy=True) # deep copy of all data
Now take optional keyword=value attributes or a dictionary of attributes which are applied to all edges affected by the method.
>>> G=nx.Graph() >>> G.add_path([0,1,2,3],width=3.2)
The preferred name is now remove_node().
No longer raises an exception on an attempt to delete a node not in the graph. The preferred name is now remove_nodes_from().
Now raises an exception on an attempt to delete an edge not in the graph. The preferred name is now remove_edge().
Renamed to get_edge_data(). Returns the edge attribute dictionary.
The fastest way to get edge data for edge (u,v) is to use G[u][v] instead of G.get_edge_data(u,v)
Use methods G.is_directed() and G.is_multigraph(). All graphs are weighted graphs now if they have numeric values in the âweightâ edge attribute.
Convenience method to add weighted edges to graph using a list of 3tuples (u,v,weight).
Renamed from get_edge().
The fastest way to get edge data for edge (u,v) is to use G[u][v] instead of G.get_edge_data(u,v)
replaces member G.directed
replaces member G.multigraph
ego_graph, stochastic_graph, PageRank algorithm, HITS algorithm, GraphML writer, freeze, is_frozen, A* algorithm, directed scalefree generator, random clustered graph.
Edge information is now stored in an attribution dictionary so all edge data must be given a key to identify it.
There is currently only one standard/reserved key, âweightâ, which is used by algorithms and functions that use weighted edges. The associated value should be numeric. All other keys are available for users to assign as needed.
>>> G=nx.Graph()
>>> G.add_edge(1,2,weight=3.1415) # add the edge 12 with a weight
>>> G[1][2]['weight']=2.3 # set the weight to 2.3
Similarly, for direct access the edge data, use the key of the edge data to retrieve it.
>>> w = G[1][2]['weight']
All NetworkX algorithms that require/use weighted edges now use the âweightâ edge attribute. If you have existing algorithms that assumed the edge data was numeric, you should replace G[u][v] and G.get_edge(u,v) with G[u][v][âweightâ].
An idiom for getting a weight for graphs with or without an assigned weight key is
>>> w= G[1][2].get('weight',1) # set w to 1 if there is no 'weight' key
The version networkx0.99 is the penultimate release before networkx1.0. We have bumped the version from 0.37 to 0.99 to indicate (in our unusual version number scheme) that this is a major change to NetworkX.
We have made some significant changes, detailed below, to NetworkX to improve performance, functionality, and clarity.
Version 0.99 requires Python 2.4 or greater.
Please send comments and questions to the networkxdiscuss mailing list. http://groups.google.com/group/networkxdiscuss
The most significant changes are in the graph classes. We have redesigned the Graph() and DiGraph() classes to optionally allow edge data. This change allows Graph and DiGraph to naturally represent weighted graphs and to hold arbitrary information on edges.
 Both Graph and DiGraph take an optional argument weighted=TrueFalse. When weighted=True the graph is assumed to have numeric edge data (with default 1). The Graph and DiGraph classes in earlier versions used the Python None as data (which is still allowed as edge data).
 The Graph and DiGraph classes now allow self loops.
 The XGraph and XDiGraph classes are removed and replaced with MultiGraph and MultiDiGraph. MultiGraph and MultiDiGraph optionally allow parallel (multiple) edges between two nodes.
The mapping from old to new classes is as follows:
 Graph > Graph (self loops allowed now, default edge data is 1)
 DiGraph > DiGraph (self loops allowed now, default edge data is 1)
 XGraph(multiedges=False) > Graph
 XGraph(multiedges=True) > MultiGraph
 XDiGraph(multiedges=False) > DiGraph
 XDiGraph(multiedges=True) > MultiDiGraph
New keyword data=TrueFalse keyword determines whether to return twotuples (u,v) (False) or threetuples (u,v,d) (True)
The preferred name is now remove_node().
No longer raises an exception on an attempt to delete a node not in the graph. The preferred name is now remove_nodes_from().
Now raises an exception on an attempt to delete an edge not in the graph. The preferred name is now remove_edge().
The preferred name is now remove_edges_from().
The add_edge() method no longer accepts an edge tuple (u,v) directly. The tuple must be unpacked into individual nodes.
>>> import networkx as nx >>> u='a' >>> v='b' >>> e=(u,v) >>> G=nx.Graph()Old
>>> # G.add_edge((u,v)) # or G.add_edge(e)New
>>> G.add_edge(*e) # or G.add_edge(*(u,v))The * operator unpacks the edge tuple in the argument list.
Add edge now has a data keyword parameter for setting the default (data=1) edge data.
>>> # G.add_edge('a','b','foo') # add edge with string "foo" as data >>> # G.add_edge(1,2,5.0) # add edge with float 5 as data
Now can take list or iterator of either 2tuples (u,v), 3tuples (u,v,data) or a mix of both.
Now has data keyword parameter (default 1) for setting the edge data for any edge in the edge list that is a 2tuple.
The has_edge() method no longer accepts an edge tuple (u,v) directly. The tuple must be unpacked into individual nodes.
Old:
>>> # G.has_edge((u,v)) # or has_edge(e)New:
>>> G.has_edge(*e) # or has_edge(*(u,v)) TrueThe * operator unpacks the edge tuple in the argument list.
Now has the keyword argument âdefaultâ to specify what value to return if no edge is found. If not specified an exception is raised if no edge is found.
The fastest way to get edge data for edge (u,v) is to use G[u][v] instead of G.get_edge(u,v)
The degree_iter method now returns an iterator over pairs of (node, degree). This was the previous behavior of degree_iter(with_labels=true) Also there is a new keyword weighted=FalseTrue for weighted degree.
The argument inplace=FalseTrue has been replaced with copy=TrueFalse.
Subgraph no longer takes create_using keyword. To change the graph type either make a copy of the graph first and then change type or change type and make a subgraph. E.g.
>>> G=nx.path_graph(5) >>> H=nx.DiGraph(G.subgraph([0,1])) # digraph of copy of induced subgraph
Getting node neighbors from the graph with G[v] now returns a dictionary.
>>> G=nx.path_graph(5) >>> # G[0] # {1: 1}To get a list of neighbors you can either use the keys of that dictionary or use
>>> G.neighbors(0) [1]This change allows algorithms to use the underlying dictofdict representation through G[v] for substantial performance gains. Warning: The returned dictionary should not be modified as it may corrupt the graph data structure. Make a copy G[v].copy() if you wish to modify the dict.
now a function
>>> G=nx.Graph(name='test me') >>> nx.info(G) Name: test me Type: Graph Number of nodes: 0 Number of edges: 0
now a function
now a function
use the directed attribute
>>> G=nx.DiGraph() >>> # G.directed # True
use G.edges()
use
>>> G=nx.DiGraph() >>> R=G.reverse() >>> R.edges() []or
>>> [(v,u) for (u,v) in G.edges()] []
Some of the code modules were moved into subdirectories.
Import statements such as:
import networkx.centrality
from networkx.centrality import *
may no longer work (including that example).
Use either
>>> import networkx # e.g. centrality functions available as networkx.fcn()
or
>>> from networkx import * # e.g. centrality functions available as fcn()
For Graph and DiGraph self loops are now allowed. This might affect code or algorithms that add self loops which were intended to be ignored.
Use the methods
 nodes_with_selfloops()
 selfloop_edges()
 number_of_selfloops()
to discover any self loops.
Copies of NetworkX graphs including using the copy() method now return complete copies of the graph. This means that all connection information is copiedâsubsequent changes in the copy do not change the old graph. But node keys and edge data in the original and copy graphs are pointers to the same data.
Used internally  now called nbunch_iter and returns an iterator.
Mostly you can just run the code and python will raise an exception for features that changed. Common places for changes are
 Converting XGraph() to either Graph or MultiGraph
 Converting XGraph.edges() to Graph.edges(data=True)
 Switching some rarely used methods to attributes (e.g. directed) or to functions (e.g. node_boundary)
 If you relied on the old default edge data being None, you will have to account for it now being 1.
You may also want to look through your code for places which could improve speed or readability. The iterators are helpful with large graphs and getting edge data via G[u][v] is quite fast. You may also want to change G.neighbors(n) to G[n] which returns the dict keyed by neighbor nodes to the edge data. It is faster for many purposes but does not work well when you are changing the graph.
Release date: TBD
This is a guide for people moving from NetworkX 1.X to NetworkX 2.0
Any issues with these can be discussed on the [mailing list](https://groups.google.com/forum/#!forum/networkxdiscuss)
As you know we have made some major changes to the methods in the Multi/Di/Graph classes.
Methods that used to return containers now return iterators and methods that returned iterators have been removed.
For example, G.nodes()
now returns an iterator and G.nodes_iter()
has been removed.
The methods changed are explained with examples below.
>>> import networkx as nx
>>> G = nx.complete_graph(5)
>>> G.nodes()
<dictionarykeyiterator at 0x102ae8730>
People suprised by this output and expecting something like this
>>> G.nodes()
[0, 1, 2, 3, 4]
donât panic. Nothing is wrong.
Now G.nodes()
returns an iterator. If you want a list of nodes send the iterator to the Python list function
>>> list(G.nodes())
[0, 1, 2, 3, 4]
In the same way for G.edges()
>>> G.edges()
<generator object edges at 0x102ae9fa0>
>>> list(G.edges())
[(0, 1),
(0, 2),
(0, 3),
(0, 4),
(1, 2),
(1, 3),
(1, 4),
(2, 3),
(2, 4),
(3, 4)]
and G.neighbors(n)
where n is a node.
>>> G.neighbors(2)
<dictionarykeyiterator at 0x102ae8aa0>
>>> list(G.neighbors(2))
[0, 1, 3, 4]
So, basically you can switch back to the old behavior by adding list()
to the method.
For methods that used to return a dict, like G.degree()
, the new iterator version
returns a (key,value) 2tuple so that passing it to Pythonâs dict function recovers
the original behavior if desired.
Note that passing a single node to the degree method still returns the degree of that node as it always has.
>>> G.degree(2)
4
>>> G.degree([1,2,3])
<generator object d_iter at 0x102ba8780>
>>> list(G.degree([1,2,3]))
[(1, 4), (2, 4), (3, 4)]
>>> dict(G.degree([1,2,3]))
{1: 4, 2: 4, 3: 4}
>>> G.degree()
<generator object d_iter at 0x102ba8af0>
>>> list(G.degree())
[(0, 4), (1, 4), (2, 4), (3, 4), (4, 4)]
>>> dict(G.degree())
{0: 4, 1: 4, 2: 4, 3: 4, 4: 4}
G.degree()
used to return a dictionary. We can typecast the generator to return a list or dict as shown in the
above example.
Now lets move to DiGraphs. Everything is similar to Graphs. But we have a few more methods for DiGraphs. Letâs have a look on them.
>>> D = nx.DiGraph()
>>> D.add_edges_from([(1, 2), (2, 3), (1, 3), (2, 4)])
>>> D.nodes()
<dictionarykeyiterator at 0x102bd68e8>
>>> list(D.nodes())
[1, 2, 3, 4]
>>> D.edges()
<generator object edges at 0x102ba88c0>
>>> list(D.edges())
[(1, 2), (1, 3), (2, 3), (2, 4)]
>>> D.in_degree(2)
1
>>> D.out_degree(2)
2
>>> D.in_edges()
<generator object in_edges at 0x102ba8cd0>
>>> list(D.in_edges())
[(1, 2), (1, 3), (2, 3), (2, 4)]
>>> D.out_edges(2)
<generator object edges at 0x102ba8c80>
>>> list(D.out_edges(2))
(2, 3), (2, 4)]
>>> D.in_degree()
<generator object d_iter at 0x102ba8a00>
>>> list(D.in_degree())
[(1, 0), (2, 1), (3, 2), (4, 1)]
>>> D.successors(2)
<dictionarykeyiterator at 0x102bdb418>
>>> list(D.successors(2))
[3, 4]
>>> D.predecessors(2)
<dictionarykeyiterator at 0x102bdb730>
>>> list(D.predecessors(2))
[1]
The same changes apply to MultiGraphs and MultiDiGraphs.
Release date: 2 August 2015
Support for Python 2.6 is dropped in this release.
Release date: 13 September 2014
Bugfix release for minor installation and documentation issues.
https://github.com/networkx/networkx/milestones/networkx1.9.1
Release date: 21 June 2014
Support for Python 3.1 is dropped in this release.
Release date: 28 July 2013
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
Release date: 4 July 2012
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=networkx1.7
Release date: 20 November 2011
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 kclique communities, and writing JSON format output.
New examples for drawing with D3 Javascript library, and ordering matrices with the CuthillMcKee algorithm.
More memory efficient implementation of currentflow betweenness and new approximation algorithms for currentflow betweenness and shortestpath 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=networkx1.6
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=networkx1.5
 Algorithms for
generating
andanalyzing
bipartite graphsMaximal independent set
algorithmErdĆsGallai graphical degree sequence test
Negative edge cycle test
 More memory efficient
Dijkstra path length
with cutoff parameterWeighted clustering coefficient
 Read and write version 1.2 of
GEXF reader
formatNeighbor degree correlation
that handle subsets of nodesInplace node relabeling
 Many âweightedâ graph algorithms now take optional parameter to use specified edge attribute (default=âweightâ) (ticket https://networkx.lanl.gov/trac/ticket/509)
 Test for
distance regular
graphs Fast
directed ErdĆsRenyi graph
generator Fast
expected degree graph
generatorNavigable small world
generatorWaxman model
generatorGeographical threshold graph
generatorKarate Club, Florentine Families, and Davis' Women's Club
graphs
 Fix edge handling for multigraphs in networkx/graphviz interface (ticket https://networkx.lanl.gov/trac/ticket/507)
 Update networkx/pydot interface for new versions of pydot (ticket https://networkx.lanl.gov/trac/ticket/506) (ticket https://networkx.lanl.gov/trac/ticket/535)
 Fix negative cycle handling in BellmanFord (ticket https://networkx.lanl.gov/trac/ticket/502)
 Write more attributes with GraphML and GML formats (ticket https://networkx.lanl.gov/trac/ticket/480)
 Handle white space better in read_edgelist (ticket https://networkx.lanl.gov/trac/ticket/513)
 Better parsing of Pajek format files (ticket https://networkx.lanl.gov/trac/ticket/524) (ticket https://networkx.lanl.gov/trac/ticket/542)
 Isolates functions work with directed graphs (ticket https://networkx.lanl.gov/trac/ticket/526)
 Faster conversion to numpy matrices (ticket https://networkx.lanl.gov/trac/ticket/529)
 Add graph[ânameâ] and use properties to access Graph.name (ticket https://networkx.lanl.gov/trac/ticket/544)
 Topological sort confused None and 0 (ticket https://networkx.lanl.gov/trac/ticket/546)
 GEXF writer mishandled weight=0 (ticket https://networkx.lanl.gov/trac/ticket/550)
 Speedup in SciPy version of PageRank (ticket https://networkx.lanl.gov/trac/ticket/554)
 Numpy PageRank node order incorrect + speedups (ticket https://networkx.lanl.gov/trac/ticket/555)
Release date: 23 January 2011
kshell,kcrust,kcorona
read GraphML files from yEd
read/write GEXF format files
find cycles in a directed graph
DFS
andBFS
algorithmschordal graph functions
Prim's algorithm for minimum spanning tree
rary tree generator
rich club coefficient
 NumPy matrix version of
Floyd's algorithm for allpairs shortest path
read GIS shapefiles
functions to get and set node and edge attributes
 and more, see https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx1.4
gnp_random_graph()
now takes a directed=TrueFalse keyword instead of create_usinggnm_random_graph()
now takes a directed=TrueFalse keyword instead of create_using
Release date: 28 August 2010
See: https://networkx.lanl.gov/trac/timeline
 Works with Python versions 2.6, 2.7, 3.1, and 3.2 (but not 2.4 and 2.5).
Minimum cost flow algorithms
BellmanFord shortest paths
GraphML reader and writer
More exception/error types
 Updated many tests to unittest style. Run with: âimport networkx; networkx.test()â (requires nose testing package)
 and more, see https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx1.3
minimum_spanning_tree() now returns a NetworkX Graph (a tree or forest)
Release date: 28 July 2010
See: https://networkx.lanl.gov/trac/timeline
FordFulkerson max flow and min cut
Closeness vitality
Eulerian circuits
Functions for isolates
Simpler s_max generator
 Compatible with IronPython2.6
 Improved testing functionality: import networkx; networkx.test() tests entire package and skips tests with missing optional packages
 All tests work with Python2.4
 and more, see https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx1.2
Release date: 21 April 2010
See: https://networkx.lanl.gov/trac/timeline
Algorithm for finding a basis for graph cycles
Blockmodeling
Assortativity and mixing matrices
indegree and outdegree centrality
Attracting components
andcondensation
.Weakly connected components
Simpler interface to shortest path algorithms
Edgelist format to read and write data with attributes
Attribute matrices
GML reader for nested attributes
 Currentflow (random walk)
betweenness
andcloseness
.Directed configuration model
, anddirected random graph model
. Improved documentation of drawing, shortest paths, and other algorithms
 Many more tests, can be run with âimport networkx; networkx.test()â
 and much more, see https://networkx.lanl.gov/trac/query?status=closed&group=milestone&milestone=networkx1.1
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:
Graph.degree()
,MultiGraph.degree()
,DiGraph.degree()
,DiGraph.in_degree()
,DiGraph.out_degree()
,MultiDiGraph.degree()
,MultiDiGraph.in_degree()
,MultiDiGraph.out_degree()
.clustering()
,triangles()
node_clique_number()
,number_of_cliques()
,cliques_containing_node()
eccentricity()
The following now return dictionaries by default (instead of lists)
pagerank()
hits()
add_nodes_from now accepts (node,attrdict) twotuples
>>> G=nx.Graph()
>>> G.add_nodes_from([(1,{'color':'red'})])
 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 doublequoted labels with pydot
 Normalize betweenness_centrality for undirected graphs correctly
 Normalize eigenvector_centrality by l2 norm
read_gml()
now returns multigraphs
Release date: 11 Jan 2010
See: https://networkx.lanl.gov/trac/timeline
Bug fix release for missing setup.py in manifest.
Release date: 8 Jan 2010
See: https://networkx.lanl.gov/trac/timeline
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* (AStar) algorithm
 PageRank, HITS, and eigenvector centrality
 Read Pajek files
 Line graphs
 Minimum spanning tree (Kruskalâs algorithm)
 Dense and sparse FruchtermanReingold layout
 Random clustered graph generator
 Directed scalefree 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=networkx1.0
 Update to work with networkx1.0 API
 Graph subclass example
Release date: 18 November 2008
See: https://networkx.lanl.gov/trac/timeline
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.
 handle root= option to draw_graphviz correctly
 Update to work with networkx0.99 API
 Drawing examples now use matplotlib.pyplot interface
 Improved drawings in many examples
 New examples  see http://networkx.lanl.gov/examples/
Release date: 17 August 2008
See: https://networkx.lanl.gov/trac/timeline
NetworkX now requires Python 2.4 or later for full functionality.
 Edge coloring and node line widths with Matplotlib drawings
 Update pydot functions to work with pydot1.0.2
 Maximumweight 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
 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 BarabasiAlbert model
 Better care of color maps with Matplotlib when drawing colored nodes and edges
 Fix error handling in layout.py
 Ubigraph examples showing 3D drawing
Release date: 13 January 2008
See: https://networkx.lanl.gov/trac/timeline
 GML format graph reader, tests, and example (football.py)
 edge_betweenness() and load_betweenness()
 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
Release date: 27 July 2007
See: https://networkx.lanl.gov/trac/timeline
Small update to fix import readwrite problem and maintain Python2.3 compatibility.
Release date: 22 July 2007
See: https://networkx.lanl.gov/trac/timeline
 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
 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 dictofdict data
Release date: 12 April 2007
See: https://networkx.lanl.gov/trac/timeline
 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
 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 uv
 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_*
Release date: 27 November 2006
See: https://networkx.lanl.gov/trac/timeline
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()
 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
 Draw edges with colormap
Release date: 29 September 2006
See: https://networkx.lanl.gov/trac/timeline
 Update to work with numpy1.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
 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
 Expected degree sequence
 New pygraphviz interface
Release date: 20 July 2006
See: https://networkx.lanl.gov/trac/timeline
 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
 Allow drawing graphs with no edges using pylab
 Use faster heapq in dijkstra
 Donât complain if X windows is not available
 update drawing examples
Release date: 23 June 2006
See: https://networkx.lanl.gov/trac/timeline
 update to work with Python 2.5
 bidirectional version of shortest_path and Dijkstra
 single_source_shortest_path and all_pairs_shortest_path
 smetric and experimental code to generate maximal smetric 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
 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
 unicode node labels
Release date: 28 April 2006
See: https://networkx.lanl.gov/trac/timeline
 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
 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
Release date: 13 March 2006
See: https://networkx.lanl.gov/trac/timeline
 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 breadthfirst search of G starting at node n. https://networkx.lanl.gov/trac/ticket/26
 Formation of giant component in binomial_graph:
 Chess masters matches:
 Gallery https://networkx.lanl.gov/gallery.html
 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 UTF8 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
Release date: 5 February 2006
See: https://networkx.lanl.gov/trac/timeline
 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 onthefly 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.
 Minardâs data for Napoleonâs Russian campaign
 XGraph(multiedges=True) returns a copy of the list of edges for get_edge()
Release date: 6 January 2006
 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).
 Several new examples showing how draw to graphs with various properties of nodes, edges, and labels
 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)
Release date: 5 December 2005
 Uses setuptools for installation http://peak.telecommunity.com/DevCenter/setuptools
 Improved testing infrastructure, can now run python setup.py test
 Added interface to draw graphs with pygraphviz https://networkx.lanl.gov/pygraphviz/
 is_directed() function call
 Email example shows how to use XDiGraph with Python objects as edge data
 Reformat menu, minor changes to Readme, better stylesheet
 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 nonrecursive toposort and is_directed_acyclic graph
Release date: 20 August 2005
 Update of Dijkstra algorithm code
 dfs_successor now calls proper search method
 Changed to list comprehension in DiGraph.reverse() for python2.3 compatibility
 BarabasiAlbert graph generator fixed
 Attempt to add self loop should add node even if parallel edges not allowed
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
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 *
 DiGraph reverse
 Graph generators
 watts_strogatz_graph now does rewiring method
 old watts_strogatz_graph>newman_watts_strogatz_graph
 Changed to reflect NXnetworkx change
 main site is now https://networkx.lanl.gov/
 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.
Release date: 17 June 2005
 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
 Kevin Bacon movie actor graph: Examples/kevin_bacon.py
 Compute eigenvalues of graph Laplacian: Examples/eigenvalues.py
 Atlas of small graphs: Examples/atlas.py
 Rewrite of setup scripts to install documentation and tests in documentation directory specified
 Handle calls to edges() with nonnode, noniterable 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 namespaces
 Other minor bugfixes and testing added
[BA02]  R. Albert and A.L. BarabĂĄsi, âStatistical mechanics of complex networksâ, Reviews of Modern Physics, 74, pp. 4797, 2002. http://arxiv.org/abs/condmat/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, SpringerVerlag, 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ĆsGallai theorem on graph sequences.â Bulletin of the Australian Mathematical Society, 33, pp 6770, 1986. http://dx.doi.org/10.1017/S0004972700002872 
[Diestel97]  R. Diestel, âGraph Theoryâ, SpringerVerlag, 1997. http://diestelgraphtheory.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, 496506, 1962. 
[havel1955]  Havel, V. âA Remark on the Existence of Finite Graphsâ Casopis Pest. Mat. 80, 477480, 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. 167256, 2003. http://epubs.siam.org/doi/abs/10.1137/S003614450342480 
[Sedgewick02]  R. Sedgewick, âAlgorithms in C: Parts 14: 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 
Release:  2.0.dev_20170518025222 

Date:  May 18, 2017 
Release:  2.0.dev_20170518025222 

Date:  May 18, 2017 
# needs mayavi2
# run with ipython wthread
import networkx as nx
import numpy as np
from enthought.mayavi import mlab
# 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
Release:  2.0.dev_20170518025222 

Date:  May 18, 2017 
#!/usr/bin/env python
"""
Create an G{n,m} random graph and compute the eigenvalues.
Requires numpy and matplotlib.
"""
import networkx as nx
import numpy.linalg
import matplotlib.pyplot as plt
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()
#!/usr/bin/env python
# * coding: utf8 *
"""
Example using unicode strings as graph labels.
Also shows creative use of the Heavy Metal Umlaut:
http://en.wikipedia.org/wiki/Heavy_metal_umlaut
"""
# Author: Aric Hagberg (hagberg@lanl.gov)
# Copyright (C) 20062016 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
try:
import pylab as P
except ImportError:
pass
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 UTF8 encoding
fh=open('edgelist.utf8','wb')
fh.write('# * coding: utf8 *\n'.encode('utf8')) # encoding hint for emacs
NX.write_multiline_adjlist(G,fh,delimiter='\t', encoding = 'utf8')
# read and store in UTF8
fh=open('edgelist.utf8','rb')
H=NX.read_multiline_adjlist(fh,delimiter='\t', encoding = 'utf8')
for n in G.nodes():
if n not in H:
print(False)
print(list(G.nodes()))
try:
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)
P.show()
except:
pass
"""
Digraphs from Integervalued 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"
"""
from networkx import *
from math import *
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 leastsignificant digit
dlist = [n % b] + dlist
# Floordivision
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=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=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