{
  "nbformat_minor": 0, 
  "nbformat": 4, 
  "cells": [
    {
      "execution_count": null, 
      "cell_type": "code", 
      "source": [
        "%matplotlib inline"
      ], 
      "outputs": [], 
      "metadata": {
        "collapsed": false
      }
    }, 
    {
      "source": [
        "\n# Antigraph\n\n\nComplement graph class for small footprint when working on dense graphs.\n\nThis class allows you to add the edges that *do not exist* in the dense\ngraph. However, when applying algorithms to this complement graph data\nstructure, it behaves as if it were the dense version. So it can be used\ndirectly in several NetworkX algorithms.\n\nThis subclass has only been tested for k-core, connected_components,\nand biconnected_components algorithms but might also work for other\nalgorithms.\n\n\n"
      ], 
      "cell_type": "markdown", 
      "metadata": {}
    }, 
    {
      "execution_count": null, 
      "cell_type": "code", 
      "source": [
        "# Author: Jordi Torrents <jtorrents@milnou.net>\n\n#    Copyright (C) 2015-2017 by\n#    Jordi Torrents <jtorrents@milnou.net>\n#    All rights reserved.\n#    BSD license.\nimport networkx as nx\nfrom networkx.exception import NetworkXError\nimport matplotlib.pyplot as plt\n\n__all__ = ['AntiGraph']\n\n\nclass AntiGraph(nx.Graph):\n    \"\"\"\n    Class for complement graphs.\n\n    The main goal is to be able to work with big and dense graphs with\n    a low memory foodprint.\n\n    In this class you add the edges that *do not exist* in the dense graph,\n    the report methods of the class return the neighbors, the edges and\n    the degree as if it was the dense graph. Thus it's possible to use\n    an instance of this class with some of NetworkX functions.\n    \"\"\"\n\n    all_edge_dict = {'weight': 1}\n\n    def single_edge_dict(self):\n        return self.all_edge_dict\n    edge_attr_dict_factory = single_edge_dict\n\n    def __getitem__(self, n):\n        \"\"\"Return a dict of neighbors of node n in the dense graph.\n\n        Parameters\n        ----------\n        n : node\n           A node in the graph.\n\n        Returns\n        -------\n        adj_dict : dictionary\n           The adjacency dictionary for nodes connected to n.\n\n        \"\"\"\n        return dict((node, self.all_edge_dict) for node in\n                    set(self.adj) - set(self.adj[n]) - set([n]))\n\n    def neighbors(self, n):\n        \"\"\"Return an iterator over all neighbors of node n in the\n           dense graph.\n\n        \"\"\"\n        try:\n            return iter(set(self.adj) - set(self.adj[n]) - set([n]))\n        except KeyError:\n            raise NetworkXError(\"The node %s is not in the graph.\" % (n,))\n\n    def degree(self, nbunch=None, weight=None):\n        \"\"\"Return an iterator for (node, degree) in the dense graph.\n\n        The node degree is the number of edges adjacent to the node.\n\n        Parameters\n        ----------\n        nbunch : iterable container, optional (default=all nodes)\n            A container of nodes.  The container will be iterated\n            through once.\n\n        weight : string or None, optional (default=None)\n           The edge attribute that holds the numerical value used\n           as a weight.  If None, then each edge has weight 1.\n           The degree is the sum of the edge weights adjacent to the node.\n\n        Returns\n        -------\n        nd_iter : iterator\n            The iterator returns two-tuples of (node, degree).\n\n        See Also\n        --------\n        degree\n\n        Examples\n        --------\n        >>> G = nx.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc\n        >>> list(G.degree(0))  # node 0 with degree 1\n        [(0, 1)]\n        >>> list(G.degree([0, 1]))\n        [(0, 1), (1, 2)]\n\n        \"\"\"\n        if nbunch is None:\n            nodes_nbrs = ((n, {v: self.all_edge_dict for v in\n                               set(self.adj) - set(self.adj[n]) - set([n])})\n                          for n in self.nodes())\n        elif nbunch in self:\n            nbrs = set(self.nodes()) - set(self.adj[nbunch]) - {nbunch}\n            return len(nbrs)\n        else:\n            nodes_nbrs = ((n, {v: self.all_edge_dict for v in\n                               set(self.nodes()) - set(self.adj[n]) - set([n])})\n                          for n in self.nbunch_iter(nbunch))\n\n        if weight is None:\n            return ((n, len(nbrs)) for n, nbrs in nodes_nbrs)\n        else:\n            # AntiGraph is a ThinGraph so all edges have weight 1\n            return ((n, sum((nbrs[nbr].get(weight, 1)) for nbr in nbrs))\n                    for n, nbrs in nodes_nbrs)\n\n    def adjacency_iter(self):\n        \"\"\"Return an iterator of (node, adjacency set) tuples for all nodes\n           in the dense graph.\n\n        This is the fastest way to look at every edge.\n        For directed graphs, only outgoing adjacencies are included.\n\n        Returns\n        -------\n        adj_iter : iterator\n           An iterator of (node, adjacency set) for all nodes in\n           the graph.\n\n        \"\"\"\n        for n in self.adj:\n            yield (n, set(self.adj) - set(self.adj[n]) - set([n]))\n\n\nif __name__ == '__main__':\n    # Build several pairs of graphs, a regular graph\n    # and the AntiGraph of it's complement, which behaves\n    # as if it were the original graph.\n    Gnp = nx.gnp_random_graph(20, 0.8, seed=42)\n    Anp = AntiGraph(nx.complement(Gnp))\n    Gd = nx.davis_southern_women_graph()\n    Ad = AntiGraph(nx.complement(Gd))\n    Gk = nx.karate_club_graph()\n    Ak = AntiGraph(nx.complement(Gk))\n    pairs = [(Gnp, Anp), (Gd, Ad), (Gk, Ak)]\n    # test connected components\n    for G, A in pairs:\n        gc = [set(c) for c in nx.connected_components(G)]\n        ac = [set(c) for c in nx.connected_components(A)]\n        for comp in ac:\n            assert comp in gc\n    # test biconnected components\n    for G, A in pairs:\n        gc = [set(c) for c in nx.biconnected_components(G)]\n        ac = [set(c) for c in nx.biconnected_components(A)]\n        for comp in ac:\n            assert comp in gc\n    # test degree\n    for G, A in pairs:\n        node = list(G.nodes())[0]\n        nodes = list(G.nodes())[1:4]\n        assert G.degree(node) == A.degree(node)\n        assert sum(d for n, d in G.degree()) == sum(d for n, d in A.degree())\n        # AntiGraph is a ThinGraph, so all the weights are 1\n        assert sum(d for n, d in A.degree()) == sum(d for n, d in A.degree(weight='weight'))\n        assert sum(d for n, d in G.degree(nodes)) == sum(d for n, d in A.degree(nodes))\n\n    nx.draw(Gnp)\n    plt.show()"
      ], 
      "outputs": [], 
      "metadata": {
        "collapsed": false
      }
    }
  ], 
  "metadata": {
    "kernelspec": {
      "display_name": "Python 2", 
      "name": "python2", 
      "language": "python"
    }, 
    "language_info": {
      "mimetype": "text/x-python", 
      "nbconvert_exporter": "python", 
      "name": "python", 
      "file_extension": ".py", 
      "version": "2.7.12", 
      "pygments_lexer": "ipython2", 
      "codemirror_mode": {
        "version": 2, 
        "name": "ipython"
      }
    }
  }
}