GSoC 2015 project ideas

NetworkX 2.0 API

In NetworkX 2.0, we plan to modernize the interfaces provided by graph objects.

Currently, NetworkX graph objects provide a variety of interfaces, with a high degree of redundancy, for accessing graph data. For example, to obtain the neighbors of a node, we have G[u] and G.neighbors(u); to obtain the edges incident to a node, we have G.edges([u]) and G.adjacency(u). And let's not forget that the neighbors/edges/adjacency have _iter-suffixed versions which return generators instead of lists. Such redundancy runs against the "one – and preferably only one – obvious way to do it" doctrine from "The Zen of Python". As we move to a new major version number, in NetworkX 2.0, we wish to review and clean up the existing design and offer a modernized API.

We have three tentative project deliverables:

1. [Difficulty: Easy] Rename the _iter-suffixed functions over their unsuffixed counterparts;
2. [Difficulty: Hard] Investigate and implement a generic interface for accessing graph data;
3. [Difficulty: Intermediate] Use the opportunity presented by a reorganization to implement efficient code for Python 2&3.

The first item is straightforward to understand. We will remove the functions returning lists. This will make the _iter suffixes redundant, and hence we will remove those as well. This is an intentionally backward-incompatible change. We need to worry about only implementation, documentation and unit tests.

The second item was summarized by @dschult in #1246 and partially implemented in #1336. We would like to continue the investigation. Potentially, this can become a clear unified interface that provides graph info in each way the users want it without confusing duplication.

The third item is best achieved at the same time as 1.) and 2.). NetworkX uses Python 3 syntax for iterating. That includes the use of range and accessing values of dictionaries. Efficiency could be improved for Python 2 with the use of the future package. This package offers range as an alias for xrange in Python 2 and functions to efficiently iterate over dictionaries.

Add-on system for NetworkX

Up till now and in the foreseeable future, NetworkX has been and remains committed to being a pure Python library. This lowers the bar for getting started with NetworkX as all one needs is a Python interpreter – a C/C++ compiler is not required. Meanwhile, we nonetheless recognize that there are many existing graph packages written in other programming languages such as Boost.Graph, LEMON and METIS. These libraries offer rich functionalities whose reimplementation in Python is a nontrivial undertaking. Some achieve greater performance than their equivalents in NetworkX due to their use of compiled languages. Therefore, we wish to somehow integrate them into NetworkX.

This gives rise to the desire for an add-on system for injecting optional components into NetworkX. We intend the add-on system to serve two purposes: 1) enabling modules based on C extensions (e.g., #1167); 2) separating out nonessential modules relying on third-party libraries other than NumPy and SciPy (e.g., #1325). Through GSoC, we hope to achieve the following goals:

1. [Difficulty: Intermediate] Design and implement an add-on system.
2. [Difficulty: Easy] Create at least two officially sanctioned add-ons and host them on GitHub.

Adjacency matrix based add-on

In #1076, @Midnighter proposed that we investigate using sparse and dense matrices to store graph data. This project has two aspects: First, the adjacency matrix based graph classes should be designed to conform with the new 2.0 API and could thus represent a drop-in for the dictionary-based graph classes. Second, this add-on should re-implement some of the functions in networkx but replace their logic with linear algebra where possible. This is aided by the availability of code in scipy and APGL.

1. [Difficulty: Hard] Design and implement a dense and sparse matrix graph class.
2. [Difficulty: Hard] Provide NetworkX functionality using linear algebra.

Alternative backends for storing graph data

Since inception, NetworkX has used Python dictionaries to store graph data. Node data are stored in the G.node nested dictionary, keyed first by the node and then by the data key. Edge data are likewise stored in another nested dictionary. On the other hand, depending on the exact design of the generic accessor interface in the NetworkX 2.0 API, we may be able to use an SQL database (e.g., SQLite) to store graph data. During GSoC, we hope to investigate the possibilities and implement at least one of them.