Implementación del árbol de dependencias

Para aquellos que usaron apt-get, usted sabe que cada vez que instala / desinstala algo, recibe las notificaciones que dicen que necesita / ya no necesita ciertas dependencias.

Estoy tratando de entender la teoría detrás de esto y potencialmente implementar mi propia versión de esto. He hecho un poco de google, se me ocurrió la mayoría de cosas de acoplamiento. Por lo que entiendo, el acoplamiento es de 2 clases / módulos que dependen unos de otros. Esto no es exactamente lo que estoy buscando. Lo que busco es más como una generación de árbol de dependencias, donde puedo encontrar el módulo menos dependiente (ya he hecho una forma recursiva de hacer esto) y (esta es la parte que no he hecho) encontrar lo que Ya no es necesario después de eliminar un nodo.

Además, ¿ayudaría aprender sobre teoría de grafos? ¿Y hay algún tutorial sobre el uso de Python como idioma?

La teoría de grafos es el camino a seguir.

Un gráfico es solo un conjunto de lugares (vértices) con caminos (bordes) entre ellos, y en particular estamos hablando de un gráfico dirigido, que significa caminos de un solo sentido. Descubrir dependencias significa, básicamente, descubrir todos los lugares que pueden llegar a una ciudad en particular a lo largo de las carreteras de un solo sentido.

Así que ahora, tienes un montón de módulos, que se convierten en tus vértices. Digamos que tenemos A y B, y sabemos que B depende de A, así que hay un borde dirigido, una “vía de un solo sentido”, de A a B.

Si C depende de B, entonces tienes A → B → C.

Formalmente, una gráfica es solo una colección de vértices y pares (ordenados) de vértices, llamados bordes. Quieres un algoritmo gráfico llamado “ordenamiento topológico”, y ahora tienes algo que leer.

Esto podría ser de algún interés:

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, vt) 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) 

Escribí una herramienta para encontrar y dibujar las dependencias entre los paquetes de Python en PyPi. Es la gula

Y utilicé para analizar las dependencias de alguna biblioteca que estoy usando. Aquí están algunos de los diagtwigs:

introduzca la descripción de la imagen aquíintroduzca la descripción de la imagen aquí

No estoy seguro de que es esto lo que quieres. Si es así, puedes leer el código fuente aquí , es un proyecto de código abierto. Para más diagtwigs de dependencias, puedes ver la galería.

Hablando de cómo lo implemento, para encontrar dependencias de paquetes, uso pip como backend. Para dibujar diagtwigs, uso Networkx .

  1. Camina el viejo árbol de la dependencia. Construye un set de todos los elementos en él.
  2. Camina el nuevo árbol de dependencias. Haz lo mismo que antes.
  3. Resta el último set del anterior. El resultado es tu respuesta.

Alternativamente:

  1. Camina el viejo árbol de la dependencia. En cada nodo, almacene la cantidad de cosas que dependen de (apuntan a) ese nodo.
  2. Elimina el elemento que deseas eliminar. Siga todas sus dependencias y reduzca su recuento de uso en 1. Si la disminución de esta manera reduce el recuento de un nodo a 0, ya no es necesario.

El primero es más simple de implementar, pero menos eficiente. Este último es eficiente, pero más difícil de implementar.

Creo que el paso que está buscando es diferenciar entre los paquetes que ha instalado explícitamente y los que son dependencias. Una vez que haya hecho esto, puede crear árboles de dependencia de todos los paquetes solicitados y comparar el conjunto de estos paquetes con el conjunto de paquetes instalados . Al XORing estos, asumiendo que todos los paquetes solicitados están instalados, debería darle el conjunto de todos los paquetes de los que ya no se depende.