Source code for fca.algorithms.fast_close_by_one

import numpy as np
from fca import Concept, utils


class FastCloseByOne:
    """Implements algorithm FastCloseByOne from Jan Outrata, Vilem Vychodil

    FCbO lists all formal concepts by a systematic search in the space of all
    formal concepts, avoiding to list the same concept multiple times by
    performing a canonicity test. The algorithm uses set of already computed
    intents which fails canonicity test.

    (cite: https://www.sciencedirect.com/science/article/pii/S0020025511004804)

    More information about the algorithm can be found here:
    https://www.sciencedirect.com/science/article/pii/S0020025511004804
    """

    @staticmethod
    def fast_generate_from(context, concept, y, n, Yj, Nj, intent,
                           output):
        """
        Recursively descends through the space of formal concepts, beginning
        with :math:`<A,B>`.

        Parameters
        ----------
        context : :py:class:`fca.Context`
            Context where the concepts should be find.
        concept : :py:class:`fca.Concept`
            Initial formal concept.
        y :
            Index of first attribute to be processed.
        n :
            Number of columns in context.
        Yj:
            Preallocated :py:class:`numpy.array` for better performance.
        Nj:
            Already computed intents which failed the canonical test.
        intent :
            Preallocated intent for better performance.
        output : list
            Output list for formal concepts.

        """

        output.append(concept)

        if np.logical_and.reduce(concept.intent) or y > n:
            return

        queue = []

        Mj = [np.full((n), False, dtype=bool)] * n

        for j in range(y, n):
            Mj[j] = Nj[j]

            # Reset value from previous call
            Yj[:] = True
            Yj[j:] = False

            # Help variables for subset test (intersections)
            i0 = np.logical_and(Nj[j], Yj)
            i1 = np.logical_and(concept.intent, Yj)

            if not concept.intent[j] and utils.fast_subset_equal(i0, i1):
                # Reset value from previous call
                intent[:] = False
                intent[j] = True

                # New concept
                C = np.logical_and(
                    concept.extent, context.down(intent))
                D = context.up(C)

                # Intersection
                i2 = np.logical_and(D, Yj)

                if np.array_equal(i1, i2):
                    queue.append((Concept(C, D), j + 1))
                else:
                    Mj[j] = D

            while queue:
                concept, y = queue.pop()
                FastCloseByOne.fast_generate_from(context, concept, y, n, Yj,
                                                  Mj, intent, output)

    @staticmethod
    def generate_concepts(context):
        """
        Lists all formal concepts by a systematic search in the space of all
        formal concepts, avoiding to list the same concept multiple times by
        performing a canonicity test.

        Parameters
        ----------
        context : :py:class:`fca.Context`
            Context where the concepts should be found.

        Returns
        -------
        output : list
            List of concepts.
        """

        n = len(context.data[0])

        init_extent = context.down(np.full(n, False))
        init_intent = context.up(init_extent)
        concept = Concept(init_extent, init_intent)

        # Preallocating
        Yj = np.empty(n, dtype=bool)
        intent = np.empty(n, dtype=bool)
        Nj = [np.full(n, False)] * n

        output = []

        FastCloseByOne.fast_generate_from(context, concept, 0, n, Yj, Nj,
                                          intent, output)

        return output