Erstellen einer Adjazenzliste aus Datei

Question

Ich habe den Auftrag, den Inhalt einer Datei einzulesen und daraus eine Adjazenzliste zu erstellen.

Jede Linie steht für eine Kante in der Grafik und die Datei sieht wie folgt aus:

0 1 
2 1 
0 2 
1 3 

Bisher habe ich gelesen, alles in und haben jetzt eine Liste, die umfasst:

[[ '0', '1'], ['2', '1'], ['0', '2'], ['1', '3']]

Meine Frage ist wie Ich benutze das obige, um eine Adjazenzliste zu erhalten, die wie folgt aussieht:

[[1; 2]; [0; 2; 3]; [1; 0]; [1]]

Bitte beachten Sie: Sehr neu in der Python-Sprache und ich darf nichts importieren.

Answer 1

Die folgende Lösung verwendet einen dictionary:

l = [['0', '1'], ['2', '1'], ['0', '2'], ['1', '3']] 
adjacencies = dict() 
for edge in l: 
    x, y = int(edge[0]), int(edge[1]) 
    if x not in adjacencies: adjacencies[x] = set() 
    if y not in adjacencies: adjacencies[y] = set() 
    adjacencies[x].add(y) 
    adjacencies[y].add(x) 
print([sorted(adjacencies[_]) for _ in sorted(adjacencies)]) 

jedoch eine elegantere Lösung wäre Wörterbuch adjacencies direkt zu konstruieren, während die Eingabedatei (test.txt im folgenden Beispiel) Parsen:

def get_adjacency_list(filename): 
    adjacencies = dict() 
    with open(filename) as infile: 
     for line in infile: 
      x, y = [int(_) for _ in line.strip().split()] 
      if x not in adjacencies: adjacencies[x] = set() 
      if y not in adjacencies: adjacencies[y] = set() 
      adjacencies[x].add(y) 
      adjacencies[y].add(x) 
    return [sorted(adjacencies[_]) for _ in sorted(adjacencies)] 

print(get_adjacency_list('test.txt')) 

Beachten Sie, dass die Werte des Wörterbuchs adjacencies vom Typ set sind, die aufgrund der Sortierung in Listen umgewandelt werden (über die integrierte Methode sorted()).

IF Sie könnten alles, was Sie verwenden sollten defaultdict anstelle von normalen Python-Wörterbücher importieren.