Erstellen Hierarchiebaum aus Wörterbuch Seiteninhalte
-
05-07-2019 - |
Frage
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.
Lösung
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 print
ing 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.
Andere Tipps
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
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.