Skip to main content
`Ctrl`+`K`

# 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. `Graph`, `DiGraph`, `MultiGraph`, etc.) expose the node and edge data of the graph via `nodes()` and `edges()`, which return dict view objects, `NodeView` (or `NodeDataView`) and `EdgeView` (or `EdgeDataView`), respectively. The node and edge `View` classes have dict-like semantics for item access, returning the data dict corresponding to a given node or edge. This NXEP proposes adding support for slicing to the relevant node & edge `View` 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 `nodes()` and `edges()` when using NetworkX interactively, e.g. in a terminal. If a graph has very many components (i.e. edges or nodes) then the `repr` of `View` 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 `G.nodes[0:5]` 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 synonyms `G.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 networkx/networkx#4086

Alternatively, to get rid of the ambiguity in slicing API with respect to the dict views we can implement a new `slice` 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.

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 Node(Data)View and Edge(Data)View and returning a list of the sliced values. For example, the `__getitem__` method for `NodeView` might look something like:

    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 `View` 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

- networkx/networkx#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` backgrounds and have been adopted by other popular libraries like `pandas`. 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()` would give the set of source nodes in a directed graph, instead of the last `n` edges.

Option 3 (add sequence semantics to `View` objects) is arguably the most convenient as it doesn’t involve raising any error messages. However, overriding the behavior of `*View.__getitem__` to mix Mapping and 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 `dict_keys` and `dict_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 networkx/networkx#4300 and networkx/networkx#4304.