Geek asks and answers

Dependency Tree Implementation

For those who used apt-get, you know that every time you install / uninstall something, you get notifications saying that you need / no longer need certain dependencies.

I am trying to understand the theory behind this and potentially implement my own version of it. I did some searches, came up mainly with communication material. From what I understand, communication is 2 classes / modules that depend on each other. This is not exactly what I am looking for. What I'm looking for is more like generating a dependency tree, where I can find the least dependent module (I already did a recursive way to do this), and (this is the part I haven't done yet), finding that it is no longer required after removal node.

Also, will studying graph theory help? And are there any tutorials in which it is desirable to use Python as a language?

+3
source share
5 answers

Graph theory is the way to go.

A graph is just a bunch of places (peaks) with roads (edges) between them, and in particular we are talking about an oriented graph, which means one-way roads. Finding out dependencies basically means finding out all the places that can reach a certain city along one-way roads.

So now you have a bunch of modules that become your vertices. Let them say that we have A and B, and we know that B depends on A, therefore there is a directional edge - a "one-way road" - from A to B.

If C depends on B, then you have A → B → C.

() , . " ", .

+3

:

def dep(arg):
    '''
        Dependency resolver

    "arg" is a dependency dictionary in which
    the values are the dependencies of their respective keys.
    '''
    d=dict((k, set(arg[k])) for k in arg)
    r=[]
    while d:
        # values not in keys (items without dep)
        t=set(i for v in d.values() for i in v)-set(d.keys())
        # and keys without value (items without dep)
        t.update(k for k, v in d.items() if not v)
        # can be done right away
        r.append(t)
        # and cleaned up
        d=dict(((k, v-t) for k, v in d.items() if v))
    return r

if __name__=='__main__':
    d=dict(
        a=('b','c'),
        b=('c','d'),
        e=(),
        f=('c','e'),
        g=('h','f'),
        i=('f',)
    )
    print dep(d)
+5

Python PyPi. gluttony

, . :

enter image description hereenter image description here

, , . , , . gallery

, , , pip . Networkx.

+4
  • . set .
  • . , .
  • set . .

:

  • . node , (point to), node.
  • , . 1. node 0, .

, . , .

0

I think the step you are looking for is to distinguish between the packages you have installed and those that are dependent. After that, you can build the dependency trees of all the requested packages and compare the set of these packages with the set of installed packages. XORing, provided that all requested packages are installed, should provide you with a set of all packages that it no longer depends on.

0
source

More articles:


All Articles