<commit_before>import networkx as nx
from itertools import combinations
from KCliquePercolation import KCliquePercolation
from ClusterUtility import ClusterUtility


class MaxCliquesPercolation(KCliquePercolation):
    """This class find maximal cliques and their percolation in a graph.

    The procedure will find any intersection (percolation) between any maximal cliques found.
    The cluster is defined as percolated maximal cliques [Reid2012]_.

    References
    ----------
    .. [Reid2012] <NAME>, <NAME>, and <NAME>. Percolation computation in complex networks.
                  In Proceedings of the 2012 IEEE/ACM International Conference on Advances in Social Networks
                  Analysis and Mining, pp. 274-281, 2012.
    """
    def __init__(self, graph, edges_weight, nodes_id):
        """This is the constructor of class MaxCliquesPercolation

        Parameters
        ----------
        graph           : graph
            Graph to be clustered.
        edges_weight    : list[tuple]
            List of tuple containing (node1, node2, cosine similarity between these two).
        nodes_id        : list
            List of all node identifier.

        Notes
        -----
        max_cliques : list[frozenset]
            List of frozenset containing node id for each maximal clique.
        """
        super(MaxCliquesPercolation, self).__init__(graph, edges_weight, nodes_id)

    def init_maxclique_percolation(self):
        """Initialization of maxial clique percolation method.

        The first step is to build temporary graph (percolation graph). Then the procedure finds
        all maximal cliques in the graph.
        """
        super(MaxCliquesPercolation, self)._build_temp_graph()
        maxcliques = self._find_maxcliques()
        self.cliques = maxcliques

    def get_maxcliques_percolation(self, k):
        """The main method to find clusters based on maximal clique percolation.

        This method looks for percolation between cliques.
        It then remove any edges that connecting two vertices but has different clusters.

        Returns
        -------
        k           : int
            Number of percolation or intersection between an individual clique.
        clusters    : dict[frozenset]
            List of frozenset containing node identifier (node id in integer).
        """
        super(MaxCliquesPercolation, self)._get_percolation_graph(self.cliques, k)
        super(MaxCliquesPercolation, self)._remove_outcluster()
        clusters = super(MaxCliquesPercolation, self)._get_clusters()

        return clusters

    def _find_maxcliques(self):
        """Find maximal cliques using `find_clique` function from NetworkX.

        Returns
        -------
        maxcliques  : list[frozenset]
            List of frozenset containing node id for each maximal clique.
        """
        maxcliques = list(frozenset(c) for c in nx.find_cliques(self.graph))
        self.cliques = maxcliques
        return maxcliques


class MaxCliquesPercolationWeighted(MaxCliquesPercolation):
    """This is a class for maximal clique percolation with edge weight [Liu2009]_.

    Edge weight is evaluated using intensity threshold or the geometric mean
    for all edge weights in a maximal clique [Studiawan2016c]_. We then remove the overlapping nodes
    where a node only follow the weighter neighboring cluster [Studiawan2016c]_.

    References
    ----------
    .. [Liu2009]        <NAME>, <NAME>, and <NAME>. Complex discovery from
                        weighted PPI networks. Bioinformatics, 25(15):1891-1897, 2009.
    .. [Studiawan2016c] <NAME>, <NAME>, <NAME>, SSH log clustering using weighted
                        maximal clique percolation (to be submitted).
    """
    def __init__(self, graph, edges_weight, nodes_id):
        """This is the constructor of class MaxCliquePercolation Weighted.

        The parameters are the same with its parent class but we add a threshold
        for the intensity for maximal clique found.

        Parameters
        ----------
        graph           : graph
            Graph to be clustered.
        edges_weight    : list[tuple]
            List of tuple containing (node1, node2, cosine similarity between these two).
        nodes_id        : list
            List of all node identifier.
        """
        super(MaxCliquesPercolationWeighted, self).__init__(graph, edges_weight, nodes_id)
        self.percolation_dict = {}

    def get_maxcliques_percolation_weighted(self, k, threshold):
        """This is the main method for maximal clique percolation for edge-weighted graph.

        Parameters
        ----------
        k           : int
            Number of percolation or intersection between an individual clique.
        threshold   : float
            Threshold for intensity of maximal clique.

        Returns
        -------
        clusters    : dict[int, frozenset]
            List of frozenset containing node identifier (node id in integer).

        Notes
        -----
        weighted_maxcliques : list[frozenset]
            List of frozenset containing node identifier for each weighted maximal clique.
        """
        # get weighted maximal cliques and get percolation
        weighted_maxcliques = ClusterUtility.get_weighted_cliques(self.graph, self.cliques, threshold)
        super(MaxCliquesPercolationWeighted, self)._get_percolation_graph(weighted_maxcliques, k)
        percolations = self.clique_percolation
        self.__set_percolation_dict(percolations)

        # remove overlapping nodes
        percolations = percolations.values()
        for p1, p2 in combinations(percolations, 2):
            intersections = p1.intersection(p2)
            if intersections:
                for node in intersections:
                    node_neighbors = self.graph.neighbors(node)
                    p1_neighbors, p2_neighbors = p1.intersection(node_neighbors), p2.intersection(node_neighbors)
                    p1_neighbors_weight = self.__get_neighbors_weight(node, p1_neighbors)
                    p2_neighbors_weight = self.__get_neighbors_weight(node, p2_neighbors)

                    # follow the neighboring cluster which has bigger sum of edge-weight
                    self.percolation_dict[node] = self.percolation_dict[list(p1_neighbors)[0]] \
                        if p1_neighbors_weight > p2_neighbors_weight else self.percolation_dict[list(p2_neighbors)[0]]

        self.__set_graph_cluster()
        clusters = self.__get_clusters()
        return clusters

    def __set_percolation_dict(self, percolations):
        """Set dictionary of node id and its index in percolations.

        Parameters
        ----------
        percolations    : dict[frozenset]
            Dictionary of frozenset containing nodes id for each maximal clique.<commit_msg>Add checking for empty weighted maxcliques and remove percolations variable because it is redundant<commit_after>import networkx as nx
from itertools import combinations
from KCliquePercolation import KCliquePercolation
from ClusterUtility import ClusterUtility


class MaxCliquesPercolation(KCliquePercolation):
    """This class find maximal cliques and their percolation in a graph.

    The procedure will find any intersection (percolation) between any maximal cliques found.
    The cluster is defined as percolated maximal cliques [Reid2012]_.

    References
    ----------
    .. [Reid2012] <NAME>, <NAME>, and <NAME>. Percolation computation in complex networks.
                  In Proceedings of the 2012 IEEE/ACM International Conference on Advances in Social Networks
                  Analysis and Mining, pp. 274-281, 2012.
    """
    def __init__(self, graph, edges_weight, nodes_id):
        """This is the constructor of class MaxCliquesPercolation

        Parameters
        ----------
        graph           : graph
            Graph to be clustered.
        edges_weight    : list[tuple]
            List of tuple containing (node1, node2, cosine similarity between these two).
        nodes_id        : list
            List of all node identifier.

        Notes
        -----
        max_cliques : list[frozenset]
            List of frozenset containing node id for each maximal clique.
        """
        super(MaxCliquesPercolation, self).__init__(graph, edges_weight, nodes_id)

    def init_maxclique_percolation(self):
        """Initialization of maxial clique percolation method.

        The first step is to build temporary graph (percolation graph). Then the procedure finds
        all maximal cliques in the graph.
        """
        super(MaxCliquesPercolation, self)._build_temp_graph()
        maxcliques = self._find_maxcliques()
        self.cliques = maxcliques

    def get_maxcliques_percolation(self, k):
        """The main method to find clusters based on maximal clique percolation.

        This method looks for percolation between cliques.
        It then remove any edges that connecting two vertices but has different clusters.

        Returns
        -------
        k           : int
            Number of percolation or intersection between an individual clique.
        clusters    : dict[frozenset]
            List of frozenset containing node identifier (node id in integer).
        """
        super(MaxCliquesPercolation, self)._get_percolation_graph(self.cliques, k)
        super(MaxCliquesPercolation, self)._remove_outcluster()
        clusters = super(MaxCliquesPercolation, self)._get_clusters()

        return clusters

    def _find_maxcliques(self):
        """Find maximal cliques using `find_clique` function from NetworkX.

        Returns
        -------
        maxcliques  : list[frozenset]
            List of frozenset containing node id for each maximal clique.
        """
        maxcliques = list(frozenset(c) for c in nx.find_cliques(self.graph))
        self.cliques = maxcliques
        return maxcliques


class MaxCliquesPercolationWeighted(MaxCliquesPercolation):
    """This is a class for maximal clique percolation with edge weight [Liu2009]_.

    Edge weight is evaluated using intensity threshold or the geometric mean
    for all edge weights in a maximal clique [Studiawan2016c]_. We then remove the overlapping nodes
    where a node only follow the weighter neighboring cluster [Studiawan2016c]_.

    References
    ----------
    .. [Liu2009]        <NAME>, <NAME>, and <NAME>. Complex discovery from
                        weighted PPI networks. Bioinformatics, 25(15):1891-1897, 2009.
    .. [Studiawan2016c] H. Studiawan, <NAME>, <NAME>, SSH log clustering using weighted
                        maximal clique percolation (to be submitted).
    """
    def __init__(self, graph, edges_weight, nodes_id):
        """This is the constructor of class MaxCliquePercolation Weighted.

        The parameters are the same with its parent class but we add a threshold
        for the intensity for maximal clique found.

        Parameters
        ----------
        graph           : graph
            Graph to be clustered.
        edges_weight    : list[tuple]
            List of tuple containing (node1, node2, cosine similarity between these two).
        nodes_id        : list
            List of all node identifier.
        """
        super(MaxCliquesPercolationWeighted, self).__init__(graph, edges_weight, nodes_id)
        self.percolation_dict = {}

    def get_maxcliques_percolation_weighted(self, k, threshold):
        """This is the main method for maximal clique percolation for edge-weighted graph.

        Parameters
        ----------
        k           : int
            Number of percolation or intersection between an individual clique.
        threshold   : float
            Threshold for intensity of maximal clique.

        Returns
        -------
        clusters    : dict[int, frozenset]
            List of frozenset containing node identifier (node id in integer).

        Notes
        -----
        weighted_maxcliques : list[frozenset]
            List of frozenset containing node identifier for each weighted maximal clique.
        """
        # get weighted maximal cliques and get percolation
        weighted_maxcliques = ClusterUtility.get_weighted_cliques(self.graph, self.cliques, threshold)
        clusters = {}
        if weighted_maxcliques:
            super(MaxCliquesPercolationWeighted, self)._get_percolation_graph(weighted_maxcliques, k)
            self.__set_percolation_dict(self.clique_percolation)

            # remove overlapping nodes
            percolations = self.clique_percolation.values()
            for p1, p2 in combinations(percolations, 2):
                intersections = p1.intersection(p2)
                if intersections:
                    for node in intersections:
                        node_neighbors = self.graph.neighbors(node)
                        p1_neighbors, p2_neighbors = p1.intersection(node_neighbors), p2.intersection(node_neighbors)
                        p1_neighbors_weight = self.__get_neighbors_weight(node, p1_neighbors)
                        p2_neighbors_weight = self.__get_neighbors_weight(node, p2_neighbors)

                        # follow the neighboring cluster which has bigger sum of edge-weight
                        self.percolation_dict[node] = self.percolation_dict[list(p1_neighbors)[0]] \
                            if p1_neighbors_weight > p2_neighbors_weight else \
                            self.percolation_dict[list(p2_neighbors)[0]]

            self.__set_graph_cluster()
            clusters = self.__get_clusters()
        return clusters

    def __set_percolation_dict(self, percolations):
        """Set dictionary of node id and its index in percolations.

        Parameters
        ----------
        percolations    : dict[frozenset]
            Dictionary of frozenset containing nodes id for each maximal clique.
{'fraction_non_alphanumeric': 0.06974241228384875, 'fraction_numerical': 0.011623735380641457, 'mean_word_length': 2.274136715997181, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '924015', 'n_tokens_mistral': 3848, 'n_tokens_neox': 3509, 'n_words': 1168}