テキストファイルからグラフ（Python）への構文解析

Question

テキストファイルをPythonでグラフに解析する方法がわかりません。このファイルの形式は次のとおりです。

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

上部の整数は寸法（行、列）です。私は各キャラクターの間のスペースを考慮する必要があります。これは、検索を実行して開始点と終了点が与えられたときの最適な経路を決定しなければならない迷路を表すと仮定しています。私はその部分を理解しました。このテキストファイルを解析してグラフにするだけで、検索を実行できるようになります。

Answer 1

この関数は、ノードの集合（元のグリッドの座標のペアとして格納されている）のようなグリッドと、エッジのdict（各ノードをそれに隣接する）。これは非常に使いやすいグラフの表現であり、それを使って迷路検索をコーディングするのに問題はありません。このコードでは、迷路の構造が辺（ - と|）だけで記述され、グリッドが水平方向と垂直方向に2重線であるという考えを使用しています。グラフには、エッジの出入りがない四角形は表示されません。

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

実装は、Pythonでグラフをどのように表現したいかによって異なります。

私は、これは動作するはずエッジリストに

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)) 

を作成していますが、私は今それをやろうとして、まだそれをテストしてやりなさい。

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)