Creazione dell'albero gerarchico dal dizionario dei contenuti delle pagine

Question

La seguente chiave: le coppie di valori sono 'page' e 'page content'.

{
  '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':''}
}

Per ogni dato 'oggetto' come posso trovare il / i percorso / i a detto articolo? Con la mia conoscenza molto limitata delle strutture di dati nella maggior parte dei casi, presumo che questo sarebbe un albero gerarchico. Per favore, correggimi se sbaglio!

AGGIORNAMENTO: Mi scuso, avrei dovuto essere più chiaro sui dati e sui risultati previsti.

Supponendo che 'page-a' sia un indice, ogni 'pagina' è letteralmente una pagina che appare su un sito Web, dove ogni 'articolo' è qualcosa come una pagina di prodotto che apparirebbe su Amazon, Newegg, ecc. p>

Pertanto, il mio output previsto per 'item-d' sarebbe un percorso (o percorsi) per quell'elemento. Ad esempio (il delimitatore è arbitrario, per l'illustrazione qui): item-d ha i seguenti percorsi:

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

AGGIORNAMENTO2: aggiornato il mio dict originale per fornire dati più precisi e reali. ".html" aggiunto per chiarimento.

Answer 1

Ecco un approccio semplice: è O (N al quadrato), quindi non molto scalabile, ma ti servirà bene per una dimensione del libro ragionevole (se hai, diciamo, milioni di pagine, devi pensare su un approccio molto diverso e meno semplice ;-).

Innanzitutto, crea un dict più utilizzabile, mappando la pagina in base al set di contenuti: ad esempio, se il dict originale è d , crea un altro dict mud come:

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

Quindi, fai in modo che il dict associ ciascuna pagina alle sue pagine padre:

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

Qui sto usando elenchi di pagine principali (anche i set andrebbero bene), ma va bene anche per le pagine con 0 o 1 genitori come nel tuo esempio - userai solo un elenco vuoto per significare " no parent " ;, altrimenti un elenco con il parent come unico e unico elemento. Questo dovrebbe essere un grafico diretto aciclico (in caso di dubbio, puoi controllare, ovviamente, ma sto saltando quel controllo).

Ora, data una pagina, trovare i percorsi che portano i suoi genitori verso un genitore senza genitori ("pagina principale") richiede semplicemente "camminare". il dict parent . Ad esempio, nel caso genitore 0/1:

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

Se puoi chiarire meglio le tue specifiche (intervalli di numero di pagine per libro, numero di genitori per pagina e così via), questo codice può senza dubbio essere perfezionato, ma spero che possa aiutarti.

Modifica : poiché l'OP ha chiarito che i casi con > 1 genitore (e quindi più percorsi) sono davvero interessanti, lascia che ti mostri come gestirlo:

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)

Naturalmente, invece di print ing, puoi cedere ogni percorso quando raggiunge una radice (trasformando la funzione il cui corpo è in un generatore), o altrimenti trattalo nel modo che desideri.

Modifica di nuovo : un commentatore è preoccupato per i cicli nel grafico. Se tale preoccupazione è giustificata, non è difficile tenere traccia dei nodi già visti in un percorso e rilevare e avvisare di eventuali cicli. Il più veloce è mantenere un set accanto a ciascun elenco che rappresenta un percorso parziale (abbiamo bisogno dell'elenco per l'ordinamento, ma il controllo dell'iscrizione è O (1) negli insiemi contro O (N) negli elenchi):

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

Probabilmente vale la pena, per chiarezza, impacchettare la lista e impostare che rappresenta un percorso parziale in una piccola classe di utilità Path con metodi adeguati.

Answer 2

Ecco un'illustrazione per la tua domanda. È più facile ragionare sui grafici quando hai una foto.

Per prima cosa, abbrevia i dati:

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

Risultato:

# 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':''}
}

Converti nel formato di 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, '}'

Risultato:

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;
}

Stampa il grafico:

$ dot -Tpng -O data.dot

Answer 3

MODIFICA Con la domanda spiegata un po 'meglio, penso che quanto segue potrebbe essere quello di cui hai bisogno, o potrebbe almeno fornire qualcosa di un punto di partenza.

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

Non so davvero cosa ti aspetti di vedere, ma forse qualcosa del genere questo funzionerà.

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

Sarebbe più facile, e penso più corretto, se lo usassi leggermente diversa struttura dei dati:

 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']}
 }

Quindi non dovresti dividere.

Dato l'ultimo caso, può anche essere espresso un po 'più breve:

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

E ancora più breve, con le liste vuote rimosse:

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

Dovrebbe essere una riga singola, ma ho usato \ come indicatore di interruzione di riga in modo che possa essere letto senza barre di scorrimento.