反图

在处理密集图时，用于减少内存占用的补图类。

此类允许您添加在密集图中*不存在*的边。然而，当将算法应用于这个补图数据结构时，它的行为就像它是密集版本一样。因此，它可以直接用于多个NetworkX算法。

这个子类仅针对k-core、connected_components和biconnected_components算法进行了测试，但也可能适用于其他算法。

import matplotlib.pyplot as plt
import networkx as nx
from networkx import Graph


class AntiGraph(Graph):
    """类用于补图。

主要目标是能够处理占用内存少的大型密集图。

在这个类中，您添加的是密集图中*不存在的*边，该类的报告方法返回邻居、边和度数，就像它是密集图一样。因此，可以使用该类的一个实例与NetworkX的一些函数一起使用。"""

    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):
        """返回稠密图中节点 n 的邻居字典。

参数
----------
n : 节点
   图中的一个节点。

返回
-------
adj_dict : 字典
   连接到节点 n 的节点的邻接字典。
"""
        return {
            node: self.all_edge_dict for node in set(self.adj) - set(self.adj[n]) - {n}
        }

    def neighbors(self, n):
        """返回稠密图中节点n的所有邻居的迭代器。
"""
        try:
            return iter(set(self.adj) - set(self.adj[n]) - {n})
        except KeyError as err:
            raise nx.NetworkXError(f"The node {n} is not in the graph.") from err

    def degree(self, nbunch=None, weight=None):
        """返回稠密图中的 (节点, 度数) 迭代器。

节点度数是与该节点相邻的边的数量。

参数
----------
nbunch : 可迭代容器, 可选 (默认=所有节点)
    包含节点的容器。该容器将被遍历一次。

weight : 字符串或 None, 可选 (默认=None)
    存储数值作为权重的边属性。如果为 None，则每条边的权重为 1。
    度数是与节点相邻的边权重的总和。

返回
-------
nd_iter : 迭代器
    迭代器返回 (节点, 度数) 的二元组。

参见
--------
degree

示例
--------
>>> G = nx.path_graph(4)  # 或 DiGraph、MultiGraph、MultiDiGraph 等
>>> G.degree(0)  # 节点 0 的度数为 1
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 是一个 ThinGraph，因此所有边的权重都为 1
            return (
                (n, sum((nbrs[nbr].get(weight, 1)) for nbr in nbrs))
                for n, nbrs in nodes_nbrs
            )

    def adjacency(self):
        """返回一个包含所有节点及其邻接集元组的迭代器。

这是查看每条边的最快方法。对于有向图，仅包含出边邻接关系。

返回
------
adj_iter : 迭代器
   一个包含图中所有节点及其邻接集的迭代器。
"""
        nodes = set(self.adj)
        for n, nbrs in self.adj.items():
            yield (n, nodes - set(nbrs) - {n})


# 构建多个图对，一个常规图
# 以及其补图的反图，其行为表现
# 仿佛它是原始图一样。
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)]
# 测试连通分量
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
# 测试双连通分量
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
# 测试程度
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 是一个 ThinGraph，因此所有权重均为 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))

pos = nx.spring_layout(G, seed=268)  # 用于可重复布局的种子
nx.draw(Gnp, pos=pos)
plt.show()