networkx / nx-guides

Examples and IPython Notebooks about NetworkX

NetworkX

NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.

• Website (including documentation): https://networkx.org
• Mailing list: https://groups.google.com/forum/#!forum/networkx-discuss
• Source: https://github.com/networkx/networkx
• Bug reports: https://github.com/networkx/networkx/issues
• Report a security vulnerability: https://tidelift.com/security
• Tutorial: https://networkx.org/documentation/latest/tutorial.html
• GitHub Discussions: https://github.com/networkx/networkx/discussions

Simple example

Find the shortest path between two nodes in an undirected graph:

>>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_edge("A", "B", weight=4)
>>> G.add_edge("B", "D", weight=2)
>>> G.add_edge("A", "C", weight=3)
>>> G.add_edge("C", "D", weight=4)
>>> nx.shortest_path(G, "A", "D", weight="weight")
['A', 'B', 'D']

Install

Install the latest version of NetworkX:

$ pip install networkx

Install with all optional dependencies:

$ pip install networkx[all]

For additional details, please see INSTALL.rst.

Bugs

Please report any bugs that you find here. Or, even better, fork the repository on GitHub and create a pull request (PR). We welcome all changes, big or small, and we will help you make the PR if you are new to git (just ask on the issue and/or see CONTRIBUTING.rst).

License

Released under the 3-Clause BSD license (see LICENSE.txt):

Copyright (C) 2004-2024 NetworkX Developers
Aric Hagberg <[email protected]>
Dan Schult <[email protected]>
Pieter Swart <[email protected]>

nx-guides's Issues

Revert to latest scipy release once 1.8 is released

To make the CI happy I am using the RC version, it should be reverted back to just "scipy" in requirements.txt

Notebook for shortest paths and simple paths

I plan to create a notebook explaining and comparing the various Shortest path and Simple path methods, based on the discussion over here.

The notebook will focus on comparison of functionality of available methods over implementation.

For shortest path methods, I want to focus only on unweighted graphs, else the notebook might become big and hard to understand.

Notebook on Graph Matching

I've started working on a notebook about the Graph Matching algorithm and have been using the following Wikipedia pages as references:

Matching
Blossom Algorithm

It is still very much in progress. Am I going in the right direction ?

Notebook to Study Centrality Measures

I am working on a notebook "Studying Protein-Protein Interaction Network using Centrality Measures" where I demonstrate the use of Centrality Measures provided by NetworkX library on the STRING Dataset. You can find the notebook here. I have interpreted the results given by the function calls as well. This is definitely a work in progress and I am still learning from various resources and applying them as I learn.
Just wanted a heads-up on whether this would be a good addition to NX-Guides or not? I have mentioned similar notebooks in my GSOC Proposal too. Would like to work on this as I find it very interesting.

Notebook for Minimum Spanning Tree Algorithms

In NetworkX, MSTs are generated via 3 different algorithms:

1. Kruskals Algorithm
2. Prims Algorithm
3. Boruvka Algorithm

I aim to create a notebook explaining how each algorithm works in NetworkX while making it as simple and understandable as possible.

Notebook on Euler algorithms

I am planning to create a notebook on the following methods of NetworkX:

• is_eulerian
• eulerian_circuit
• is_semieulerian
• has_eulerian_path
• eulerian_path

Since the methods are very related to each other, I believe that having them all in one notebook would not be a problem. Please let me know if you prefer otherwise. @MridulS

Rename the repo?

This has been discussed before, but I wanted to make something more visible so we could collect more ideas/feedback.

I think the biggest problem with the name "notebooks" is that there are many repositories with this name (in other orgs), and when you try to fork a repository and GitHub detects a name conflict, it automatically starts appending numbers to the end of the fork. This requires manual intervention to fix - and even then can get very confusing because if you look at other users' forks they may all have different names. If we were going to stick with "notebooks" generally, we could solve this problem by getting cute with the name, e.g. notebookx.

NumPy has gone with numpy-tutorials for a similar project, but networkx-tutorials isn't a great fit because "tutorial" doesn't really describe the full range of material we envision having here. IIRC some other ideas that have been mentioned:

• networkx-guides
• networkx-handbook

Improve per-page binder integration

The sphinx-book-theme has a really nice feature that maps each page with executable code to a direct binder link. However, I think we want to stick with the pydata-sphinx-theme to have thematic consistency with the main nx docs, and unfortunately the per-page launch feature doesn't quite work out of the box.

You can still access all the notebooks on binder, but it's annoying for two reasons:

1. the user has to click through from the root of the repository to the notebook they want and
2. The user has to right-click and select "open as notebook" on binder.

We definitely want the original behavior from the sphinx-book-theme - I think there are two ways we could potentially get it back:

1. Jinja templates + macros for URL remapping
2. upstreaming the functionality from sphinx-book-theme either to the pydata theme, to myst-nb, or pulling it out as a separate sphinx extension. See executablebooks/sphinx-book-theme#326

Add a CONTRIBUTING.md to nx-guides

Mirror it with what we do in networkx/networkx

Progress Notes for Topological Sort Notebook

Related to: #44.

Meeting Notes Friday, 16 July 2021

• @vdshk has the idea to include DFS as an algorithm for doing toposort, but we think it can be left for a later PR.
• Planning for future "chunks" of work: one h3 section at a time would be a good chunk to work on per week.
• @rossbar proposed kickstarting the graph colouring notebook so that @vdshk is not blocked on reviews for toposort.

Action Items

• @ericmjl will review the PR #44 notebook by Saturday 17 July 2021, then ping @vdshk
• @vdshk will open a new draft PR for a new notebook topic of choice.

Exploratory network data science notebooks.

Notebooks which uses different network science techniques and algorithms to explore and analyse real world datasets.

Notebook for graph traversal algorithms

I wish to create a notebook explaining the various graph traversal algorithms discussed here

Let me know if I have the green light! @MridulS @rossbar

Notebooks at the interface of GIS and Networks

We have a lot of users of NetworkX, who use networks in the field of geographical information systems.
We already have some examples in our gallery.

It would be nice to get some new material showing the use cases of networkx with GIS tools.

This is an open call! Feel free to propose a notebook :)

Numpy deprecation function numpy.int

Hi there, I'm getting this error message when I try to use NetworkX:

/usr/local/lib/python3.10/dist-packages/networkx/init.py in
113 from networkx.generators import *
114
--> 115 import networkx.readwrite
116 from networkx.readwrite import *
117

/usr/local/lib/python3.10/dist-packages/networkx/readwrite/init.py in
13 from networkx.readwrite.nx_yaml import *
14 from networkx.readwrite.gml import *
---> 15 from networkx.readwrite.graphml import *
16 from networkx.readwrite.gexf import *
17 from networkx.readwrite.nx_shp import *

/usr/local/lib/python3.10/dist-packages/networkx/readwrite/graphml.py in
312
313
--> 314 class GraphML(object):
315 NS_GRAPHML = "http://graphml.graphdrawing.org/xmlns"
316 NS_XSI = "http://www.w3.org/2001/XMLSchema-instance"

/usr/local/lib/python3.10/dist-packages/networkx/readwrite/graphml.py in GraphML()
344 types = [(np.float64, "float"), (np.float32, "float"),
345 (np.float16, "float"), (np.float_, "float"),
--> 346 (np.int, "int"), (np.int8, "int"),
347 (np.int16, "int"), (np.int32, "int"),
348 (np.int64, "int"), (np.uint8, "int"),

/usr/local/lib/python3.10/dist-packages/numpy/init.py in getattr(attr)
317
318 if attr in former_attrs:
--> 319 raise AttributeError(former_attrs[attr])
320
321 if attr == 'testing':
AttributeError: module 'numpy' has no attribute 'int'.

Its seems that the class function is using (or including) "np.int", which has been deprecated.

I tried to downgrade Numpy, but other libraries show conflicts with earlier Numpy versions.

Can anyone help me to fix it? please.

Notebook for Connected Components Algorithm

Currently NetworkX provides various Algorithms to find connected connected components in graph. The functions for this are based on:

1. BFS based Algorithms
2. Kosaraju’s algorithm (strongly connected components)
3. Tarjan’s algorithm (strongly connected components)

I aim to create a notebook that will delve deeper into each of these algorithms and showcase how the connected components functions work in NetworkX.

Missing repository license

There is no license file in this repository. I could create one if you could specify the license type.

Issue on page /content/algorithms/dag/index.html

I came across 2 problems on the page:

1. In this line in 'Step 3':

We process all the vertices of the current level in variable this_generation and we store the next level in variable zero_degree.

'zero_degree' should instead be 'zero_indegree'.

2. The 'Suggest edit' link does not work on the page https://networkx.org/nx-guides/content/algorithms/dag/index.html
   It leads to the following:
   

Notebook for Minimum Spanning Tree Algorithms

In NetworkX, MSTs are generated via 3 different algorithms:

1. Kruskals Algorithm
2. Prims Algorithm
3. Boruvka Algorithm

I aim to create a notebook explaining how each algorithm works in NetworkX while making it as simple and understandable as possible.

Linting and formatting notebooks

There have been some previous discussions on how best to handle tasks like linting and formatting the notebooks. For example - we'd like to have the code cells formatted (e.g. via black) and have the markdown cells respect line character limits. Ultimately, I think we'd like to be able to incorporate automated linting/formatting to the workflow so that authors don't have to think about it at all. This issue is for starting the discussion on how best to do that.

These topics have been discussed in other communities as well, most notably in mwouts/jupytext#432. There are some really nice ideas there. Fortunately, it looks like jupytext has built-in support for applying black to code cells. In our case (with .md-formatted notebooks) this would look like:

jupytext notebook.md --pipe black

I've tried this out a bit and it seems pretty robust - I think we could incorporate this into the workflow (maybe via pre-commit + a "style" CI job, similar to how NetworkX does it) relatively easily.

Formatting the non-code-cell markdown is a bit trickier. There is a suggestion from that same jupytext issue (mwouts/jupytext#432 (comment)) to try pandoc which has support for softbreaks (i.e. line breaks in source files) and automatically applies this formatting:

jupytext notebook.md --pipe-fmt ipynb --pipe 'pandoc --from ipynb --to ipynb --atx-headers'

This kind of works, but doesn't inherently support/recognize all the features of MyST markdown. For example, when I tried this on one of our notebooks, it dropped the footnotes. This seems like a reasonable approach, but it's not suitable (in the current state) for incorporation into an automated workflow.

Notebook to study Betweenness Centrality of a graph

I am extremely interested in studying the algorithm behind calculating the betweenness centrality in graphs. It's widely used and a notebook explaining it would be beneficial to any person who aims to use the function.
The current algorithm is referred from -

• Ulrik Brandes: A Faster Algorithm for Betweenness Centrality.
  Journal of Mathematical Sociology 25(2):163-177, 2001.
  https://doi.org/10.1080/0022250X.2001.9990249

draw_networkx_edge_labels does not work for multidigraph

The dictionary returned by nx.get_edge_attributes has the structure (source, dest, enum):attr, where the third field just enumerates the occurrences of each edge. This third field is necessary because keys have to be unique in the dictionary. However this will imply that it cannot be used in nx.draw_networkx_edge_labels, because it expects a (source, dest):attr structured dict.

Any plan to fix this bug

How do I share my ipynb file?

@MridulS I have created a documentation in jupyter notebook regarding Basic functions of Bipartite graphs and I want to share it with you so you can check and approve or give me feedback on how to improve and what to add so it can be documented. Please, guide me on How can I share it with you?

BUG: Logo is not showing up properly

Logo transparency is annoyingly invisible, I noticed it when I linked the same logo for the jupyterbook gallery.
I suspect you may have checked on the rendering in dark mode.

Notebook on Planarity

i am working on a planarity guide and would appreciate anything I would like to know about it

Minor error in edge indexes printing

Hi,
I think there is a somewhat minor error in the entry [39].
The printed indexes are those of the previous cell, if I understood correctly.

This piece of code:

for (u, v, d) in FG.edges(data='weight'):
    if d < 0.5:
        print('(%d, %d, %.3f)'%(n, nbr, d))

should be:

for (u, v, d) in FG.edges(data='weight'):
    if d < 0.5:
        print('(%d, %d, %.3f)'%(u, v, d))

Thanks for the great tutorial.

Gautier

What to do with the tutorial in nx-guides

Currently there is a tutorial.md which is a (potentially out-of-date), notebook-ified copy of the networkx tutorial from the main documentation. Maintaining two versions of the same content has obvious downsides. Some ideas:

1. Add a binder link to the tutorial in the main documentation and remove the version here (the version in the main documentation already has a "download as notebook" link)
2. Remove the tutorial from the main documentation and instead point to the version here from the main documentation.
3. Update the tutorial in this repository so that it's not just repeated content. For example, NumPy has a Quickstart Tutorial which serves as a quick reference to introduce syntax to new users, and an absolute beginner's tutorial which reads more like an article and has more text to explain basic concepts etc.

Other ideas?

My personal preference is a combination of 1) and 3) - remove the tutorial.md from this repo for now to get rid of duplicated content, and in the longer term aim to add a "networkx for beginners" tutorial that provides more high-level background than the tutorial in the main docs.

Use full extended MyST syntax in notebooks?

The myst-nb extension is used to provide support for the text-based notebook format. It also supports the MyST markdown flavor which adds additional functionality beyond what is available from commonmark markdown. One of the main features is support for sphinx roles and directives. This is a very nice feature, especially for integrating with other documentation - for example, you can use intersphinx to create cross-project references (e.g. between the notebooks and the main networkx docs).

However, the problem that arises from using extended MyST syntax is that it is not supported in jupyter notebook itself. In other words, the roles and directives only work for .html and .pdf outputs. For users running tutorials either with a local jupyter notebook instance or on some cloud service like binder, the extended syntax will not render properly. To illustrate, I've created #31 which sets up intersphinx and uses it to reference a module in the main networkx documentation. If you view the static site in the build artifact, the link renders just fine. However, if you instead view things in Jupyter notebook (e.g. juypter notebook content/generators/geometric.md), the link will not be rendered.

So the question is: do we use the full MyST syntax now, reap the nice benefits for the generated site and deal with having some warts when the tutorials are opened in jupyter notebook, or do we limit ourselves to commonmark markdown so that all markdown elements render correctly in both html and notebook? I tend to lean towards the former, which will help integrate the notebooks content w/ the main documentation & especially since some of the things we hope to do with this repo (e.g. explanations of algorithms/graph concepts) would benefit greatly from extended support for math markup, e.g. proofs, theorems, lemma, etc..

FWIW it seems there is interest in adding support for MyST to Jupyter itself (xref jupyterlab/jupyterlab#272, jupyter discussion forum post, executablebooks/meta#184, executablebooks/jupyter-book#1094, executablebooks/MyST-NB#210), but I wasn't able to find any info on a potential timeline for adoption.

notes on threshold graphs

i am working on the threshold graph guide I kindly request if any suggestions.
link: https://github.com/akshayamadhuri/nx-guides/new/main/content/algorithms

Notebook for Shortest Path Algorithms

I wish to create a Notebook explaining the following algorithms on weighted graphs as linked Here

1. Floyd- Warshall Algorithm
2. Bellman- Ford Algorithm
3. Dijkstra's Algorithm
4. A* Algorithm

Steps that I would be following for the notebook if given the opportunity:

1. Brief History and Introduction of Algorithms
2. Example and In depth explanation of each function with code
3. Real-life Application to transport routes for better understanding
4. Conclusion

Resources I plan on using:-

1. Dataset from :-https://snap.stanford.edu/data/index.html
2. Books :-

• Graph Theory with Applications to Engineering and Computer Science by Narsingh Deo
• Introduction to Graph Theory by Douglas B West

3. Research Papers

• https://iopscience.iop.org/article/10.1088/1742-6596/1217/1/012116/meta
• https://iopscience.iop.org/article/10.1088/1742-6596/1217/1/012116/pdf
  I shall also be referring to various articles and more papers which I will document later in references.

Why trust me for making this notebook?

I have experience in writing efficient code with in-depth documentation. I have written several tutorial jupyter notebooks as a few examples here:-

1. https://www.kaggle.com/code/mvanshika/diabetes-prediction
2. https://github.com/vanshika230/Machine-Learning

Please suggest any improvements required and review this request. @MridulS @rossbar .Thankyou for your time and consideration.

Viewing w/out using binder

Binder is super slow and annoying. Is it possible to see a static version of these guides w/out having to wait for binder to launch? I keep trying to view this, but I don't have the patience to wait on binder.

Issue on page /content/exploratory_notebooks/facebook_notebook.html

Your issue content here.

Issue on page /content/exploratory_notebooks/facebook_notebook.html

js-global-screen-reader-notice

Notebook on Coloring Algorithms

I plan on creating a notebook that explains:

• Greedy Color - It will show all strategies for node ordering
• Equitable Color

Notebook on lowest common ancestor algorithm

Hello,

I want to create an explanatory notebook on lowest common ancestor algorithm. If it is okay for you, I will start working on it.

Pedagogical notebooks to explain algorithms in networkx

Notebooks which explain algorithms implemented in networkx will be a great addition to this repository.