Graph algorithms: Requirements Resolution

Tutorials

electricmonk

https://www.electricmonk.nl/docs/dependency_resolving_algorithm/dependency_resolving_algorithm.html

Overview

1. Recurse to the leaf-node(s) of each pathway through graph.

Recurse to the leaf-node(s) of each pathway through graph. Do not modify requirements.

# step 1
    +
    |
    +
   /
  +

2.

On the way back upwards from the bottom, append nodes. This way the deepest nodes (with no requirements) are added first, only afterwards followed by nodes with requirements.

# step 2

    +
    |
    +
   /
  o
  
  # step 3
    +
    |
    +
   /|
  o o
  
  # step 4
    +
    |
    +
   /|\
  o o o
  
  # step 5
    +
    |
    o
   /|\
  o o o

3.

We can ignore repeated nodes, since we know it is impossible for their dependencies not to have already been added.

      A
      ++
     /  \
   B     C   F
   +  \  +  /
   |   \ | +
   D    +E

Navigating it with left-first works

# left paths
reqs = [D]           # children of B
reqs.extend([B])     # child of A (left)

# right paths
reqs.extend([F])     # children of E  (skip B, already seen)
reqs.extend([E])     # children of C
reqs.extend([C])     # child of A (right)

# top
reqs.append(A)

reqs = [D, B, F, E, C, A]

Navigating it right-first also works

# right paths
reqs = [F]          # child of E (right)
reqs.extend([D])    # child of B
reqs.extend([B])    # child of E (left)
reqs.extend([E])    # child of C
reqs.extend([C])    # child of A (right)

# left paths
reqs.extend([D])    # children of B
reqs.extend([])     # child of A (left) (skip B, already seen)

# top
reqs.append(A)

reqs = [F, D, B, E, C, A]

Code

class InvalidGraph(Exception):
    pass


class Requirement(object):
    @property
    def name(self):
        return self._name

    def __init__(self, name):
        """ Constructor.
        Args:
            name (str): ``(ex: 'mysoftware')``
                name or unique-identifier of this requirement.
        """
        super(Requirement, self).__init__()
        self._name = name
        self._requires = []

    def __eq__(self, requirement):
        """ Does `requirement` name match this object's name?
        Args:
            requirement (Requirement):
                requirement you are checking for in this object's requirements
        Returns:
            bool: True if equal
        """
        self._validate_type_requirement(requirement)
        return self.name == requirement.name

    def __repr__(self):
        return '<Requirement({}) at {}>'.format(self.name, hex(id(self)))

    def __str__(self):
        """ When converted to a string, returns name.
        """
        return self.name

    def __neq__(self, requirement):
        """ Does `requirement` name match this object's name?
        Args:
            requirement (Requirement):
                requirement you are checking for in this object's requirements
        Returns:
            bool: True if not-equal
        """
        self._validate_type_requirement(requirement)
        return not self.__eq__(requirement)

    def __contains__(self, requirement):
        """ Does `requirement` exist anywhere in this requirements-tree?
        Args:
            requirement (Requirement):
                requirement you are checking for in this object's requirements
        """
        self._validate_type_requirement(requirement)
        requirements = self.resolve()
        return requirement in requirements

    def _validate_type_requirement(self, requirement):
        """
        Args:
            requirement (Requirement):  object being validated
        Raises:
            TypeError:                  if provided `requirement` is not correct type
        """
        if not isinstance(requirement, Requirement):
            msg = ('expected `requirement` to be of type {}. \n'
                   'Received: {}').format(self.__class__.__name__, repr(type(requirement)))
            raise TypeError(msg)

    def add_requirement(self, requirement):
        """ Add a requirement to this node.
        Args:
            requirement (Requirement):
                a requirement object
        """
        self._validate_type_requirement(requirement)
        if requirement in self._requires:
            return
        self._requires.append(requirement)

    def resolve(self, _requirements=None, _seen=None):
        #: final list of requirements (added after children)
        if _requirements is None:
            _requirements = []

        #: detects cyclical dependencies (added before children)
        if _seen is None:
            _seen = []

        _seen.append(self)
        for requirement in self._requires:
            # skip requirements that have been added
            if requirement in _requirements:
                continue
            # detect cycle
            if requirement in _seen:
                msg = 'Dependency-Cycle detected involving requirement: "{}"'.format(repr(requirement))
                raise InvalidGraph(msg)
            requirement.resolve(_requirements, _seen)
        _requirements.append(self)
        return _requirements