Python - Build-Adjazenz-Liste aus der Liste der Knoten und Kanten

Question

Ich habe eine Liste der Knoten-und Kantenobjekte aus der National Highway Planning Network-Datenbank. Ein großer Teil der Daten ist mir verborgen, aber das ist, was mir gegeben:

class Node: 
    def __init__(self, longitude, latitude, state, description): 
     self.longitude = longitude 
     self.latitude = latitude 
     self.state = state 
     self.description = description 

class Link: 
    """A bi-directional edge linking two NHPN nodes.""" 

    def __init__ (self, begin, end, description): 
     """create a link given its beginning and end (which must be nodes) 
     and possibly a description string.""" 
     self.begin = begin 
     self.end = end 
     self.description = description 

Ich weiß, dass es nicht viele Informationen gegeben ist, aber ich versuche eine Adjazenzliste aus diesen Daten zu bauen. Ich würde sehr gerne ein Wörterbuch benutzen. Dies ist, was ich versucht habe:

for node in nodes: 
    adj[node] = None 
for edge in edges: 
    adj[node] = (edge.begin, edge.end) #edge.begin and edge.end being node's neighbors 

gefolgt von einer Druckanweisung, nur um zu sehen, ob es funktioniert hat. Aber es hat nie gedruckt, was befürchtet, dass die Eingabe enorm ist und mein Code unglaublich langsam ist. Wie kann ich meine Implementierung überarbeiten? Ich würde gerne ein Wörterbuch benutzen, aber ich bin offen für alle Vorschläge.

Answer 1

Hier ist ein Programm, das die Adjazenzliste für eine sehr kleine Menge von Autobahnen berechnet. Ich habe den Code Ihrer Frage so oft wie möglich verwendet.

from pprint import pprint 
class Node: 
    def __init__(self, longitude, latitude, state, description): 
     self._longitude = longitude 
     self._latitude = latitude 
     self.state = state 
     self.description = description 

    @property 
    def longitude(self): 
     return self._longitude 
    @property 
    def latitude(self): 
     return self._latitude 

    def __hash__(self): 
     return hash((self.longitude, self.latitude)) 

    def __repr__(self): 
     return 'Node({_longitude!r}, {_latitude!r}, {state!r}, {description!r})'.format(**vars(self)) 

class Link: 
    """A bi-directional edge linking two NHPN nodes.""" 

    def __init__ (self, begin, end, description): 
     """create a link given its beginning and end (which must be nodes) 
     and possibly a description string.""" 
     self.begin = begin 
     self.end = end 
     self.description = description 

chicago = Node(-87, 41, 'IL', 'Windy City') 
bloomington = Node(-89, 40, 'IL', 'Twin City') 
indy = Node(-86, 40, 'IN', 'Naptown') 
nodes = [ chicago, bloomington, indy ] 
edges = [ 
    Link(chicago, bloomington, 'I-55'), 
    Link(chicago, indy, 'I-65'), 
    Link(indy, bloomington, 'I-74'), 
] 

adj = {} 
for edge in edges: 
    adj.setdefault(edge.begin, set()).add(edge.end) 
    adj.setdefault(edge.end, set()).add(edge.begin) 
pprint(adj) 

Hier ist, wie es aussehen würde, wenn wir zur Verfügung gestellt haben nicht Link und Node wie zu verwenden: Und hier ist

from pprint import pprint 
from collections import namedtuple 

Node = namedtuple('Node', 'longitude latitude state description') 
Link = namedtuple('Link', 'begin end description') 

chicago = Node(-87, 41, 'IL', 'Windy City') 
bloomington = Node(-89, 40, 'IL', 'Twin City') 
indy = Node(-86, 40, 'IN', 'Naptown') 
nodes = [ chicago, bloomington, indy ] 
edges = [ 
    Link(chicago, bloomington, 'I-55'), 
    Link(chicago, indy, 'I-65'), 
    Link(indy, bloomington, 'I-74'), 
] 

adj = {} 
for edge in edges: 
    adj.setdefault(edge.begin, set()).add(edge.end) 
    adj.setdefault(edge.end, set()).add(edge.begin) 
pprint(adj) 

ein, ohne überhaupt alle Klassendefinitionen zu verwenden:

from pprint import pprint 

chicago = (-87, 41, 'IL', 'Windy City') 
bloomington = (-89, 40, 'IL', 'Twin City') 
indy = (-86, 40, 'IN', 'Naptown') 
nodes = [ chicago, bloomington, indy ] 
edges = [ 
    (chicago, bloomington, 'I-55'), 
    (chicago, indy, 'I-65'), 
    (indy, bloomington, 'I-74'), 
] 

adj = {} 
for edge in edges: 
    adj.setdefault(edge[0], set()).add(edge[1]) 
    adj.setdefault(edge[1], set()).add(edge[0]) 
pprint(adj)