mvjw9a
Last Updated: February 20, 2018
·
2.383K
· oz123

Recursively finding dependencies in Python

Here is how you can find a list of dependencies of Python classes, given that a class has an
attribute depends. This list is not topologically sorted, but it is very easy to use with a topological sort algorithm.
Using recursion and generator it is possible to get a complete list of dependecies given that

start_dependecie = {'A': 'B'}

This means that class A depends on class B. But what if class B depends on N other classes?
The following will do the job:

#!/usr/bin/env python
def _yield_name_dep(rules_deps):
    # yield all rules by their name and dependencies
    for rule, dep in rules_deps.items():
        if not dep:
            yield rule, dep
            continue
        else:
            yield rule, dep
            for ii in dep:
                i = getattr(rules, ii)
                instance = i()
                if instance.depends:
                    new_dep={str(instance): instance.depends}
                    for dep in _yield_name_dep(new_dep):
                        yield dep    
                else:
                    yield str(instance), instance.depends

Here is how you can easily test the above method:

demo_class_content ="""
class A(object):
    depends = 'B'

    def __str__(self):
        return self.__class__.__name__

class B(object):
    depends = ('C','F')

    def __str__(self):
        return self.__class__.__name__

class C(object):
    depends = ('D', 'E')

    def __str__(self):
        return self.__class__.__name__


class D(object):
    depends = None

    def __str__(self):
        return self.__class__.__name__


class F(object):
    depends = 'E'

    def __str__(self):
        return self.__class__.__name__

class E(object):
    depends = None

    def __str__(self):
        return self.__class__.__name__
"""       

with open('demo_classes.py', 'w') as clsdemo:
    clsdemo.write(demo_class_content)

import demo_classes as rules

rule_start={'A': 'B'}


recursion_counter = 0
def _yield_name_dep(rules_deps):
    global recursion_counter
    recursion_counter = recursion_counter +1 
    # yield all rules by their named and dependencies
    for rule, dep in rules_deps.items():
        if not dep:
            yield rule, dep
            continue
        else:
            yield rule, dep
            for ii in dep:
                i = getattr(rules, ii)
                instance = i()
                if instance.depends:
                    new_dep={str(instance): instance.depends}
                    for dep in _yield_name_dep(new_dep):
                        yield dep    
                else:
                    yield str(instance), instance.depends

if __name__ == '__main__':
    rule_dependencies = list(set(_yield_name_dep(rule_start)))
    print recursion_counter
    print rule_dependencies

The output should be:

4
[('B', ('C', 'F')), ('C', ('D', 'E')), ('E', None), ('F', 'E'), ('D', None), ('A', 'B')]

4 Responses
Add your response

9898

If your only requirement here is to get a full list of dependencies, why not use inspect.getmro? For example: http://codepad.org/k7iGWYFf

Although I might be off with what your requirements are because I noticed there isn't any actual inheritance going on in your example.

over 1 year ago ·
9900

Hi Demian,
First of all, I didn't know about ├Čnspect.mro. Thanks for that one. Second, yep, my idea was that these class can represent anything (e.g. rules, package dependencies) so they don't necessarily inherit like Python objects, but the have a dependencies. Kind of like decencies solving in packages. So, it was done for the exercise, and I wanted to share my experience and see if I get some feedback.

over 1 year ago ·
9909

No worries, always happy to share the knowledge of the Python stdlib :)

I'm still at a bit of a loss as to how this can't be solved by common Python functions. i.e. if your requirements are to add package dependencies, that should be solved by pip/setuptools (requirements.txt or setup.py or a combination of). Python has introspection capabilities second to none. If you need to look up the inheritance tree of a class, you can easily do so (although I understand that this isn't your particular use case).

Here are the major flaws I see with your solution (of course, just IMHO, so take it with a grain of salt :)):

  1. It doesn't conform to standards. Someone looking at this (especially one who has spent quite a bit of time with Python) is likely to to say "wat?". The stdlib and supporting cast should /always/ be exhausted prior to rolling your own solution. Not only will you benefit from a solution that's thoroughly tested (and reviewed by core devs), but you'll also benefit from learning about areas of the stdlib that you were previously unaware.
  2. Huge margin for human error. At any point, a programmer can forget to add a dependency. As your code base grows, I'd imagine that the problems would be more and more difficult to track down.
  3. The attribute name is confusing. "Dependencies" in OO-land (not saying that Python is strictly OO, I'm simply referring to your examples) means "base classes that this class depends on". Introducing a "depends" attribute to a class that has a different function would likely be confusing to those reading your code. (I also realize that this can be trivially changed, just calling it out as it's in your example)
over 1 year ago ·
9917

With all three arguments you are right.
I would always opt for stdlib. However, with packages I didn't necessarily mean Python packages.
The idea was to write a code that should work on similar cases. Not always on classes.
Imagine you wrote your own package manager (for Distro X) then you will need something.
Yep, you are right dependencies are forgotten. This is the case with RPMs or DEBs. Package x gets dependency y and the maintainer forgets to add it.
This code was not meant to conform to standard.
It was slightly altered from a project I worked for which something similar to package management. In order not complicate stuff and make it clear for fellow programmers, I chose to talk about classes. It was a wrong choice.
Never the less, I find the discussion, interesting and I learned already a lot just from the discussion with you. Therefore thank you for the discussion and extended comments.

over 1 year ago ·