Criação de árvore hierárquica do dicionário do conteúdo das páginas

Question

A seguinte chave:. Pares de valores são 'page' e 'conteúdo da 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 qualquer 'item' como eu poderia encontrar o caminho (s) para o referido produto? Com meu conhecimento muito limitado de estruturas de dados na maioria dos casos, eu estou supondo que esta seria uma árvore de hierarquia. Por favor me corrijam se eu estiver errado!

UPDATE: As minhas desculpas, eu deveria ter sido mais claro sobre os dados e meu resultado esperado.

A página-a 'Assumindo que é um índice, cada 'página' é, literalmente, uma página que aparece em um site, onde, como cada um 'item' é algo como uma página de produto que iria aparecer na Amazon, Newegg, etc.

Assim, a minha saída esperada para 'ponto-d' seria um caminho (ou caminhos) para esse item. Por exemplo (delimitador é arbitrária, para a ilustração aqui): ponto-d tem os seguintes caminhos:

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

UPDATE2: Atualizado meu dict original para fornecer dados mais precisos e reais. '.Html' adicionado para esclarecimentos.

Answer 1

Aqui está uma abordagem simples - é O (N ao quadrado), por isso, nem tudo o que altamente escalável, mas irá atendê-lo bem para um tamanho razoável livro (se você tem, digamos, milhões de páginas, você precisa ser o pensamento sobre uma abordagem muito diferente e menos simples; -).

Em primeiro lugar, fazer um dicionário mais utilizável, página de mapeamento de conjunto de conteúdos: por exemplo, se o dict original está d, fazer outra mud dict como:

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

Em seguida, faça o dict mapeamento de cada página para suas páginas pai:

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

Aqui, eu estou usando listas de páginas pai (conjuntos seria bom também), mas isso é OK para páginas com 0 ou 1 pais como no seu exemplo, também - você só vai estar usando uma lista vazia a média "nenhum pai", então uma lista com o pai como o único item. Este deve ser um grafo acíclico dirigido (se você estiver em dúvida, você pode verificar, é claro, mas eu estou saltando o cheque).

Agora, dada uma página, encontrar os caminhos até seu pai (s) a um parentless-pai ( "página raiz") simplesmente exigir "curta" a dict parent. Por exemplo, no caso 0/1 pai:

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

Se você pode esclarecer suas especificações melhor (faixas de número de páginas por livro, número de pais por página, e assim por diante), este código pode sem dúvida ser refinados, mas como começar espero que possa ajudar.

Editar : como o OP esclareceu que casos com> 1 pai (e, portanto, múltiplos caminhos) são realmente de interesse, deixe-me mostrar como é que lidar com isso:

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)

É claro que, em vez de printing, você pode yield cada caminho quando atinge uma raiz (fazendo a função cujo corpo é em um gerador), ou de outra forma tratá-lo da maneira que você precisa.

Editar novamente : um comentarista está preocupado com ciclos no gráfico. Se essa preocupação está garantido, não é difícil manter o controle de nós já visto em um caminho e detectar e alertar sobre quaisquer ciclos. Mais rápido é manter um conjunto ao lado de cada lista que representa um caminho parcial (eu preciso de uma lista de ordenação, mas a verificação de adesão é O (1) em conjuntos vs O (N) em 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,))

É provavelmente vale a pena, para maior clareza, a embalagem na lista e defina o que representa um caminho parcial em um pequeno caminho de classe utilitário com métodos adequados.

Answer 2

Aqui está uma ilustração para sua pergunta. É mais fácil raciocinar sobre gráficos quando você tem uma imagem.

Em primeiro lugar, abreviar os dados:

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

converter para o formato do 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;
}

Traçar o gráfico:

$ dot -Tpng -O data.dot

Answer 3

Editar Com a questão explicou um pouco melhor eu acho o seguinte pode ser o que você precisa, ou pelo menos poderia fornecer algo de um ponto 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

Eu realmente não sei o que você espera para ver, mas talvez algo como isso vai 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

Seria mais fácil, e eu acho mais correto, se você usaria um pouco estrutura de dados diferente:

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

Em seguida, você não precisa de divisão.

Dado que último caso, pode até ser expresso um pouco menor:

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

E ainda mais curto, com as listas vazias removidos:

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

Isso deve ser uma única linha, mas eu usei \ como indicador de quebra de linha para que ele possa ser lido sem barras de rolagem.