phân tích cú pháp từ tệp văn bản sang đồ thị (python)

Question

Tôi đang gặp khó khăn khi tìm cách phân tích cú pháp tệp văn bản thành biểu đồ trong python. Tệp có định dạng sau:

4 4 
o . o . o . o 
- - . - 
o . o . o | o 
. - . . 
o | o . o . o 
. - . - 
o . o . o . o 

Các số nguyên ở trên cùng là kích thước (hàng, cột). Tôi cần tính đến khoảng trống giữa mỗi nhân vật. Đây là giả sử để đại diện cho một mê cung mà tôi sẽ phải chạy một tìm kiếm để xác định đường dẫn tối ưu cho một điểm bắt đầu và điểm cuối. Đó là một phần tôi đã tìm ra. Tôi chỉ cần giúp phân tích cú pháp tệp văn bản này thành biểu đồ để tôi có thể chạy tìm kiếm.

Answer 1

Hàm này phân tích một lưới giống như lưới bạn đã đưa vào một bộ nút (được lưu trữ dưới dạng cặp tọa độ trong lưới ban đầu) và một góc cạnh (ánh xạ từng nút đến danh sách các nút tiếp giáp với nó). Đây là một biểu diễn rất dễ sử dụng cho biểu đồ, và bạn sẽ không gặp khó khăn khi mã hóa tìm kiếm mê cung bằng cách sử dụng nó. Mã sử ​​dụng ý tưởng rằng cấu trúc của mê cung được mô tả bởi chỉ các cạnh (- và |), và lưới là hai dòng khoảng cách theo chiều ngang và chiều dọc. Một hình vuông không có cạnh vào hoặc ra khỏi nó sẽ không xuất hiện trong biểu đồ.

import collections 

def parse_grid(grid): 
    edges = collections.defaultdict(list) 
    for i in xrange(len(grid)): 
     for j in xrange(len(grid[i])): 
      if grid[i][j] == '-': 
       edges[i, j - 2].append((i, j + 2)) 
       edges[i, j + 2].append((i, j - 2)) 
      if grid[i][j] == '|': 
       edges[i - 2, j].append((i + 2,j)) 
       edges[i + 2, j].append((i - 2,j)) 
    nodes = set() 
    for e in edges.iterkeys(): 
     nodes.add(e) 
    return nodes, edges 

grid = """\ 
o . o . o . o 
- - . - 
o . o . o | o 
. - . . 
o | o . o . o 
. - . - 
o . o . o . o""" 
print parse_grid(grid.split('\n')) 

Answer 2

Việc triển khai sẽ phụ thuộc vào cách bạn muốn thể hiện biểu đồ bằng Python.

tôi là tạo ra một danh sách cạnh

edgelist = [] 
y=0 
for line in file: 

    chars = [char for char in line.split(" ") if len(char)] 
    x = 0 

    if ('|' in chars): 
     y+=1 
     for char in chars: 
      if char == 'o' 
       x+=1 
      elif char == '.' 
       edgelist.append([(x,y),(x+1,y)]) 
    else: 
     for char in chars: 
      x+=1 
      if char == '.' 
       edges.append([(y,x),(y,x+1)) 

này nên làm việc, nhưng tôi havn't thử nghiệm được chưa, sẽ làm điều đó ngay bây giờ.

Answer 3

""" 
maze1.txt 

4 4 
o . o . o . o 
- - . - 
o . o . o | o 
. - . . 
o | o . o . o 
. - . - 
o . o . o . o 
""" 

readfile = open('maze1.txt', 'r') 
line = readfile.readline() 
rowcount, colcount = [int(elem) for elem in line.strip().split(' ')] 
rights = [] 
downs = [] 
chars =  ('o', ' ', '.', '-', '|', '') 
translated = ('o', ' ', '.', '-', '|', '') # if needed, could be int or method 

while line: 
    line = readfile.readline() 
    if chars[0] in line: 
     for elem in line.strip().split(chars[0])[1:]: 
      rights.append(translated[chars.index(elem.strip())]) 
    else: 
     for elem in line.strip().split(chars[1])[:colcount]: 
      downs.append(translated[chars.index(elem.strip())]) 


readfile.close() 

for i, elem in enumerate(rights): 
    print elem, divmod(i, colcount) 
print "##" 
for i, elem in enumerate(downs): 
    print elem, divmod(i, colcount)