# vim:ts=4:sw=4:sts=4:et
# -*- coding: utf-8 -*-
"""Classes related to graph clustering.

@undocumented: _handle_mark_groups_arg_for_clustering, _prepare_community_comparison"""

__license__ = u"""
Copyright (C) 2006-2012  Tamás Nepusz <ntamas@gmail.com>
Pázmány Péter sétány 1/a, 1117 Budapest, Hungary

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA
"""

from copy import deepcopy
from itertools import izip
from math import pi
from cStringIO import StringIO

from igraph import community_to_membership
from igraph.compat import property
from igraph.configuration import Configuration
from igraph.datatypes import UniqueIdGenerator
from igraph.drawing.colors import ClusterColoringPalette
from igraph.statistics import Histogram
from igraph.summary import _get_wrapper_for_width
from igraph.utils import str_to_orientation

class Clustering(object):
    """Class representing a clustering of an arbitrary ordered set.

    This is now used as a base for L{VertexClustering}, but it might be
    useful for other purposes as well.

    Members of an individual cluster can be accessed by the C{[]} operator:

      >>> cl = Clustering([0,0,0,0,1,1,1,2,2,2,2])
      >>> cl[0]
      [0, 1, 2, 3]

    The membership vector can be accessed by the C{membership} property:

      >>> cl.membership
      [0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2]

    The number of clusters can be retrieved by the C{len} function:

      >>> len(cl)
      3

    You can iterate over the clustering object as if it were a regular list
    of clusters:

      >>> for cluster in cl:
      ...     print " ".join(str(idx) for idx in cluster)
      ...
      0 1 2 3
      4 5 6
      7 8 9 10

    If you need all the clusters at once as lists, you can simply convert
    the clustering object to a list:

      >>> cluster_list = list(cl)
      >>> print cluster_list
      [[0, 1, 2, 3], [4, 5, 6], [7, 8, 9, 10]]

    @undocumented: _formatted_cluster_iterator
    """

    def __init__(self, membership, params = None):
        """Constructor.

        @param membership: the membership list -- that is, the cluster
          index in which each element of the set belongs to.
        @param params: additional parameters to be stored in this
          object's dictionary."""
        self._membership = list(membership)
        if len(self._membership)>0:
            self._len = max(m for m in self._membership if m is not None)+1
        else:
            self._len = 0

        if params:
            self.__dict__.update(params)

    def __getitem__(self, idx):
        """Returns the members of the specified cluster.

        @param idx: the index of the cluster
        @return: the members of the specified cluster as a list
        @raise IndexError: if the index is out of bounds"""
        if idx < 0 or idx >= self._len:
            raise IndexError("cluster index out of range")
        return [i for i, e in enumerate(self._membership) if e == idx]

    def __iter__(self):
        """Iterates over the clusters in this clustering.

        This method will return a generator that generates the clusters
        one by one."""
        clusters = [[] for _ in xrange(self._len)]
        for idx, cluster in enumerate(self._membership):
            clusters[cluster].append(idx)
        return iter(clusters)

    def __len__(self):
        """Returns the number of clusters.

        @return: the number of clusters
        """
        return self._len

    def __str__(self):
        return self.summary(verbosity=1, width=78)

    def as_cover(self):
        """Returns a L{Cover} that contains the same clusters as this clustering."""
        return Cover(self._graph, self)

    def compare_to(self, other, *args, **kwds):
        """Compares this clustering to another one using some similarity or
        distance metric.

        This is a convenience method that simply calls L{compare_communities}
        with the two clusterings as arguments. Any extra positional or keyword
        argument is also forwarded to L{compare_communities}."""
        return compare_communities(self, other, *args, **kwds)

    @property
    def membership(self):
        """Returns the membership vector."""
        return self._membership[:]

    @property
    def n(self):
        """Returns the number of elements covered by this clustering."""
        return len(self._membership)

    def size(self, idx):
        """Returns the size of a given cluster.

        @param idx: the cluster in which we are interested.
        """
        return len(self[idx])

    def sizes(self, *args):
        """Returns the size of given clusters.

        The indices are given as positional arguments. If there are no
        positional arguments, the function will return the sizes of all clusters.
        """
        counts = [0] * len(self)
        for x in self._membership:
            counts[x] += 1

        if args:
            return [counts[idx] for idx in args]

        return counts

    def size_histogram(self, bin_width = 1):
        """Returns the histogram of cluster sizes.

        @param bin_width: the bin width of the histogram
        @return: a L{Histogram} object
        """
        return Histogram(bin_width, self.sizes())

    def summary(self, verbosity=0, width=None):
        """Returns the summary of the clustering.

        The summary includes the number of items and clusters, and also the
        list of members for each of the clusters if the verbosity is nonzero.

        @param verbosity: determines whether the cluster members should be
          printed. Zero verbosity prints the number of items and clusters only.
        @return: the summary of the clustering as a string.
        """
        out = StringIO()
        print >>out, "Clustering with %d elements and %d clusters" % \
                (len(self._membership), len(self))

        if verbosity < 1:
            return out.getvalue().strip()

        ndigits = len(str(len(self)))
        wrapper = _get_wrapper_for_width(width,
                subsequent_indent = " " * (ndigits+3))

        for idx, cluster in enumerate(self._formatted_cluster_iterator()):
            wrapper.initial_indent = "[%*d] " % (ndigits, idx)
            print >>out, "\n".join(wrapper.wrap(cluster))

        return out.getvalue().strip()

    def _formatted_cluster_iterator(self):
        """Iterates over the clusters and formats them into a string to be
        presented in the summary."""
        for cluster in self:
            yield ", ".join(str(member) for member in cluster)


class VertexClustering(Clustering):
    """The clustering of the vertex set of a graph.

    This class extends L{Clustering} by linking it to a specific L{Graph} object
    and by optionally storing the modularity score of the clustering.
    It also provides some handy methods like getting the subgraph corresponding
    to a cluster and such.

    @note: since this class is linked to a L{Graph}, destroying the graph by the
      C{del} operator does not free the memory occupied by the graph if there
      exists a L{VertexClustering} that references the L{Graph}.

    @undocumented: _formatted_cluster_iterator
    """

    # Allow None to be passed to __plot__ as the "palette" keyword argument
    _default_palette = None

    def __init__(self, graph, membership = None, modularity = None, \
                 params = None, modularity_params = None):
        """Creates a clustering object for a given graph.

        @param graph: the graph that will be associated to the clustering
        @param membership: the membership list. The length of the list must
          be equal to the number of vertices in the graph. If C{None}, every
          vertex is assumed to belong to the same cluster.
        @param modularity: the modularity score of the clustering. If C{None},
          it will be calculated when needed.
        @param params: additional parameters to be stored in this object.
        @param modularity_params: arguments that should be passed to
          L{Graph.modularity} when the modularity is (re)calculated. If the
          original graph was weighted, you should pass a dictionary
          containing a C{weight} key with the appropriate value here.
        """
        if membership is None:
            Clustering.__init__(self, [0]*graph.vcount(), params)
        else:
            if len(membership) != graph.vcount():
                raise ValueError("membership list has invalid length")
            Clustering.__init__(self, membership, params)

        self._graph = graph
        self._modularity = modularity
        self._modularity_dirty = modularity is None
        if modularity_params is None:
            self._modularity_params = {}
        else:
            self._modularity_params = dict(modularity_params)

    # pylint: disable-msg=C0103
    @classmethod
    def FromAttribute(cls, graph, attribute, intervals=None, params=None):
        """Creates a vertex clustering based on the value of a vertex attribute.

        Vertices having the same attribute will correspond to the same cluster.

        @param graph: the graph on which we are working
        @param attribute: name of the attribute on which the clustering
            is based.
        @param intervals: for numeric attributes, you can either pass a single
            number or a list of numbers here. A single number means that the
            vertices will be put in bins of that width and vertices ending up
            in the same bin will be in the same cluster. A list of numbers
            specify the bin positions explicitly; e.g., C{[10, 20, 30]} means
            that there will be four categories: vertices with the attribute
            value less than 10, between 10 and 20, between 20 and 30 and over 30.
            Intervals are closed from the left and open from the right.
        @param params: additional parameters to be stored in this object.

        @return: a new VertexClustering object
        """
        from bisect import bisect

        def safeintdiv(x, y):
            """Safe integer division that handles None gracefully"""
            if x is None:
                return None
            return int(x / y)

        def safebisect(intervals, x):
            """Safe list bisection that handles None gracefully"""
            if x is None:
                return None
            return bisect(intervals, x)

        try:
            _ = iter(intervals)
            iterable = True
        except TypeError:
            iterable = False
        if intervals is None:
            vec = graph.vs[attribute]
        elif iterable:
            intervals = list(intervals)
            vec = [safebisect(intervals, x) for x in graph.vs[attribute]]
        else:
            intervals = float(intervals)
            vec = [safeintdiv(x, intervals) for x in graph.vs[attribute]]

        idgen = UniqueIdGenerator()
        idgen[None] = None
        vec = [idgen[i] for i in vec]
        return cls(graph, vec, None, params)

    def as_cover(self):
        """Returns a L{VertexCover} that contains the same clusters as this
        clustering."""
        return VertexCover(self._graph, self)

    def cluster_graph(self, combine_vertices=None, combine_edges=None):
        """Returns a graph where each cluster is contracted into a single
        vertex.

        In the resulting graph, vertex M{i} represents cluster M{i} in this
        clustering. Vertex M{i} and M{j} will be connected if there was
        at least one connected vertex pair M{(a, b)} in the original graph such
        that vertex M{a} was in cluster M{i} and vertex M{b} was in cluster
        M{j}.

        @param combine_vertices: specifies how to derive the attributes of
          the vertices in the new graph from the attributes of the old ones.
          See L{Graph.contract_vertices()} for more details.
        @param combine_edges: specifies how to derive the attributes of the
          edges in the new graph from the attributes of the old ones. See
          L{Graph.simplify()} for more details. If you specify C{False}
          here, edges will not be combined, and the number of edges between
          the vertices representing the original clusters will be equal to
          the number of edges between the members of those clusters in the
          original graph.

        @return: the new graph.
        """
        result = self.graph.copy()
        result.contract_vertices(self.membership, combine_vertices)
        if combine_edges != False:
            result.simplify(combine_edges=combine_edges)
        return result

    def crossing(self):
        """Returns a boolean vector where element M{i} is C{True} iff edge
        M{i} lies between clusters, C{False} otherwise."""
        membership = self.membership
        return [membership[v1] != membership[v2] \
                for v1, v2 in self.graph.get_edgelist()]

    @property
    def modularity(self):
        """Returns the modularity score"""
        if self._modularity_dirty:
            return self._recalculate_modularity_safe()
        return self._modularity
    q = modularity

    @property
    def graph(self):
        """Returns the graph belonging to this object"""
        return self._graph

    def recalculate_modularity(self):
        """Recalculates the stored modularity value.

        This method must be called before querying the modularity score of the
        clustering through the class member C{modularity} or C{q} if the
        graph has been modified (edges have been added or removed) since the
        creation of the L{VertexClustering} object.

        @return: the new modularity score
        """
        self._modularity = self._graph.modularity(self._membership,
                **self._modularity_params)
        self._modularity_dirty = False
        return self._modularity

    def _recalculate_modularity_safe(self):
        """Recalculates the stored modularity value and swallows all exceptions
        raised by the modularity function (if any).

        @return: the new modularity score or C{None} if the modularity function
        could not be calculated.
        """
        try:
            return self.recalculate_modularity()
        except:
            return None
        finally:
            self._modularity_dirty = False

    def subgraph(self, idx):
        """Get the subgraph belonging to a given cluster.

        @param idx: the cluster index
        @return: a copy of the subgraph
        @precondition: the vertex set of the graph hasn't been modified since
          the moment the clustering was constructed.
        """
        return self._graph.subgraph(self[idx])


    def subgraphs(self):
        """Gets all the subgraphs belonging to each of the clusters.

        @return: a list containing copies of the subgraphs
        @precondition: the vertex set of the graph hasn't been modified since
          the moment the clustering was constructed.
        """
        return [self._graph.subgraph(cl) for cl in self]


    def giant(self):
        """Returns the giant community of the clustered graph.

        The giant component a community for which no larger community exists.
        @note: there can be multiple giant communities, this method will return
          the copy of an arbitrary one if there are multiple giant communities.

        @return: a copy of the giant community.
        @precondition: the vertex set of the graph hasn't been modified since
          the moment the clustering was constructed.
        """
        ss = self.sizes()
        max_size = max(ss)
        return self.subgraph(ss.index(max_size))

    def __plot__(self, context, bbox, palette, *args, **kwds):
        """Plots the clustering to the given Cairo context in the given
        bounding box.

        This is done by calling L{Graph.__plot__()} with the same arguments, but
        coloring the graph vertices according to the current clustering (unless
        overridden by the C{vertex_color} argument explicitly).

        This method understands all the positional and keyword arguments that
        are understood by L{Graph.__plot__()}, only the differences will be
        highlighted here:

          - C{mark_groups}: whether to highlight some of the vertex groups by
            colored polygons. Besides the values accepted by L{Graph.__plot__}
            (i.e., a dict mapping colors to vertex indices, a list containing
            lists of vertex indices, or C{False}), the following are also
            accepted:

              - C{True}: all the groups will be highlighted, the colors matching
                the corresponding color indices from the current palette
                (see the C{palette} keyword argument of L{Graph.__plot__}.

              - A dict mapping cluster indices or tuples of vertex indices to
                color names.  The given clusters or vertex groups will be
                highlighted by the given colors.

              - A list of cluster indices. This is equivalent to passing a
                dict mapping numeric color indices from the current palette
                to cluster indices; therefore, the cluster referred to by element
                I{i} of the list will be highlighted by color I{i} from the
                palette.

            The value of the C{plotting.mark_groups} configuration key is also
            taken into account here; if that configuration key is C{True} and
            C{mark_groups} is not given explicitly, it will automatically be set
            to C{True}.

            In place of lists of vertex indices, you may also use L{VertexSeq}
            instances.

            In place of color names, you may also use color indices into the
            current palette. C{None} as a color name will mean that the
            corresponding group is ignored.

          - C{palette}: the palette used to resolve numeric color indices to RGBA
            values. By default, this is an instance of L{ClusterColoringPalette}.

        @see: L{Graph.__plot__()} for more supported keyword arguments.
        """
        if "edge_color" not in kwds and "color" not in self.graph.edge_attributes():
            # Set up a default edge coloring based on internal vs external edges
            colors = ["grey20", "grey80"]
            kwds["edge_color"] = [colors[is_crossing]
                                  for is_crossing in self.crossing()]

        if palette is None:
            palette = ClusterColoringPalette(len(self))

        if "mark_groups" not in kwds:
            if Configuration.instance()["plotting.mark_groups"]:
                kwds["mark_groups"] = (
                    (group, color) for color, group in enumerate(self)
                )
        else:
            kwds["mark_groups"] = _handle_mark_groups_arg_for_clustering(
                    kwds["mark_groups"], self)

        if "vertex_color" not in kwds:
            kwds["vertex_color"] = self.membership

        return self._graph.__plot__(context, bbox, palette, *args, **kwds)

    def _formatted_cluster_iterator(self):
        """Iterates over the clusters and formats them into a string to be
        presented in the summary."""
        if self._graph.is_named():
            names = self._graph.vs["name"]
            for cluster in self:
                yield ", ".join(str(names[member]) for member in cluster)
        else:
            for cluster in self:
                yield ", ".join(str(member) for member in cluster)


###############################################################################

class Dendrogram(object):
    """The hierarchical clustering (dendrogram) of some dataset.

    A hierarchical clustering means that we know not only the way the
    elements are separated into groups, but also the exact history of
    how individual elements were joined into larger subgroups.

    This class internally represents the hierarchy by a matrix with n rows
    and 2 columns -- or more precisely, a list of lists of size 2. This is
    exactly the same as the original format used by C{igraph}'s C core.
    The M{i}th row of the matrix contains the indices of the two clusters
    being joined in time step M{i}. The joint group will be represented by
    the ID M{n+i}, with M{i} starting from one. The ID of the joint group
    will be referenced in the upcoming steps instead of any of its individual
    members. So, IDs less than or equal to M{n} (where M{n} is the number of
    rows in the matrix) mean the original members of the dataset (with ID
    from 0 to M{n}), while IDs up from M{n+1} mean joint groups. As an
    example, take a look at the dendrogram and the internal representation of
    a given clustering of five nodes::

      0 -+
         |
      1 -+-+
           |
      2 ---+-+        <====>   [[0, 1], [3, 4], [2, 5], [6, 7]]
             |
      3 -+   |
         |   |
      4 -+---+---

    @undocumented: _item_box_size, _plot_item, _traverse_inorder
    """

    def __init__(self, merges):
        """Creates a hierarchical clustering.

        @param merges: the merge history either in matrix or tuple format"""
        self._merges = [tuple(pair) for pair in merges]
        self._nmerges = len(self._merges)
        if self._nmerges:
            self._nitems = max(self._merges[-1])-self._nmerges+2
        else:
            self._nitems = 0
        self._names = None

    @staticmethod
    def _convert_matrix_to_tuple_repr(merges, n=None):
        """Converts the matrix representation of a clustering to a tuple
        representation.

        @param merges: the matrix representation of the clustering
        @return: the tuple representation of the clustering
        """
        if n is None:
            n = len(merges)+1
        tuple_repr = range(n)
        idxs = range(n)
        for rowidx, row in enumerate(merges):
            i, j = row
            try:
                idxi, idxj = idxs[i], idxs[j]
                tuple_repr[idxi] = (tuple_repr[idxi], tuple_repr[idxj])
                tuple_repr[idxj] = None
            except IndexError:
                raise ValueError("malformed matrix, subgroup referenced "+
                                 "before being created in step %d" % rowidx)
            idxs.append(j)
        return [x for x in tuple_repr if x is not None]

    def _traverse_inorder(self):
        """Conducts an inorder traversal of the merge tree.

        The inorder traversal returns the nodes on the last level in the order
        they should be drawn so that no edges cross each other.

        @return: the result of the inorder traversal in a list."""
        result = []
        seen_nodes = set()

        for node_index in reversed(xrange(self._nitems+self._nmerges)):
            if node_index in seen_nodes:
                continue

            stack = [node_index]
            while stack:
                last = stack.pop()
                seen_nodes.add(last)
                if last < self._nitems:
                    # 'last' is a regular node so the traversal ends here, we
                    # can append it to the results
                    result.append(last)
                else:
                    # 'last' is a merge node, so let us proceed with the entry
                    # where this merge node was created
                    stack.extend(self._merges[last-self._nitems])

        return result

    def __str__(self):
        return self.summary(verbosity=1)

    def format(self, format="newick"):
        """Formats the dendrogram in a foreign format.

        Currently only the Newick format is supported.

        Example:

            >>> d = Dendrogram([(2, 3), (0, 1), (4, 5)])
            >>> d.format()
            '((2,3)4,(0,1)5)6;'
            >>> d.names = list("ABCDEFG")
            >>> d.format()
            '((C,D)E,(A,B)F)G;'
        """
        if format == "newick":
            n = self._nitems + self._nmerges
            if self._names is None:
                nodes = range(n)
            else:
                nodes = list(self._names)
            if len(nodes) < n:
                nodes.extend("" for _ in xrange(n - len(nodes)))
            for k, (i, j) in enumerate(self._merges, self._nitems):
                nodes[k] = "(%s,%s)%s" % (nodes[i], nodes[j], nodes[k])
                nodes[i] = nodes[j] = None
            return nodes[-1] + ";"
        raise ValueError("unsupported format: %r" % format)

    def summary(self, verbosity=0, max_leaf_count=40):
        """Returns the summary of the dendrogram.

        The summary includes the number of leafs and branches, and also an
        ASCII art representation of the dendrogram unless it is too large.

        @param verbosity: determines whether the ASCII representation of the
          dendrogram should be printed. Zero verbosity prints only the number
          of leafs and branches.
        @param max_leaf_count: the maximal number of leafs to print in the
          ASCII representation. If the dendrogram has more leafs than this
          limit, the ASCII representation will not be printed even if the
          verbosity is larger than or equal to 1.
        @return: the summary of the dendrogram as a string.
        """
        out = StringIO()
        print >>out, "Dendrogram, %d elements, %d merges" % \
                (self._nitems, self._nmerges)

        if self._nitems == 0 or verbosity < 1 or self._nitems > max_leaf_count:
            return out.getvalue().strip()

        print >>out

        positions = [None] * self._nitems
        inorder = self._traverse_inorder()
        distance = 2
        level_distance = 2
        nextp = 0
        for idx, element in enumerate(inorder):
            positions[element] = nextp
            inorder[idx] = str(element)
            nextp += max(distance, len(inorder[idx])+1)

        width = max(positions)+1

        # Print the nodes on the lowest level
        print >>out, (" " * (distance-1)).join(inorder)
        midx = 0
        max_community_idx = self._nitems
        while midx < self._nmerges:
            char_array = [" "] * width
            for position in positions:
                if position >= 0:
                    char_array[position] = "|"
            char_str = "".join(char_array)
            for _ in xrange(level_distance-1):
                print >>out, char_str # Print the lines

            cidx_incr = 0
            while midx < self._nmerges:
                id1, id2 = self._merges[midx]
                if id1 >= max_community_idx or id2 >= max_community_idx:
                    break
                midx += 1

                pos1, pos2 = positions[id1], positions[id2]
                positions[id1], positions[id2] = -1, -1

                if pos1 > pos2:
                    pos1, pos2 = pos2, pos1
                positions.append((pos1+pos2) // 2)

                dashes = "-" * (pos2 - pos1 - 1)
                char_array[pos1:(pos2+1)] = "`%s'" % dashes

                cidx_incr += 1

            max_community_idx += cidx_incr

            print >>out, "".join(char_array)

        return out.getvalue().strip()

    def _item_box_size(self, context, horiz, idx):
        """Calculates the amount of space needed for drawing an
        individual vertex at the bottom of the dendrogram."""
        if self._names is None or self._names[idx] is None:
            x_bearing, _, _, height, x_advance, _ = context.text_extents("")
        else:
            x_bearing, _, _, height, x_advance, _ = context.text_extents(str(self._names[idx]))

        if horiz:
            return x_advance - x_bearing, height
        return height, x_advance - x_bearing

    # pylint: disable-msg=R0913
    def _plot_item(self, context, horiz, idx, x, y):
        """Plots a dendrogram item to the given Cairo context

        @param context: the Cairo context we are plotting on
        @param horiz: whether the dendrogram is horizontally oriented
        @param idx: the index of the item
        @param x: the X position of the item
        @param y: the Y position of the item
        """
        if self._names is None or self._names[idx] is None:
            return

        height = self._item_box_size(context, True, idx)[1]
        if horiz:
            context.move_to(x, y+height)
            context.show_text(str(self._names[idx]))
        else:
            context.save()
            context.translate(x, y)
            context.rotate(-pi/2.)
            context.move_to(0, height)
            context.show_text(str(self._names[idx]))
            context.restore()

    # pylint: disable-msg=C0103,W0613
    # W0613 = unused argument 'palette'
    def __plot__(self, context, bbox, palette, *args, **kwds):
        """Draws the dendrogram on the given Cairo context

        Supported keyword arguments are:

          - C{orientation}: the orientation of the dendrogram. Must be one of
            the following values: C{left-right}, C{bottom-top}, C{right-left}
            or C{top-bottom}. Individual elements are always placed at the
            former edge and merges are performed towards the latter edge.
            Possible aliases: C{horizontal} = C{left-right},
            C{vertical} = C{bottom-top}, C{lr} = C{left-right},
            C{rl} = C{right-left}, C{tb} = C{top-bottom}, C{bt} = C{bottom-top}.
            The default is C{left-right}.

        """
        from igraph.layout import Layout

        if self._names is None:
            self._names = [str(x) for x in xrange(self._nitems)]

        orientation = str_to_orientation(kwds.get("orientation", "lr"),
                reversed_vertical=True)
        horiz = orientation in ("lr", "rl")

        # Get the font height
        font_height = context.font_extents()[2]

        # Calculate space needed for individual items at the
        # bottom of the dendrogram
        item_boxes = [self._item_box_size(context, horiz, idx) \
          for idx in xrange(self._nitems)]

        # Small correction for cases when the right edge of the labels is
        # aligned with the tips of the dendrogram branches
        ygap = 2 if orientation == "bt" else 0
        xgap = 2 if orientation == "lr" else 0
        item_boxes = [(x+xgap, y+ygap) for x, y in item_boxes]

        # Calculate coordinates
        layout = Layout([(0, 0)] * self._nitems, dim=2)
        inorder = self._traverse_inorder()
        if not horiz:
            x, y = 0, 0
            for idx, element in enumerate(inorder):
                layout[element] = (x, 0)
                x += max(font_height, item_boxes[element][0])

            for id1, id2 in self._merges:
                y += 1
                layout.append(((layout[id1][0]+layout[id2][0])/2., y))

            # Mirror or rotate the layout if necessary
            if orientation == "bt":
                layout.mirror(1)
        else:
            x, y = 0, 0
            for idx, element in enumerate(inorder):
                layout[element] = (0, y)
                y += max(font_height, item_boxes[element][1])

            for id1, id2 in self._merges:
                x += 1
                layout.append((x, (layout[id1][1]+layout[id2][1])/2.))

            # Mirror or rotate the layout if necessary
            if orientation == "rl":
                layout.mirror(0)

        # Rescale layout to the bounding box
        maxw = max(e[0] for e in item_boxes)
        maxh = max(e[1] for e in item_boxes)

        # w, h: width and height of the area containing the dendrogram
        # tree without the items.
        # delta_x, delta_y: displacement of the dendrogram tree
        width, height = float(bbox.width), float(bbox.height)
        delta_x, delta_y = 0, 0
        if horiz:
            width -= maxw
            if orientation == "lr":
                delta_x = maxw
        else:
            height -= maxh
            if orientation == "tb":
                delta_y = maxh

        if horiz:
            delta_y += font_height / 2.
        else:
            delta_x += font_height / 2.
        layout.fit_into((delta_x, delta_y, width - delta_x, height - delta_y),
                        keep_aspect_ratio=False)

        context.save()

        context.translate(bbox.left, bbox.top)
        context.set_source_rgb(0., 0., 0.)
        context.set_line_width(1)

        # Draw items
        if horiz:
            sgn = 0 if orientation == "rl" else -1
            for idx in xrange(self._nitems):
                x = layout[idx][0] + sgn * item_boxes[idx][0]
                y = layout[idx][1] - item_boxes[idx][1]/2.
                self._plot_item(context, horiz, idx, x, y)
        else:
            sgn = 1 if orientation == "bt" else 0
            for idx in xrange(self._nitems):
                x = layout[idx][0] - item_boxes[idx][0]/2.
                y = layout[idx][1] + sgn * item_boxes[idx][1]
                self._plot_item(context, horiz, idx, x, y)

        # Draw dendrogram lines
        if not horiz:
            for idx, (id1, id2) in enumerate(self._merges):
                x0, y0 = layout[id1]
                x1, y1 = layout[id2]
                x2, y2 = layout[idx + self._nitems]
                context.move_to(x0, y0)
                context.line_to(x0, y2)
                context.line_to(x1, y2)
                context.line_to(x1, y1)
                context.stroke()
        else:
            for idx, (id1, id2) in enumerate(self._merges):
                x0, y0 = layout[id1]
                x1, y1 = layout[id2]
                x2, y2 = layout[idx + self._nitems]
                context.move_to(x0, y0)
                context.line_to(x2, y0)
                context.line_to(x2, y1)
                context.line_to(x1, y1)
                context.stroke()

        context.restore()

    @property
    def merges(self):
        """Returns the performed merges in matrix format"""
        return deepcopy(self._merges)

    @property
    def names(self):
        """Returns the names of the nodes in the dendrogram"""
        return self._names

    @names.setter
    def names(self, items):
        """Sets the names of the nodes in the dendrogram"""
        if items is None:
            self._names = None
            return

        items = list(items)
        if len(items) < self._nitems:
            raise ValueError("must specify at least %d names" % self._nitems)

        n = self._nitems + self._nmerges
        self._names = items[:n]
        if len(self._names) < n:
            self._names.extend("" for _ in xrange(n-len(self._names)))


class VertexDendrogram(Dendrogram):
    """The dendrogram resulting from the hierarchical clustering of the
    vertex set of a graph."""

    def __init__(self, graph, merges, optimal_count = None, params = None,
            modularity_params = None):
        """Creates a dendrogram object for a given graph.

        @param graph: the graph that will be associated to the clustering
        @param merges: the merges performed given in matrix form.
        @param optimal_count: the optimal number of clusters where the
          dendrogram should be cut. This is a hint usually provided by the
          clustering algorithm that produces the dendrogram. C{None} means
          that such a hint is not available; the optimal count will then be
          selected based on the modularity in such a case.
        @param params: additional parameters to be stored in this object.
        @param modularity_params: arguments that should be passed to
          L{Graph.modularity} when the modularity is (re)calculated. If the
          original graph was weighted, you should pass a dictionary
          containing a C{weight} key with the appropriate value here.
        """
        Dendrogram.__init__(self, merges)
        self._graph = graph
        self._optimal_count = optimal_count
        if modularity_params is None:
            self._modularity_params = {}
        else:
            self._modularity_params = dict(modularity_params)

    def as_clustering(self, n=None):
        """Cuts the dendrogram at the given level and returns a corresponding
        L{VertexClustering} object.

        @param n: the desired number of clusters. Merges are replayed from the
          beginning until the membership vector has exactly M{n} distinct elements
          or until there are no more recorded merges, whichever happens first.
          If C{None}, the optimal count hint given by the clustering algorithm
          will be used If the optimal count was not given either, it will be
          calculated by selecting the level where the modularity is maximal.
        @return: a new L{VertexClustering} object.
        """
        if n is None:
            n = self.optimal_count
        num_elts = self._graph.vcount()
        idgen = UniqueIdGenerator()
        membership = community_to_membership(self._merges, num_elts, \
                                             num_elts - n)
        membership = [idgen[m] for m in membership]
        return VertexClustering(self._graph, membership,
                modularity_params=self._modularity_params)

    @property
    def optimal_count(self):
        """Returns the optimal number of clusters for this dendrogram.

        If an optimal count hint was given at construction time, this
        property simply returns the hint. If such a count was not given,
        this method calculates the optimal number of clusters by maximizing
        the modularity along all the possible cuts in the dendrogram.
        """
        if self._optimal_count is not None:
            return self._optimal_count

        n = self._graph.vcount()
        max_q, optimal_count = 0, 1
        for step in xrange(min(n-1, len(self._merges))):
            membs = community_to_membership(self._merges, n, step)
            q = self._graph.modularity(membs, **self._modularity_params)
            if q > max_q:
                optimal_count = n-step
                max_q = q
        self._optimal_count = optimal_count
        return optimal_count

    @optimal_count.setter
    def optimal_count(self, value):
        self._optimal_count = max(int(value), 1)

    def __plot__(self, context, bbox, palette, *args, **kwds):
        """Draws the vertex dendrogram on the given Cairo context

        See L{Dendrogram.__plot__} for the list of supported keyword
        arguments."""
        from igraph.drawing.metamagic import AttributeCollectorBase

        class VisualVertexBuilder(AttributeCollectorBase):
            _kwds_prefix = "vertex_"
            label = None

        builder = VisualVertexBuilder(self._graph.vs, kwds)
        self._names = [vertex.label for vertex in builder]
        self._names = [name if name is not None else str(idx)
                       for idx, name in enumerate(self._names)]
        result = Dendrogram.__plot__(self, context, bbox, palette, \
                *args, **kwds)
        del self._names

        return result

###############################################################################

class Cover(object):
    """Class representing a cover of an arbitrary ordered set.

    Covers are similar to clusterings, but each element of the set may
    belong to more than one cluster in a cover, and elements not belonging
    to any cluster are also allowed.

    L{Cover} instances provide a similar API as L{Clustering} instances;
    for instance, iterating over a L{Cover} will iterate over the clusters
    just like with a regular L{Clustering} instance. However, they are not
    derived from each other or from a common superclass, and there might
    be functions that exist only in one of them or the other.

    Clusters of an individual cover can be accessed by the C{[]} operator:

      >>> cl = Cover([[0,1,2,3], [2,3,4], [0,1,6]])
      >>> cl[0]
      [0, 1, 2, 3]

    The membership vector can be accessed by the C{membership} property.
    Note that contrary to L{Clustering} instances, the membership vector
    will contain lists that contain the cluster indices each item belongs
    to:

      >>> cl.membership
      [[0, 2], [0, 2], [0, 1], [0, 1], [1], [], [2]]

    The number of clusters can be retrieved by the C{len} function:

      >>> len(cl)
      3

    You can iterate over the cover as if it were a regular list of
    clusters:

      >>> for cluster in cl:
      ...     print " ".join(str(idx) for idx in cluster)
      ...
      0 1 2 3
      2 3 4
      0 1 6

    If you need all the clusters at once as lists, you can simply convert
    the cover to a list:

      >>> cluster_list = list(cl)
      >>> print cluster_list
      [[0, 1, 2, 3], [2, 3, 4], [0, 1, 6]]

    L{Clustering} objects can readily be converted to L{Cover} objects
    using the constructor:

      >>> clustering = Clustering([0, 0, 0, 0, 1, 1, 1, 2, 2, 2])
      >>> cover = Cover(clustering)
      >>> list(clustering) == list(cover)
      True

    @undocumented: _formatted_cluster_iterator
    """

    def __init__(self, clusters, n=0):
        """Constructs a cover with the given clusters.

        @param clusters: the clusters in this cover, as a list or iterable.
          Each cluster is specified by a list or tuple that contains the
          IDs of the items in this cluster. IDs start from zero.

        @param n: the total number of elements in the set that is covered
          by this cover. If it is less than the number of unique elements
          found in all the clusters, we will simply use the number of unique
          elements, so it is safe to leave this at zero. You only have to
          specify this parameter if there are some elements that are covered
          by none of the clusters.
        """

        self._clusters = [list(cluster) for cluster in clusters]
        try:
            self._n = max(max(cluster)+1 for cluster in self._clusters if cluster)
        except ValueError:
            self._n = 0
        self._n = max(n, self._n)

    def __getitem__(self, index):
        """Returns the cluster with the given index."""
        return self._clusters[index]

    def __iter__(self):
        """Iterates over the clusters in this cover."""
        return iter(self._clusters)

    def __len__(self):
        """Returns the number of clusters in this cover."""
        return len(self._clusters)

    def __str__(self):
        """Returns a string representation of the cover."""
        return self.summary(verbosity=1, width=78)

    @property
    def membership(self):
        """Returns the membership vector of this cover.

        The membership vector of a cover covering I{n} elements is a list of
        length I{n}, where element I{i} contains the cluster indices of the
        I{i}th item.
        """
        result = [[] for _ in xrange(self._n)]
        for idx, cluster in enumerate(self):
            for item in cluster:
                result[item].append(idx)
        return result

    @property
    def n(self):
        """Returns the number of elements in the set covered by this cover."""
        return self._n

    def size(self, idx):
        """Returns the size of a given cluster.

        @param idx: the cluster in which we are interested.
        """
        return len(self[idx])

    def sizes(self, *args):
        """Returns the size of given clusters.

        The indices are given as positional arguments. If there are no
        positional arguments, the function will return the sizes of all clusters.
        """
        if args:
            return [len(self._clusters[idx]) for idx in args]
        return [len(cluster) for cluster in self]

    def size_histogram(self, bin_width = 1):
        """Returns the histogram of cluster sizes.

        @param bin_width: the bin width of the histogram
        @return: a L{Histogram} object
        """
        return Histogram(bin_width, self.sizes())

    def summary(self, verbosity=0, width=None):
        """Returns the summary of the cover.

        The summary includes the number of items and clusters, and also the
        list of members for each of the clusters if the verbosity is nonzero.

        @param verbosity: determines whether the cluster members should be
          printed. Zero verbosity prints the number of items and clusters only.
        @return: the summary of the cover as a string.
        """
        out = StringIO()
        print >>out, "Cover with %d clusters" % len(self)

        if verbosity < 1:
            return out.getvalue().strip()

        ndigits = len(str(len(self)))
        wrapper = _get_wrapper_for_width(width,
                subsequent_indent = " " * (ndigits+3))

        for idx, cluster in enumerate(self._formatted_cluster_iterator()):
            wrapper.initial_indent = "[%*d] " % (ndigits, idx)
            print >>out, "\n".join(wrapper.wrap(cluster))

        return out.getvalue().strip()

    def _formatted_cluster_iterator(self):
        """Iterates over the clusters and formats them into a string to be
        presented in the summary."""
        for cluster in self:
            yield ", ".join(str(member) for member in cluster)


class VertexCover(Cover):
    """The cover of the vertex set of a graph.

    This class extends L{Cover} by linking it to a specific L{Graph} object.
    It also provides some handy methods like getting the subgraph corresponding
    to a cluster and such.

    @note: since this class is linked to a L{Graph}, destroying the graph by the
      C{del} operator does not free the memory occupied by the graph if there
      exists a L{VertexCover} that references the L{Graph}.

    @undocumented: _formatted_cluster_iterator
    """

    def __init__(self, graph, clusters = None):
        """Creates a cover object for a given graph.

        @param graph: the graph that will be associated to the cover
        @param clusters: the list of clusters. If C{None}, it is assumed
          that there is only a single cluster that covers the whole graph.
        """
        if clusters is None:
            clusters = [range(graph.vcount())]

        Cover.__init__(self, clusters, n = graph.vcount())
        if self._n > graph.vcount():
            raise ValueError("cluster list contains vertex ID larger than the "
                             "number of vertices in the graph")

        self._graph = graph

    def crossing(self):
        """Returns a boolean vector where element M{i} is C{True} iff edge
        M{i} lies between clusters, C{False} otherwise."""
        membership = [frozenset(cluster) for cluster in self.membership]
        return [membership[v1].isdisjoint(membership[v2]) \
                for v1, v2 in self.graph.get_edgelist()]

    @property
    def graph(self):
        """Returns the graph belonging to this object"""
        return self._graph

    def subgraph(self, idx):
        """Get the subgraph belonging to a given cluster.

        @param idx: the cluster index
        @return: a copy of the subgraph
        @precondition: the vertex set of the graph hasn't been modified since
          the moment the cover was constructed.
        """
        return self._graph.subgraph(self[idx])

    def subgraphs(self):
        """Gets all the subgraphs belonging to each of the clusters.

        @return: a list containing copies of the subgraphs
        @precondition: the vertex set of the graph hasn't been modified since
          the moment the cover was constructed.
        """
        return [self._graph.subgraph(cl) for cl in self]

    def __plot__(self, context, bbox, palette, *args, **kwds):
        """Plots the cover to the given Cairo context in the given
        bounding box.

        This is done by calling L{Graph.__plot__()} with the same arguments, but
        drawing nice colored blobs around the vertex groups.

        This method understands all the positional and keyword arguments that
        are understood by L{Graph.__plot__()}, only the differences will be
        highlighted here:

          - C{mark_groups}: whether to highlight the vertex clusters by
            colored polygons. Besides the values accepted by L{Graph.__plot__}
            (i.e., a dict mapping colors to vertex indices, a list containing
            lists of vertex indices, or C{False}), the following are also
            accepted:

              - C{True}: all the clusters will be highlighted, the colors matching
                the corresponding color indices from the current palette
                (see the C{palette} keyword argument of L{Graph.__plot__}.

              - A dict mapping cluster indices or tuples of vertex indices to
                color names.  The given clusters or vertex groups will be
                highlighted by the given colors.

              - A list of cluster indices. This is equivalent to passing a
                dict mapping numeric color indices from the current palette
                to cluster indices; therefore, the cluster referred to by element
                I{i} of the list will be highlighted by color I{i} from the
                palette.

            The value of the C{plotting.mark_groups} configuration key is also
            taken into account here; if that configuration key is C{True} and
            C{mark_groups} is not given explicitly, it will automatically be set
            to C{True}.

            In place of lists of vertex indices, you may also use L{VertexSeq}
            instances.

            In place of color names, you may also use color indices into the
            current palette. C{None} as a color name will mean that the
            corresponding group is ignored.

          - C{palette}: the palette used to resolve numeric color indices to RGBA
            values. By default, this is an instance of L{ClusterColoringPalette}.

        @see: L{Graph.__plot__()} for more supported keyword arguments.
        """
        if "edge_color" not in kwds and "color" not in self.graph.edge_attributes():
            # Set up a default edge coloring based on internal vs external edges
            colors = ["grey20", "grey80"]
            kwds["edge_color"] = [colors[is_crossing]
                                  for is_crossing in self.crossing()]

        if "palette" in kwds:
            palette = kwds["palette"]
        else:
            palette = ClusterColoringPalette(len(self))

        if "mark_groups" not in kwds:
            if Configuration.instance()["plotting.mark_groups"]:
                kwds["mark_groups"] = enumerate(self)
        else:
            kwds["mark_groups"] = _handle_mark_groups_arg_for_clustering(
                    kwds["mark_groups"], self)

        return self._graph.__plot__(context, bbox, palette, *args, **kwds)

    def _formatted_cluster_iterator(self):
        """Iterates over the clusters and formats them into a string to be
        presented in the summary."""
        if self._graph.is_named():
            names = self._graph.vs["name"]
            for cluster in self:
                yield ", ".join(str(names[member]) for member in cluster)
        else:
            for cluster in self:
                yield ", ".join(str(member) for member in cluster)


class CohesiveBlocks(VertexCover):
    """The cohesive block structure of a graph.

    Instances of this type are created by L{Graph.cohesive_blocks()}. See
    the documentation of L{Graph.cohesive_blocks()} for an explanation of
    what cohesive blocks are.

    This class provides a few more methods that make handling of cohesive
    block structures easier.
    """

    def __init__(self, graph, blocks = None, cohesion = None, parent = None):
        """Constructs a new cohesive block structure for the given graph.

        If any of I{blocks}, I{cohesion} or I{parent} is C{None}, all the
        arguments will be ignored and L{Graph.cohesive_blocks()} will be
        called to calculate the cohesive blocks. Otherwise, these three
        variables should describe the *result* of a cohesive block structure
        calculation. Chances are that you never have to construct L{CohesiveBlocks}
        instances directly, just use L{Graph.cohesive_blocks()}.

        @param graph: the graph itself
        @param blocks: a list containing the blocks; each block is described
          as a list containing vertex IDs.
        @param cohesion: the cohesion of each block. The length of this list
          must be equal to the length of I{blocks}.
        @param parent: the parent block of each block. Negative values or
          C{None} mean that there is no parent block for that block. There
          should be only one parent block, which covers the entire graph.
        @see: Graph.cohesive_blocks()
        """
        if blocks is None or cohesion is None or parent is None:
            blocks, cohesion, parent = graph.cohesive_blocks()

        VertexCover.__init__(self, graph, blocks)

        self._cohesion = cohesion
        self._parent = parent
        for idx, p in enumerate(self._parent):
            if p < 0:
                self._parent[idx] = None

    def cohesion(self, idx):
        """Returns the cohesion of the group with the given index."""
        return self._cohesion[idx]

    def cohesions(self):
        """Returns the list of cohesion values for each group."""
        return self._cohesion[:]

    def hierarchy(self):
        """Returns a new graph that describes the hierarchical relationships
        between the groups.

        The new graph will be a directed tree; an edge will point from
        vertex M{i} to vertex M{j} if group M{i} is a superset of group M{j}.
        In other words, the edges point downwards.
        """
        from igraph import Graph
        edges = [pair for pair in izip(self._parent, xrange(len(self)))
                 if pair[0] is not None]
        return Graph(edges, directed=True)

    def max_cohesion(self, idx):
        """Finds the maximum cohesion score among all the groups that contain
        the given vertex."""
        result = 0
        for cohesion, cluster in izip(self._cohesion, self._clusters):
            if idx in cluster:
                result = max(result, cohesion)
        return result

    def max_cohesions(self):
        """For each vertex in the graph, returns the maximum cohesion score
        among all the groups that contain the vertex."""
        result = [0] * self._graph.vcount()
        for cohesion, cluster in izip(self._cohesion, self._clusters):
            for idx in cluster:
                result[idx] = max(result[idx], cohesion)
        return result

    def parent(self, idx):
        """Returns the parent group index of the group with the given index
        or C{None} if the given group is the root."""
        return self._parent[idx]

    def parents(self):
        """Returns the list of parent group indices for each group or C{None}
        if the given group is the root."""
        return self._parent[:]

    def __plot__(self, context, bbox, palette, *args, **kwds):
        """Plots the cohesive block structure to the given Cairo context in
        the given bounding box.

        Since a L{CohesiveBlocks} instance is also a L{VertexCover}, keyword
        arguments accepted by L{VertexCover.__plot__()} are also accepted here.
        The only difference is that the vertices are colored according to their
        maximal cohesions by default, and groups are marked by colored blobs
        except the last group which encapsulates the whole graph.

        See the documentation of L{VertexCover.__plot__()} for more details.
        """
        prepare_groups = False
        if "mark_groups" not in kwds:
            if Configuration.instance()["plotting.mark_groups"]:
                prepare_groups = True
        elif kwds["mark_groups"] == True:
            prepare_groups = True

        if prepare_groups:
            colors = [pair for pair in enumerate(self.cohesions())
                if pair[1] > 1]
            kwds["mark_groups"] = colors

        if "vertex_color" not in kwds:
            kwds["vertex_color"] = self.max_cohesions()

        return VertexCover.__plot__(self, context, bbox, palette, *args, **kwds)

def _handle_mark_groups_arg_for_clustering(mark_groups, clustering):
    """Handles the mark_groups=... keyword argument in plotting methods of
    clusterings.

    This is an internal method, you shouldn't need to mess around with it.
    Its purpose is to handle the extended semantics of the mark_groups=...
    keyword argument in the C{__plot__} method of L{VertexClustering} and
    L{VertexCover} instances, namely the feature that numeric IDs are resolved
    to clusters automatically.
    """
    # Handle the case of mark_groups = True, mark_groups containing a list or
    # tuple of cluster IDs, and and mark_groups yielding (cluster ID, color)
    # pairs
    if mark_groups is True:
        group_iter = ((group, color) for color, group in enumerate(clustering))
    elif isinstance(mark_groups, dict):
        group_iter = mark_groups.iteritems()
    elif hasattr(mark_groups, "__getitem__") and hasattr(mark_groups, "__len__"):
        # Lists, tuples
        try:
            first = mark_groups[0]
        except:
            # Hmm. Maybe not a list or tuple?
            first = None
        if first is not None:
            # Okay. Is the first element of the list a single number?
            if isinstance(first, (int, long)):
                # Yes. Seems like we have a list of cluster indices.
                # Assign color indices automatically.
                group_iter = ((group, color)
                        for color, group in enumerate(mark_groups))
            else:
                # No. Seems like we have good ol' group-color pairs.
                group_iter = mark_groups
        else:
            group_iter = mark_groups
    elif hasattr(mark_groups, "__iter__"):
        # Iterators etc
        group_iter = mark_groups
    else:
        group_iter = {}.iteritems()

    def cluster_index_resolver():
        for group, color in group_iter:
            if isinstance(group, (int, long)):
                group = clustering[group]
            yield group, color

    return cluster_index_resolver()

##############################################################

def _prepare_community_comparison(comm1, comm2, remove_none=False):
    """Auxiliary method that takes two community structures either as
    membership lists or instances of L{Clustering}, and returns a
    tuple whose two elements are membership lists.

    This is used by L{compare_communities} and L{split_join_distance}.

    @param comm1: the first community structure as a membership list or
      as a L{Clustering} object.
    @param comm2: the second community structure as a membership list or
      as a L{Clustering} object.
    @param remove_none: whether to remove C{None} entries from the membership
      lists. If C{remove_none} is C{False}, a C{None} entry in either C{comm1}
      or C{comm2} will result in an exception. If C{remove_none} is C{True},
      C{None} values are filtered away and only the remaining lists are
      compared.
    """
    def _ensure_list(obj):
        if isinstance(obj, Clustering):
            return obj.membership
        return list(obj)

    vec1, vec2 = _ensure_list(comm1), _ensure_list(comm2)
    if len(vec1) != len(vec2):
        raise ValueError("the two membership vectors must be equal in length")

    if remove_none and (None in vec1 or None in vec2):
        idxs_to_remove = [i for i in xrange(len(vec1)) \
                if vec1[i] is None or vec2[i] is None]
        idxs_to_remove.reverse()
        n = len(vec1)
        for i in idxs_to_remove:
            n -= 1
            vec1[i], vec1[n] = vec1[n], vec1[i]
            vec2[i], vec2[n] = vec2[n], vec2[i]
        del vec1[n:]
        del vec2[n:]

    return vec1, vec2


def compare_communities(comm1, comm2, method="vi", remove_none=False):
    """Compares two community structures using various distance measures.

    @param comm1: the first community structure as a membership list or
      as a L{Clustering} object.
    @param comm2: the second community structure as a membership list or
      as a L{Clustering} object.
    @param method: the measure to use. C{"vi"} or C{"meila"} means the
      variation of information metric of Meila (2003), C{"nmi"} or C{"danon"}
      means the normalized mutual information as defined by Danon et al (2005),
      C{"split-join"} means the split-join distance of van Dongen (2000),
      C{"rand"} means the Rand index of Rand (1971), C{"adjusted_rand"}
      means the adjusted Rand index of Hubert and Arabie (1985).
    @param remove_none: whether to remove C{None} entries from the membership
      lists. This is handy if your L{Clustering} object was constructed using
      L{VertexClustering.FromAttribute} using an attribute which was not defined
      for all the vertices. If C{remove_none} is C{False}, a C{None} entry in
      either C{comm1} or C{comm2} will result in an exception. If C{remove_none}
      is C{True}, C{None} values are filtered away and only the remaining lists
      are compared.

    @return: the calculated measure.
    @newfield ref: Reference
    @ref: Meila M: Comparing clusterings by the variation of information.
          In: Scholkopf B, Warmuth MK (eds). Learning Theory and Kernel
          Machines: 16th Annual Conference on Computational Learning Theory
          and 7th Kernel Workship, COLT/Kernel 2003, Washington, DC, USA.
          Lecture Notes in Computer Science, vol. 2777, Springer, 2003.
          ISBN: 978-3-540-40720-1.
    @ref: Danon L, Diaz-Guilera A, Duch J, Arenas A: Comparing community
          structure identification. J Stat Mech P09008, 2005.
    @ref: van Dongen D: Performance criteria for graph clustering and Markov
          cluster experiments. Technical Report INS-R0012, National Research
          Institute for Mathematics and Computer Science in the Netherlands,
          Amsterdam, May 2000.
    @ref: Rand WM: Objective criteria for the evaluation of clustering
          methods. J Am Stat Assoc 66(336):846-850, 1971.
    @ref: Hubert L and Arabie P: Comparing partitions. Journal of
          Classification 2:193-218, 1985.
    """
    import igraph._igraph
    vec1, vec2 = _prepare_community_comparison(comm1, comm2, remove_none)
    return igraph._igraph._compare_communities(vec1, vec2, method)


def split_join_distance(comm1, comm2, remove_none=False):
    """Calculates the split-join distance between two community structures.

    The split-join distance is a distance measure defined on the space of
    partitions of a given set. It is the sum of the projection distance of
    one partition from the other and vice versa, where the projection
    number of A from B is if calculated as follows:

      1. For each set in A, find the set in B with which it has the
         maximal overlap, and take note of the size of the overlap.

      2. Take the sum of the maximal overlap sizes for each set in A.

      3. Subtract the sum from M{n}, the number of elements in the
         partition.

    Note that the projection distance is asymmetric, that's why it has to be
    calculated in both directions and then added together.  This function
    returns the projection distance of C{comm1} from C{comm2} and the
    projection distance of C{comm2} from C{comm1}, and returns them in a pair.
    The actual split-join distance is the sum of the two distances. The reason
    why it is presented this way is that one of the elements being zero then
    implies that one of the partitions is a subpartition of the other (and if
    it is close to zero, then one of the partitions is close to being a
    subpartition of the other).

    @param comm1: the first community structure as a membership list or
      as a L{Clustering} object.
    @param comm2: the second community structure as a membership list or
      as a L{Clustering} object.
    @param remove_none: whether to remove C{None} entries from the membership
      lists. This is handy if your L{Clustering} object was constructed using
      L{VertexClustering.FromAttribute} using an attribute which was not defined
      for all the vertices. If C{remove_none} is C{False}, a C{None} entry in
      either C{comm1} or C{comm2} will result in an exception. If C{remove_none}
      is C{True}, C{None} values are filtered away and only the remaining lists
      are compared.

    @return: the projection distance of C{comm1} from C{comm2} and vice versa
      in a tuple. The split-join distance is the sum of the two.
    @newfield ref: Reference
    @ref: van Dongen D: Performance criteria for graph clustering and Markov
          cluster experiments. Technical Report INS-R0012, National Research
          Institute for Mathematics and Computer Science in the Netherlands,
          Amsterdam, May 2000.

    @see: L{compare_communities()} with C{method = "split-join"} if you are
      not interested in the individual projection distances but only the
      sum of them.
    """
    import igraph._igraph
    vec1, vec2 = _prepare_community_comparison(comm1, comm2, remove_none)
    return igraph._igraph._split_join_distance(vec1, vec2)