def inter_community_edges(G, partition):
    """Returns the number of inter-community edges according to the given
    partition of the nodes of `G`.

    `G` must be a NetworkX graph.

    `partition` must be a partition of the nodes of `G`.

    The *inter-community edges* are those edges joining a pair of nodes
    in different blocks of the partition.

    Implementation note: this function creates an intermediate graph
    that may require the same amount of memory as required to store
    `G`.

    """
    # Alternate implementation that does not require constructing a new
    # graph object (but does require constructing an affiliation
    # dictionary):
    #
    #     aff = dict(chain.from_iterable(((v, block) for v in block)
    #                                    for block in partition))
    #     return sum(1 for u, v in G.edges() if aff[u] != aff[v])
    #
    if G.is_directed():
        return nx.quotient_graph(G, partition, create_using=nx.MultiDiGraph()).size()
    else:
        return nx.quotient_graph(G, partition, create_using=nx.MultiGraph()).size()

def blockmodel(G, partition, multigraph=False):
    """Returns a reduced graph constructed using the generalized block modeling
    technique.

    The blockmodel technique collapses nodes into blocks based on a
    given partitioning of the node set.  Each partition of nodes
    (block) is represented as a single node in the reduced graph.
    Edges between nodes in the block graph are added according to the
    edges in the original graph.  If the parameter multigraph is False
    (the default) a single edge is added with a weight equal to the
    sum of the edge weights between nodes in the original graph
    The default is a weight of 1 if weights are not specified.  If the
    parameter multigraph is True then multiple edges are added each
    with the edge data from the original graph.

    Parameters
    ----------
    G : graph
        A networkx Graph or DiGraph

    partition : list of lists, or list of sets
        The partition of the nodes.  Must be non-overlapping.

    multigraph : bool, optional
        If True return a MultiGraph with the edge data of the original
        graph applied to each corresponding edge in the new graph.
        If False return a Graph with the sum of the edge weights, or a
        count of the edges if the original graph is unweighted.

    Returns
    -------
    blockmodel : a Networkx graph object

    Examples
    --------
    >>> G = nx.path_graph(6)
    >>> partition = [[0,1],[2,3],[4,5]]
    >>> M = nx.blockmodel(G,partition)

    References
    ----------
    .. [1] Patrick Doreian, Vladimir Batagelj, and Anuska Ferligoj
           "Generalized Blockmodeling",Cambridge University Press, 2004.

    .. note:: Deprecated in NetworkX v1.11

        ``blockmodel`` will be removed in NetworkX 2.0. Instead use
        ``quotient_graph`` with keyword argument ``relabel=True``, and
        ``create_using=nx.MultiGraph()`` for multigraphs.
    """
    if multigraph:
        return nx.quotient_graph(G, partition,
                                 create_using=nx.MultiGraph(), relabel=True)
    else:
        return nx.quotient_graph(G, partition, relabel=True)

    def test_quotient_graph_incomplete_partition(self):
        G = nx.path_graph(6)
        partition = []
        H = nx.quotient_graph(G, partition, relabel=True)
        assert_nodes_equal(H.nodes(), [])
        assert_edges_equal(H.edges(), [])

        partition = [[0, 1], [2, 3], [5]]
        H = nx.quotient_graph(G, partition, relabel=True)
        assert_nodes_equal(H.nodes(), [0, 1, 2])
        assert_edges_equal(H.edges(), [(0, 1)])

 def test_blockmodel(self):
     G = nx.path_graph(6)
     partition = [[0, 1], [2, 3], [4, 5]]
     M = nx.quotient_graph(G, partition, relabel=True)
     assert_nodes_equal(M.nodes(), [0, 1, 2])
     assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
     for n in M.nodes():
         assert_equal(M.nodes[n]['nedges'], 1)
         assert_equal(M.nodes[n]['nnodes'], 2)
         assert_equal(M.nodes[n]['density'], 1.0)

 def test_multigraph_path(self):
     G = nx.MultiGraph(nx.path_graph(6))
     partition = [{0, 1}, {2, 3}, {4, 5}]
     M = nx.quotient_graph(G, partition, relabel=True)
     assert_equal(sorted(M), [0, 1, 2])
     assert_equal(sorted(M.edges()), [(0, 1), (1, 2)])
     for n in M:
         assert_equal(M.node[n]['nedges'], 1)
         assert_equal(M.node[n]['nnodes'], 2)
         assert_equal(M.node[n]['density'], 1)

 def test_path(self):
     G = nx.path_graph(6)
     partition = [{0, 1}, {2, 3}, {4, 5}]
     M = nx.quotient_graph(G, partition, relabel=True)
     assert_nodes_equal(M, [0, 1, 2])
     assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
     for n in M:
         assert_equal(M.nodes[n]['nedges'], 1)
         assert_equal(M.nodes[n]['nnodes'], 2)
         assert_equal(M.nodes[n]['density'], 1)

 def test_barbell(self):
     G = nx.barbell_graph(3, 0)
     partition = [{0, 1, 2}, {3, 4, 5}]
     M = nx.quotient_graph(G, partition, relabel=True)
     assert_equal(sorted(M), [0, 1])
     assert_equal(sorted(M.edges()), [(0, 1)])
     for n in M:
         assert_equal(M.node[n]['nedges'], 3)
         assert_equal(M.node[n]['nnodes'], 3)
         assert_equal(M.node[n]['density'], 1)

 def test_directed_path(self):
     G = nx.DiGraph()
     G.add_path(range(6))
     partition = [{0, 1}, {2, 3}, {4, 5}]
     M = nx.quotient_graph(G, partition, relabel=True)
     assert_equal(sorted(M), [0, 1, 2])
     assert_equal(sorted(M.edges()), [(0, 1), (1, 2)])
     for n in M:
         assert_equal(M.node[n]['nedges'], 1)
         assert_equal(M.node[n]['nnodes'], 2)
         assert_equal(M.node[n]['density'], 0.5)

 def test_directed_multigraph_path(self):
     G = nx.MultiDiGraph()
     nx.add_path(G, range(6))
     partition = [{0, 1}, {2, 3}, {4, 5}]
     M = nx.quotient_graph(G, partition, relabel=True)
     assert_nodes_equal(M, [0, 1, 2])
     assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
     for n in M:
         assert_equal(M.nodes[n]['nedges'], 1)
         assert_equal(M.nodes[n]['nnodes'], 2)
         assert_equal(M.nodes[n]['density'], 0.5)

 def test_barbell_plus(self):
     G = nx.barbell_graph(3, 0)
     # Add an extra edge joining the bells.
     G.add_edge(0, 5)
     partition = [{0, 1, 2}, {3, 4, 5}]
     M = nx.quotient_graph(G, partition, relabel=True)
     assert_equal(sorted(M), [0, 1])
     assert_equal(sorted(M.edges()), [(0, 1)])
     assert_equal(M[0][1]['weight'], 2)
     for n in M:
         assert_equal(M.node[n]['nedges'], 3)
         assert_equal(M.node[n]['nnodes'], 3)
         assert_equal(M.node[n]['density'], 1)

def labeled_blockmodel(g,partition):
    """
    Perform blockmodel transformation on graph *g*
    and partition represented by dictionary *partition*.
    Values of *partition* are used to partition the graph.
    Keys of *partition* are used to label the nodes of the
    new graph.
    """
    new_g = nx.quotient_graph(g,partition.values(),relabel=True)
    labels = dict(enumerate(partition.keys()))
    new_g = nx.relabel_nodes(new_g,labels)
    
    return new_g

def test_quotient_graph_edge_relation():
    """Tests for specifying an alternate edge relation for the quotient graph.

    """
    G = nx.path_graph(5)
    identity = lambda u, v: u == v
    peek = lambda x: next(iter(x))
    same_parity = lambda b, c: peek(b) % 2 == peek(c) % 2
    actual = nx.quotient_graph(G, identity, same_parity)
    expected = nx.Graph()
    expected.add_edges_from([(0, 2), (0, 4), (2, 4)])
    expected.add_edge(1, 3)
    assert_true(nx.is_isomorphic(actual, expected))

    def test_quotient_graph_edge_relation(self):
        """Tests for specifying an alternate edge relation for the quotient
        graph.

        """
        G = nx.path_graph(5)
        identity = lambda u, v: u == v
        same_parity = lambda b, c: (arbitrary_element(b) % 2
                                    == arbitrary_element(c) % 2)
        actual = nx.quotient_graph(G, identity, same_parity)
        expected = nx.Graph()
        expected.add_edges_from([(0, 2), (0, 4), (2, 4)])
        expected.add_edge(1, 3)
        assert_true(nx.is_isomorphic(actual, expected))

 def test_weighted_path(self):
     G = nx.path_graph(6)
     for i in range(5):
         G[i][i + 1]['weight'] = i + 1
     partition = [{0, 1}, {2, 3}, {4, 5}]
     M = nx.quotient_graph(G, partition, relabel=True)
     assert_equal(sorted(M), [0, 1, 2])
     assert_equal(sorted(M.edges()), [(0, 1), (1, 2)])
     assert_equal(M[0][1]['weight'], 2)
     assert_equal(M[1][2]['weight'], 4)
     for n in M:
         assert_equal(M.node[n]['nedges'], 1)
         assert_equal(M.node[n]['nnodes'], 2)
         assert_equal(M.node[n]['density'], 1)

    def test_quotient_graph_complete_bipartite(self):
        """Tests that the quotient graph of the complete bipartite graph under
        the "same neighbors" node relation is `K_2`.

        """
        G = nx.complete_bipartite_graph(2, 3)
        # Two nodes are equivalent if they are not adjacent but have the same
        # neighbor set.
        same_neighbors = lambda u, v: (u not in G[v] and v not in G[u]
                                       and G[u] == G[v])
        expected = nx.complete_graph(2)
        actual = nx.quotient_graph(G, same_neighbors)
        # It won't take too long to run a graph isomorphism algorithm on such
        # small graphs.
        assert_true(nx.is_isomorphic(expected, actual))

    def test_condensation_as_quotient(self):
        """This tests that the condensation of a graph can be viewed as the
        quotient graph under the "in the same connected component" equivalence
        relation.

        """
        # This example graph comes from the file `test_strongly_connected.py`.
        G = nx.DiGraph()
        G.add_edges_from([(1, 2), (2, 3), (2, 11), (2, 12), (3, 4), (4, 3),
                          (4, 5), (5, 6), (6, 5), (6, 7), (7, 8), (7, 9),
                          (7, 10), (8, 9), (9, 7), (10, 6), (11, 2), (11, 4),
                          (11, 6), (12, 6), (12, 11)])
        scc = list(nx.strongly_connected_components(G))
        C = nx.condensation(G, scc)
        component_of = C.graph['mapping']
        # Two nodes are equivalent if they are in the same connected component.
        same_component = lambda u, v: component_of[u] == component_of[v]
        Q = nx.quotient_graph(G, same_component)
        assert_true(nx.is_isomorphic(C, Q))

 def test_overlapping_blocks(self):
     G = nx.path_graph(6)
     partition = [{0, 1, 2}, {2, 3}, {4, 5}]
     nx.quotient_graph(G, partition)

    for n, p in zip(list(range(len(G))), membership):
        partition[p].append(n)
    return list(partition.values())


if __name__ == '__main__':
    G = nx.read_edgelist("hartford_drug.edgelist")

    # Extract largest connected component into graph H
    H = next(nx.connected_component_subgraphs(G))
    # Makes life easier to have consecutively labeled integer nodes
    H = nx.convert_node_labels_to_integers(H)
    # Create parititions with hierarchical clustering
    partitions = create_hc(H)
    # Build blockmodel graph
    BM = nx.quotient_graph(H, partitions, relabel=True)

    # Draw original graph
    pos = nx.spring_layout(H, iterations=100)
    plt.subplot(211)
    nx.draw(H, pos, with_labels=False, node_size=10)

    # Draw block model with weighted edges and nodes sized by number of internal nodes
    node_size = [BM.nodes[x]['nnodes'] * 10 for x in BM.nodes()]
    edge_width = [(2 * d['weight']) for (u, v, d) in BM.edges(data=True)]
    # Set positions to mean of positions of internal nodes from original graph
    posBM = {}
    for n in BM:
        xy = numpy.array([pos[u] for u in BM.nodes[n]['graph']])
        posBM[n] = xy.mean(axis=0)
    plt.subplot(212)