from operator import itemgetter
from pygraphc.abstraction.ClusterAbstraction import ClusterAbstraction
from pygraphc.preprocess.CreateGraph import CreateGraph
from pygraphc.preprocess.PreprocessLog import PreprocessLog


class MajorClust(object):
    """The implementation of MajorClust graph clustering algorithm [Stein1999]_.

    References
    ----------
    .. [Stein1999] B. Stein and O. Niggemann, On the nature of structure and its identification,
                   Proceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science,
                   pp. 122-134, 1999.
    """
    def __init__(self, graph):
        """The constructor of class MajorClust.

        Parameters
        ----------
        graph   : graph
            A graph to be clustered.
        """
        self.graph = graph
        self.clusters = {}

    def get_majorclust(self, graph):
        """The main method to run MajorClust algorithm.

        Parameters
        ----------
        graph   : graph
            A graph to be clustered.

        Returns
        -------
        clusters = dict[list]
            Dictionary of list containing node identifier for each cluster.
        """
        # run majorclust algorithm
        self._majorclust(graph)
        self._get_cluster()

        return self.clusters

    def _majorclust(self, graph):
        """The main procedure of MajorClust which is visiting every node to be evaluated for its neighbor cluster.

        Parameters
        ----------
        graph   : graph
            A graph to be clustered. It can be original graph or the refined one.
        """
        reclusters = set()
        terminate = False
        while not terminate:
            terminate = True
            for node in graph.nodes_iter(data=True):
                initial_cluster = node[1]['cluster']
                current_cluster = self._re_majorclust(node, graph)
                recluster = (node[0], initial_cluster, current_cluster)

                # if has not checked, recluster again
                if initial_cluster != current_cluster and recluster not in reclusters:
                    reclusters.add(recluster)
                    node[1]['cluster'] = current_cluster
                    terminate = False

    def _re_majorclust(self, node, graph):
        """Evaluating the neighbor nodes.

        Parameters
        ----------
        node    : node
            A node in a processed graph.
        graph   : graph
            A graph to be clustered. It can be original graph or the refined one.
        """
        # reclustering
        visited_neighbor, visited_neigbor_num, neighbor_weights = {}, {}, {}

        # observe neighboring edges and nodes
        for current_node, neighbor_node, weight in graph.edges_iter([node[0]], data='weight'):
            neighbor_weights[neighbor_node] = weight
            visited_neighbor[graph.node[neighbor_node]['cluster']] = \