text: """Functions for measuring the quality of a partition (into
  communities).
  
  """
  
  from functools import wraps
  from itertools import product
  
  import networkx as nx
  from networkx import NetworkXError
  from networkx.utils import not_implemented_for
  from networkx.algorithms.community.community_utils import is_partition
  
  __all__ = ['coverage', 'modularity', 'performance']
  
  
  class NotAPartition(NetworkXError):
      """Raised if a given collection is not a partition.
  
      """
      def __init__(self, G, collection):
          msg = f"{G} is not a valid partition of the graph {collection}"
          super().__init__(msg)
  
  
  def require_partition(func):
      """Decorator to check that a valid partition is input to a function
  
      Raises :exc:`networkx.NetworkXError` if the partition is not valid.
  
      This decorator should be used on functions whose first two arguments
      are a graph and a partition of the nodes of that graph (in that
      order)::
  
          >>> @require_partition
          ... def foo(G, partition):
          ...     print('partition is valid!')
          ...
          >>> G = nx.complete_graph(5)
          >>> partition = [{0, 1}, {2, 3}, {4}]
          >>> foo(G, partition)
          partition is valid!
          >>> partition = [{0}, {2, 3}, {4}]
          >>> foo(G, partition)
          Traceback (most recent call last):
            ...
          networkx.exception.NetworkXError: `partition` is not a valid partition of the nodes of G
          >>> partition = [{0, 1}, {1, 2, 3}, {4}]
          >>> foo(G, partition)
          Traceback (most recent call last):
            ...
          networkx.exception.NetworkXError: `partition` is not a valid partition of the nodes of G
  
      """
      @wraps(func)
      def new_func(*args, **kw):
          # Here we assume that the first two arguments are (G, partition).
          if not is_partition(*args[:2]):
              raise nx.NetworkXError('`partition` is not a valid partition of'
                                     ' the nodes of G')
          return func(*args, **kw)
      return new_func
  
  
  def intra_community_edges(G, partition):
      """Returns the number of intra-community edges for a partition of `G`.
  
      Parameters
      ----------
      G : NetworkX graph.
  
      partition : iterable of sets of nodes
          This must be a partition of the nodes of `G`.
  
      The "intra-community edges" are those edges joining a pair of nodes
      in the same block of the partition.
  
      """
      return sum(G.subgraph(block).size() for block in partition)
  
  
  def inter_community_edges(G, partition):
      """Returns the number of inter-community edges for a prtition of `G`.
      according to the given
      partition of the nodes of `G`.
  
      Parameters
      ----------
      G : NetworkX graph.
  
      partition : iterable of sets of nodes
          This 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 that of `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])
      #
      MG = nx.MultiDiGraph if G.is_directed() else nx.MultiGraph
      return nx.quotient_graph(G, partition, create_using=MG).size()
  
  
  def inter_community_non_edges(G, partition):
      """Returns the number of inter-community non-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`.
  
      A *non-edge* is a pair of nodes (undirected if `G` is undirected)
      that are not adjacent in `G`. The *inter-community non-edges* are
      those non-edges on a pair of nodes in different blocks of the
      partition.
  
      Implementation note: this function creates two intermediate graphs,
      which may require up to twice the amount of memory as required to
      store `G`.
  
      """
      # Alternate implementation that does not require constructing two
      # new graph objects (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 nx.non_edges(G) if aff[u] != aff[v])
      #
      return inter_community_edges(nx.complement(G), partition)
  
  
  @not_implemented_for('multigraph')
  @require_partition
  def performance(G, partition):
      """Returns the performance of a partition.
  
      The *performance* of a partition is the ratio of the number of
      intra-community edges plus inter-community non-edges with the total
      number of potential edges.
  
      Parameters
      ----------
      G : NetworkX graph
          A simple graph (directed or undirected).
  
      partition : sequence
          Partition of the nodes of `G`, represented as a sequence of
          sets of nodes. Each block of the partition represents a
          community.
  
      Returns
      -------
      float
          The performance of the partition, as defined above.
  
      Raises
      ------
      NetworkXError
          If `partition` is not a valid partition of the nodes of `G`.
  
      References
      ----------
      .. [1] Santo Fortunato.
             "Community Detection in Graphs".
             *Physical Reports*, Volume 486, Issue 3--5 pp. 75--174
             <https://arxiv.org/abs/0906.0612>
  
      """
      # Compute the number of intra-community edges and inter-community
      # edges.
      intra_edges = intra_community_edges(G, partition)
      inter_edges = inter_community_non_edges(G, partition)
      # Compute the number of edges in the complete graph (directed or
      # undirected, as it depends on `G`) on `n` nodes.
      #
      # (If `G` is an undirected graph, we divide by two since we have
      # double-counted each potential edge. We use integer division since
      # `total_pairs` is guaranteed to be even.)
      n = len(G)
      total_pairs = n * (n - 1)
      if not G.is_directed():
          total_pairs //= 2
      return (intra_edges + inter_edges) / total_pairs
  
  
  @require_partition
  def coverage(G, partition):
      """Returns the coverage of a partition.
  
      The *coverage* of a partition is the ratio of the number of
      intra-community edges to the total number of edges in the graph.
  
      Parameters
      ----------
      G : NetworkX graph
  
      partition : sequence
          Partition of the nodes of `G`, represented as a sequence of
          sets of nodes. Each block of the partition represents a
          community.
  
      Returns
      -------
      float
          The coverage of the partition, as defined above.
  
      Raises
      ------
      NetworkXError
          If `partition` is not a valid partition of the nodes of `G`.
  
      Notes
      -----
      If `G` is a multigraph, the multiplicity of edges is counted.
  
      References
      ----------
      .. [1] Santo Fortunato.
             "Community Detection in Graphs".
             *Physical Reports*, Volume 486, Issue 3--5 pp. 75--174
             <https://arxiv.org/abs/0906.0612>
  
      """
      intra_edges = intra_community_edges(G, partition)
      total_edges = G.number_of_edges()
      return intra_edges / total_edges
  
  
  def modularity(G, communities, weight='weight'):
      r"""Returns the modularity of the given partition of the graph.
  
      Modularity is defined in [1]_ as
  
      .. math::
  
          Q = \frac{1}{2m} \sum_{ij} \left( A_{ij} - \frac{k_ik_j}{2m}\right)
              \delta(c_i,c_j)
  
      where $m$ is the number of edges, $A$ is the adjacency matrix of
      `G`, $k_i$ is the degree of $i$ and $\delta(c_i, c_j)$
      is 1 if $i$ and $j$ are in the same community and 0 otherwise.
  
      Parameters
      ----------
      G : NetworkX Graph
  
      communities : list or iterable of set of nodes
          These node sets must represent a partition of G's nodes.
  
      Returns
      -------
      Q : float
          The modularity of the paritition.
  
      Raises
      ------
      NotAPartition
          If `communities` is not a partition of the nodes of `G`.
  
      Examples
      --------
      >>> import networkx.algorithms.community as nx_comm
      >>> G = nx.barbell_graph(3, 0)
      >>> nx_comm.modularity(G, [{0, 1, 2}, {3, 4, 5}])
      0.35714285714285704
      >>> nx_comm.modularity(G, nx_comm.label_propagation_communities(G))
      0.35714285714285704
  
      References
      ----------
      .. [1] M. E. J. Newman *Networks: An Introduction*, page 224.
         Oxford University Press, 2011.
  
      """
      if not isinstance(communities, list):
          communities = list(communities)
      if not is_partition(G, communities):
          raise NotAPartition(G, communities)
  
      multigraph = G.is_multigraph()
      directed = G.is_directed()
      m = G.size(weight=weight)
      if directed:
          out_degree = dict(G.out_degree(weight=weight))
          in_degree = dict(G.in_degree(weight=weight))
          norm = 1 / m
      else:
          out_degree = dict(G.degree(weight=weight))
          in_degree = out_degree
          norm = 1 / (2 * m)
  
      def val(u, v):
          try:
              if multigraph:
                  w = sum(d.get(weight, 1) for k, d in G[u][v].items())
              else:
                  w = G[u][v].get(weight, 1)
          except KeyError:
              w = 0
          # Double count self-loops if the graph is undirected.
          if u == v and not directed:
              w *= 2
          return w - in_degree[u] * out_degree[v] * norm
  
      Q = sum(val(u, v) for c in communities for u, v in product(c, repeat=2))
      return Q * norm
  