Question about Drawing a graph with networkx

Question

I am using NetworkX for drawing graph, when I searching in NetworkX documentation I saw a code from Antigraph class that was confusing and I can't understand some line of this code. Help me for understanding this code, please.

I attached this code:

import networkx as nx
from networkx.exception import NetworkXError
import matplotlib.pyplot as plt


class AntiGraph(nx.Graph):
    """
    Class for complement graphs.

    The main goal is to be able to work with big and dense graphs with
    a low memory footprint.

    In this class you add the edges that *do not exist* in the dense graph,
    the report methods of the class return the neighbors, the edges and
    the degree as if it was the dense graph. Thus it's possible to use
    an instance of this class with some of NetworkX functions.
    """

    all_edge_dict = {"weight": 1}

    def single_edge_dict(self):
        return self.all_edge_dict

    edge_attr_dict_factory = single_edge_dict

    def __getitem__(self, n):
        """Return a dict of neighbors of node n in the dense graph.

        Parameters
        ----------
        n : node
           A node in the graph.

        Returns
        -------
        adj_dict : dictionary
           The adjacency dictionary for nodes connected to n.

        """
        return {
            node: self.all_edge_dict for node in set(self.adj) - set(self.adj[n]) - {n}
        }

    def neighbors(self, n):
        """Return an iterator over all neighbors of node n in the
           dense graph.

        """
        try:
            return iter(set(self.adj) - set(self.adj[n]) - {n})
        except KeyError as e:
            raise NetworkXError(f"The node {n} is not in the graph.") from e

    def degree(self, nbunch=None, weight=None):
        """Return an iterator for (node, degree) in the dense graph.

        The node degree is the number of edges adjacent to the node.

        Parameters
        ----------
        nbunch : iterable container, optional (default=all nodes)
            A container of nodes.  The container will be iterated
            through once.

        weight : string or None, optional (default=None)
           The edge attribute that holds the numerical value used
           as a weight.  If None, then each edge has weight 1.
           The degree is the sum of the edge weights adjacent to the node.

        Returns
        -------
        nd_iter : iterator
            The iterator returns two-tuples of (node, degree).

        See Also
        --------
        degree

        Examples
        --------
        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
        >>> list(G.degree(0))  # node 0 with degree 1
        [(0, 1)]
        >>> list(G.degree([0, 1]))
        [(0, 1), (1, 2)]

        """
        if nbunch is None:
            nodes_nbrs = (
                (
                    n,
                    {
                        v: self.all_edge_dict
                        for v in set(self.adj) - set(self.adj[n]) - {n}
                    },
                )
                for n in self.nodes()
            )
        elif nbunch in self:
            nbrs = set(self.nodes()) - set(self.adj[nbunch]) - {nbunch}
            return len(nbrs)
        else:
            nodes_nbrs = (
                (
                    n,
                    {
                        v: self.all_edge_dict
                        for v in set(self.nodes()) - set(self.adj[n]) - {n}
                    },
                )
                for n in self.nbunch_iter(nbunch)
            )

        if weight is None:
            return ((n, len(nbrs)) for n, nbrs in nodes_nbrs)
        else:
            # AntiGraph is a ThinGraph so all edges have weight 1
            return (
                (n, sum((nbrs[nbr].get(weight, 1)) for nbr in nbrs))
                for n, nbrs in nodes_nbrs
            )

    def adjacency_iter(self):
        """Return an iterator of (node, adjacency set) tuples for all nodes
           in the dense graph.

        This is the fastest way to look at every edge.
        For directed graphs, only outgoing adjacencies are included.

        Returns
        -------
        adj_iter : iterator
           An iterator of (node, adjacency set) for all nodes in
           the graph.

        """
        for n in self.adj:
            yield (n, set(self.adj) - set(self.adj[n]) - {n})


# Build several pairs of graphs, a regular graph
# and the AntiGraph of it's complement, which behaves
# as if it were the original graph.
Gnp = nx.gnp_random_graph(20, 0.8, seed=42)
Anp = AntiGraph(nx.complement(Gnp))
Gd = nx.davis_southern_women_graph()
Ad = AntiGraph(nx.complement(Gd))
Gk = nx.karate_club_graph()
Ak = AntiGraph(nx.complement(Gk))
pairs = [(Gnp, Anp), (Gd, Ad), (Gk, Ak)]
# test connected components
for G, A in pairs:
    gc = [set(c) for c in nx.connected_components(G)]
    ac = [set(c) for c in nx.connected_components(A)]
    for comp in ac:
        assert comp in gc
# test biconnected components
for G, A in pairs:
    gc = [set(c) for c in nx.biconnected_components(G)]
    ac = [set(c) for c in nx.biconnected_components(A)]
    for comp in ac:
        assert comp in gc
# test degree
for G, A in pairs:
    node = list(G.nodes())[0]
    nodes = list(G.nodes())[1:4]
    assert G.degree(node) == A.degree(node)
    assert sum(d for n, d in G.degree()) == sum(d for n, d in A.degree())
    # AntiGraph is a ThinGraph, so all the weights are 1
    assert sum(d for n, d in A.degree()) == sum(d for n, d in A.degree(weight="weight"))
    assert sum(d for n, d in G.degree(nodes)) == sum(d for n, d in A.degree(nodes))

nx.draw(Gnp)
plt.show()

I can't understand in these 2 lines:

(1) for v in set(self.adj) - set(self.adj[n]) - {n}

(2) nbrs = set(self.nodes()) - set(self.adj[nbunch]) - {nbunch}

Answer 1

To understand these lines, lets break each term carefully. For the purpose of explaination, I will create the following Graph:

import networkx as nx

source = [1, 2, 3, 4, 2, 3]
dest = [2, 3, 4, 6, 5, 5]
edge_list = [(u, v) for u, v in zip(source, dest)]

G = nx.Graph()

G.add_edges_from(ed_ls)

The Graph has the following edges:

print(G.edges())
# EdgeView([(1, 2), (2, 3), (2, 5), (3, 4), (3, 5), (4, 6)])

Now lets understand the terms in the above code:

set(self.adj)
If we print this out, we can see it is the set of nodes in the Graph:

print(set(self.adj))
# {1, 2, 3, 4, 5, 6}

set(self.adj[n])
This is the set of nodes adjacent to node n:

print(set(G.adj[2]))
# {1, 3, 5}

Now lets look at the first line that you asked in your question

for v in set(self.adj) - set(self.adj[n]) - {n}

This can be translated as follows:

for v in set of all nodes - set of nodes adjacent to node N - node N

So, this set of all nodes - set of nodes adjacent to node N returns the set of nodes that are not adjacent to node N (and this includes node N itself). (Essentially this will create the complement of the Graph).

Lets, look at an example:

nodes_nbrs = (
                (
                    n,
                    {
                        v: {'weight': 1}
                        for v in set(G.adj) - set(G.adj[n]) - {n}
                    },
                )
                for n in G.nodes()
            )

This will have the following value:

Node 1: {3: {'weight': 1}, 4: {'weight': 1}, 5: {'weight': 1}, 6: {'weight': 1}}
Node 2: {4: {'weight': 1}, 6: {'weight': 1}}
Node 3: {1: {'weight': 1}, 6: {'weight': 1}}
Node 4: {1: {'weight': 1}, 2: {'weight': 1}, 5: {'weight': 1}}
Node 6: {1: {'weight': 1}, 2: {'weight': 1}, 3: {'weight': 1}, 5: {'weight': 1}}
Node 5: {1: {'weight': 1}, 4: {'weight': 1}, 6: {'weight': 1}}

So if you look closely, for each node, we get the a list of nodes that were not adjacent to the node.

For say, node 2, the calculation would look something like this:

{1, 2, 3, 4, 5, 6} - {1, 3, 5} - {2} = {4, 6}

---

Now lets come to the second line:

nbrs = set(self.nodes()) - set(self.adj[nbunch]) - {nbunch}

Here set(self.adj[nbunch]) is basically the set of nodes adjacent to nodes in nbunch. nbunch is nothing but an iterator of nodes, so instead of set(self.adj[n]) where we get neighbors of a single node, here we get neighbors of multiple nodes.

So the expression can be translated as follows: Set of all nodes - Set of all nodes adjacent to each node in nbunch - Set of nodes in nbunch

Which is same as the first expression that you asked except that this one is for multiple nodes, i.e. This will also return the list of nodes that are not adjacent to nodes in nbunch