Nrthugu

What is the time complexity of getting the neighbors of a node in networkx?

>>> G = nx.Graph()

>>> G.add_edges_from([('a', 'b'), ('a', 'c')])

>>> G.neighbors('a')

Short answer: obtaining the neighbors takes linear time O(m) (with m the number neighbors, or in unlikely scenarios O(m+n) with n the number of nodes). Adding edges to the network will normally take linear time as well O(n) in the number of edges that you add, so constant for a single edge, but in a (very) unlikely scenario could take quadratic time O(n²). You can access the dictionary of neighbors in constant time (well in a worst case scenario linear time) with `G['a'].

We can inspect the source code, and see:

def neighbors(self, n):

    # ...

    try:

        return list(self.adj[n])

    except KeyError:

        raise NetworkXError("The node %s is not in the graph." % (n,))

Now if inspect the source code, we see that (by default) adj is a dictionary, indeed:

node_dict_factory = dict

adjlist_dict_factory = dict

edge_attr_dict_factory = dict



def __init__(self, data=None, **attr):

    # ...

    self.node_dict_factory = ndf = self.node_dict_factory

    # ...

    self.node = ndf()  # empty node attribute dict

    # ...

So even if the dictionary lookup takes - worst case, but very unlikely - linear time O(n) in the number of nodes, then we only have another linear time to convert the list of keys into a list.

The add_edges_from method on the other hand is implemented as:

def add_edges_from(self, ebunch, attr_dict=None, **attr):

    # ...

    for e in ebunch:

        ne = len(e)

        if ne == 3:

            u, v, dd = e

        elif ne == 2:

            u, v = e

            dd = {}  # doesnt need edge_attr_dict_factory

        else:

            raise NetworkXError(

                "Edge tuple %s must be a 2-tuple or 3-tuple." % (e,))

        if u not in self.node:

            self.adj[u] = self.adjlist_dict_factory()

            self.node[u] = {}

        if v not in self.node:

            self.adj[v] = self.adjlist_dict_factory()

            self.node[v] = {}

        datadict = self.adj[u].get(v, self.edge_attr_dict_factory())

        datadict.update(attr_dict)

        datadict.update(dd)

        self.adj[u][v] = datadict

        self.adj[v][u] = datadict

So we basically iterate over every item in the list, do some unpacking, and then add the data dictionary twice to the adj (once in one direction, once in the other). If the dictionary lookup is fast (usually it is constant time), then this algorithm has linear time (in the number of tuples to add). Worst case (but very unlikely) dictionary lookups can take linear time, so then inserting can scale up to O(n²).

The Graph class however allows access to the subdictionary with G['a']:

>>> G['a']

AtlasView({'b': {}, 'c': {}})

The AtlasView is a view over the dictionary to prevent one from editing the underlying dictionary.