노드 목록과 에지리스트에서 연결성 찾기

Question

(TL; DR)

점의 사전 정의 노드의 집합이 주어와 키 튜플 사전 정의 에지들의 집합 , 파이썬에서 연속적인 세그먼트를 쉽게 찾을 수있는 알고리즘이 있습니까?

(컨텍스트 :

나는 두 개의 파일이있는 도로 네트워크의 모델 세그먼트.

Nodes.txt

:

1;-5226574;-3118329 # latitude and longitude as integers (multiplied by 1e5) 
2;-5226702;-3118330 
3;-5226750;-3118332 
4;-5226793;-3118338 
... 

Edges.txt :

1;1;2 
2;3;5 
3;23;345 
4;23;11 
... 

각 에지 노드 인덱스에 의해 두 개의 노드들 사이의 (인덱스)의 링크를 나타낸다.

생성 된 네트워크의 하위 섹션 아래에 그려집니다 :

당신이 볼 수 있듯이

, 노드의 압도적 인 다수는 "간단한"노드는 그것의 중간에 의미입니다 도로 구간과 정확히 2 개의 가장자리에 속합니다. 반면에 세 개 이상의 가장자리에 속해 있기 때문에 분기 또는 교차점을 나타내는 "특수"노드가 있습니다.

현재 분리 된 도로 구간의 컬렉션이 있습니다. 두 개의 특수 노드 사이의 각 도로 구간을 시퀀스 노드로 정의하고 싶습니다. 그것은 모든 것을 플롯하고 거리를 측정하는 등의 작업을 훨씬 빠르게 해주 며, 또한 두 개의 특수 노드를 연결하는 "수퍼 에지"로서 각 노드 시퀀스를 표현할 수있게하여 토폴로지를 단순화합니다.

나는 그것을하기위한 몇 가지 무차별적인 방법을 쉽게 상상할 수 있지만, 노드의 양은 상대적으로 높기 때문에 이것을 해결할 수있는 이론적 인 배경이 없다.

UPDATE :

내 원시 데이터 created a gist 있습니다. 각 선은 도로를 일련의 점 (lat, lon)으로 나타내며 도로는 많이 겹칩니다. 내 목표는 노드와 링크에 대한 사전을 파일에서이 "도로 목록"으로 생성하는 것입니다.

당신은 콘텐츠에 액세스하려면 다음 파이썬 스크립트를 사용할 수 있습니다 : 다른

with open('RawRoads.txt') as roadsFile: 
    for line in roadsFile.readlines(): 
     road = [tuple(map(lambda x:int(float(x)*1e5), coord.split(','))) for coord in line.strip().split(' ')] 

또는 :

import urllib 

url = "https://gist.githubusercontent.com/heltonbiker/ca043f8ee191db5bf8349b1b7af0394c/raw/RawRoads.txt" 

lines = urllib.urlopen(url).readlines() 
for line in lines: 
    # you got the idea 

Answer 1

이의 너무 짐승하지 보자. edge [i]은 최대 세 요소의 목록이고 노드가 인 노드이 연결되어있는 간단한 목록을 작성하면됩니다. 노드 번호가 밀집되어 0 근처에서 시작하면 목록을 사용할 수 있습니다. 그렇지 않은 경우 디렉토리를 사용합니다.

나는 가장자리에서 목록을 만듭니다.형태 TXT

edge_list = [(1,2), (2,3), (3,5), (2, 23), (23,345) (23,11), ...]

지금 양방향 가장자리 참조 디렉토리 구축 :

다음,이 아닌 다른 순서와 그 특수 노드를 식별 : 교차로와지도 가장자리를. 그런 다음 하나를 선택하고 다른 세그먼트를 칠 때까지 세그먼트를 만듭니다. OP FROM

# Dictionary of edges, indexed in both directions by node number. 
edge = {} 

# Ingest the data and build teh dictionary 
with open("edges.txt") as efile: 
    for line in efile: 
     eid, src, dst = line.strip().split(';') 
     src = int(src) 
     dst = int(dst) 

     for key, val in [(src, dst), (dst, src)] : 
      if key in edge: 
       edge[key].append(val) 
      else: 
       edge[key] = ([val]) 
print "edge dictionary has entries:", len(edge) 

# Identify endpoint nodes: order other than 2 
end_ct = 0 
print "Endpoint Nodes" 
endpoint = [] 
for src, dst in edge.iteritems(): 
    if len(dst) != 2: 
     print len(dst), src, dst 
     endpoint.append(src) 
     end_ct += len(dst) 
print end_ct, "road ends" 

atlas = [] # List of roads, each a list of nodes 

# Build roads between the identified endpoints 
# Pick the first endpoint in the remaining list. 
# Move to the first-listed adjacent node. 
# Keep going until we hit another node on the endpoint list. 
while len(endpoint) > 0: 
    here = endpoint[0] 
# print "Road starting at", here, edge[here] 

    # Pick a first step and consume the edge 
    next = edge[here].pop(0) 
    edge[next].remove(here) 
    road = [here, next] 

    # If that's the last connection to the node, remove that node from the endpoints list. 
    if len(edge[here]) == 0: 
     del endpoint[0] 
     del edge[here] 
    # Special case for a one-segment road; endpoint entry of "next" is removed after the loop 
    if len(edge[next]) == 0: 
     del edge[next] 

    # Consume edges until we reach another endpoint. 
    debug = False 
    while next not in endpoint: 
     here = next 
     next = edge[here].pop(0) 
     edge[next].remove(here) 
     road.append(next) 
     if len(edge[next]) == 0: 
      del edge[next] 
#   print "removing node", next 

    if next not in edge: 
     endpoint.remove(next) 
#  print "removing endpoint", next 

    print "\nRoad from", road[0], "to", road[-1], ':\n\t', road 
    atlas.append(road) 

print "\n", len(atlas), "roads built" 
# print "edge dictionary still has entries:", len(edge) 

편집 :

그것은 일

, 그것은 빠르고 정확한, 그리고 내가 찾아 그것을 시각화를받을 자격 :

import matplotlib.pyplot as plt 

for road in atlas: 
    path = [nodesdict[i] for i in road] 
    lons, lats = zip(*path) 
    plt.plot(lons, lats) 

plt.grid() 
plt.axis('equal') 
plt.show()