Doc/ Templates/Autosummary/Base
{{ objname | escape | underline }}
.. currentmodule:: {{ module }}
.. auto{{ objtype }}:: {{ objname }}
---
Doc/ Templates/Autosummary/Class
{{ fullname | escape | underline}}
.. currentmodule:: {{ module }}
.. autoclass:: {{ objname }}
{% block methods %}
.. automethod:: __init__
{% if methods %}
.. rubric:: {{ _('Methods') }}
.. autosummary::
:toctree: generated/
{% for item in methods %}
{% if item != "__init__" %}
~{{ name }}.{{ item }}
{% endif %}
{%- endfor %}
{% endif %}
{% endblock %}
{% block attributes %}
{% if attributes %}
.. rubric:: {{ _('Attributes') }}
.. autosummary::
:toctree: generated/
{% for item in attributes %}
~{{ name }}.{{ item }}
{%- endfor %}
{% endif %}
{% endblock %}
---
Doc/ Static/README
wget https://raw.githubusercontent.com/networkx/branding/main/logo/networkx_favicon.svg
inkscape -w 16 -h 16 -o 16.png networkx_favicon.svg
inkscape -w 32 -h 32 -o 32.png networkx_favicon.svg
inkscape -w 48 -h 48 -o 48.png networkx_favicon.svg
convert 16.png 32.png 48.png favicon.ico
---
Doc/Developer/Nxeps/Index
.. _nxep_list:
NXEPs
*
NetworkX Enhancement Proposals (NXEPs) document major changes or proposals.
.. toctree::
:maxdepth: 1
nxep-0000
nxep-0001
nxep-0002
nxep-0003
nxep-0004
.. toctree::
:hidden:
nxep-template
---
Doc/Developer/Nxeps/Nxep 0000
.. _NXEP0:
============================
NXEP 0 — Purpose and Process
============================
:Author: Jarrod Millman <[email protected]>
:Status: Accepted
:Type: Process
:Created: 2020-06-25
What is a NXEP?
---------------
NXEP stands for NetworkX Enhancement Proposal. NXEPs are the primary
mechanisms for proposing major new features, for collecting community input on
an issue, and for documenting the design decisions that have gone into
NetworkX. A NXEP should provide a concise technical specification of the
feature and a rationale for the feature. The NXEP author is responsible for
building consensus within the community and documenting dissenting opinions.
Because the NXEPs are maintained as text files in a versioned
repository, their revision history is the historical record of the
feature proposal [1]_.
Types
^^^^^
There are three kinds of NXEPs:
1. A Standards Track NXEP describes a new feature or implementation
for NetworkX.
2. An Informational NXEP describes a NetworkX design issue, or provides
general guidelines or information to the Python community, but does not
propose a new feature. Informational NXEPs do not necessarily represent a
NetworkX community consensus or recommendation, so users and implementers are
free to ignore Informational NXEPs or follow their advice.
3. A Process NXEP describes a process surrounding NetworkX, or
proposes a change to (or an event in) a process. Process NXEPs are
like Standards Track NXEPs but apply to areas other than the NetworkX
language itself. They may propose an implementation, but not to
NetworkX's codebase; they require community consensus. Examples include
procedures, guidelines, changes to the decision-making process, and
changes to the tools or environment used in NetworkX development.
Any meta-NXEP is also considered a Process NXEP.
NXEP Workflow
-------------
The NXEP process begins with a new idea for NetworkX. It is highly
recommended that a single NXEP contain a single key proposal or new
idea. Small enhancements or patches often don't need
a NXEP and can be injected into the NetworkX development workflow with a
pull request to the NetworkX repo_. The more focused the
NXEP, the more successful it tends to be.
If in doubt, split your NXEP into several well-focused ones.
Each NXEP must have a champion---someone who writes the NXEP using the style
and format described below, shepherds the discussions in the appropriate
forums, and attempts to build community consensus around the idea. The NXEP
champion (a.k.a. Author) should first attempt to ascertain whether the idea is
suitable for a NXEP. Posting to the networkx-discussion mailing list_ is the best
way to go about doing this.
The proposal should be submitted as a draft NXEP via a GitHub pull_ to the `
requestdoc/nxeps directory with the name nxep-<n>.rst
where <n> is an appropriately assigned four-digit number (e.g.,nxep-0000.rst). The draft must use the :doc:nxep-template file.
Once the PR for the NXEP is in place, a post should be made to the
mailing list containing the sections up to "Backward compatibility",
with the purpose of limiting discussion there to usage and impact.
Discussion on the pull request will have a broader scope, also including
details of implementation.
At the earliest convenience, the PR should be merged (regardless of
whether it is accepted during discussion). Additional PRs may be made
by the Author to update or expand the NXEP, or by maintainers to set
its status, discussion URL, etc.
Standards Track NXEPs consist of two parts, a design document and a
reference implementation. It is generally recommended that at least a
prototype implementation be co-developed with the NXEP, as ideas that sound
good in principle sometimes turn out to be impractical when subjected to the
test of implementation. Often it makes sense for the prototype implementation
to be made available as PR to the NetworkX repo (making sure to appropriately
mark the PR as a WIP).
Review and Resolution
^^^^^^^^^^^^^^^^^^^^^
NXEPs are discussed on the mailing list. The possible paths of the
status of NXEPs are as follows:
.. image:: _static/nxep-0000.png
All NXEPs should be created with the Draft status.
Eventually, after discussion, there may be a consensus that the NXEP
should be accepted – see the next section for details. At this point
the status becomes Accepted.
Once a NXEP has been Accepted, the reference implementation must be
completed. When the reference implementation is complete and incorporated
into the main source code repository, the status will be changed to Final.
To allow gathering of additional design and interface feedback before
committing to long term stability for a language feature or standard library
API, a NXEP may also be marked as "Provisional". This is short for
"Provisionally Accepted", and indicates that the proposal has been accepted for
inclusion in the reference implementation, but additional user feedback is
needed before the full design can be considered "Final". Unlike regular
accepted NXEPs, provisionally accepted NXEPs may still be Rejected or Withdrawn
even after the related changes have been included in a Python release.
Wherever possible, it is considered preferable to reduce the scope of a
proposal to avoid the need to rely on the "Provisional" status (e.g. by
deferring some features to later NXEPs), as this status can lead to version
compatibility challenges in the wider NetworkX ecosystem.
A NXEP can also be assigned status Deferred. The NXEP author or a
core developer can assign the NXEP this status when no progress is being made
on the NXEP.
A NXEP can also be Rejected. Perhaps after all is said and done it
was not a good idea. It is still important to have a record of this
fact. The Withdrawn status is similar---it means that the NXEP author
themselves has decided that the NXEP is actually a bad idea, or has
accepted that a competing proposal is a better alternative.
When a NXEP is Accepted, Rejected, or Withdrawn, the NXEP should be
updated accordingly. In addition to updating the status field, at the very
least the Resolution header should be added with a link to the relevant
thread in the mailing list archives.
NXEPs can also be Superseded by a different NXEP, rendering the
original obsolete. The Replaced-By and Replaces headers
should be added to the original and new NXEPs respectively.
Process NXEPs may also have a status of Active if they are never
meant to be completed, e.g. NXEP 0 (this NXEP).
How a NXEP becomes Accepted
^^^^^^^^^^^^^^^^^^^^^^^^^^^
A NXEP is Accepted by consensus of all interested contributors. We
need a concrete way to tell whether consensus has been reached. When
you think a NXEP is ready to accept, send an email to the
networkx-discussion mailing list with a subject like:
Proposal to accept NXEP #<number>: <title>
In the body of your email, you should:
* link to the latest version of the NXEP,
* briefly describe any major points of contention and how they were
resolved,
* include a sentence like: "If there are no substantive objections
within 7 days from this email, then the NXEP will be accepted; see
NXEP 0 for more details."
For an example, see: https://mail.python.org/pipermail/networkx-discussion/2018-June/078345.html
After you send the email, you should make sure to link to the email
thread from the Discussion section of the NXEP, so that people can
find it later.
Generally the NXEP author will be the one to send this email, but
anyone can do it – the important thing is to make sure that everyone
knows when a NXEP is on the verge of acceptance, and give them a final
chance to respond. If there's some special reason to extend this final
comment period beyond 7 days, then that's fine, just say so in the
email. You shouldn't do less than 7 days, because sometimes people are
travelling or similar and need some time to respond.
In general, the goal is to make sure that the community has consensus,
not provide a rigid policy for people to try to game. When in doubt,
err on the side of asking for more feedback and looking for
opportunities to compromise.
If the final comment period passes without any substantive objections,
then the NXEP can officially be marked Accepted. You should send a
followup email notifying the list (celebratory emoji optional but
encouraged 🎉✨), and then update the NXEP by setting its :Status:
to Accepted, and its :Resolution: header to a link to your
followup email.
If there are substantive objections, then the NXEP remains inDraft state, discussion continues as normal, and it can be
proposed for acceptance again later once the objections are resolved.
In unusual cases, disagreements about the direction or approach may
require escalation to the NetworkX :ref:steering_council who
then decide whether a controversial NXEP is Accepted.
Maintenance
^^^^^^^^^^^
In general, Standards track NXEPs are no longer modified after they have
reached the Final state as the code and project documentation are considered
the ultimate reference for the implemented feature.
However, finalized Standards track NXEPs may be updated as needed.
Process NXEPs may be updated over time to reflect changes
to development practices and other details. The precise process followed in
these cases will depend on the nature and purpose of the NXEP being updated.
Format and Template
-------------------
NXEPs are UTF-8 encoded text files using the reStructuredText_ format. Please
see the :doc:nxep-template file and the reStructuredTextPrimer_ for more
information. We use Sphinx_ to convert NXEPs to HTML for viewing on the web
[2]_.
Header Preamble
^^^^^^^^^^^^^^^
Each NXEP must begin with a header preamble. The headers
must appear in the following order. Headers marked with * are
optional. All other headers are required. ::
:Author: <list of authors' real names and optionally, email addresses>
:Status: <Draft | Active | Accepted | Deferred | Rejected |
Withdrawn | Final | Superseded>
:Type: <Standards Track | Process>
:Created: <date created on, in dd-mmm-yyyy format>
* :Requires: <nxep numbers>
* :NetworkX-Version: <version number>
* :Replaces: <nxep number>
* :Replaced-By: <nxep number>
* :Resolution: <url>
The Author header lists the names, and optionally the email addresses
of all the authors of the NXEP. The format of the Author header
value must be
Random J. User <[email protected]>
if the email address is included, and just
Random J. User
if the address is not given. If there are multiple authors, each should be on
a separate line.
References and Footnotes
------------------------
.. [1] This historical record is available by the normal git commands
for retrieving older revisions, and can also be browsed on
GitHub <https://github.com/networkx/networkx/tree/main/doc/developer/nxeps>_.
.. [2] The URL for viewing NXEPs on the web is
https://networkx.org/documentation/latest/developer/nxeps/index.html
.. _repo: https://github.com/networkx/networkx
.. _mailing list: https://groups.google.com/group/networkx-discuss/
.. _issue tracker: https://github.com/networkx/networkx/issues
.. _GitHub pull request: https://github.com/networkx/networkx/pulls
.. _reStructuredText: http://docutils.sourceforge.net/rst.html
.. _reStructuredTextPrimer: http://www.sphinx-doc.org/en/stable/rest.html
.. _Sphinx: http://www.sphinx-doc.org/en/stable/
---
Doc/Developer/Nxeps/Nxep 0001
.. _governance:
=======================================
NXEP 1 — Governance and Decision Making
=======================================
:Author: Jarrod Millman <[email protected]>
:Author: Dan Schult <[email protected]>
:Status: Accepted
:Type: Process
:Created: 2020-06-25
Abstract
========
NetworkX is a consensus-based community project. Anyone with an interest in the
project can join the community, contribute to the project design, and
participate in the decision making process. This document describes how that
participation takes place, how to find consensus, and how deadlocks are
resolved.
Roles And Responsibilities
==========================
The Community
-------------
The NetworkX community consists of anyone using or working with the project
in any way.
Contributors
------------
Any community member can become a contributor by interacting directly with the
project in concrete ways, such as:
- proposing a change to the code or documentation via a GitHub pull request;
- reporting issues on our
GitHub issues page <https://github.com/networkx/networkx/issues>_;mailing list <http://groups.google.com/group/networkx-discuss/>
- discussing the design of the library, website, or tutorials on the
_,open pull requests <https://github.com/networkx/networkx/pulls>
or in existing issues and pull requests; or
- reviewing
_,
among other possibilities. By contributing to the project, community members
can directly help to shape its future.
Contributors should read the :ref:contributor_guide and our :ref:code_of_conduct.
Core Developers
---------------
Core developers are community members that have demonstrated continued
commitment to the project through ongoing contributions. They
have shown they can be trusted to maintain NetworkX with care. Becoming a
core developer allows contributors to merge approved pull requests, cast votes
for and against merging a pull request, and be involved in deciding major
changes to the API, and thereby more easily carry on with their project related
activities. Core developers appear as team members on the
:ref:NetworkX Core Developers gallery<core-developers-team> and can
be messaged @networkx/core-developers. Corecore_dev
developers are expected to review code contributions while adhering to the
:ref:.
New core developers can be nominated by any existing core developer.
Discussion about new core developer nominations is one of the few activities
that takes place on the project's private management list. The decision to
invite a new core developer must be made by “lazy consensus”, meaning unanimous
agreement by all responding existing core developers. Invitation must take
place at least one week after initial nomination, to allow existing members
time to voice any objections.
.. _steering_council:
Steering Council
----------------
The Steering Council (SC) members are core developers who have additional
responsibilities to ensure the smooth running of the project. SC members are
expected to participate in strategic planning, approve changes to the
governance model, and make decisions about funding granted to the project
itself. (Funding to community members is theirs to pursue and manage.) The
purpose of the SC is to ensure smooth progress from the big-picture
perspective. Changes that impact the full project require analysis informed by
long experience with both the project and the larger ecosystem. When the core
developer community (including the SC members) fails to reach such a consensus
in a reasonable timeframe, the SC is the entity that resolves the issue.
The current list of steering council members appears on the
NetworkX Steering Council gallery<steering-council-team> and can
be messaged @networkx/steering-council.
Decision Making Process
=======================
Decisions about the future of the project are made through discussion with all
members of the community. All non-sensitive project management discussion takes
place on the project
mailing list <http://groups.google.com/group/networkx-discuss/>_issue tracker <https://github.com/networkx/networkx/issues>
and the _.
Occasionally, sensitive discussion may occur on a private list.
Decisions should be made in accordance with our :ref:mission_and_values.
NetworkX uses a consensus seeking process for making decisions. The group
tries to find a resolution that has no open objections among core developers.
Core developers are expected to distinguish between fundamental objections to a
proposal and minor perceived flaws that they can live with, and not hold up the
decision making process for the latter. If no option can be found without
an objection, the decision is escalated to the SC, which will itself use
consensus seeking to come to a resolution. In the unlikely event that there is
still a deadlock, the proposal will move forward if it has the support of a
simple majority of the SC. Any proposal must be described by a NetworkX :ref:nxep.
Decisions (in addition to adding core developers and SC membership as above)
are made according to the following rules:
- Minor documentation changes, such as typo fixes, or addition / correction of a
sentence (but no change of the NetworkX landing page or the “about”
page), require approval by a core developer and no disagreement or requested
changes by a core developer on the issue or pull request page (lazy
consensus). Core developers are expected to give “reasonable time” to others
to give their opinion on the pull request if they’re not confident others
would agree.
- Code changes and major documentation changes require agreement by two
core developers and no disagreement or requested changes by a core developer
on the issue or pull-request page (lazy consensus).
- Changes to the API principles require a :ref:nxep and follow the
decision-making process outlined above.
- Changes to this governance model or our mission and values
require a :ref:nxep and follow the decision-making process outlined above,
unless there is unanimous agreement from core developers on the change.
If an objection is raised on a lazy consensus, the proposer can appeal to the
community and core developers and the change can be approved or rejected by
escalating to the SC, and if necessary, a NXEP (see below).
.. _nxep:
Enhancement Proposals (NXEPs)
=============================
Any proposals for enhancements of NetworkX should be written as a formal NXEP
following the template :doc:nxep-template. The NXEP must be made public andnxep0
discussed before any vote is taken. The discussion must be summarized by a
key advocate of the proposal in the appropriate section of the NXEP.
Once this summary is made public and after sufficient time to allow the
core team to understand it, they vote.
The workflow of a NXEP is detailed in :ref:.
A list of all existing NXEPs is available :ref:here <nxep_list>.
Acknowledgments
===============
This document is based on the scikit-image governance document
<https://scikit-image.org/docs/stable/skips/1-governance.html>_.
---
Doc/Developer/Nxeps/Nxep 0002
.. _NXEP2:
==================================
NXEP 2 — API design of view slices
==================================
:Author: Mridul Seth
:Status: Accepted
:Type: Standards Track
:Created: 2020-07-23
Abstract
--------
Iterating over a subset of nodes or edges in a graph is a very common
operation in networkx analysis.
The graph classes in NetworkX (e.g. :class:~networkx.Graph,~networkx.DiGraph
:class:, :class:~networkx.MultiGraph, etc.) expose the~networkx.Graph.nodes
node and edge data of the graph via :meth: and~networkx.Graph.edges
:meth:, which return dict view objects, NodeView
(or ) and EdgeView (or EdgeDataView), respectively.View
The node and edge classes have dict-like semantics for item access,View
returning the data dict corresponding to a given node or edge.
This NXEP proposes adding support for slicing to the relevant node & edge classes.
Motivation and Scope
--------------------
While accessing Graph data with G.nodes and G.edges, the only way of slicing the data
is by casting the view to a list manually and then calling a slice on it.
A slice inherently implies an ordering of the elements. We intend to use the ordering
imposed on the nodes and edges by the iteration order (due to the adjacency data structure).
G.nodes(data=True) returns a NodeDataView of all the nodes, G.nodes(data=True)[x] returns an attribute dictionary for the node x.
The current way of getting a slice out of the underlying dict view is to cast it to list and then
slice it list(G.nodes(data=True))[0:10]. This bit of code is something that is written a lot of times
by users. For graphs with a lot of nodes and edges, G.nodes and G.edges will take a lot of screen space and
when the users try to slice the resulting view (the first instinct) it will error out. Users definitely need to go through
a couple of documentation links before they realise that they need to first cast this NodeDataView to a list and then create
a slice. Updating the documentation to make this more clear would be helpful.
But it also seems good to ease the complexity of this common idiom.
In this NXEP we propose to move the casting as list inside the Node(data)View methods.
Thus list(G.nodes(data=True))[0:10] either becomes G.nodes(data=True)[0:10]
or it is provided by a new slicing method like G.nodes(data=True).slice(10)
or a new slicing object to allow subscripting like G.nodes(data=True).slice[0:10:2].
Then users can get a small subset of nodes by creating a slice.
Motivating Use-Case
~~~~~~~~~~~~~~~~~~~
It is common to use :meth:~networkx.Graph.nodes and~networkx.Graph.edges
:meth: when using NetworkX interactively, e.g. in arepr
terminal.
If a graph has very many components (i.e. edges or nodes) then the ofView object may be very long::
>>> G = nx.complete_graph(100) # A graph with 4950 edges
>>> G.edges # Output suppressed
In this case, the first instinct of the user is often to inspect only the first
few edges, say 10, via slicing::
>>> G.edges[0:10]
Traceback (most recent call last)
...
TypeError: cannot unpack non-iterable slice object
The resulting TypeError is opaque and hard to understand in the context of
what was originally intended.
Usage and Impact
----------------
The main impact and the decision that needs to be taken in this NXEP is with
respect to the user facing API. By implementing this NXEP via subscripting NodeViews,
we may end up adding some ambiguity for users. As for example G.nodes[x]
will return an attribute dict but will return a list of first five nodes.
This will be more ambiguous with EdgeView as G.edges[0, 1] will return an
attribute dictionary of the edge between 0 and 1 and G.edges[0:1] will return the first edge.
We need to find a way to counter this potential confusion.
The alternative proposal of a new slicing method is one possible solution.
For a historical context, in pre 2.0 NetworkX, G.nodes() and G.edges() returned lists.
So, slicing was native behavior like G.nodes()[:10]. One caveat is that the order
of that list could change from one call to the next if the adjacency structure changed
between calls.
In more detail, in pre 2.0 NetworkX, there were 3 ways to access node information:
- G.node was a dict keyed by node to that node's attribute dict as a value.
- G.nodes() returned a list.
- G.nodes_iter() returned an iterator over the nodes.
In line with Python 3's move toward returning dict views and iterators rather than lists,
NetworkX 2.0 introduced a single interface for node information. G.nodes is a
dict-like object keyed by node to that node's attribute dict.
It also provides set-like operations on the nodes. And it offers a method G.nodes.data
which provides an interface similar to dict.items but pulling out specific attributes
from the inner attribute dict rather than the entire dict. Functional synonymsG.nodes(data="cost", default=1) and G.nodes.data("cost", 1) allow an interface
that looks like a dict keyed by node to a specific node attribute.
Slicing was not provided in NetworkX 2.0 primarily because there was
no inherent order to the nodes or edges as stored in the
dict-of-dict-of-dict data structure. However, in Python 3.6, dicts
became ordered based on insertion order. So, nodes are ordered based
on when they were added to the graph and edges are ordered based on the
adjacency dict-of-dict structure. So, there is now a concept of the "first edge".
With this NXEP we would like to bring the intuitiveness
of slicing behavior back to G.edges and G.nodes using the node
add order and edge order based on adjacency storage.
On the computational front, if we create lists to allow slices, we use memory to store the lists.
This is something user would have anyway done with something like list(G.nodes(data=True))[0:10].
But we can do better with our slicing mechanisms.
We should be able to avoid constructing the entire list simply to get the slices by internally
using code like: indx=[n for i, n in enumerate(G.nodes(data=True)) if i in range(x.start, x.stop, s.step)]
where x is the desired slice object.
Backward compatibility
----------------------
N/A
Detailed description
--------------------
The new implementation will let users slice Node(Data)View and Edge(Data)View.
The following code will be valid::
>>> G.nodes(data=True)[0:10]
>>> G.nodes[3:10]
>>> G.edges[1:10]
>>> G.edges(data=True)[4:6]
Preliminary implementation work is available at https://github.com/networkx/networkx/pull/4086
Alternatively, to get rid of the ambiguity in slicing API with respect to
the dict views we can implement a newslice method which leads to a less ambiguous API.::
>>> G.nodes(data=True).slice[:10]
>>> G.nodes.slice[10:30]
>>> G.edges.slice[10:40]
>>> G.edges(data=True).slice[5:]
Related Work
------------
N/A
Implementation
--------------
A reference implementation is proposed in
#4086 <https://github.com/networkx/networkx/pull/4086/files>_.
The core of this NXEP is to implement slicing to Node(Data)View
and Edge(Data)View to allow users to access a subset of nodes and edges without casting them
first to a list. We will do this by adding a check of slice in the getitem dunder method of__getitem__
Node(Data)View and Edge(Data)View and returning a list of the sliced values.
For example, the method for NodeView might look something like:
.. code-block:: python
def __getitem__(self, n):
if isinstance(n, slice):
return list(self._nodes).__getitem__(n)
return self._nodes[n]
We can instead move the check for slice to an independent slice method for nodes and edges to
implement this NXEP.
Alternatives
------------
The following list summarizes some alternatives to modifying the __getitem__
of the various classes.
The listed alternatives are not mutually exclusive.
- Improved Documentation - Add more explicit documentation about the
necessity of casting Node(Data)View and Edge(Data)View objects to lists in
order to be able to use slicing.
- Improved Exceptions - Currently, users see the following exception when
attempting to slice a View::
>>> G.nodes[0:10]
Traceback (most recent call last)
...
TypeError: unhashable type: 'slice'
The exception message is not very useful in the context of accessing a subset
of nodes or edges of a graph.
A more specific exception message could be something along the lines of::
>>> G.nodes[0:10]
Traceback (most recent call last)
...
NetworkXError: NodeView does not support slicing. Try list(G.nodes)[0:10].
- Instead of changing the behavior of __getitem__ we can implement a new
method, something like G.nodes.head(x) (inspired by pandas) which
returns the first x nodes.
This approach could be expanded to using a slice object directly but
interfacing it with an independent slice method of G.nodes and G.edges
instead of implementing it in getitem dunder method.
- The nice colon syntax for slices is only available with subscript notation.
To allow G.nodes.slice to use the nice colon syntax, we could make it a
property that creates a subscriptable object. Syntax would be G.nodes.slice[4:9:2].
Discussion
----------
- https://github.com/networkx/networkx/pull/4086
The motivating example for the NXEP is the use-case where users want to
introspect a subset (usually the first few) of the nodes and/or edges.
If we look at the changes proposed by this NXEP and the listed alternatives,
there are several ways that this use-case might be improved.
1. Add a descriptive error message when users try to access View objects
with a slice object.
2. Add specialized methods to the slice object (e.g. head() and tail()
or slice() that provide functionality useful for introspection.
3. The approach this NXEP proposes - modify View.__getitem__ to add
Sequence semantics.
Option 1 (better error messages) changes neither API nor behavior and would
help guide users to the correct solution for the introspection use-case.
The downside is that it does not offer the same level of convenience that
support for slicing does.
Option 2 (head, tail, and/or slice methods) would add new methods
to view a subset of the nodes/edges.
For example::
>>> G = nx.path_graph(10)
>>> G.nodes()
NodeView((0, 1, 2, 3, 4, 5, 6, 7, 8, 9))
>>> G.nodes().head(3) # Display the first three nodes
NodeView((0, 1, 2))
One drawback of the approach is that is introduces new API, which has to be
both discoverable and intuitive in order to make node/edge viewing more
convenient.
For example, is G.nodes().head(3) or G.nodes().slice(0, 10, 2)
more convenient than list(G.nodes())[:3] or list(G.nodes())[0:10:2],
respectively?
Another complication involves choosing the names for the new methods.head and tail are intuitive for users coming from *nix backgroundspandas
and have been adopted by other popular libraries like .
However, head and tail also have meaning in the context of network
science pertaining to e.g. graph edges.
For example, a user might reasonably assume that G.edges().tail() wouldn
give the set of source nodes in a directed graph, instead of the last
edges.
Option 3 (add sequence semantics to View objects) is arguably the most*View.__getitem__
convenient as it doesn't involve raising any error messages.
However, overriding the behavior of to mix Mapping anddict_keys
Sequence semantics is a relatively pervasive change that may have
unforeseen consequences for some use-cases.
Furthermore there is precedent in Python itself for returning un-sliceable view
objects from some mappings, a notable example being the anddict_values objects returned when accessing components in dictionaries::
>>> d = {k:v for k, v in zip(range(10), range(10))}
>>> d.values()[3:6]
Traceback (most recent call last)
...
TypeError: 'dict_values' object is not subscriptable
>>> list(d.values())[3:6]
[3, 4, 5]
Since Python dictionaries are now ordered by default (as of 3.6 in CPython),
this behavior may change in the future.
Given the considerations associated with the listed options, the following
course of action is proposed:
- Adopt option 1 - more informative error messages for the motivating
use-case (e.g. G.edges()[0:10]) alleviates the need for users to go
digging through the documentation to find/remember how to get the
desired behavior.
Since no new API is introduced nor are there any backwards compatibility
concerns, this change doesn't require any further design discussion.
It is possible that this change is enough to resolve the motivating
use-case satisfactorily - monitor user feedback.
- Option 2 doesn't require any further discussion in a design doc (i.e. NXEP).
New methods along the lines discussed above can be proposed via PR.
- Defer implementing option 3 for now, but reconsider if:
- The improved error message is not in itself a sufficient solution
- Other use-cases are identified for which adding slicing to the *View
objects would be a nice improvement (e.g. improved performance).
Resolution
----------
To make slicing intuitive for new users, we went ahead with Option 1 in the
discussion above. Users will now see NetworkXError when they try to slice a*View object.::
>>> G.edges()[0:10]
Traceback (most recent call last)
...
NetworkXError: EdgeView does not support slicing, try list(G.edges)[0:10:None]
The implementation is available at https://github.com/networkx/networkx/pull/4300 and
https://github.com/networkx/networkx/pull/4304.
---
Doc/Developer/Nxeps/Nxep 0003
.. _NXEP3:
==================================
NXEP 3 — Graph Builders
==================================
:Author: Dan Schult
:Author: Kelly Boothby
:Status: Draft
:Type: Standards Track
:Created: 2020-11-27
:Revision: Spring 2023
Abstract
--------
Graph generators in NetworkX create a Graph starting from an object
specified in the create_using argument. Many of these generatorsedgelist
do no more than create edges to add to the graph. Sometimes all we
want the graph for is to generate those edges. It might be better
to allow the graph generator functions to return either
the or a graph object as specified by create_using.
This NXEP proposes a framework for graph builders which allows a
user friendly interface to this feature and decorators to make it
easy for developers to provide this feature whether the graph
builder algorithm requires a graph, or just edges.
Motivation and Scope
--------------------
Consider, for example, the function nx.path_graph(nodes, create_using).create_using
It creates the edges for the indicated path and adds them to a
graph data structure created using the type .path_graph does not use the graph structure to create the edgesnx.path_graph_generator(nodes)
being generated and could arguably just yield
the edges without involving the data structure at all.
This NXEP proposes the syntax
to obtain a generator of the graph. That is, the result iterates
over the edge-list for the graph without constructing the graph itself.
Note that we are adding a new function for each of the existing graph
building functions. The API is for the graph builder, and*_graph_generator() for the generator of edges.
An edge-list is actually not sufficient to represent a graph because
of node attributes, graph attributes and isolated nodes. To handle these
more exotic elements, we introduce the Graph Sequence as a way to specify
all nodes, edges and attributes for a graph. The generator yields this
sequence.
Separating edge generation from graph data structure creation
arguably makes a cleaner interface where independent tools can be put
together in creative ways. To the extent that users need to generate
edges rather than graphs, having an edge generator that doesn't store
the graph is an advantage. It's not exactly clear how much demand there
is for this feature. But as an example of the flexibility of this approach,
the nx.utils.pairwise(nbunch) call could be replaced vianx.path_graph_generator(nbunch).
The create_using parameter is a mechanism to tell the builder function whatcreate_using
class of graph data structure to start with. Separating edge generation
from graph construction would mean the edge generator function would
no longer need a type for the graph data structure when there isn't one.
This NXEP proposes one way to provide an interface that separates edge
generation from graph data structure creation when desired, while leaving
the familiar syntax for graph type selection when desired.
Graph Sequences
---------------
Edgelists that only contain pairs of nodes indicating an edge are restrictive.
Some graphs have isolated nodes which would not appear in any node-pair.
Some graphs have node or edge attributes associated with the node or edge.
Multigraphs have edge keys associated with each edge, often as a 3-tuple
(u, v, ekey). This proposal suggests that we adopt the following Graph
Sequence protocol for describing a graph.
A Graph Sequence is a sequence-of-sequences, usually a list-of-tuples.
The length of each tuple along with the hashable nature of the tuple's final
element determine the type of information included in the tuple.
All networkx graph information can be stored in such a sequence.
The logic is as follows where S denotes the inner sequence:
+------------------------------+--------+-----------------+
| | len(S) | hashable(S[-1]) |
+==============================+========+=================+
|Graph attributes: | 1 | False |
+------------------------------+--------+-----------------+
|Node without attributes: | 1 | True |
+------------------------------+--------+-----------------+
|Node with attributes: | 2 | False |
+------------------------------+--------+-----------------+
|Edge without attributes: | 2 | True |
+------------------------------+--------+-----------------+
|Edge with attributes: | 3 | False |
+------------------------------+--------+-----------------+
|Multiedge without attributes: | 3 | True |
+------------------------------+--------+-----------------+
|Multiedge with attributes: | 4 | False |
+------------------------------+--------+-----------------+
Here is some code to process such a sequence and construct the graph
starting from an empty graph G:
.. code-block:: python
for S in graphsequence:
N = len(S)
last_entry = S[-1]
attrs = not hashable(last_entry)
if N == 1:
if attrs:
G.graph.update(last_entry) # graph attributes
else:
G.add_node(last_entry) # node without attributes
elif N == 2:
if attrs:
G.add_node(S[0], last_entry) # (node, attrdict)
else:
G.add_edge(*S) # (u, v)
elif N == 3:
if attrs:
G.add_edge(S[:2], *last_entry) # (u, v, attrdict)
else:
G.add_edge(*S) # (u, v, edge_key)
elif N == 4:
if attrs:
G.add_edge(*S) # (u, v, edge_key, attrdict)
else:
raise NetworkXInvalidEdgelist(
"Sequence element has 4 items and last is not hashable: {S}"
)
else:
raise NetworkXInvalidEdgelist(
"Graph Sequence element has more than 4 items: {S}"
)
Note that order does not affect the network structure, but the reporting
order of nodes can be retained if the nodes are added in the desired order
before the edges.
Usage and Impact
----------------
Each graph builder function (formerly called graph generators) will allow
return of graph structures with the same syntax as before. For example,
create a wheel graph with 9 spokes (10 nodes):
>>> G = nx.wheel_graph(9) # same as current code
To iterate over a Graph Sequence without creating a graph:
>>> for u, v in nx.binomial_graph.edges(9):
>>> process(u, v)
Add 10 new nodes with random edges (maybe including isolated nodes)
to an existing graph G:
>>> G.update(nx.binomial_graph_generator(range(9, 19))
Construct a path graph using a MultiDiGraph data structure (two methods):
>>> MDG = nx.path_graph([3, 4, 2, 5, 7, 6], create_using=MultiDiGraph)
>>> MDG = nx.MultiDiGraph(nx.path_graph_generator([3, 4, 2, 5, 7, 6])
The code to read in an edgelist upon instantiation, or via the update methodG.as_sequence()
will change to allow Graph Sequences in addition to edgelists. An additional
base class method will yield the Graph Sequence for the graph.
Developers will use a decorator to indicate whether their graph builder
has underlying code that yields from an edgelist, or returns a graph.
.. code-block:: python
@graph_builder
@py_random_state(4)
def extended_barabasi_albert_graph(n, m, p, q, seed=None):
# some fancy code that requires we construct G to use graph properties
# while we decide what edges to add next.
return G
The @graph_builder decorator adds code to enablenx.extended_barabasi_albert_graph_generator
e.g. .
Another decorator provides code to handle the create_using argument for developers
that write code which simply yields an edgelist.
.. code-block:: python
@node_and_edge_builder
def ladder_graph_generator(n):
yield from pairwise(range(n))
yield from pairwise(range(n, 2 * n))
yield from ((v, v + n) for v in range(n))
The @node_and_edge_builder decorator adds code to enablenx.ladder_graph(6, create_using=MultiGraph)
e.g. . Note that nx.ladder_graph(6)
would still return an nx.Graph as it currently does. To make use of the
edgelist functionality, the syntax would be .
It would be ideal to have the doc_strings show up on a single webpage for
both the function and generator. We are exploring this possibility.
Backward compatibility
----------------------
To reduce backward incompatibility, the base calling structure nx.path_graph(9)
works as it currently does. The parameter behaves as usual.
So, no existing code should break.
To reduce developer impact, upon inception, we could reuse all current graph
generators as graph builders by attaching the @graph_builder decorator.@node_and_edge_builder
Presumably for efficiency many of them should be rewritten to yield
edgelists rather than returning graphs. But this could be done gradually
and along with switching the decorator to .
Both sets of code should return equivalent graph builder objects.
Detailed description
--------------------
This can be accomplished through a couple decorators, which could be
adopted gradually -- a big patch initially decorating all existing generators
with @graph_builder would immediately support the notationnx.complete_graph_generator(...) without impacting existing code.@node_and_edge_builder
Later generators could use .
NEEDS UPDATING
.. code-block:: python
def node_and_edge_builder(f):
@wraps(f)
def graph(args, create_using=None, *kwargs):
G = nx.empty_graph(0, create_using=create_using)
G.update(f(args, *kwargs))
return G
graph.edges = f
graph.edges_plus = f
return graph
def graph_builder(f):
@wraps(f)
def edgelist(args, *kwargs):
G = f(args, *kwargs)
return itertools.ichain(map(tuple, G.nodes.data()), map(tuple, G.edges.data()))
def edges(args, *kwargs):
G = f(args, *kwargs)
return map(tuple, G.edges.data())
f.edges_plus = edgelist
f.edges = edges
return f
Note: the graph_builder underlying code should accept a create_using
parameter for this implementation to work. We need to think if this is
universally applicable and how to handle builders that shouldn't work
with all four of the major NetworkX graph classes.
Graph.update will need to handle graph sequence input. It currently handles
node-pairs and node-pair-with-edge-key triples for multigraphs. Code like
that shown above in the description of Graph Sequences should be used.
Example developer usage:
.. code-block:: python
@node_and_edge_builder
def path_graph(n):
"""an overly simplified path graph implementation"""
return pairwise(range(n))
@graph_builder
def complete_graph(n, create_using=None):
"""an overly simplified complete graph implementation"""
if create_using is None:
create_using = nx.Graph
g = empty_graph(0, create_using)
g.update(itertools.combinations(range(n), 2))
return g
Related Work
------------
This proposal is based on ideas and discussions from #3036 and #1393.
This proposal does not delve into backends using the _dispatchable functionality
and whether we should be providing or allowing control over the builder
functions for backend libraries. This is a potentially helpful discussion
but is beyond the scope of this NXEP.
Implementation
--------------
The first major step is to implement the two builder decorators.
Next we need to change the Graph update methods, convert functions, etc.
to process graph sequences that contain isolated nodes and data attributes.
Third we should identify any functions that build graphs or edgelists
and decorate them to make them Graph Builders. And we should take care
that code which handles edgelists and are not able to handle Graph Sequences
are appropriately protected.
Special care should be made to ensure only desired graph types are
accepted and appropriate errors raised when not.
Later steps include going through the existing generator code and switching
that code to yield edgelists instead of returning graphs (where appropriate).
Alternatives
------------
#) We can just leave the generators as they are and deal with the cost of
creating a graph when one only needs the edgelist. It's not a huge cost
most of the time.
#) We can create an attribute-function on the graph builder function to
provide the generator functionality. Like: nx.path_graph.edges_plus()
along with .
#) We can provide nx.path_graph.edges_plus without providing the edges
attribute. The simpler interface (by one attribute function) costs us
making sure that easy tools for creating, consuming and handling Graph
Sequences are available.
#) We can provide the decorators to use an attribute syntax for graph type
instead of the argument create_using. Thus nx.path_graph.MultiGraph(9)
would be the same as .Graph
Similarly for , DiGraph, MultiDiGraph and perhaps CustomGraph
with a kwarg .
An earlier version of this proposal included this attribute-style alternative
as a replacement of the create_using argument. Developers would still write
code to either 1) yield edges, or 2) construct a graph from an input graph
parameter. Two decorators would then add the extra code needed to
construct a single object so users would use the same interface no
matter which style of underlying code was used. The user facing
interface would allow the user to specify a graph data structure
by type, or request an edgelist. One syntax proposal was::
G = nx.path_graph(9)
DG = nx.path_graph.DiGraph(9)
MG = nx.path_graph.MultiGraph(9)
MDG = nx.path_graph.MultiDiGraph(9)
CG = nx.path_graph.CustomGraph(9, create_using)
elist = nx.path_graph.edgelist(9)
This can be accomplished through decorators named as above,
and coded similar to these examples.
.. code-block:: python
def node_and_edge_builder(f):
@wraps(f)
def graph(args, *kwargs):
return nx.Graph(f(args, *kwargs))
def digraph(args, *kwargs):
return nx.DiGraph(f(args, *kwargs))
def multigraph(args, *kwargs):
return nx.MultiGraph(f(args, *kwargs))
def multidigraph(args, *kwargs):
return nx.MultiDiGraph(f(args, *kwargs))
def custom_graph(args, create_using=None, *kwargs):
g = create_using()
g.update(f(args, *kwargs))
return g
graph.Graph = graph
graph.DiGraph = digraph
graph.MultiGraph = multigraph
graph.MultiDiGraph = multidigraph
graph.CustomGraph = custom_graph
graph.edgelist = f
return graph
def graph_builder(f):
@wraps(f)
def edgelist(args, *kwargs):
g = f(args, *kwargs)
return itertools.ichain(map(tuple, G.nodes.data()), map(tuple, G.edges.data()))
f.edgelist = edgelist
f.CustomGraph = f
def graph(args, *kwargs):
return f(args, create_using=nx.Graph, *kwargs)
def digraph(args, *kwargs):
return f(args, create_using=nx.DiGraph, *kwargs)
def multigraph(args, *kwargs):
return f(args, create_using=nx.MultiGraph, *kwargs)
def multidigraph(args, *kwargs):
return f(args, create_using=nx.MultiDiGraph, *kwargs)
f.Graph = graph
f.DiGraph = digraph
f.MultiGraph = multigraph
f.MultiDiGraph = multidigraph
return f
#) We might be able to avoid the function attribute syntax altogether
if we can construct a Graph Sequence generator object (of class EdgesPlus?)
that can be provided as the create_using argument. Graph builder codeadd_node
would treat it like a graph class, but the object would magically handle
all the and add_edge calls in the style of an iterator,nx.path_graph, create_using=EdgesPlus)
yielding graph information as construction progresses. The user could
halt construction if the structure showed early signs of not being useful.
Graph Sequences could then be generated using
This could perhaps be built with some creative coroutine magic.
Discussion
----------
Most of the ideas here are from
- [#3036 <https://github.com/networkx/networkx/pull/3036>_]#1393 <https://github.com/networkx/networkx/pull/1393>
which built on discussion from
- [_]
Over a year of occasional thought and more occasional mentioning-in-passing,
most core developers feel that the create_using parameter should be retained.edges
The proposal was rewritten to retain that feature and not develop the attribute
syntax seen in the Alternatives section. The attribute syntax continued to be
used for the and edges_plus generators, with edges for an edge-listedges_plus
and for the full Graph Sequence.
More discussion led to the proposal to make two functions for each graph type.
That is, nx.path_graph(9) for a graph and nx.path_graph_generator(9) for the
generator. This gained enough support to be included. No attribute support is
needed.
Remaining questions:
- how to handle docs
- how to have a decorator add two functions to the namespace.
---
Doc/Developer/Nxeps/Nxep 0004
.. _NXEP4:
=================================
NXEP 4 — Default random interface
=================================
:Author: Ross Barnowski ([email protected])
:Status: Draft
:Type: Standards Track
:Created: 2022-02-24
Abstract
--------
Pseudo-random numbers play an important role in many graph and network analysis
algorithms in NetworkX.
NetworkX provides a :ref:standard interface to random number generators <randomness>
that includes support for and the Python built-in random module.numpy.random is used extensively within NetworkX and in several cases is thenumpy.random
preferred package for random number generation.
NumPy introduced a new interface in the package in NumPy versionNEP19 <nep-0019-rng-policy>
1.17.
According to :external+neps:doc:, the new interface based onnumpy.random.Generator
is recommended over the legacy as the former hasbetter statistical properties <https://www.pcg-random.org/index.html>_,more features <reference/random/new-or-different>
:external+numpy:doc:,improved performance <reference/random/performance>
and :external+numpy:doc:.numpy.random.Generator
This NXEP proposes a strategy for adopting as the
default interface for random number generation within NetworkX.
Motivation and Scope
--------------------
The primary motivation for adopting numpy.random.Generator as the defaultnumpy.random.Generator
random number generation engine in NetworkX is to allow users to benefit from
the improvements in , including:
- Advances in statistical quality of modern pRNG's
- Improved performance
- Additional features
The numpy.random.Generator API is very similar to the numpy.random.RandomState
API, so users can benefit from these improvements without any additional changes
[#f1]_ to their existing NetworkX code.
In principle this change would impact NetworkX users that use any of the
functions decorated by ~networkx.utils.decorators.np_random_state
or (when the random_state argument
involves numpy).
See the next section for details.
.. [#f1] See note about the compatibility layer in the :ref:Implementation section <implementation>
Usage and Impact
----------------
In NetworkX, random number generators are typically created via a decorator::
from networkx.utils import np_random_state
@np_random_state("seed") # Or could be the arg position, i.e. 0
def foo(seed=None):
return seed
The decorator is responsible for mapping various different inputs into an
instance of a random number generator within the function.
Currently, the random number generator instance that is returned is a
numpy.random.RandomState object::
>>> type(foo(None))
numpy.random.mtrand.RandomState
>>> type(foo(12345))
numpy.random.mtrand.RandomState
The only way to get a numpy.random.Generator instance from the random state
decorators is to pass the instance in directly::
>>> import numpy as np
>>> rng = np.random.default_rng()
>>> type(foo(rng))
numpy.random._generator.Generator
This NXEP proposes to change the behavior so that when e.g. and integer or
None is given for the seed parameter, a numpy.random.Generator instance
is returned instead, i.e.::
>>> type(foo(None))
numpy.random._generator.Generator
>>> type(foo(12345))
numpy.random._generator.Generator
numpy.random.RandomState instances can still be used as seed, but they
must be explicitly passed in::
>>> rs = np.random.RandomState(12345)
>>> type(foo(rs))
numpy.random.mtrand.RandomState
Backward compatibility
----------------------
There are three main concerns:
1. The Generator interface is not stream-compatible with RandomState,
thus the results of the Generator methods will not be exactly the same
as the corresponding RandomState methods.
2. There are a few slight differences in method names and availability between
the RandomState and Generator APIs.
3. There is no global Generator instance internal to numpy.random as isnumpy.random.RandomState
the case for .
The numpy.random.Generator interface breaks the stream-compatibilitynumpy.random.RandomState
guarantee that upheld of exact reproducibility of
values.
Switching the default random number generator from RandomState toGenerator would mean functions decorated with np_random_state would
produce different results when a value other than an instantiated rng is used
as the seed.
For example, let's take the following function::
@np_random_state("seed")
def bar(num, seed=None):
"""Return an array of num uniform random numbers."""
return seed.random(num)
With the current implementation of np_random_state, a user can pass in an
integer value to seed which will be used to seed a new RandomState
instance.
Using the same seed value guarantees the output is always exactly reproducible::
>>> bar(10, seed=12345)
array([0.92961609, 0.31637555, 0.18391881, 0.20456028, 0.56772503,
0.5955447 , 0.96451452, 0.6531771 , 0.74890664, 0.65356987])
>>> bar(10, seed=12345)
array([0.92961609, 0.31637555, 0.18391881, 0.20456028, 0.56772503,
0.5955447 , 0.96451452, 0.6531771 , 0.74890664, 0.65356987])
However, after changing the default rng returned by np_random_state to
a Generator instance, the values produced by the decorated bar function
for integer seeds would no longer be identical::
>>> bar(10, seed=12345)
array([0.22733602, 0.31675834, 0.79736546, 0.67625467, 0.39110955,
0.33281393, 0.59830875, 0.18673419, 0.67275604, 0.94180287])
In order to recover exact reproducibility of the original results, a seededRandomState instance would need to be explicitly created and passed in
via seed::
>>> import numpy as np
>>> rng = np.random.RandomState(12345)
>>> bar(10, seed=rng)
array([0.92961609, 0.31637555, 0.18391881, 0.20456028, 0.56772503,
0.5955447 , 0.96451452, 0.6531771 , 0.74890664, 0.65356987])
Because the streams would no longer be compatible, it is proposed in this NXEP
that switching the default random number generator only be considered for a
major release, e.g. the transition from NetworkX 2.X to NetworkX 3.0.
The second point is only a concern for users who are using
~networkx.utils.misc.create_random_state and the corresponding decorator~networkx.utils.decorators.np_random_state in their own libraries.numpy.random.RandomState.randint
For example, the method has been replacednumpy.random.Generator.integers
by .create_random_state
Thus any code that uses or create_py_random_state and
relies on the randint method of the returned rng would result in anAttributeError.networkx.utils.misc.PythonRandomInterface
This can be addressed with a compatibility class similar to the class, which provides a compatibilityrandom
layer between and numpy.random.RandomState.
create_random_state currently returns the global numpy.random.mtrand._rand instance when the input is None or the numpy.random module.numpy.random.Generator
By switching to , this will no longer be possible asGenerator
there is no global, internal instance in the numpy.random module.
This should have no effect on users, as seed=None currently does not
guarantee reproducible results.
Detailed description
--------------------
This NXEP proposes to change the default random number generator produced by
the ~networkx.utils.misc.create_random_state function (and the related~networkx.utils.decorators.np_random_state
decorator ) from a numpy.random.RandomState
instance to a instance when the input to theNone
function is either an integer or .
Related Work
------------
Scikit-learn has a similar pattern for imposing determinism on functions that
depend on randomness.
For example, many functions in scikit-learn have a random_state argument
that functions similarly to how seed behaves in many NetworkX function
signatures.
One difference between scikit-learn and networkx is that scikit-learn
only supports RandomState via the random_state keyword argument,random
whereas NetworkX implicitly supports both the built-in module, as well
as both the numpy RandomState and Generator instances (depending on
the type of seed).
This is reflected in the name of the keyword argument as random_state
(used by scikit-learn) is les ambiguous than seed (used by NetworkX).
There are multiple relevant discussions in the scikit-learn community about
potential approaches to supporting the new NumPy random interface:
- scikit-learn/scikit-learn#16988 <sklearn16988>_ covers strategies and concerns
related to enabling users to use the Generator-based random number generators.scikit-learn/scikit-learn#14042 <sklearn14042>
- _ is a higher-level discussion
that includes additional information about the design considerations and constraints
related to scikit-learn's random_state.SLEP <slep011>
- There is also a related _.
.. _sklearn16988: https://github.com/scikit-learn/scikit-learn/issues/16988
.. _sklearn14042: https://github.com/scikit-learn/scikit-learn/issues/14042
.. _slep011: https://github.com/scikit-learn/enhancement_proposals/pull/24
.. _implementation:
Implementation
--------------
The implementation itself is quite simple. The logic that determines how
inputs are mapped to random number generators is encapsulated in the
~networkx.utils.misc.create_random_state function (and the related~networkx.utils.misc.create_py_random_state).
Currently (i.e. NetworkX <= 2.X), this function maps inputs like None,numpy.random, and integers to RandomState instances::
def create_random_state(random_state=None):
if random_state is None or random_state is np.random:
return np.random.mtrand._rand
if isinstance(random_state, np.random.RandomState):
return random_state
if isinstance(random_state, int):
return np.random.RandomState(random_state)
if isinstance(random_state, np.random.Generator):
return random_state
msg = (
f"{random_state} cannot be used to create a numpy.random.RandomState or\n"
"numpy.random.Generator instance"
)
raise ValueError(msg)
This NXEP proposes to modify the function to produce Generator instances
for these inputs. An example implementation might look something like::
def create_random_state(random_state=None):
if random_state is None or random_state is np.random:
return np.random.default_rng()
if isinstance(random_state, (np.random.RandomState, np.random.Generator)):
return random_state
if isinstance(random_state, int):
return np.random.default_rng(random_state)
msg = (
f"{random_state} cannot be used to create a numpy.random.RandomState or\n"
"numpy.random.Generator instance"
)
raise ValueError(msg)
The above captures the essential change in logic, though implementation details
may differ.
Most of the work related implementing this change will be associated with
improved/reorganized tests; including adding tests rng-stream reproducibility.
Alternatives
------------
The status quo, i.e. using RandomState by default, is a completely
acceptable alternative.RandomState is not deprecated, and is expected to maintain its stream-compatibility
guarantee in perpetuity.
Another possible alternative would be to provide a package-level toggle that
users could use to switch the behavior the seed kwarg for all functions
decorated by np_random_state or py_random_state.
To illustrate (ignoring implementation details)::
>>> import networkx as nx
>>> from networkx.utils.misc import create_random_state
# NetworkX 2.X behavior: RandomState by default
>>> type(create_random_state(12345))
numpy.random.mtrand.RandomState
# Change random backend by setting pkg attr
>>> nx._random_backend = "Generator"
>>> type(create_random_state(12345))
numpy.random._generator.Generator
Discussion
----------
This NXEP has been discussed at several community meetings, see e.g.
these meeting notes <https://github.com/networkx/archive/blob/main/meetings/2023-03-14.md#nxep-topic-of-the-week>_.
The main concern that has surfaced during these discussions is that the
NumPy Generator interface does not make the same strict stream-compatibility
guarantees as the older RandomState.
Therefore, if this NXEP were implemented as proposed, code that relies on seeded
random numbers could in principle return different results with some future
NumPy version due to changes in the default BitGenerator or Generator methods.
Many NetworkX functions are quite sensitive to the random seed.
For example, changing the seed for the default spring_layout function can
yield a vastly different (but equally valid) layout for a network.
Stream-compatibility is important for reproducibility in these contexts.
Thus we have concluded through various discussions not to implement the
changes proposed in this NXEP.RandomState will remain the default random number generator for the random_state
decorator in an effort to support strict backward compatibility for all NetworkX
user code that relies on random_state.
The Generator interface is supported in the random_state decorator,
and users are encouraged to use Generator instances in new code where
stream-compatibility is not a priority.
---
Doc/Developer/Nxeps/Nxep Template
==================================
NXEP X — Template and Instructions
==================================
:Author: <list of authors' real names and optionally, email addresses>
:Status: <Draft | Active | Accepted | Deferred | Rejected | Withdrawn | Final | Superseded>
:Type: <Standards Track | Process>
:Created: <date created on, in yyyy-mm-dd format>
:Resolution: <url> (required for Accepted | Rejected | Withdrawn)
Abstract
--------
The abstract should be a short description of what the NXEP will achieve.
Note that the — in the title is an elongated dash, not -.
Motivation and Scope
--------------------
This section describes the need for the proposed change. It should describe
the existing problem, who it affects, what it is trying to solve, and why.
This section should explicitly address the scope of and key requirements for
the proposed change.
Usage and Impact
----------------
This section describes how users of NetworkX will use features described in this
NXEP. It should be comprised mainly of code examples that wouldn't be possible
without acceptance and implementation of this NXEP, as well as the impact the
proposed changes would have on the ecosystem. This section should be written
from the perspective of the users of NetworkX, and the benefits it will provide
them; and as such, it should include implementation details only if
necessary to explain the functionality.
Backward compatibility
----------------------
This section describes the ways in which the NXEP breaks backward compatibility.
The mailing list post will contain the NXEP up to and including this section.
Its purpose is to provide a high-level summary to users who are not interested
in detailed technical discussion, but may have opinions around, e.g., usage and
impact.
Detailed description
--------------------
This section should provide a detailed description of the proposed change.
It should include examples of how the new functionality would be used,
intended use-cases and pseudo-code illustrating its use.
Related Work
------------
This section should list relevant and/or similar technologies, possibly in other
libraries. It does not need to be comprehensive, just list the major examples of
prior and relevant art.
Implementation
--------------
This section lists the major steps required to implement the NXEP. Where
possible, it should be noted where one step is dependent on another, and which
steps may be optionally omitted. Where it makes sense, each step should
include a link to related pull requests as the implementation progresses.
Any pull requests or development branches containing work on this NXEP should
be linked to from here. (A NXEP does not need to be implemented in a single
pull request if it makes sense to implement it in discrete phases).
Alternatives
------------
If there were any alternative solutions to solving the same problem, they should
be discussed here, along with a justification for the chosen approach.
Discussion
----------
This section may just be a bullet list including links to any discussions
regarding the NXEP:
- This includes links to mailing list threads or relevant GitHub issues.
---
Doc/Developer/About Us
About Us
========
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.
.. include:: teams.inc
Contributors
------------
If you are a NetworkX contributor, please feel free to
open an issue <https://github.com/networkx/networkx/issues/new>_ orpull request <https://github.com/networkx/networkx/compare/>
submit a _
to add your name to the bottom of the list.
- Aric Hagberg, GitHub: hagberg <https://github.com/hagberg>_dschult <https://github.com/dschult>
- Dan Schult, GitHub: _jtorrents <https://github.com/jtorrents>
- Pieter Swart
- Katy Bold
- Hernan Rozenfeld
- Brendt Wohlberg
- Jim Bagrow
- Holly Johnsen
- Arnar Flatberg
- Chris Myers
- Joel Miller
- Keith Briggs
- Ignacio Rozada
- Phillipp Pagel
- Sverre Sundsdal
- Ross M. Richardson
- Eben Kenah
- Sasha Gutfriend
- Udi Weinsberg
- Matteo Dell'Amico
- Andrew Conway
- Raf Guns
- Salim Fadhley
- Fabrice Desclaux
- Arpad Horvath
- Minh Van Nguyen
- Willem Ligtenberg
- Loïc Séguin-C.
- Paul McGuire
- Jesus Cerquides
- Ben Edwards
- Jon Olav Vik
- Hugh Brown
- Ben Reilly
- Leo Lopes
- Jordi Torrents, GitHub: _dheerajrav <https://github.com/dheerajrav>
- Dheeraj M R, GitHub: _chebee7i <https://github.com/chebee7i>
- Franck Kalala
- Simon Knight
- Conrad Lee
- Sérgio Nery Simões
- Robert King
- Nick Mancuso
- Brian Cloteaux
- Alejandro Weinstein
- Dustin Smith
- Mathieu Larose
- Romain Fontugne
- Vincent Gauthier
- chebee7i, GitHub: _jg-you <https://github.com/jgyou>
- Jeffrey Finkelstein
- Jean-Gabriel Young, GitHub: _MridulS <https://github.com/MridulS>
- Andrey Paramonov, http://aparamon.msk.ru
- Mridul Seth, GitHub: _theosotr <https://github.com/theosotr>
- Thodoris Sotiropoulos, GitHub: _k-karakatsanis <https://github.com/k-karakatsanis>
- Konstantinos Karakatsanis, GitHub: _rnelsonchem <https://github.com/rnelsonchem>
- Ryan Nelson, GitHub: _NvanAdrichem <https://github.com/NvanAdrichem>
- Niels van Adrichem, GitHub: _Michael-E-Rose <https://github.com/Michael-E-Rose>
- Michael E. Rose, GitHub: _jarrodmillman <https://github.com/jarrodmillman>
- Jarrod Millman, GitHub: _atombrella <https://github.com/atombrella>
- Andre Weltsch
- Lewis Robbins
- Mads Jensen, GitHub: _elplatt <https://elplatt.com>
- Edward L. Platt, _leamingrad <https://github.com/leamingrad>
- James Owen, GitHub: _gmyr <https://github.com/gmyr>
- Robert Gmyr, GitHub: _Erotemic <https://github.com/Erotemic>
- Mike Trenfield
- Jon Crall, GitHub: _Moradnejad <https://github.com/Moradnejad>
- Issa Moradnejad, GitHub: _, LinkedIn: Issa Moradnejad <https://linkedin.com/in/moradnejad/>_bkief <https://github.com/bkief>
- Brian Kiefer, GitHub: _pckroon <https://github.com/pckroon>
- Julien Klaus
- Peter C. Kroon, GitHub: _ws4u <https://github.com/ws4u>
- Weisheng Si, GitHub: _haakonhr <https://gitlab.com/haakonhr>
- Haakon H. Rød, GitLab: _, <https://haakonhr.gitlab.io>_efraimrodrigues <https://github.com/efraimrodrigues>
- Efraim Rodrigues, GitHub: _, LinkedIn: efraim-rodrigues <https://linkedin.com/in/efraim-rodrigues/>_fuglede <https://github.com/fuglede>
- Erwan Le Merrer
- Søren Fuglede Jørgensen, GitHub: _salymdotme <https://www.linkedin.com/in/salymdotme/>
- Salim BELHADDAD, LinkedIn: _jangwon-yie <https://github.com/jangwon-yie>
- Jangwon Yie, GitHub: _, LinkedIn: jangwon-yie-a7960065 <https://www.linkedin.com/in/jangwon-yie-a7960065/>_kazimierz-256 <https://github.com/kazimierz-256>
- ysitu
- Tomas Gavenciak
- Luca Baldesi
- Yuto Yamaguchi
- James Clough
- Minas Gjoka
- Drew Conway
- Alex Levenson
- Haochen Wu
- Erwan Le Merrer
- Alex Roper
- P C Kroon
- Christopher Ellison
- D. Eppstein
- Federico Rosato
- Aitor Almeida
- Ferran Parés
- Christian Olsson
- Fredrik Erlandsson
- Nanda H Krishna
- Nicholas Mancuso
- Fred Morstatter
- Ollie Glass
- Rodrigo Dorantes-Gilardi
- Pranay Kanwar
- Balint Tillman
- Diederik van Liere
- Ferdinando Papale
- Miguel Sozinho Ramalho
- Brandon Liu
- Nima Mohammadi
- Jason Grout
- Jan Aagaard Meier
- Henrik Haugbølle
- Piotr Brodka
- Sasha Gutfraind
- Alessandro Luongo
- Huston Hedinger
- Oleguer Sagarra
- Kazimierz Wojciechowski, GitHub: _, LinkedIn: wojciechowski-kazimierz <https://linkedin.com/in/wojciechowski-kazimierz/>_Carghaez <https://github.com/Carghaez>
- Gaetano Pietro Paolo Carpinato, GitHub: _, LinkedIn: gaetanocarpinato <https://linkedin.com/in/gaetanocarpinato/>_arunwise <https://github.com/arunwise>
- Arun Nampally, GitHub: _, LinkedIn: arun-nampally-b57845b7 <https://www.linkedin.com/in/arun-nampally-b57845b7/>_itsshavar <https://github.com/itsshavar>
- Ryan Duve
- Shashi Prakash Tripathi, GitHub: _, LinkedIn: itsshashitripathi <https://www.linkedin.com/in/itsshashitripathi/>_jamestrimble <https://github.com/jamestrimble>
- Danny Niquette
- James Trimble, GitHub: _mbruhns <https://github.com/mbruhns>
- Matthias Bruhns, GitHub: _mjschwenne <https://github.com/mjschwenne>
- Philip Boalch
- Matt Schwennesen, GitHub: _lobpcg <https://github.com/lobpcg>
- Andrew Knyazev, GitHub: _, LinkedIn: andrew-knyazev <https://www.linkedin.com/in/andrew-knyazev>_LucaCappelletti94 <https://github.com/LucaCappelletti94>
- Luca Cappelletti, GitHub: _SultanOrazbayev <https://github.com/SultanOrazbayev>
- Sultan Orazbayev, GitHub: _, LinkedIn: Sultan Orazbayev <https://www.linkedin.com/in/sultan-orazbayev/>_https://github.com/boldip
- Paolo Boldi, Github:
- Davide D'Ascenzo, Github:
- Flavio Furia, Github:
- Sebastiano Vigna, Github:
- Aaron Zolnai-Lucas, GitHub: _, LinkedIn: aaronzolnailucas <https://www.linkedin.com/in/aaronzolnailucas/>_eriknw <https://github.com/eriknw>
- Erik Welch, GitHub: _, LinkedIn: eriknwelch <https://www.linkedin.com/in/eriknwelch/>_mohamedrezk122 <https://github.com/mohamedrezk122>
- Mohamed Rezk, Github: _OrionSehn <https://github.com/OrionSehn>
- Orion Sehn, GitHub: _berlincho <https://github.com/berlincho>
- Berlin Cho, GitHub: _amcandio <https://github.com/amcandio>
- Alejandro Candioti, GitHub: _, LinkedIn: <https://www.linkedin.com/in/amcandio/>
A supplementary (but still incomplete) list of contributors is given by the
list of names that have commits in networkx'sgit <http://git-scm.com>_ 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 <https://github.com/networkx/networkx/blob/886e790437bcf30e9f58368829d483efef7a2acc/doc/source/reference/credits_old.rst>_.
Support
-------
NetworkX acknowledges support from the following organizations:
- Center for Nonlinear Studies <http://cnls.lanl.gov>_, Los Alamos National
Laboratory, PI: Aric Hagberg
- Open Source Programs Office <https://developers.google.com/open-source/>_,
Google
- Complexity Sciences Center <http://csc.ucdavis.edu/>_, Department of
Physics, University of California-Davis, PI: James P. Crutchfield
- Center for Complexity and Collective Computation <http://c4.discovery.wisc.edu>_,
Wisconsin Institute for Discovery, University of Wisconsin-Madison,
PIs: Jessica C. Flack and David C. Krakauer
- Colgate University <https://www.colgate.edu/>_
- California Institute of Technology <https://www.caltech.edu/>_
- Berkeley Institute for Data Science <https://bids.berkeley.edu/>_
- NVIDIA Corporation <https://www.nvidia.com/>_
NetworkX acknowledges the following financial support:
- Google Summer of Code via Python Software Foundation (2013, 2015),
NumFOCUS (2021-2024)
- U.S. Army Research Office grant W911NF-12-1-0288
- DARPA Physical Intelligence Subcontract No. 9060-000709
- NSF Grant No. PHY-0748828
- John Templeton Foundation through a grant to the Santa Fe Institute to
study complexity
- U.S. Army Research Laboratory and the U.S. Army Research Office under
contract number W911NF-13-1-0340
- Chan Zuckerberg Initiative Essential Open Source Software for Science
EOSS2-0000000066 and EOSS4-0000000138
- Wellcome Trust via CZI, Wellcome and Kavli EOSS Cycle 6 (EOSS6-000000368)
---
Doc/Developer/Core Developer
.. _core_dev:
Core Developer Guide
====================
As a core developer, you should continue making pull requests
in accordance with the :ref:contributor_guide.mission_and_values
You are responsible for shepherding other contributors through the review process.
You should be familiar with our :ref:.Reviewing
You also have the ability to merge or approve other contributors' pull requests.
Much like nuclear launch keys, it is a shared power: you must merge only after
another core developer has approved the pull request, and after you yourself have carefully
reviewed it. (See _ and especially Merge Only Changes You
Understand_ below.) To ensure a clean git history, use GitHub'sSquash and Merge <https://help.github.com/en/github/collaborating-with-issues-and-pull-requests/merging-a-pull-request#merging-a-pull-request-on-github>__
feature to merge, unless you have a good reason not to do so.
Reviewing
---------
Pre-Merge Requirements
~~~~~~~~~~~~~~~~~~~~~~
All pull requests should meet the following criteria before merging into main:
1. Have at least two approvals from reviewers on the maintainers or triage team.
2. Have one of the type: <https://github.com/networkx/networkx/labels?q=type>_
labels applied prior to merge.
The two approvals requirement applies to PRs originating from external contributors.
If the PR submitter is a maintainer, then careful review from another maintainer
is sufficient to meet the "two reviews" threshold.
The type: labels are used to automatically categorize and generate the
release notes; therefore one of these labels must be applied for the release
notes to be generated properly.
The rule-of-thumb is the first approver is responsible for applying the
label, but anyone with at least triaging permissions is welcome to apply atype: label.
How to Conduct A Good Review
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Always be kind to contributors. Nearly all of NetworkX is
volunteer work, for which we are tremendously grateful. Provide
constructive criticism on ideas and implementations, and remind
yourself of how it felt when your own work was being evaluated as a
novice.
NetworkX strongly values mentorship in code review. New users
often need more handholding, having little to no git
experience. Repeat yourself liberally, and, if you don’t recognize a
contributor, point them to our development guide, or other GitHub
workflow tutorials around the web. Do not assume that they know how
GitHub works (e.g., many don't realize that adding a commit
automatically updates a pull request). Gentle, polite, kind
encouragement can make the difference between a new core developer and
an abandoned pull request.
When reviewing, focus on the following:
1. API: The API is what users see when they first use
NetworkX. APIs are difficult to change once released, so
should be simple, functional
<https://en.wikipedia.org/wiki/Functional_programming>__ (i.e. notdeprecation_policy
carry state), consistent with other parts of the library, and
should avoid modifying input variables. Please familiarize
yourself with the project's :ref:.
2. Documentation: Any new feature should have a gallery
example that not only illustrates but explains it.
3. The algorithm: You should understand the code being modified or
added before approving it. (See Merge Only Changes You
Understand_ below.) Implementations should do what they claim,
and be simple, readable, and efficient.
4. Tests: All contributions to the library must be tested, and
each added line of code should be covered by at least one test. Good
tests not only execute the code, but explores corner cases. It is tempting
not to review tests, but please do so.
Other changes may be nitpicky: spelling mistakes, formatting,
etc. Do not ask contributors to make these changes, and instead
make the changes by pushing to their branch
<https://help.github.com/en/github/collaborating-with-issues-and-pull-requests/committing-changes-to-a-pull-request-branch-created-from-a-fork>__,suggestion
or using GitHub’s
<https://help.github.com/en/github/collaborating-with-issues-and-pull-requests/commenting-on-a-pull-request>__feature
<https://help.github.com/en/github/collaborating-with-issues-and-pull-requests/incorporating-feedback-in-your-pull-request>__.
(The latter is preferred because it gives the contributor a choice in
whether to accept the changes.)
Our default merge policy is to squash all PR commits into a single
commit. Users who wish to bring the latest changes from main
into their branch should be advised to merge, not to rebase. Even
when merge conflicts arise, don’t ask for a rebase unless you know
that a contributor is experienced with git. Instead, rebase the branch
yourself, force-push to their branch, and advise the contributor on
how to force-pull. If the contributor is no longer active, you may
take over their branch by submitting a new pull request and closing
the original. In doing so, ensure you communicate that you are not
throwing the contributor's work away! You should use GitHub'sCo-authored-by: keyword for commit messages to credit the
original contributor.
Please add a note to a pull request after you push new changes; GitHub
may not send out notifications for these.
Merge Only Changes You Understand
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Long-term maintainability is an important concern. Code doesn't
merely have to work, but should be understood by multiple core
developers. Changes will have to be made in the future, and the
original contributor may have moved on.
Therefore, do not merge a code change unless you understand it. Ask
for help freely: we have a long history of consulting community
members, or even external developers, for added insight where needed,
and see this as a great learning opportunity.
While we collectively "own" any patches (and bugs!) that become part
of the code base, you are vouching for changes you merge. Please take
that responsibility seriously.
Closing issues and pull requests
--------------------------------
Sometimes, an issue must be closed that was not fully resolved. This can be
for a number of reasons:
- the person behind the original post has not responded to calls for
clarification, and none of the core developers have been able to reproduce
their issue;
- fixing the issue is difficult, and it is deemed too niche a use case to
devote sustained effort or prioritize over other issues; or
- the use case or feature request is something that core developers feel
does not belong in NetworkX,
among others. Similarly, pull requests sometimes need to be closed without
merging, because:
- the pull request implements a niche feature that we consider not worth the
added maintenance burden;
- the pull request implements a useful feature, but requires significant
effort to bring up to NetworkX's standards, and the original
contributor has moved on, and no other developer can be found to make the
necessary changes; or
- the pull request makes changes that do not align with our values, such as
increasing the code complexity of a function significantly to implement a
marginal speedup,
among others.
All these may be valid reasons for closing, but we must be wary not to alienate
contributors by closing an issue or pull request without an explanation. When
closing, your message should:
- explain clearly how the decision was made to close. This is particularly
important when the decision was made in a community meeting, which does not
have as visible a record as the comments thread on the issue itself;
- thank the contributor(s) for their work; and
- provide a clear path for the contributor or anyone else to appeal the
decision.
These points help ensure that all contributors feel welcome and empowered to
keep contributing, regardless of the outcome of past contributions.
Further resources
-----------------
As a core member, you should be familiar with community and developer
resources such as:
- Our :ref:contributor_guide
- Our :ref:
- __ for Python stylePEP257 <https://www.python.org/dev/peps/pep-0257/>
- __ and the NumPy
documentation
guide <https://numpy.org/doc/stable/docs/howto_document.html>__tag on
for docstrings. (NumPy docstrings are a superset of PEP257. You
should read both.)
- The NetworkX
StackOverflow <https://stackoverflow.com/questions/tagged/networkx>__mailing
- Our
list <http://groups.google.com/group/networkx-discuss/>__
You are not required to monitor all of the social resources.
---
Doc/Developer/Deprecations
Deprecations
============
.. _deprecation_policy:
Policy
------
If the behavior of the library has to be changed, a deprecation cycle must be
followed to warn users.
A deprecation cycle is not necessary when:
* adding a new function, or
adding a new keyword argument to the end* of a function signature, or
* fixing buggy behavior
A deprecation cycle is necessary for any breaking API change, meaning a
change where the function, invoked with the same arguments, would return a
different result after the change. This includes:
* changing the order of arguments or keyword arguments, or
* adding arguments or keyword arguments to a function, or
* changing the name of a function, class, method, etc., or
* moving a function, class, etc. to a different module, or
* changing the default value of a function's arguments.
Usually, our policy is to put in place a deprecation cycle over two minor
releases (e.g., if a deprecation warning appears in 2.3, then the functionality
should be removed in 2.5). For major releases we usually require that all
deprecations have at least a 1-release deprecation cycle (e.g., if 3.0 occurs
after 2.5, then all removed functionality in 3.0 should be deprecated in 2.5).
Note that these 1- and 2-release deprecation cycles for major and minor
releases is not a strict rule and in some cases, the developers can agree on a
different procedure upon justification (like when we can't detect the change,
or it involves moving or deleting an entire function for example).
Procedure
---------
To set up a function for deprecation:
- Use a deprecation warning to warn users. For example::
msg = "curly_hair is deprecated and will be removed in v3.0. Use sum() instead."
warnings.warn(msg, DeprecationWarning)
- Add a warnings filter to networkx/conftest.py::
warnings.filterwarnings(
"ignore", category=DeprecationWarning, message=<start of message>
)
- Add a reminder to doc/developer/deprecations.rst for the team
to remove the deprecated functionality in the future. For example:
.. code-block:: rst
* In utils/misc.py remove generate_unique_node and related tests.
.. note::
To reviewers: make sure the merge message has a brief description of the
change(s) and if the PR closes an issue add, for example, "Closes #123"
where 123 is the issue number.
Todo
----
Make sure to review networkx/conftest.py after removing deprecated code.
Version 3.8
~~~~~~~~~~~
* Remove maybe_regular_expander from networkx.generators.expanders.
* In algorithms/approximation/steinertree.py remove metric_closure and related tests.
Version 3.9
~~~~~~~~~~~
* Remove bfs_predecessors from networkx.algorithms.traversal.breadth_first_searcph.
---
Doc/Developer/Index
.. _developer:
Developer
*
.. only:: html
:Release: |version|
:Date: |today|
.. toctree::
:maxdepth: 2
about_us
code_of_conduct
values
contribute
projects
new_contributor_faq
core_developer
release
deprecations
roadmap
nxeps/index
---
Doc/Developer/New Contributor Faq
.. _contributing_faq:
New Contributor FAQ
*
A collection of frequently-asked questions by newcomers to
open-source development and first-time contributors to NetworkX.
Q: I'm new to open source and would like to contribute to NetworkX. How do I get started?
-----------------------------------------------------------------------------------------
To contribute to NetworkX, you will need three things:
1. The source code
2. A development environment
3. An idea of what you'd like to contribute
Steps 1 & 2 are covered extensively in :ref:Development Workflow <dev_workflow>.
There is no generic answer for step 3. There are many ways that NetworkX can
be improved, from adding new algorithms, improving existing algorithms,
improving the test suite (e.g. increasing test coverage), and improving the
documentation.
The "best" way to find a place to start is to follow your own personal
interests!
That said, a few places to check for ideas on where to get started:
- The issue tracker <https://github.com/networkx/networkx/issues>_ listsAlgorithms discussion
known bugs and feature requests.
- The _ includes a listing of algorithms that users
would like to have but that are not yet included in NetworkX.
.. _Algorithms discussion: https://github.com/networkx/networkx/discussions/categories/algorithms
Q: I've found an issue I'm interested in, can I have it assigned to me?
-----------------------------------------------------------------------
NetworkX doesn't typically assign issues to contributors. If you find an issue
or feature request on the issue tracker that you'd like to work on, you should
first check the issue thread to see if there are any linked pull requests.
If not, then feel free to open a new PR to address the issue - no need
to ask for permission - and don't forget to reference the issue number in the PR
comments so that others know you are now working on it!
Q: How do I contribute an example to the Gallery?
-------------------------------------------------
The example gallery is great place to contribute, particularly if you have an
interesting application or visualization that uses NetworkX.
The gallery is generated using :doc:sphinx-gallery <sphinx-gallery:index>
from Python scripts stored in the examples/ directory.
For instance, let's say I'd like to contribute an example of visualizing a
complete graph <networkx.generators.classic.complete_graph> using acircular layout <networkx.drawing.layout.circular_layout>.setting up a development environment <dev_workflow>
Assuming you have already followed the procedure for
:ref:, start by
creating a new branch:
.. code-block:: bash
git checkout -b complete-graph-circular-layout-example
.. note:: It's generally a good idea to give your branch a descriptive name so
that it's easy to remember what you are working on.
Now you can begin work on your example. Sticking with the circular layout idea,
you might create a file in examples/drawing called plot_circular_layout.py
with the following contents::
import networkx as nx
import matplotlib.pyplot as plt
G = nx.complete_graph(10) # A complete graph with 10 nodes
nx.draw_networkx(G, pos=nx.circular_layout(G))
.. note:: It may not be clear where exactly an example belongs. Our circular
layout example is very simple, so perhaps it belongs in examples/basic.
It would also make sense for it to be in examples/drawing since it deals
with visualization. Don't worry if you're not sure: questions like this will
be resolved during the review process.
At this point, your contribution is ready to be reviewed. You can make the
changes on your complete-graph-circular-layout-example branch visible tocreating a pull request
other NetworkX developers by__.
.. _PR: https://docs.github.com/en/github/collaborating-with-issues-and-pull-requests/creating-a-pull-request
__ PR_
.. seealso:: The :ref:developer guide <dev_workflow> has more details on
creating pull requests.
Q: I want to work on a specific function. How do I find it in the source code?
------------------------------------------------------------------------------
Assuming you have followed the instructions for
:ref:setting up the development workflow <dev_workflow>, there are several
ways of determining where the in the source code a particular function or
class is defined.
For example, let's say you are interested in making a change to the
~networkx.drawing.layout.kamada_kawai_layout function, so you need to know
where it is defined. In an IPython terminal, you can use ? --- the source file is
listed in the File: field:
.. code-block:: ipython3
In [1]: import networkx as nx
In [2]: nx.kamada_kawai_layout?
.. code-block:: text
Signature: <clipped for brevity>
Docstring: <clipped for brevity>
File: ~/networkx/networkx/drawing/layout.py
Type: function
Command line utilities like grep or git grep are also very useful.
For example, from the NetworkX source directory:
.. code-block:: bash
$ grep -r "def kamada_kawai_layout" .
./networkx/drawing/layout.py:def kamada_kawai_layout(
Q: What is the policy for deciding whether to include a new algorithm?
----------------------------------------------------------------------
There is no official policy setting explicit inclusion criteria for new
algorithms in NetworkX. New algorithms are more likely to be included if they
have been published and are cited by others. More important than number of
citations is how well proposed additions fit the project :ref:mission_and_values.
Testing is also an important factor in determining whether algorithms
should be included. Proposals that include thorough tests which illustrate
expected behavior are much easier to review, and therefore likely to progress more rapidly.
.. note::
Thorough does not mean exhaustive. The quality of unit tests is much
more important than quantity. Thorough tests should address questions like:
- Does the algorithm support different graph types (undirected, directed,
multigraphs)?
- How does the algorithm behave with disconnected inputs and graphs which
contain self-loops?
- Are there explicit test cases outlined in the literature which can be
incorporated in the test suite?
---
Doc/Developer/Projects
Mentored Projects
==================
This page maintains a list of mentored project ideas that contributors can work
on if they are interested in contributing to the NetworkX project. Feel free to
suggest any other idea if you are interested on the
NetworkX GitHub discussions page <https://github.com/networkx/networkx/discussions>__
These ideas can be used as projects for Google Summer of Code, Outreachy,
NumFOCUS Small Development Grants and university course/project credits (if
your university allows contribution to open source for credit). Mentee/contributors
participating under NetworkX organisation would be expected to share their weekly
work updates and get feedback in a 1-hr weekly meetings. If this isn't feasible for
the contributor we can discuss further to figure something else out.
If you are a professor interested in having your class develop tools
and contribute the results to NetworkX, we welcome your submissions!
We encourage you to consider rewriting/improving existing functions
as a potential source of projects. Working off of and
improving existing tools involves reading, evaluating and writing code,
rather than just writing new code. We also encourage them to review each
other's PRs. You can have students submit their PRs to your personal fork,
discuss, review, etc in an environment conducive to mentoring and learning.
Once their branch is ready to merge, it can be submitted to the main NetworkX
repository. This will help keep in-class discussions separate from the
broader NetworkX review process, making both more manageable and readable.
Feel free to reach out to use as you plan these activities.
Creating a cookie-cutter backend repository in NetworkX
-------------------------------------------------------
- Abstract: NetworkX has recently incorporated a backend plugin <https://en.wikipedia.org/wiki/Plug-in_(computing)>__Python entry-points <https://packaging.python.org/en/latest/specifications/entry-points/>
system based on __.
This project aims to develop a template backend repository to help developers
create their own NetworkX backends with ease. The template will clearly distinguish
between the mandatory, optional, and additional features/requirements that a NetworkX
backend package needs to have. We expect this template backend to be forked by the
developers, and then they would only have to add their backend implementation for the
algorithms they want to support at the designated places, and they would not have to
care about setting up all the other aspects of a backend unless they want to enable
or adopt any of the optional or additional functionalities of a backend. You can start by:
- looking at nx-j4f <https://github.com/Schefflera-Arboricola/nx-j4f>__nx-parallel <https://github.com/networkx/nx-parallel>
(a dummy backend) and __
(a simple backend) for inspiration.
- reading and understanding :ref:backends and :ref:configs documentation.
Feel free to ask questions or open an issue if you find something hard to understand,
as the above documentations are not that well-written.
- Recommended Skills: Python, willingness to roll up your sleeves and dig deep
and understand the dispatching mechanism in NetworkX, and ability to take feedback
and iterate on your work.
- Expected Outcome: A "ready-to-fork" and comprehensive backend template in the
NetworkX organization.
- Expected time commitment: ~350 hours project
- Complexity: Medium
- Interested Mentors: @Schefflera-Arboricola <https://github.com/Schefflera-Arboricola>__,@dschult <https://github.com/dschult/>
__
Adding embarrassingly parallel graph algorithms in nx-parallel
--------------------------------------------------------------
- Abstract: nx-parallel <https://github.com/networkx/nx-parallel>__ is a NetworkXjoblib <https://joblib.readthedocs.io/en/latest/index.html>
backend that uses __ foralgorithms are implemented in nx-parallel <https://github.com/networkx/nx-parallel?tab=readme-ov-file#algorithms-in-nx-parallel>
implementing parallel graph algorithms. Currently, only some of the NetworkX
__.embarrassingly parallel <https://en.wikipedia.org/wiki/Embarrassingly_parallel>
We expect the contributor to find __wide variety of graph algorithms <Algorithms>
graph algorithms from the :ref:
implemented in NetworkX and then write their parallel implementations in nx-parallel.
You can start by looking at:
- the implementations of existing algorithms in nx-parallel for inspiration.
- Joblib docs: Embarrassingly parallel for loops <https://joblib.readthedocs.io/en/latest/parallel.html>__
Find more details in Issue#82 <https://github.com/networkx/nx-parallel/issues/82>__.
- Recommended Skills: Python, willingness to roll up your sleeves and dig deep
and understand nx-parallel's infrastructure, and ability to take feedback and
iterate on your work.
- Expected Outcome: 3 parallel graph algorithms (~175 hours), or 7 (~350 hours),
implemented in nx-parallel.
- Complexity: Medium
- Interested Mentors: @Schefflera-Arboricola <https://github.com/Schefflera-Arboricola>__,@dschult <https://github.com/dschult/>
__
Pedagogical Interactive Notebooks for Algorithms Implemented in NetworkX
------------------------------------------------------------------------
- Abstract: NetworkX has a :ref:wide variety of algorithms <Algorithms>
implemented. Even though the algorithms are well documented, explanations of
the ideas behind the algorithms are often missing and we would like to
collect these, write Jupyter notebooks to elucidate these ideas and explore
the algorithms experimentally, and publish the notebooks at
https://github.com/networkx/notebooks. The goal is to gives readers a
deeper outlook behind standard network science and graph theory algorithms
and encourage them to delve further into the topic.
- Recommended Skills: Python, Jupyter notebooks, graph algorithms.
- Expected Outcome: A collection of Interactive Jupyter notebooks which
explain and explore network algorithms to readers and users of NetworkX.
For example, see this notebook on
:doc:Geometric Generator Models <nx-guides:content/generators/geometric>
- Complexity: Depending on the algorithms you are interested to work on.
- Interested Mentors: @rossbar <https://github.com/rossbar/>__,@Schefflera-Arboricola <https://github.com/Schefflera-Arboricola>
__
- Expected time commitment: This project can be either a medium project (~175 hours)
or a large project (~350 hours). The contributor is expected to contribute 2-3
pedagogical interactive notebooks for the medium duration project and 4-5 notebooks
for the long duration project.
Incorporate a Python library for ISMAGs isomorphism calculations
----------------------------------------------------------------
- Abstract: A team from Sandia Labs has converted the original java implementation of
the ISMAGS isomorphism routines to Python. They have invited us to incorporate that
code into NetworkX if we are interested. We'd like someone to learn the ISMAGS code
we currently provide, and the code from this new library and figure out what the
best combination is to include in NetworkX moving forward. That could be two separate
subpackages of tools, or more likely a combination of the two sets of code, or a
third incantation that combines good features from each.
- Recommended Skills: Python, graph algorithms.
- Expected Outcome: A plan for how to best incorporate ISMAGS into NetworkX along
with code to do that incorporation.
- Interested Mentors: @dschult <https://github.com/dschult/>__,@rossbar <https://github.com/rossbar/>
__
- Expected time commitment: This project will be a full time 10 week project (~350 hrs).
Centrality Atlas
----------------
- Abstract: The goal of this project would be to produce a comprehensive review
of network centrality measures.
Centrality is a central concept in network science and has many applications
across domains. NetworkX provides many functions for measuring
various types of :doc:network centrality</reference/algorithms/centrality>.
The individual centrality functions are typically well-described by their
docstrings (though there's always room for improvement!); however, there
currently is no big-picture overview of centrality.
Furthermore, many of the centrality measures are closely related, but there is
no documentation that describes these relationships.
- Recommended Skills: Python, literature review, technical writing
- Expected Outcome: An executable document that provides an overview and applications
of network centrality measures. Potential outputs include (but are not limited
to): an article for nx-guides (see above) and/or an example gallery for centrality
measures.
- Interested Mentors: @dschult <https://github.com/dschult/>__,@rossbar <https://github.com/rossbar/>
__,@Schefflera-Arboricola <https://github.com/Schefflera-Arboricola>
__
- Expected time commitment: Variable, though a high-quality review article would
be expected to take several months of dedicated research (~350 hours).
Completed Projects
==================
- Revisiting and expanding nx-parallel_@Schefflera-Arboricola <https://github.com/Schefflera-Arboricola>
- Program: Google Summer of Code 2024
- Contributor: __GSoC 2024: Revisiting and expanding nx-parallel <https://github.com/networkx/archive/blob/main/proposals-gsoc/GSoC-2024-Revisiting-and-expanding-nx-parallel.pdf>
- Link to Proposal: _
- Unifying the Visualization Interface for NetworkX
- Program: Funded by a grant from CZI (Chan-Zuckerberg Initiative) 2024
- Contributor: __
- Summary: Refactored existing draw functions to a single function with all drawing
attributes stored in the NetworkX Graph object.
- VF2++ algorithm for graph isomorphism_@kpetridis24 <https://github.com/kpetridis24/>
- Program: Google Summer of Code 2022
- Contributor: __GSoC 2022: VF2++ Algorithm <https://github.com/networkx/archive/blob/main/proposals-gsoc/GSoC-2022-VF2plusplus-isomorphism.pdf>
- Link to Proposal: _
- Louvain community detection algorithm_@z3y50n <https://github.com/z3y50n/>
- Program: Google Summer of Code 2021
- Contributor: __GSoC 2021: Community Detection Algorithms <https://github.com/networkx/archive/blob/main/proposals-gsoc/GSoC-2021-Community-Detection-Algorithms.pdf>
- Link to Proposal: __
- Asadpour algorithm for directed travelling salesman problem_@mjschwenne <https://github.com/mjschwenne/>
- Program: Google Summer of Code 2021
- Contributor: __GSoC 2021: Asadpour algorithm <https://github.com/networkx/archive/blob/main/proposals-gsoc/GSoC-2021-Asadpour-Asymmetric-Traveling%20Salesman-Problem.pdf>
- Link to Proposal: __
- Pedagogical notebook: Directed acyclic graphs and topological sort_@vdshk <https://github.com/vdshk>
- Program: Google Summer of Code 2021
- Contributor: __
- Pedagogical notebooks: Graph assortativity_ & Network flow analysis and Dinitz algorithm_@harshal-dupare <https://github.com/harshal-dupare/>
- Program: Google Summer of Code 2021
- Contributor: __
- Add On system for NetworkX: NetworkX-Metis_@OrkoHunter <https://github.com/OrkoHunter/>
- Program: Google Summer of Code 2015
- Contributor: __GSoC 2015: Add On System for NetworkX <https://github.com/networkx/archive/blob/main/proposals-gsoc/GSoC-2015-Add-on-system-for-NetworkX.md>
- Link to Proposal: __
- NetworkX 2.0 API_@MridulS <https://github.com/MridulS/>
- Program: Google Summer of Code 2015
- Contributor: __GSoC 2015: NetworkX 2.0 API <https://github.com/networkx/archive/blob/main/proposals-gsoc/GSoC-2015-NetworkX-2.0-api.md>
- Link to Proposal: __
.. _Revisiting and expanding nx-parallel: https://github.com/Schefflera-Arboricola/blogs/tree/main/networkx/GSoC24VF2++ algorithm for graph isomorphism
.. _: https://github.com/networkx/networkx/pull/5788Louvain community detection algorithm
.. _: https://github.com/networkx/networkx/pull/4929Asadpour algorithm for directed travelling salesman problem
.. _: https://github.com/networkx/networkx/pull/4740Directed acyclic graphs and topological sort
.. _: https://github.com/networkx/nx-guides/pull/44Graph assortativity
.. _: https://github.com/networkx/nx-guides/pull/42Network flow analysis and Dinitz algorithm
.. _: https://github.com/networkx/nx-guides/pull/46NetworkX-Metis
.. _: https://github.com/networkx/networkx-metisNetworkX 2.0 API
.. _: https://networkx.org/documentation/latest/release/migration_guide_from_1.x_to_2.0.html
..
Project Idea Template
---------------------
- Abstract:
- Recommended Skills:
- Expected Outcome:
- Complexity;
- Interested Mentors:
---
Doc/Developer/Release
Pre-release checklist
=====================
Things to double-check prior to cutting a NetworkX release:
- Ensure that the copyright in README.rst and LICENSE.txt is
updated to the current year.
Release Process
===============
- Set release variables:
.. code-block:: bash
export VERSION=<version number>
export PREVIOUS=<previous version number>
export ORG="networkx"
export REPO="networkx"
If this is a prerelease:
.. code-block:: bash
export NOTES="doc/release/release_dev.rst"
If this is release:
.. code-block:: bash
export NOTES="doc/release/release_${VERSION}.rst"
git rm doc/release/release_dev.rst
- Autogenerate release notes:
.. code-block:: bash
changelist ${ORG}/${REPO} networkx-${PREVIOUS} main --version ${VERSION} --out ${NOTES} --format rst
changelist ${ORG}/${REPO} networkx-${PREVIOUS} main --version ${VERSION} --out ${VERSION}.md
.. note::
The release notes are generated twice here - the reST version is included in
the documentation, while the markdown version is included with releases
on GitHub.
- Edit doc/_static/version_switcher.json in order to add the release, move the
key value pair "preferred": true to the most recent stable version, and commit.
For an rc, skip this step.
- Update doc/release/index.rst.
- Update __version__ in networkx/__init__.py.
- Commit changes:
.. code-block:: bash
git add networkx/__init__.py ${NOTES} doc/_static/version_switcher.json doc/release/index.rst
git commit -m "Designate ${VERSION} release"
- Add the version number as a tag in git:
.. code-block:: bash
git tag -s networkx-${VERSION} -m "signed ${VERSION} tag"
- Push the new meta-data to github:
.. code-block:: bash
git push --tags origin main
(where origin is the name of the github.com:networkx/networkx repository.)
- Review the github release page: https://github.com/networkx/networkx/tags
- Update documentation on the web:
.. note::
This step does not apply to rc releases.
The documentation is kept in a separate repo:
https://github.com/networkx/documentation
- Wait for the CI service to deploy to GitHub Pages
- Sync your branch with the remote repo: git pull.
- Copy the documentation built by the CI service.
Assuming you are at the top-level of the documentation repo:
.. code-block:: bash
# FIXME - use eol_banner.html
cp -a latest ../networkx-${VERSION}
git reset --hard <commit from last release>
mv ../networkx-${VERSION} .
rm -rf stable
cp -rf networkx-${VERSION} stable
git add networkx-${VERSION} stable
git commit -m "Add ${VERSION} docs"
git push # force push---be careful!
- Update __version__ in networkx/__init__.py.
The new version should increment either the patch number or the rc number
depending on whether or not the release is an rc.
For example, if you are releasing version X.Y, the __version__ should
be updated to X.Y.1rc0.dev0.
If instead the release is an rc, then increment the rc number --- for example,
if releasing X.Yrc0, the __version__ should be updated to X.Yrc1.dev0.
- Commit and push changes:
.. code-block:: bash
git add networkx/__init__.py
git commit -m "Bump release version"
git push origin main
- Update the web frontpage:
.. note::
This step does not apply to rc releases.
The webpage is kept in a separate repo: https://github.com/networkx/website
- Sync your branch with the remote repo: git pull.
If you try to make github when your branch is out of sync, it
creates headaches.
- Update build/index.html.
- Edit build/_static/docversions.js and commit
- Push your changes to the repo.
- Deploy using make github.
- Post release notes on mailing list.
---
Doc/Developer/Roadmap
=======
Roadmap
=======
The roadmap is intended for larger, fundamental changes to
the project that are likely to take months or years of developer time.
Smaller-scoped items will continue to be tracked on our issue tracker.
The scope of these improvements means that these changes may be
controversial, are likely to involve significant discussion
among the core development team, and may require the creation
of one or more :ref:nxep.
Installation
------------
We aim to make NetworkX as easy to install as possible.
Some of our dependencies can be tricky to install.
Other of our dependencies are easy to install on the CPython platform, but
may be more involved on other platforms such as PyPy.
Addressing these installation issues may involve working with the external projects.
Sustainability
--------------
We aim to reduce barriers to contribution, speed up pull request (PR) review,
onboard new maintainers, and attract new developers to ensure the long-term
sustainability of NetworkX.
This includes:
- improving continuous integration
- making code base more approachable
- creating new pathways beyond volunteer effort
- growing maintainers and leadership
- increasing diversity of developer community
Benchmarks
----------
Speed improvements, lower memory usage, and the ability to parallelize
algorithms are beneficial to most science domains and use cases.
Toward that goal we want a benchmarking system using something
like airspeed velocity (https://asv.readthedocs.io/en/stable/).
See a fairly extensive version of this in benchmarks/benchmarks.
Performance
-----------
Individual functions can be optimized for performance and memory use.
We are also interested in exploring new technologies to accelerate
code and reduce memory use. Before adopting any new technologies
we will need to carefully consider its impact on code readability
and difficulty of building and installing NetworkX.
For more information, see our :ref:mission_and_values.
Many functions can be trivially parallelized. nx-parallel
(https://github.com/networkx/nx-parallel) is one possible approach
using backends. Python's new freethreading feature is a powerful
possibility.
Documentation
-------------
We’d like to improve the content, structure, and presentation of the NetworkX
documentation. Some specific goals include:
- examples that include short workflows for specific domains
- summary doc pages for suites of functions e.g. community with comparisons of
functions and why you might pick one over another
- longer gallery examples or nx-guides, including complete life science workflows
- domain-specific documentation (NetworkX for Geneticists,
NetworkX for Neuroscientists, etc.) probably as nx-guides
- examples of how to use NetworkX with other packages, e.g. Cytoscape
Linear Algebra
--------------
We would like to improve our linear algebra based algorithms.
This includes investigating SciPy's csgraph and possibly getting SciPy to support
a new sparse array format that uses a NX Graph as storage.
We should also decide how to handle algorithms with multiple implementations
(e.g., some algorithms are implemented in Python, NumPy, and SciPy).
Perhaps we can build off of NumPy's array-api to get e.g. PyTorch in our linalg.
Interoperability
----------------
We'd like to improve interoperability with the rest of the scientific Python
ecosystem.
This includes projects we depend on (e.g., NumPy, SciPy, Pandas, Matplotlib)
as well as ones we don't (e.g., Geopandas).
For example, we would also like to be able to seamlessly exchange graphs with
other network analysis software. Perhaps SciPy can support a sparse array format
that uses a NX Graph data structure. Perhaps we can store all node and edge
attributes in a DataFrame without copy.
Another way to integrate with other scientific python ecosystem tools is to
take on features from the other tools that are useful. And we should develop
tools to ease use of NetworkX from within these other tools.
Additional examples of interoperability improvements may include providing a more
pandas-like interface for the `__getitem__` dunder function of node andNXEP2
edge views (:ref:).`
Also developing a universal method to represent a graph as a single sequence ofnodes_and_edges` objects that allow attribute dicts, nodes and edges asdiscussed for graph generators
<https://github.com/networkx/networkx/issues/3036>_.
Visualization
-------------
Visualization is not a primary focus on NetworkX, but it is a major feature for
many users. We need to enhance the drawing tools for NetworkX. We intend to
evolve to a new display function that enhances both api and performance relative
to the draw functions. We should also enhance docs to make connections with
iplotx and GraphViz.
---
Doc/Developer/Values
.. _mission_and_values:
==================
Mission and Values
==================
Our mission
-----------
NetworkX aims to be the reference library for network science algorithms in
Python. We accomplish this by:
- being easy to use and install. We are careful in taking on new
dependencies, and sometimes cull existing ones, or make them optional. All
functions in our API have thorough docstrings clarifying expected inputs and
outputs.
- providing a consistent API. Conceptually identical arguments have the
same name and position in a function signature.
- ensuring correctness. Test coverage is close to 100% and code is reviewed by
at least two core developers before being included in the library.
- caring for users’ data. We have a functional API and don't modify
input data unless explicitly directed to do so.
- promoting education in network science, with extensive pedagogical
documentation.
Our values
----------
- We are inclusive (:ref:code_of_conduct). We welcome and mentor newcomers who aregovernance
making their first contribution.
- We are open source and community-driven (:ref:).NumPy-style
- We focus on graph data structures and algorithms for network science applications.
- We prefer pure Python implementations using native data structures
(especially dicts) due to their consistent, intuitive interface and amazing
performance capabilities. We include interfaces to other data structures,
especially NumPy arrays and SciPy sparse matrices for algorithms that more
naturally use arrays and matrices or where time or space requirements are
significantly lower. Sometimes we provide two algorithms for the same result,
one using each data structure, when pedagogy or space/time trade-offs justify
such multiplicity.
- We value simple, readable implementations over getting every last ounce of
performance. Readable code that is easy to understand, for newcomers and
maintainers alike, makes it easier to contribute new code as well as prevent
bugs. This means that we will prefer a 20% slowdown if it reduces lines of
code two-fold, for example.
- We value education and documentation. All functions should have
docstrings <https://numpy.org/doc/stable/docs/howto_document.html>,
preferably with examples, as well as gallery examples that showcase how that
function is used in a scientific application.
Acknowledgments
---------------
This document is modified from the scikit-image mission and values document.
---
Doc/Reference/Algorithms/Shortest Paths/Dijkstra
Dijkstra's Algorithm
====================
Dijkstra's algorithm is a classical algorithm for finding the shortest paths
from a single source node to all other nodes in a weighted graph with
non-negative edge weights. It was conceived by Edsger W. Dijkstra in 1956 and
is widely used in routing, network optimization, and pathfinding problems.
Because Dijkstra's algorithm works only with non-negative edge weights,
alternative algorithms such as Bellman-Ford or Johnson's algorithm are used
for graphs with negative weights. For a general overview of the shortest path
problem see :doc:/reference/algorithms/shortest_paths.
Problem Definition
------------------
Given a weighted graph $G = (V, E)$ and a source node $s \in V$, compute the
shortest-path distances $d(s, v)$ from $s$ to every node $v \in V$, where each
edge $(u, v) \in E$ has a non-negative weight $w(u, v)$. Optionally, the
algorithm can also produce the actual shortest paths.
Algorithm
---------
Dijkstra's algorithm is a greedy, iterative algorithm. The main idea is to
incrementally build a set of nodes with known shortest distances, selecting at
each step the node with the smallest tentative distance. At each step, the
tentative distance of the selected node becomes final, as no shorter path to it
can be found.
A key operation in Dijkstra's algorithm is edge relaxation. When a node is
selected, the algorithm examines all of its outgoing edges and checks whether
reaching a neighboring node through it would yield a shorter path than the one
currently known. If so, the tentative distance of that neighbor is updated.
Through repeated relaxation of edges, the algorithm gradually refines the
shortest-path estimates until all distances are finalized. The procedure can be
summarized in three main stages: initialization, iteration, and
termination, as outlined below.
Initialization
1. Assign source node $s$ a tentative distance value of $0$
($dist[s] = 0$).
2. Optionally, initialize a $predecessor$ dict to reconstruct shortest
paths.
At this point, all nodes are considered unvisited and no shortest distance
is considered final.
Iteration
While there are unvisited nodes:
1. Select the unvisited node $u$ with the smallest tentative distance.
2. Mark $u$ as visited. A visited node will not be checked again because
this is the shortest path to get to it. Distance to $u$ is now
considered final.
3. Edge relaxation. For each neighbor $v$ of $u$:
* Compute alternative distance: $alt = dist[u] + w(u, v)$
* If $alt < dist[v]$, update $dist[v] = alt$ and set $predecessor[v] = u$.
Termination
The algorithm terminates when all nodes have been visited. The final distances
represent the shortest paths from the source to every reachable node. Shortest
paths can be reconstructed by following predecessor dict backward from each
target node to the source.
Example
-------
Consider the weighted graph:
.. code-block:: text
(2)
A ------- B
| |
(1) (3)
| |
C ------- D
(1)
We can compute the shortest path from A to all nodes by doing:
>>> import networkx as nx
>>> # Create a weighted graph
>>> G = nx.Graph()
>>> edges = [('A', 'B', 2), ('A', 'C', 1), ('B', 'D', 3), ('C', 'D', 1)]
>>> G.add_weighted_edges_from(edges)
>>> distances = nx.single_source_dijkstra_path_length(G, source='A')
>>> print("Shortest distances from A:", distances)
Shortest distances from A: {'A': 0, 'C': 1, 'B': 2, 'D': 2}
Complexity
----------
The time complexity of Dijkstra's algorithm depends on the data structure used
to select the node with the smallest tentative distance. Using a simple array
results in a time complexity of :math:O(|V|^2), while a binary heap reduces it toO((|V| + |E|) \log |V|)
:math:. Using a Fibonacci heap further improves theO(|V| \log |V| + |E|)
complexity to :math:. The space complexity of the algorithm isO(|V| + |E|)
:math:, which accounts for storing the graph representation as well as
the distance and predecessor information.
In practice, Fibonacci heaps have a higher constant overhead compared to binary
heaps, which can make them slower for typical problem sizes despite their
better asymptotic performance. NetworkX's implementation of Dijkstra's
algorithm uses a Python built-in binary heap.
Available Functions
-------------------
.. automodule:: networkx.algorithms.shortest_paths.weighted
:no-index:
.. autosummary::
dijkstra_predecessor_and_distance
dijkstra_path
dijkstra_path_length
single_source_dijkstra
single_source_dijkstra_path
single_source_dijkstra_path_length
multi_source_dijkstra
multi_source_dijkstra_path
multi_source_dijkstra_path_length
all_pairs_dijkstra
all_pairs_dijkstra_path
all_pairs_dijkstra_path_length
bidirectional_dijkstra
---
Doc/Reference/Algorithms/Approximation
*
Approximations and Heuristics
*
.. automodule:: networkx.algorithms.approximation
Connectivity
------------
.. automodule:: networkx.algorithms.approximation.connectivity
.. autosummary::
:toctree: generated/
all_pairs_node_connectivity
local_node_connectivity
node_connectivity
K-components
------------
.. automodule:: networkx.algorithms.approximation.kcomponents
.. autosummary::
:toctree: generated/
k_components
Clique
------
.. automodule:: networkx.algorithms.approximation.clique
.. autosummary::
:toctree: generated/
maximum_independent_set
max_clique
clique_removal
large_clique_size
Clustering
----------
.. automodule:: networkx.algorithms.approximation.clustering_coefficient
.. autosummary::
:toctree: generated/
average_clustering
Density
-------
.. automodule:: networkx.algorithms.approximation.density
.. autosummary::
:toctree: generated/
densest_subgraph
Distance Measures
-----------------
.. automodule:: networkx.algorithms.approximation.distance_measures
.. autosummary::
:toctree: generated/
diameter
Dominating Set
---------------
.. automodule:: networkx.algorithms.approximation.dominating_set
.. autosummary::
:toctree: generated/
min_weighted_dominating_set
min_edge_dominating_set
Matching
--------
.. automodule:: networkx.algorithms.approximation.matching
.. autosummary::
:toctree: generated/
min_maximal_matching
Ramsey
------
.. automodule:: networkx.algorithms.approximation.ramsey
.. autosummary::
:toctree: generated/
ramsey_R2
Steiner Tree
------------
.. automodule:: networkx.algorithms.approximation.steinertree
.. autosummary::
:toctree: generated/
metric_closure
steiner_tree
Traveling Salesman
------------------
.. automodule:: networkx.algorithms.approximation.traveling_salesman
.. autosummary::
:toctree: generated/
christofides
traveling_salesman_problem
greedy_tsp
simulated_annealing_tsp
threshold_accepting_tsp
asadpour_atsp
Treewidth
---------
.. automodule:: networkx.algorithms.approximation.treewidth
.. autosummary::
:toctree: generated/
treewidth_min_degree
treewidth_min_fill_in
Vertex Cover
------------
.. automodule:: networkx.algorithms.approximation.vertex_cover
.. autosummary::
:toctree: generated/
min_weighted_vertex_cover
Max Cut
-------
.. automodule:: networkx.algorithms.approximation.maxcut
.. autosummary::
:toctree: generated/
randomized_partitioning
one_exchange
---
Doc/Reference/Algorithms/Assortativity
*
Assortativity
*
.. automodule:: networkx.algorithms.assortativity
.. autosummary::
:toctree: generated/
.. _networkx.algorithms.assortativity.correlation:
Assortativity
-------------
.. autosummary::
:toctree: generated/
degree_assortativity_coefficient
attribute_assortativity_coefficient
numeric_assortativity_coefficient
degree_pearson_correlation_coefficient
.. _networkx.algorithms.assortativity.neighbor_degree:
Average neighbor degree
-----------------------
.. autosummary::
:toctree: generated/
average_neighbor_degree
.. _networkx.algorithms.assortativity.connectivity:
Average degree connectivity
---------------------------
.. autosummary::
:toctree: generated/
average_degree_connectivity
.. _networkx.algorithms.assortativity.mixing:
Mixing
------
.. autosummary::
:toctree: generated/
attribute_mixing_matrix
degree_mixing_matrix
attribute_mixing_dict
degree_mixing_dict
mixing_dict
.. _networkx.algorithms.assortativity.pairs:
Pairs
-----
.. autosummary::
:toctree: generated/
node_attribute_xy
node_degree_xy
---
Doc/Reference/Algorithms/Asteroidal
Asteroidal
.. automodule:: networkx.algorithms.asteroidal
.. autosummary::
:toctree: generated/
is_at_free
find_asteroidal_triple
---
Doc/Reference/Algorithms/Bipartite
*
Bipartite
*
.. automodule:: networkx.algorithms.bipartite
Basic functions
---------------
.. automodule:: networkx.algorithms.bipartite.basic
.. autosummary::
:toctree: generated/
is_bipartite
is_bipartite_node_set
sets
color
density
degrees
Edgelist
--------
.. automodule:: networkx.algorithms.bipartite.edgelist
.. autosummary::
:toctree: generated/
generate_edgelist
write_edgelist
parse_edgelist
read_edgelist
Matching
--------
.. automodule:: networkx.algorithms.bipartite.matching
.. autosummary::
:toctree: generated/
eppstein_matching
hopcroft_karp_matching
to_vertex_cover
maximum_matching
minimum_weight_full_matching
Matrix
------
.. automodule:: networkx.algorithms.bipartite.matrix
.. autosummary::
:toctree: generated/
biadjacency_matrix
from_biadjacency_matrix
Projections
-----------
.. automodule:: networkx.algorithms.bipartite.projection
.. autosummary::
:toctree: generated/
projected_graph
weighted_projected_graph
collaboration_weighted_projected_graph
overlap_weighted_projected_graph
generic_weighted_projected_graph
Spectral
--------
.. automodule:: networkx.algorithms.bipartite.spectral
.. autosummary::
:toctree: generated/
spectral_bipartivity
Clustering
----------
.. automodule:: networkx.algorithms.bipartite.cluster
.. autosummary::
:toctree: generated/
clustering
average_clustering
butterflies
latapy_clustering
robins_alexander_clustering
Redundancy
----------
.. automodule:: networkx.algorithms.bipartite.redundancy
.. autosummary::
:toctree: generated/
node_redundancy
Centrality
----------
.. automodule:: networkx.algorithms.bipartite.centrality
.. autosummary::
:toctree: generated/
closeness_centrality
degree_centrality
betweenness_centrality
Generators
----------
.. automodule:: networkx.algorithms.bipartite.generators
.. autosummary::
:toctree: generated/
complete_bipartite_graph
configuration_model
havel_hakimi_graph
reverse_havel_hakimi_graph
alternating_havel_hakimi_graph
preferential_attachment_graph
random_graph
gnmk_random_graph
Covering
--------
.. automodule:: networkx.algorithms.bipartite.covering
.. autosummary::
:toctree: generated/
min_edge_cover
Extendability
-------------
.. automodule:: networkx.algorithms.bipartite.extendability
.. autosummary::
:toctree: generated/
maximal_extendability
Link Analysis
-------------
.. automodule:: networkx.algorithms.bipartite.link_analysis
.. autosummary::
:toctree: generated/
birank
Communities
-----------
.. automodule:: networkx.algorithms.bipartite.community
.. autosummary::
:toctree: generated/
modularity
---
Doc/Reference/Algorithms/Boundary
Boundary
.. automodule:: networkx.algorithms.boundary
.. autosummary::
:toctree: generated/
edge_boundary
node_boundary
---
Doc/Reference/Algorithms/Bridges
Bridges
=======
.. automodule:: networkx.algorithms.bridges
.. autosummary::
:toctree: generated/
bridges
has_bridges
local_bridges
---
Doc/Reference/Algorithms/Broadcasting
Broadcasting
.. automodule:: networkx.algorithms.broadcasting
.. autosummary::
:toctree: generated/
tree_broadcast_center
tree_broadcast_time
---
Doc/Reference/Algorithms/Centrality
Centrality
.. automodule:: networkx.algorithms.centrality
.. _networkx.algorithms.centrality.degree_alg:
Degree
------
.. autosummary::
:toctree: generated/
degree_centrality
in_degree_centrality
out_degree_centrality
.. _networkx.algorithms.centrality.eigenvector:
.. _networkx.algorithms.centrality.katz:
Eigenvector
-----------
.. autosummary::
:toctree: generated/
eigenvector_centrality
eigenvector_centrality_numpy
katz_centrality
katz_centrality_numpy
.. _networkx.algorithms.centrality.closeness:
Closeness
---------
.. autosummary::
:toctree: generated/
closeness_centrality
incremental_closeness_centrality
.. _networkx.algorithms.centrality.current_flow_closeness:
Current Flow Closeness
----------------------
.. autosummary::
:toctree: generated/
current_flow_closeness_centrality
information_centrality
.. _networkx.algorithms.centrality.betweenness:
.. _networkx.algorithms.centrality.betweenness_subset:
(Shortest Path) Betweenness
---------------------------
.. autosummary::
:toctree: generated/
betweenness_centrality
betweenness_centrality_subset
edge_betweenness_centrality
edge_betweenness_centrality_subset
.. _networkx.algorithms.centrality.current_flow_betweenness:
.. _networkx.algorithms.centrality.current_flow_betweenness_subset:
Current Flow Betweenness
------------------------
.. autosummary::
:toctree: generated/
current_flow_betweenness_centrality
edge_current_flow_betweenness_centrality
approximate_current_flow_betweenness_centrality
current_flow_betweenness_centrality_subset
edge_current_flow_betweenness_centrality_subset
Communicability Betweenness
---------------------------
.. autosummary::
:toctree: generated/
communicability_betweenness_centrality
.. _networkx.algorithms.centrality.group:
Group Centrality
----------------
.. autosummary::
:toctree: generated/
group_betweenness_centrality
group_closeness_centrality
group_degree_centrality
group_in_degree_centrality
group_out_degree_centrality
prominent_group
.. _networkx.algorithms.centrality.load:
Load
----
.. autosummary::
:toctree: generated/
load_centrality
edge_load_centrality
.. _networkx.algorithms.centrality.subgraph_alg:
Subgraph
--------
.. autosummary::
:toctree: generated/
subgraph_centrality
subgraph_centrality_exp
estrada_index
.. _networkx.algorithms.centrality.harmonic:
Harmonic Centrality
-------------------
.. autosummary::
:toctree: generated/
harmonic_centrality
Dispersion
----------
.. autosummary::
:toctree: generated/
dispersion
.. _networkx.algorithms.centrality.reaching:
Reaching
--------
.. autosummary::
:toctree: generated/
local_reaching_centrality
global_reaching_centrality
.. _networkx.algorithms.centrality.percolation:
Percolation
-----------
.. autosummary::
:toctree: generated/
percolation_centrality
.. _networkx.algorithms.centrality.second_order:
Second Order Centrality
-----------------------
.. autosummary::
:toctree: generated/
second_order_centrality
.. _networkx.algorithms.centrality.trophic:
Trophic
-------
.. autosummary::
:toctree: generated/
trophic_levels
trophic_differences
trophic_incoherence_parameter
.. _networkx.algorithms.centrality.voterank_alg:
VoteRank
--------
.. autosummary::
:toctree: generated/
voterank
.. _networkx.algorithms.centrality.laplacian:
Laplacian
---------
.. autosummary::
:toctree: generated/
laplacian_centrality
---
Doc/Reference/Algorithms/Chains
Chains
======
.. automodule:: networkx.algorithms.chains
.. autosummary::
:toctree: generated/
chain_decomposition
---
Doc/Reference/Algorithms/Chordal
.. _chordal:
Chordal
=======
.. automodule:: networkx.algorithms.chordal
.. autosummary::
:toctree: generated/
is_chordal
chordal_graph_cliques
chordal_graph_treewidth
complete_to_chordal_graph
find_induced_nodes
---
Doc/Reference/Algorithms/Clique
Clique
.. automodule:: networkx.algorithms.clique
.. autosummary::
:toctree: generated/
enumerate_all_cliques
find_cliques
find_cliques_recursive
make_max_clique_graph
make_clique_bipartite
node_clique_number
number_of_cliques
max_weight_clique
---
Doc/Reference/Algorithms/Clustering
Clustering
.. automodule:: networkx.algorithms.cluster
.. autosummary::
:toctree: generated/
triangles
all_triangles
transitivity
clustering
average_clustering
square_clustering
generalized_degree
---
Doc/Reference/Algorithms/Coloring
.. _networkx.algorithms.coloring.greedy_coloring:
.. _networkx.algorithms.coloring.equitable_coloring:
Coloring
.. automodule:: networkx.algorithms.coloring
.. autosummary::
:toctree: generated/
greedy_color
equitable_color
Some node ordering strategies are provided for use with :func:greedy_color`.
.. autosummary::
:toctree: generated/
strategy_connected_sequential
strategy_connected_sequential_dfs
strategy_connected_sequential_bfs
strategy_independent_set
strategy_largest_first
strategy_random_sequential
strategy_saturation_largest_first
strategy_smallest_last
---
Doc/Reference/Algorithms/Communicability Alg
*
Communicability
*
.. automodule:: networkx.algorithms.communicability_alg
.. autosummary::
:toctree: generated/
communicability
communicability_exp
---
Doc/Reference/Algorithms/Community
*
Communities
*
.. automodule:: networkx.algorithms.community
.. currentmodule:: networkx
Bipartitions
------------
.. automodule:: networkx.algorithms.community.bipartitions
.. autosummary::
:toctree: generated/
kernighan_lin_bisection
spectral_modularity_bipartition
greedy_node_swap_bipartition
Divisive Communities
--------------------
.. automodule:: networkx.algorithms.community.divisive
.. autosummary::
:toctree: generated/
edge_betweenness_partition
edge_current_flow_betweenness_partition
K-Clique
--------
.. automodule:: networkx.algorithms.community.kclique
.. autosummary::
:toctree: generated/
k_clique_communities
Modularity-based communities
----------------------------
.. automodule:: networkx.algorithms.community.modularity_max
.. autosummary::
:toctree: generated/
greedy_modularity_communities
naive_greedy_modularity_communities
Tree partitioning
-----------------
.. automodule:: networkx.algorithms.community.lukes
.. autosummary::
:toctree: generated/
lukes_partitioning
Label propagation
-----------------
.. automodule:: networkx.algorithms.community.label_propagation
.. autosummary::
:toctree: generated/
asyn_lpa_communities
label_propagation_communities
fast_label_propagation_communities
Local Community Detection
-------------------------
.. automodule:: networkx.algorithms.community.local
.. autosummary::
:toctree: generated/
greedy_source_expansion
Louvain Community Detection
---------------------------
.. automodule:: networkx.algorithms.community.louvain
.. autosummary::
:toctree: generated/
louvain_communities
louvain_partitions
Leiden Community Detection
---------------------------
.. automodule:: networkx.algorithms.community.leiden
.. autosummary::
:toctree: generated/
leiden_communities
leiden_partitions
Fluid Communities
-----------------
.. automodule:: networkx.algorithms.community.asyn_fluid
.. autosummary::
:toctree: generated/
asyn_fluidc
Measuring partitions
--------------------
.. automodule:: networkx.algorithms.community.quality
.. autosummary::
:toctree: generated/
modularity
overlapping_modularity
constant_potts_model
partition_quality
Partitions via centrality measures
----------------------------------
.. automodule:: networkx.algorithms.community.centrality
.. autosummary::
:toctree: generated/
girvan_newman
Validating partitions
---------------------
.. automodule:: networkx.algorithms.community.community_utils
.. autosummary::
:toctree: generated/
is_partition
is_cover
---
Doc/Reference/Algorithms/Component
Components
.. automodule:: networkx.algorithms.components
.. _networkx.algorithms.components.connected:
Connectivity
------------
.. autosummary::
:toctree: generated/
is_connected
number_connected_components
connected_components
node_connected_component
.. _networkx.algorithms.components.strongly_connected:
Strong connectivity
-------------------
.. autosummary::
:toctree: generated/
is_strongly_connected
number_strongly_connected_components
strongly_connected_components
kosaraju_strongly_connected_components
condensation
.. _networkx.algorithms.components.weakly_connected:
Weak connectivity
-----------------
.. autosummary::
:toctree: generated/
is_weakly_connected
number_weakly_connected_components
weakly_connected_components
.. _networkx.algorithms.components.attracting:
Attracting components
---------------------
.. autosummary::
:toctree: generated/
is_attracting_component
number_attracting_components
attracting_components
.. _networkx.algorithms.components.biconnected:
Biconnected components
----------------------
.. autosummary::
:toctree: generated/
is_biconnected
biconnected_components
biconnected_component_edges
articulation_points
.. _networkx.algorithms.components.semiconnected:
Semiconnectedness
-----------------
.. autosummary::
:toctree: generated/
is_semiconnected
---
Doc/Reference/Algorithms/Connectivity
Connectivity
.. automodule:: networkx.algorithms.connectivity
Edge-augmentation
-----------------
.. automodule:: networkx.algorithms.connectivity.edge_augmentation
.. autosummary::
:toctree: generated/
k_edge_augmentation
is_k_edge_connected
is_locally_k_edge_connected
K-edge-components
-----------------
.. automodule:: networkx.algorithms.connectivity.edge_kcomponents
.. autosummary::
:toctree: generated/
k_edge_components
k_edge_subgraphs
bridge_components
EdgeComponentAuxGraph
K-node-components
-----------------
.. automodule:: networkx.algorithms.connectivity.kcomponents
.. autosummary::
:toctree: generated/
k_components
K-node-cutsets
--------------
.. automodule:: networkx.algorithms.connectivity.kcutsets
.. autosummary::
:toctree: generated/
all_node_cuts
Flow-based disjoint paths
-------------------------
.. automodule:: networkx.algorithms.connectivity.disjoint_paths
.. autosummary::
:toctree: generated/
edge_disjoint_paths
node_disjoint_paths
Flow-based Connectivity
-----------------------
.. automodule:: networkx.algorithms.connectivity.connectivity
.. autosummary::
:toctree: generated/
average_node_connectivity
all_pairs_node_connectivity
edge_connectivity
local_edge_connectivity
local_node_connectivity
node_connectivity
Flow-based Minimum Cuts
-----------------------
.. automodule:: networkx.algorithms.connectivity.cuts
.. autosummary::
:toctree: generated/
minimum_edge_cut
minimum_node_cut
minimum_st_edge_cut
minimum_st_node_cut
Stoer-Wagner minimum cut
------------------------
.. automodule:: networkx.algorithms.connectivity.stoerwagner
.. autosummary::
:toctree: generated/
stoer_wagner
Utils for flow-based connectivity
---------------------------------
.. automodule:: networkx.algorithms.connectivity.utils
.. autosummary::
:toctree: generated/
build_auxiliary_edge_connectivity
build_auxiliary_node_connectivity
---
Doc/Reference/Algorithms/Core
*
Cores
*
.. automodule:: networkx.algorithms.core
.. autosummary::
:toctree: generated/
core_number
k_core
k_shell
k_crust
k_corona
k_truss
onion_layers
---
Doc/Reference/Algorithms/Covering
Covering
.. automodule:: networkx.algorithms.covering
.. autosummary::
:toctree: generated/
min_edge_cover
is_edge_cover
---
Doc/Reference/Algorithms/Cuts
Cuts
.. automodule:: networkx.algorithms.cuts
.. autosummary::
:toctree: generated/
boundary_expansion
conductance
cut_size
edge_expansion
mixing_expansion
node_expansion
normalized_cut_size
volume
---
Doc/Reference/Algorithms/Cycles
Cycles
.. automodule:: networkx.algorithms.cycles
.. autosummary::
:toctree: generated/
cycle_basis
simple_cycles
recursive_simple_cycles
find_cycle
minimum_cycle_basis
chordless_cycles
girth
---
Doc/Reference/Algorithms/D Separation
============
D-Separation
============
.. automodule:: networkx.algorithms.d_separation
.. autosummary::
:toctree: generated/
is_d_separator
is_minimal_d_separator
find_minimal_d_separator
---
Doc/Reference/Algorithms/Dag
*
Directed Acyclic Graphs
*
.. automodule:: networkx.algorithms.dag
.. autosummary::
:toctree: generated/
ancestors
antichain_width
descendants
topological_sort
topological_generations
all_topological_sorts
lexicographical_topological_sort
is_directed_acyclic_graph
is_aperiodic
transitive_closure
transitive_closure_dag
transitive_reduction
antichains
dag_longest_path
dag_longest_path_length
dag_to_branching
colliders
v_structures
---
Doc/Reference/Algorithms/Distance Measures
*
Distance Measures
*
.. automodule:: networkx.algorithms.distance_measures
.. autosummary::
:toctree: generated/
center
centroid
diameter
harmonic_diameter
eccentricity
effective_graph_resistance
kemeny_constant
periphery
radius
resistance_distance
---
Doc/Reference/Algorithms/Distance Regular
*
Distance-Regular Graphs
*
.. automodule:: networkx.algorithms.distance_regular
.. autosummary::
:toctree: generated/
is_distance_regular
is_strongly_regular
intersection_array
global_parameters
---
Doc/Reference/Algorithms/Dominance
*
Dominance
*
.. automodule:: networkx.algorithms.dominance
.. autosummary::
:toctree: generated/
immediate_dominators
dominance_frontiers
---
Doc/Reference/Algorithms/Dominating
*
Dominating Sets
*
.. automodule:: networkx.algorithms.dominating
.. autosummary::
:toctree: generated/
dominating_set
is_dominating_set
---
Doc/Reference/Algorithms/Efficiency Measures
Efficiency
.. automodule:: networkx.algorithms.efficiency_measures
.. autosummary::
:toctree: generated/
efficiency
local_efficiency
global_efficiency
---
Doc/Reference/Algorithms/Euler
Eulerian
.. automodule:: networkx.algorithms.euler
.. autosummary::
:toctree: generated/
is_eulerian
eulerian_circuit
eulerize
is_semieulerian
has_eulerian_path
eulerian_path
---
Doc/Reference/Algorithms/Flow
*
Flows
*
.. automodule:: networkx.algorithms.flow
.. _networkx.algorithms.flow.maxflow:
Maximum Flow
------------
.. autosummary::
:toctree: generated/
maximum_flow
maximum_flow_value
minimum_cut
minimum_cut_value
.. _networkx.algorithms.flow.edmondskarp:
Edmonds-Karp
------------
.. autosummary::
:toctree: generated/
edmonds_karp
.. _networkx.algorithms.flow.shortestaugmentingpath:
Shortest Augmenting Path
------------------------
.. autosummary::
:toctree: generated/
shortest_augmenting_path
.. _networkx.algorithms.flow.preflowpush:
Preflow-Push
------------
.. autosummary::
:toctree: generated/
preflow_push
.. _networkx.algorithms.flow.dinitz_alg:
Dinitz
------
.. autosummary::
:toctree: generated/
dinitz
.. _networkx.algorithms.flow.boykovkolmogorov:
Boykov-Kolmogorov
-----------------
.. autosummary::
:toctree: generated/
boykov_kolmogorov
.. _networkx.algorithms.flow.gomory_hu:
Gomory-Hu Tree
--------------
.. autosummary::
:toctree: generated/
gomory_hu_tree
.. _networkx.algorithms.flow.utils:
Utils
-----
.. autosummary::
:toctree: generated/
build_residual_network
.. _networkx.algorithms.flow.mincost:
.. _networkx.algorithms.flow.networksimplex:
Network Simplex
---------------
.. autosummary::
:toctree: generated/
network_simplex
min_cost_flow_cost
min_cost_flow
cost_of_flow
max_flow_min_cost
.. _networkx.algorithms.flow.capacityscaling:
Capacity Scaling Minimum Cost Flow
----------------------------------
.. autosummary::
:toctree: generated/
capacity_scaling
---
Doc/Reference/Algorithms/Graph Hashing
*
Graph Hashing
*
.. automodule:: networkx.algorithms.graph_hashing
.. autosummary::
:toctree: generated/
weisfeiler_lehman_graph_hash
weisfeiler_lehman_subgraph_hashes
---
Doc/Reference/Algorithms/Graphical
*
Graphical degree sequence
*
.. automodule:: networkx.algorithms.graphical
.. autosummary::
:toctree: generated/
is_graphical
is_digraphical
is_multigraphical
is_pseudographical
is_valid_degree_sequence_havel_hakimi
is_valid_degree_sequence_erdos_gallai
---
Doc/Reference/Algorithms/Hierarchy
*
Hierarchy
*
.. automodule:: networkx.algorithms.hierarchy
.. autosummary::
:toctree: generated/
flow_hierarchy
---
Doc/Reference/Algorithms/Hybrid
Hybrid
.. automodule:: networkx.algorithms.hybrid
.. autosummary::
:toctree: generated/
kl_connected_subgraph
is_kl_connected
---
Doc/Reference/Algorithms/Index
.. _algorithms:
Algorithms
.. currentmodule:: networkx
.. toctree::
:maxdepth: 2
approximation
assortativity
asteroidal
bipartite
boundary
bridges
broadcasting
centrality
chains
chordal
clique
clustering
coloring
communicability_alg
community
component
connectivity
core
covering
cycles
cuts
d_separation
dag
distance_measures
distance_regular
dominance
dominating
efficiency_measures
euler
flow
graph_hashing
graphical
hierarchy
hybrid
isolates
isomorphism
link_analysis
link_prediction
lowest_common_ancestors
matching
minors
mis
non_randomness
moral
node_classification
operators
perfect_graph
planarity
planar_drawing
polynomials
reciprocity
regular
rich_club
shortest_paths
similarity
simple_paths
smallworld
smetric
sparsifiers
structuralholes
summarization
swap
threshold
time_dependent
tournament
traversal
tree
triads
vitality
voronoi
walks
wiener
---
Doc/Reference/Algorithms/Isolates
Isolates
.. automodule:: networkx.algorithms.isolate
.. autosummary::
:toctree: generated/
is_isolate
isolates
number_of_isolates
---
Doc/Reference/Algorithms/Isomorphism.Ismags
.. _ismags:
.. automodule:: networkx.algorithms.isomorphism.ismags
ISMAGS object
-------------
.. currentmodule:: networkx.algorithms.isomorphism
.. autosummary::
:toctree: generated/
ISMAGS
---
Doc/Reference/Algorithms/Isomorphism
.. _isomorphism:
.. _networkx.algorithms.isomorphism.isomorph:
*
Isomorphism
*
.. automodule:: networkx.algorithms.isomorphism
.. autosummary::
:toctree: generated/
is_isomorphic
could_be_isomorphic
fast_could_be_isomorphic
faster_could_be_isomorphic
VF2++
-----
.. automodule:: networkx.algorithms.isomorphism.vf2pp
.. autosummary::
:toctree: generated/
vf2pp_is_isomorphic
vf2pp_all_isomorphisms
vf2pp_isomorphism
Tree Isomorphism
-----------------
.. automodule:: networkx.algorithms.isomorphism.tree_isomorphism
.. autosummary::
:toctree: generated/
rooted_tree_isomorphism
tree_isomorphism
Advanced Interfaces
-------------------
.. toctree::
:maxdepth: 2
isomorphism.vf2
isomorphism.ismags
---