Erstellen Hierarchiebaum aus Wörterbuch Seiteninhalte

Question

Die folgenden Schlüssel:. Wertepaare sind ‚Seite‘ und ‚Seiteninhalte‘

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

Für jede gegebene ‚item‘ wie konnte ich den Weg (s) zu finden, sagte Artikel? Mit meinem sehr begrenzten Kenntnis von Datenstrukturen in den meisten Fällen gehe ich davon aus das ein Hierarchiebaum sein würde. Bitte korrigieren Sie mich, wenn ich falsch!

UPDATE: Ich entschuldige mich, ich sollte mehr Klarheit über die Daten und meine erwartete Ergebnis gewesen.

Unter der Annahme, ‚Seite-a‘ ist ein Index, jede ‚Seite‘ ist buchstäblich eine Seite auf einer Website erscheinen, wo, wie jeder ‚item‘ so etwas wie eine Produktseite, die auf Amazon, Newegg, etc. erscheinen würde.

Damit meine erwartete Ausgabe für ‚item-d‘ würde einen Weg (oder Pfade) zu diesem Artikel. Zum Beispiel (Trennzeichen sind frei wählbar, zur Veranschaulichung hier): item-d hat die folgenden Pfade:

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

UPDATE2: Aktualisiert meinen ursprünglichen dict genaue und reale Daten zur Verfügung zu stellen. '.Html' hinzugefügt für die Klarstellung.

Answer 1

Hier ist ein einfacher Ansatz - es ist O (N zum Quadrat), so, nicht alles, was hoch skalierbare, aber Sie werden auch für eine angemessene Buchgröße dienen (wenn Sie, sagen wir, Millionen von Seiten, müssen Sie denken über einen ganz anderen und weniger einfachen Ansatz; -).

Sie zunächst eine brauchbare dict, Mapping Seite von Inhalten zu setzen: zum Beispiel, wenn der ursprüngliche dict d ist, macht eine andere dict mud wie:

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

Dann machen den dict-Mapping jede Seite zu seinen übergeordneten Seiten:

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

Hier bin ich mit Listen der übergeordneten Seiten (Sets wäre auch in Ordnung), aber das ist für Seiten mit 0 oder 1 Eltern wie in Ihrem Beispiel zu OK - Sie müssen nur eine leere Liste verwenden zu bedeuten „kein Elternteil“, sonst eine Liste mit den Eltern als den einen und einzigen Punkt. Dies sollte ein azyklischen gerichteten Graphen sein (wenn Sie im Zweifel sind, können Sie natürlich prüfen, aber ich bin Skipping, dass der Check).

Jetzt gegeben, eine Seite, seine Eltern die Wege zu finden, bis (s) zu einem elternlos-Eltern ( „Root-Seite“) einfach benötigen „zu Fuß“, um die parent dict. Z. B. im 0/1 Mutter Fall:

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

Wenn Sie Ihren Angaben klären können besser (Bereiche Anzahl der Seiten pro Buch, die Anzahl der Eltern pro Seite, usw.), kann dieser Code kein Zweifel verfeinert werden, aber als Start hoffe, dass ich es kann helfen.

Bearbeiten : als OP stellte klar, dass Fälle mit> 1 Elternteil (und so, mehrere Pfade) in der Tat von Interesse sind, lassen Sie mich zeigen, wie mit dem gehe:

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)

Natürlich statt printing können Sie jeden Pfad yield, wenn er eine Wurzel erreicht (so dass die Funktion, dessen Körper das ist in einen Generator), oder auf andere Weise behandelt sie in welcher Weise auch immer Sie benötigen.

Sie Bearbeiten wieder : ein Kommentator über Zyklen in der Grafik besorgt ist. Wenn das Sorge ist garantiert, ist es nicht schwer, den Überblick von Knoten zu halten bereits in einem Pfad zu sehen und erkennen und über alle Zyklen zu warnen. Schnellste ist neben jeder Liste einen Satz zu halten einen Teilpfad darstellt (wir benötigen die Liste für die Bestellung, aber für die Mitgliedschaft Überprüfung ist O (1) in den Sätzen vs O (N) in Listen):

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

Es ist wohl die Mühe wert, für Klarheit, die Liste der Verpackung und setzt einen Teil Weg in einen kleinen Utility-Klasse-Pfad mit geeigneten Methoden darstellen.

Answer 2

Hier ist eine Illustration für Ihre Frage. Es ist leichter, über Graphen zu folgern, wenn Sie ein Bild haben.

Zuerst abkürzen die Daten:

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

Ergebnis:

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

Konvertieren

zu graphviz das Format:

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

Ergebnis:

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

Zeichnen Sie die grafische Darstellung:

$ dot -Tpng -O data.dot

Answer 3

Bearbeiten Mit der Frage ein wenig besser erklärt denke ich, die folgende sein könnte, was Sie benötigen, oder zumindest etwas von einem Ausgangspunkt bieten könnte.

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

Ich weiß nicht wirklich, was Sie erwarten zu sehen, aber vielleicht so etwas wie dies funktionieren wird.

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

Es wäre einfacher, und ich denke, mehr korrekt, wenn Sie ein wenig verwenden würden unterschiedliche Datenstruktur:

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

Dann würden Sie nicht brauchen, zu trennen.

In Anbetracht, dass im letzten Fall kann es sogar ein bisschen kürzer ausgedrückt werden:

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

Und noch kürzer, wobei die leeren Listen entfernt:

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

Das sollte eine einzige Zeile, aber ich verwende \ als Zeilenumbruch Indikatoren so kann es zu lesen ohne Scrollbalken.