Creación de árbol jerárquico a partir del diccionario de contenidos de las páginas.

Question

Los siguientes pares clave: valor son 'página' y 'contenido de la página'.

{
  'section-a.html':{'contents':'section-b.html section-c.html section-d.html'},
  'section-b.html':{'contents':'section-d.html section-e.html'},
  'section-c.html':{'contents':'product-a.html product-b.html product-c.html product-d.html'},
  'section-d.html':{'contents':'product-a.html product-c.html'},
  'section-e.html':{'contents':'product-b.html product-d.html'},
  'product-a.html':{'contents':''},
  'product-b.html':{'contents':''},
  'product-c.html':{'contents':''},
  'product-d.html':{'contents':''}
}

Para cualquier 'elemento' dado, ¿cómo puedo encontrar la (s) ruta (s) a dicho elemento? Con mi conocimiento muy limitado de las estructuras de datos en la mayoría de los casos, asumo que esto sería un árbol jerárquico. ¡Por favor corrígeme si me equivoco!

ACTUALIZACIÓN: Mis disculpas, debería haber sido más claro sobre los datos y mi resultado esperado.

Suponiendo que 'page-a' es un índice, cada 'página' es literalmente una página que aparece en un sitio web, donde cada 'elemento' es algo así como una página de producto que aparecería en Amazon, Newegg, etc.

Por lo tanto, mi salida esperada para 'item-d' sería una ruta (o rutas) a ese artículo. Por ejemplo (el delimitador es arbitrario, para ilustración aquí): item-d tiene las siguientes rutas:

page-a > page-b > page-e > item-d
page-a > page-c > item-d

ACTUALIZACIÓN2: Actualicé mi dict original para proporcionar datos más precisos y reales. '.html' agregado para aclaración.

Answer 1

Este es un enfoque simple: es O (N al cuadrado), por lo tanto, no es tan escalable, pero le servirá para un tamaño de libro razonable (si tiene, por ejemplo, millones de páginas, debe estar pensando) sobre un enfoque muy diferente y menos simple ;-).

Primero, cree un dictado más útil, asigne una página a un conjunto de contenidos: por ejemplo, si el dict original es d , cree otro dict barro como:

mud = dict((p, set(d[p]['contents'].split())) for p in d)

Luego, realice el dictado asignando cada página a sus páginas principales:

parent = dict((p, [k for k in mud if p in mud[k]]) for p in mud)

Aquí, estoy usando listas de páginas principales (los conjuntos también estarían bien), pero eso está bien para las páginas con 0 o 1 padres como en tu ejemplo, también usarás una lista vacía para indicar " ningún padre " ;, sino una lista con el padre como el único elemento. Este debe ser un gráfico dirigido acíclico (si tiene dudas, puede verificarlo, por supuesto, pero me estoy saltando ese control).

Ahora, dada una página, encontrar las rutas de acceso de sus padres a un padre sin padres (" página raíz ") simplemente requiere " caminar " el padre dict. Por ejemplo, en el caso principal 0/1:

path = [page]
while parent[path[-1]]:
  path.append(parent[path[-1]][0])

Si puede aclarar mejor sus especificaciones (rangos de número de páginas por libro, número de padres por página, etc.), este código puede sin duda ser refinado, pero para empezar, espero que pueda ayudar.

Editar : cuando el OP aclaró que los casos con > 1 padre (y por lo tanto, las múltiples rutas) son de interés, déjame mostrarte cómo lidiar con eso:

partial_paths = [ [page] ]
while partial_paths:
  path = partial_paths.pop()
  if parent[path[-1]]:
    # add as many partial paths as open from here
    for p in parent[path[-1]]:
      partial_paths.append(path + [p])
  else:
    # we've reached a root (parentless node)
    print(path)

Por supuesto, en lugar de print ing, puede ceder cada ruta cuando llega a una raíz (haciendo que la función cuyo cuerpo está en un generador), o de otra manera trátela de la forma que necesite.

Editar de nuevo : un comentarista está preocupado por los ciclos en el gráfico. Si se justifica esa preocupación, no es difícil hacer un seguimiento de los nodos ya vistos en una ruta y detectar y avisar sobre cualquier ciclo. Lo más rápido es mantener un conjunto junto a cada lista que represente una ruta parcial (necesitamos la lista para ordenar, pero la verificación de la membresía es O (1) en los conjuntos frente a O (N) en las listas):

partial_paths = [ ([page], set([page])) ]
while partial_paths:
  path, pset = partial_paths.pop()
  if parent[path[-1]]:
    # add as many partial paths as open from here
    for p in parent[path[-1]]:
      if p in pset:
        print('Cycle: %s (%s)' % (path, p))
        continue
      partial_paths.append((path + [p], pset.union([p])))
  else:
    # we've reached a root (parentless node)
    print('Path: %s' % (path,))

Probablemente valga la pena, para mayor claridad, empaquetar la lista y el conjunto que representa una ruta parcial en una ruta de clase de utilidad pequeña con los métodos adecuados.

Answer 2

Aquí hay una ilustración para su pregunta. Es más fácil razonar sobre los gráficos cuando tienes una imagen.

Primero, abrevia los datos:

#!/usr/bin/perl -pe
s/section-([a-e])\.html/uc$1/eg; s/product-([a-e])\.html/$1/g

Resultado:

# graph as adj list
DATA = {
  'A':{'contents':'B C D'},
  'B':{'contents':'D E'},
  'C':{'contents':'a b c d'},
  'D':{'contents':'a c'},
  'E':{'contents':'b d'},
  'a':{'contents':''},
  'b':{'contents':''},
  'c':{'contents':''},
  'd':{'contents':''}
}

Convertir al formato de graphviz:

with open('data.dot', 'w') as f:
    print >> f, 'digraph {'
    for node, v in data.iteritems():
        for child in v['contents'].split():
            print >> f, '%s -> %s;' % (node, child),
        if v['contents']: # don't print empty lines
            print >> f
    print >> f, '}'

Resultado:

digraph {
A -> C; A -> B; A -> D;
C -> a; C -> b; C -> c; C -> d;
B -> E; B -> D;
E -> b; E -> d;
D -> a; D -> c;
}

Dibuja la gráfica:

$ dot -Tpng -O data.dot

Answer 3

EDIT Con la pregunta un poco mejor, creo que lo siguiente podría ser lo que necesitas, o al menos podría proporcionar algo de un punto de partida.

data = {
  'section-a.html':{'contents':'section-b.html section-c.html section-d.html'},
  'section-b.html':{'contents':'section-d.html section-e.html'},
  'section-c.html':{'contents':\
                    'product-a.html product-b.html product-c.html product-d.html'},
  'section-d.html':{'contents':'product-a.html product-c.html'},
  'section-e.html':{'contents':'product-b.html product-d.html'},
  'product-a.html':{'contents':''},
  'product-b.html':{'contents':''},
  'product-c.html':{'contents':''},
  'product-d.html':{'contents':''}
}

def findSingleItemInData(item):
    return map( lambda x: (item, x), \
                [key for key in data if data[key]['contents'].find(item) <> -1])

def trace(text):
    searchResult = findSingleItemInData(text)
    if not searchResult:
        return text

    retval = [] 
    for item in searchResult:
        retval.append([text, trace(item[-1])]) 

    return retval

print trace('product-d.html')

OLD

Realmente no sé lo que esperas ver, pero tal vez algo como esto funcionará.

data = {
   'page-a':{'contents':'page-b page-c'},
   'page-b':{'contents':'page-d page-e'},
   'page-c':{'contents':'item-a item-b item-c item-d'},
   'page-d':{'contents':'item-a item-c'},
   'page-e':{'contents':'item-b item-d'}
}

itemToFind = 'item-c'

for key in data:
  for index, item in enumerate(data[key]['contents'].split()):
    if item == itemToFind:
      print key, 'at position', index

Sería más fácil, y creo que más correcto, si usas un poco diferente estructura de datos:

 data = {
   'page-a':{'contents':['page-b', 'page-c']},
   'page-b':{'contents':['page-d', 'page-e']},
   'page-c':{'contents':['item-a', 'item-b item-c item-d']},
   'page-d':{'contents':['item-a', 'item-c']},
   'page-e':{'contents':['item-b', 'item-d']}
 }

Entonces no necesitarías dividirte.

Dado el último caso, incluso se puede expresar un poco más corto:

for key in data:
    print [ (key, index, value) for index,value in \
             enumerate(data[key]['contents']) if value == 'item-c' ]

Y aún más corto, con las listas vacías eliminadas:

print filter(None, [[ (key, index, value) for index,value in \ 
       enumerate(data[key]['contents']) if value == 'item-c' ] for key in data])

Debería ser una sola línea, pero utilicé \ como indicador de salto de línea para que pueda leerse sin barras de desplazamiento.