ruleset.py

# Léo Duret - May 2019
# For AGFLOW


class RuleSet(object):
    """
        Holds Dependencies and Conflict rules adding the abilitty
        to check coherence of them.
    """

    def __init__(self):
        # Will hold the element of the set and their matrix indexes.
        self.elements = dict()

        # Holding the conflicts and dependencies.
        self.confs = list()
        self.deps = list()

        # Will be filled when matrix is created.
        self.matrix = None

    def _update_table(self, one):
        # Adds new elements to table by checking if the key exists.
        if one not in self.elements:
            self.elements[one] = len(self.elements)

    def addDep(self, one, other):
        # Making sure the dependencies have a element in the set.
        self._update_table(one)
        self._update_table(other)

        self.deps.append((one, other))

    def addConflict(self, one, other):
        # Making sure the conflicts have a element in the set.
        self._update_table(one)
        self._update_table(other)

        self.confs.append((one, other))

    def _add_deps(self):
        # Adding the dependencies the the matrix by fetching the index
        # and setting the coordinates to 1.
        for one, other in self.deps:
            y = self.elements.get(one)
            x = self.elements.get(other)

            # Coordinates should never be None but maintaining intergrity.
            assert(x is not None and y is not None)
            self.matrix[y][x] = 1

    def _add_conflicts(self):
        # Adding the conflicts to the matrix by fetching the index
        # and setting the coordinates to 2.
        for one, other in self.confs:
            y = self.elements.get(one)
            x = self.elements.get(other)

            # Coordinates should never be None but maintaining intergrity.
            assert(x is not None and y is not None)
            self.matrix[y][x] = 2
            self.matrix[x][y] = 2

    def make_matrix(self):
        # Create the matrix.

        # Using double list comprehension to create identity matrix because
        # values depend on themsleves.
        self.matrix = [
            [
                0 if o != i else 1
                for o in self.elements
            ]
            for i in self.elements
        ]

        # See fonction definition
        self._add_deps()

        # Extending dependencies such as A->B, B->C then A->C.
        for y in range(len(self.matrix)):
            for x in range(len(self.matrix[y])):
                if self.matrix[y][x] == 1:
                    for i in range(len(self.matrix[x])):
                        if self.matrix[x][i] == 1:
                            self.matrix[y][i] = 1

    def isCoherent(self):
        # Checking coherence such that if A->B and B-/>A then it's false.

        # Reset matrix.
        self.make_matrix()

        # Iterating conflicts
        for one, other in self.confs:
            y = self.elements.get(one)
            x = self.elements.get(other)
            assert(x is not None and y is not None)

            # Checking if a conflict lands on a dependency -> False
            if self.matrix[x][y] == 1 or self.matrix[y][x] == 1:
                return False
            else:
                # Cant' have dependencies between elements in conflict
                for line in self.matrix:
                    if line[x] == 1 and line[y] == 1:
                        return False
            # Adding conflicts
            self._add_conflicts()

        # No coherence errors found
        return True


class Options(object):
    """
        Container for selected elements, used the RuleSet matrix to
        determin dependencies and conflicts
    """

    def __init__(self, rs):
        # Assuring the class the used in the right context.
        assert(isinstance(rs, RuleSet))
        self.rs = rs

        # Selected elements set.
        self.opts = set()

    def _get_chain(self, arg):
        # Get all inline dependencies.
        ret_set = set()

        index = self.rs.elements.get(arg)
        line = self.rs.matrix[index]

        for i in range(len(line)):
            key = list(self.rs.elements.keys())[i]
            if line[i] == 1 and key not in ret_set:
                ret_set.add(key)

        return ret_set

    def toggle(self, arg):
        # Keep the matrix up to date.
        self.rs.make_matrix()

        # Set of elements that will be removed.
        rm = set()

        # Set of dependencies of the argument.
        toolchain = self._get_chain(arg)

        # Case in which we need to unselect.
        if arg in self.opts:
            index = self.rs.elements.get(arg)
            # Going through the column of the argument to remove
            # every thing that depend on it.
            for i in range(len(self.rs.matrix)):
                key = list(self.rs.elements.keys())[i]
                # if dependency in toolchain remove it
                if self.rs.matrix[i][index] == 1 and key in toolchain:
                    rm.add(key)
            self.opts -= rm

        # Case in which we select and element.
        else:
            # Checking for conflict in the dependency chain.
            for dep in toolchain:
                for conf in self.rs.confs:
                    # If there is a conflict get the dependencies
                    # of the conflictuous argument and add them to remove set.
                    rest = set(conf) - set(dep)
                    other = rest.pop()
                    if other in self.opts:
                        rm = rm.union(self._get_chain(other))
            self.opts -= rm

            # add all the new items dependencies.
            self.opts = self.opts.union(toolchain)

    def selection(self):
        # Returning all the selected options as a set of strings.
        return set(str(key) for key in self.opts)

solution.md

Dependencies, Conflict and Coherence

Datastructure

To model dependencies and conflict I used a matrix. The entries worked the following way Y has a dependency with X. So every Y that depended on X were in the X column, and every dependecy of Y were in the Y line.

| | X:0 | X:1 | |-----------------| | Y:0 | 1 | 1 | | Y:1 | 0 | 1 |

I used two classes as called in the unit test.

The first one beeing the RuleSet class which contained three data containers:

• A dictionnary to store the keys and table index of the matrix
• One list to store the dependencies as tuples (Y, X) can be read as Y depends on X.
• Another list to store conflict using the same method as for dependencies, however conflicts have no order and (X, Y) == (Y, X)

The second class Options is a wrapper around the RuleSet class to keep track of the selected options to keep track of the selected options I used a set to be able to use set maths to add and remove elements quicker.

Algorithms

RuleSet -> Coherence

To determine the coherence of a Ruleset you first need to build it from the informations given by the user. You just get the indexes from the dictionnary and enter 0 for no relationship and 1 for dependency.

The second part when you build the dependencies is to extend them on each line, this means that if A depends on B and B on C then A depends on C. I implemented this using the built matrix, fetching (in this example) all the B dependencies and adding them to A.

Last part of the coherence check is only to verify that where you need to put the conflict there are no dependencies already. Else we mark the valid conflict with a 2 value.

Options -> Toggling

Toggling comes in two parts, the first beeing if the object is not already toggled and if it is. If it is not you walk through the matrix and add all key that correspond to a 1 value in the matrix. Then you need to add the dependencies of these as well.

The second part is to remove already existing dependencies from the set For this you need to remove all element that depend on the element you are removing which means reading the matrixs column.