Adjacency List (dict) kumuliert aus Adjacency List (dict)

[Auctor]

Hallo Zusammen,

ich hätte eine Frage bzw. hab ein Problem bei dem ich nicht weiter komme. Folgende Problemstellung:

Ich generiere aus einer Datenbank eine Adjacency list welche als dict aufgebaut ist:

{'Knoten1': [('Knoten2',1),
('Knoten3',1),
('Knoten4', 1)],
'Knoten2': [('Knoten1',1),
('Knoten3',1),
('Knoten4', 1)],
.
.
.}

Also erst mal eine Matrix in der jedes Element eine Verknüpfung (mit dem Gewicht 1) zu jedem anderen Element hat ausser sich selbst. Soweit so gut.

Nun möchte ich aber aus einer grossen Menge dieser ersten listen(dict in dict) eine kumulierte erstellen (wobei sich die Knoten Art und Anzahl bei jeder Liste unterscheiden kann. Ist der Knoten nicht vorhanden wird er angelegt, ist er vorhanden soll das Gewicht des Knotens erhöht werden. Das habe ich wie folgt zu lösen versucht:

Code: Alles auswählen

pgraph = {}      #hier ist eine "projekt" adjacency list die kumuliert werden soll
wgraph = {}      #das soll der kumulierte Gewichtete graph werden.


	pgraph.clear()
	#construct the adjacency list per project
	for module in raw_data:                                                  #raw_data sind knoten
		pgraph[module] = dict.fromkeys(raw_data, 1)
	
		#Delete dependency of module on it self 
		if pgraph[module].has_key(module):
			del pgraph[module][module]

       #bis hier hin funktioniert es. Die Projektliste wird erstellt. 

	for key in pgraph.keys():							#iterate over the keys of project list
		
		if wgraph.has_key(key):							#if the weighted graph has already the key e.g. has the module
			for key in pgraph[key].keys():				#iterate over dependencies of the module
				if key in wgraph[key]:                             #hat der knoten bereits die verbindung zu anderen knoten
					wgraph[key][key] += 1                   #erhöhe das gewicht
				else:
					wgraph[key] = pgraph[key].items()  #ansonsten lege die verbindung zu dem knoten an. HIER LIEGT WOHL DAS PROBLEM: wie greife ich auf das dict im dict zu. keys() geht nicht da er sagt das dies nicht auf listen geht. 

		else:
										#if the key is new, it is appended to the weighted graph
			wgraph[key] = pgraph[key].items()

Ich hoffe mein Problem ist einigermaßen verständlich. Ich glaube ich habe noch nicht so richtig dict in dict verstanden. hmpf...

Vielleicht hat ja jemand auf die schnelle eine Lösung.

Vielen Dank

Martin

[Auctor]

ok, ich bin weiter gekommen.

klar, erstell ja ne liste im dict und kein dict.

mit

Code: Alles auswählen

	else:
										#if the key is new, it is appended to the weighted graph
			wgraph[key] = dict.fromkeys(pgraph[key], 1)

erstell ich nun das dict und komm auch in die schleife rein. Nun kann ich nur noch nicht die werte erhöhen.

Code: Alles auswählen

wgraph[key][key] += 1

funktioniert wohl nicht. mhmm...

[BlackJack]

@Auctor: Du hast da zwei verschachtelte ``for``-Schleifen die beide den Namen `key` als "Laufvariable" verwenden. Selbst wenn das nicht das Problem sein sollte, ist das doch hochgradig verwirrend.

`dict.has_key()` sollte man nicht mehr verwenden, die Methode ist bei Python 3 mittlerweile auch rausgeflogen. Den ``in``-Operator kennst Du ja anscheinend.

Der Aufruf der `keys()`-Methode bei den ``for``-Schleifen ist sehr wahrscheinlich unnötig es sei denn Du willst wirklich vor dem Iterieren eine extra Liste mit den Schlüsseln erstellen. Eine ``for``-Schleife über ein `dict` geht nämlich auch so schon nur über die Schlüssel.

Ansonsten wäre es vielleicht hilfreich wenn Du mal Eingabedaten mit allen "Sonderfällen" zeigst und was Du da gerne als Ergebnis haben möchtest. Und dazu minimal lauffähigen Quelltext damit man das einfach ausprobieren kann.

[Auctor]

Hallo BlackJack,

vielen Dank schon mal für die Hilfe.

Die Eingabedaten sind Knotenbezeichnungen (eher Kryptisch) in der Form

A0GR, B00R, 602I, 904I, 9017, A07G....

Was ich vorhabe lässt sich vielleicht besser auf einem Bild zeigen:
removed!

Als Ergebnis hätte ich gerne eine adjacency list (in form von dict in dict damit man das mit networkX verarbeiten kann) mit knoten (z.b. A0GR) die auf andere knoten (z.b. B00R) und die Gewichtung dieser Kanten (ergibt sich daraus wie oft diese knoten zusammen in einem projekt benutzt wurden).

aktuell sieht es so aus:

Code: Alles auswählen

#Dictionary for cumulated weighted graph
wgraph = defaultdict(dict)

#Dictionary for project graph
pgraph = defaultdict(dict)

for project in projects:

#SQL STATEMENT

	modulenum = cursor.fetchall()

	#Filter the data. modulenum returns tuples or so..
	raw_data = []
	a = 0
	for i in modulenum:
		raw_data.append(modulenum[0+a][0])
		a += 1
		
	pgraph.clear()
		
	#construct the adjacency list per project
	for module in raw_data:
		pgraph[module] = dict.fromkeys(raw_data, 1)
	
		#Delete dependency of module on it self 
		if pgraph[module].has_key(module):
			del pgraph[module][module]

	for key in pgraph.keys():											#iterate over the keys of project list
		if wgraph.has_key(key):											#if the weighted graph has the key e.g. has the module
			for key in pgraph[key].keys():								#iterate over dependencies of the module
				if key in wgraph[key].keys() and not wgraph[key]:
					wgraph[key][key] += 1	
				elif key in wgraph[key].keys() and wgraph[key]:
					del wgraph[key]
				else:
					wgraph[key] = dict.fromkeys(pgraph[key], 1)
		else:											
			wgraph[key] = dict.fromkeys(pgraph[key], 1)  				#if the key is new, it is appended to the weighted graph

Ich kann leider nur python 2.6.4 benutzen.

wgraph[key][key] += 1 -> funktioniert nicht weil der wert kein integer ist. kann man bei dict angeben dass das dict im dict als value int hat?


puh, sorry für die umstände. seh grad den wald vor lauter bäumen nicht.

[BlackJack]

@Auctor: `raw_data` baust Du sehr umständlich auf. Was soll das ``0 + a`` da drin? Ist Dir klar das das `i` in der Schleife an die einzelnen Elemente von `modulenum` gebunden wird, Du den Indexzugriff also überhaupt nicht brauchst!? Das wäre letztendlich nur ein Einzeiler:

Code: Alles auswählen

        raw_data = [a[0] for a in modulenum]

Den Test vor dem Löschen der Beziehung zu sich selbst, verstehe ich nicht. Da zu jedem `module` aus `raw_data` alle Elemente aus `raw_data` als Schlüssel um Wert erzeugt werden, *muss* es diese Beziehung doch geben!? Warum dann der Test?

Du verwendest immer noch `has_key()` und `keys()` wo es nicht nötig ist. Insbesondere so etwas wie ``a in d.keys()`` ist total kontraproduktiv, weil da erst eine Schlüsselliste erzeugt wird, die dann linear nach `a` durchsucht wird, während der ``in``-Operator auf Dictionaries direkt, in konstanter Zeit läuft.

Die Zeile ``wgraph[key][key] += 1`` verstehe ich nicht. Du hast doch explizit dafür gesorgt, dass kein Knoten eine Beziehung zu sich selbst hat und versuchst dann hier das Gewicht der Kante vom Knoten `key` zu sich selbst um eins zu erhöhen!? Das kann doch gar nicht funktionieren.

Die Bedingungen dort sehen übrigens etwas ungünstig formuliert aus. Wenn sich zwei aufeinanderfolgende Bedingungen nur durch Teilausdrücke unterscheiden kann man den gemeinsamen Teil in der Regel herausziehen. Und wenn der Unterschied in beiden Bedingungen eine Umkehr selbiger ist, kann man die wiederholte Prüfung normalerweise durch ein ``else`` ausdrücken.

Nachvollziehen kann man den Quelltext ja nicht, da nicht lauffähig und keine Testdaten vorhanden sind.

Die Beschreibung warum die Zeile nicht funktioniert ist auch ein wenig dünn. Wenn Du Ausnahmen bekommst, dann zeig die am besten. Komplett. Und da wir keine Daten haben, wäre der Inhalt der betroffenen Objekte zu dem Zeitpunkt auch interessant.

[Auctor]

so, ich glaub ich habs. SUPER VIELEN DANK für die Hilfe.

Und ähm, unglaublich wie flott das nun ist ohne die keys() und has_key(). Faktor 20.

Code: Alles auswählen

for module in pgraph:											
		if module in wgraph:											
			for knoten in pgraph[module]:								
				if knoten in wgraph[module]:
					wgraph[module][knoten] += 1	
				else:
					wgraph[module][knoten] = pgraph[module][knoten]
		else:											
			wgraph[module] = dict.fromkeys(pgraph.keys(), 1)  			

und das mit raw_data... puh... dafür muss ich mich echt schämen.

Gruß

Martin

[pillmuncher]

So ginge es auch:

Code: Alles auswählen

from collections import defaultdict

def make_pgraph(project):
    return [(a, [b for b in project if a != b]) for a in project]

def make_wgraph(*pgs):
    wg = defaultdict(lambda:defaultdict(int))
    for pg in pgs:
        for a, bs in pg:
            for b in bs:
                wg[a][b] += 1
    return wg

project1 = ['N1', 'N2', 'N3', 'N4', 'N5', 'N6']
project2 = ['N4', 'N6', 'N8', 'N9']
project3 = ['N1', 'N4', 'N6', 'N9', 'N16']

pgraph1 = make_pgraph(project1)
pgraph2 = make_pgraph(project2)
pgraph3 = make_pgraph(project3)

wgraph = make_wgraph(pgraph1, pgraph2, pgraph3)

import pprint
pprint.pprint(dict(wgraph))

Ich hoffe, ich habe nicht gerade deine Hausaufgabe gemacht

[edit]oops! In Project 3 stand bei mir, anders als im Bild, N8 statt N9 -> korrigiert.[/edit]

[Auctor]

wow, das ist natürlich die luxus Lösung.

Keine Angst, Hausaufgaben sind bei mir schon ne ganze Weile kein Thema mehr.

Gruß

Martin

[pillmuncher]

Mir ist gerade aufgefallen, dass du schreibst, dass es sich um eine große Menge Listen handelt, und ich vermute, dass die zudem selber ziemlich groß sind. Da würde es sich anbieten, Iteratoren statt Listen zu verwenden, und das ganze mittels itertools.permutations abzukürzen:

Code: Alles auswählen

from collections import defaultdict
from itertools import permutations

def make_wgraph(ps):
    wg = defaultdict(lambda:defaultdict(int))
    for p in ps:
        for a, b in permutations(p, 2):
            if a != b:
                wg[a][b] += 1
    return wg

def read_projects_from_db(): # dummy
    yield iter(['N1', 'N2', 'N3', 'N4', 'N5', 'N6'])
    yield iter(['N4', 'N6', 'N8', 'N9'])
    yield iter(['N1', 'N4', 'N6', 'N9', 'N16'])

wgraph = make_wgraph(read_projects_from_db())

import pprint
pprint.pprint(dict(wgraph))