decir que tenemos algunos artículos, y cada uno define unas reglas de clasificación parciales, así:orden de clasificación parcial?
estoy
A
y quiero ser antesB
estoy
C
y yo quiero estar despuésA
pero antesD
Así que tenemos artículos A,B,C,D
con estas reglas:
A>B
C<A
,C>D
- nada más! Por lo tanto,
B
yD
no tienen 'preferencias' en el pedido y se consideran iguales.
Como ve, las reglas de relación transitiva no funcionan aquí. Sin embargo, si A>B
todavía significa que B<A
. Por lo tanto, no puede haber varios posibles resultados de la clasificación:
- A B C D
- A C D B
- A C B D
- A B C D
¿Cómo puedo implementar un algoritmo de ordenación que se encarga de esta situación?
La razón: hay múltiples módulos de carga dinámica, y algunos de ellos dependen '' a los demás de una manera. Cada módulo puede declarar reglas simples, en relación con otros módulos:
me carga antes de módulo A
a cargar después de módulo B
a cargar antes del módulo A, pero después de módulo B
ahora tengo que poner en práctica este ordenamiento de alguna manera .. :)
Respuesta: code por Paddy McCarthy (MIT)
## {{{ http://code.activestate.com/recipes/577413/ (r1)
try:
from functools import reduce
except:
pass
data = {
'des_system_lib': set('std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee'.split()),
'dw01': set('ieee dw01 dware gtech'.split()),
'dw02': set('ieee dw02 dware'.split()),
'dw03': set('std synopsys dware dw03 dw02 dw01 ieee gtech'.split()),
'dw04': set('dw04 ieee dw01 dware gtech'.split()),
'dw05': set('dw05 ieee dware'.split()),
'dw06': set('dw06 ieee dware'.split()),
'dw07': set('ieee dware'.split()),
'dware': set('ieee dware'.split()),
'gtech': set('ieee gtech'.split()),
'ramlib': set('std ieee'.split()),
'std_cell_lib': set('ieee std_cell_lib'.split()),
'synopsys': set(),
}
def toposort2(data):
for k, v in data.items():
v.discard(k) # Ignore self dependencies
extra_items_in_deps = reduce(set.union, data.values()) - set(data.keys())
data.update({item:set() for item in extra_items_in_deps})
while True:
ordered = set(item for item,dep in data.items() if not dep)
if not ordered:
break
yield ' '.join(sorted(ordered))
data = {item: (dep - ordered) for item,dep in data.items()
if item not in ordered}
assert not data, "A cyclic dependency exists amongst %r" % data
print ('\n'.join(toposort2(data)))
## end of http://code.activestate.com/recipes/577413/ }}}
+1 Spot-on con la terminología. Hay muchas implementaciones de Python (por ejemplo, [ésta] (http://www.bitformation.com/art/python_toposort.html)) si OP necesita. – marcog
¡Ayudó mucho, gracias! Sin embargo, esto tiene poco que ver con los gráficos en su implementación. La lógica es: 0. crear una lista vacía 'ordenado'. 1. recorra la lista, elija el elemento más pequeño 'min' (en comparación con todos los demás). Puede haber varios más pequeños, elegir cualquiera. 2. Agregue 'min' a' sorted' 3. Si hay más elementos, vuelva a '1' – kolypto
@o_O Tync La única diferencia es que su versión es' O (n^2) ', donde 'apropiada' topológicamente la ordenación funciona en 'O (E)' (donde 'E' es el número de bordes-dependencias). En cuanto a la relación con los gráficos, toda su estructura es un gráfico, le guste o no :) –