2016-07-02 22 views
-3

Ich habe eine Adjazenzmatrix wie hier untenWie konvertiert man eine Adjazenzmatrix in eine Adjazenzliste mit Python?

[[ 0., 15., 0., 7., 10., 0.], 
    [ 15., 0., 9., 11., 0., 9.], 
    [ 0., 9., 0., 0., 12., 7.], 
    [ 7., 11., 0., 0., 8., 14.], 
    [ 10., 0., 12., 8., 0., 8.], 
    [ 0., 9., 7., 14., 8., 0.]] 

Wie kann ich es auf eine Adjazenzliste wie diese konvertieren?

graph = {'1': [{'2':'15'}, {'4':'7'}, {'5':'10'}], 
'2': [{'3':'9'}, {'4':'11'}, {'6':'9'}], 
'3': [{'5':'12'}, {'6':'7'}], 
'4': [{'5':'8'}, {'6':'14'}], 
'5': [{'6':'8'}]} 

?

+0

Ihre Adjazenzmatrix sieht völlig leer aus. Wie soll das zu den Graph-Daten führen? –

+0

@StefanPochmann Da ist das Original adj. Matrix. Ich musste den letzten Schnitt von OP zurücksetzen. Warum hat er nicht die ursprüngliche Matrix ausgelöscht? –

Antwort

2

Behalten Sie eine Liste der bereits hinzugefügten Kanten in einem Satz edges. Diese Kanten werden in einer frozenset gespeichert, so dass bereits hinzugefügte Paare nicht repliziert werden.


bauen dann Ihr Diagramm von die äußeren Liste mit einem Startindex einer aufzählt, dann der innere Liste auch mit einem Startindex von einem. Nullwertige Einträge werden mit dem if Zustand auf Werte eliminiert:

from collections import defaultdict 
from pprint import pprint 

l =[[ 0., 15., 0., 7., 10., 0.], 
    [ 15., 0., 9., 11., 0., 9.], 
    [ 0., 9., 0., 0., 12., 7.], 
    [ 7., 11., 0., 0., 8., 14.], 
    [ 10., 0., 12., 8., 0., 8.], 
    [ 0., 9., 7., 14., 8., 0.]]  

graph = defaultdict(list) 
edges = set() 

for i, v in enumerate(l, 1): 
    for j, u in enumerate(v, 1): 
     if u != 0 and frozenset([i, j]) not in edges: 
      edges.add(frozenset([i, j])) 
      graph[i].append({j: u}) 

pprint(graph) 
# {1: [{2: 15.0}, {4: 7.0}, {5: 10.0}], 
# 2: [{3: 9.0}, {4: 11.0}, {6: 9.0}], 
# 3: [{5: 12.0}, {6: 7.0}], 
# 4: [{5: 8.0}, {6: 14.0}], 
# 5: [{6: 8.0}]} 

eine defaultdict Verwendung, die einen list als Standardwert nimmt die Liste bewertet Wörterbuch on the fly helfen zu bauen.

+0

Danke @MosesKoledoye, das war ich will! – killx1997

Verwandte Themen