从文本文件到图形的解析（Python）

Question

我很难想象如何将一个文本文件解析成python的图形。这个文件的格式如下：

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

顶部的整数表示行列尺寸。我需要考虑每个字符之间的空格。这应该代表一个迷宫，我将在其中运行搜索以确定给定起点和终点的最佳路径。那部分我已经想出来了。我只需要帮助将此文本文件解析为图形，以便我可以运行搜索。

- wxm8562

---

你所说的解析到一个"图"具体是什么意思？Python中有没有内置的"图"类型？（我得到name 'graph' is not defined）。这是你创建的一种自定义类型吗？还是你没有具体的想法，希望我们提供一个合适的表示方法？ - Mark Byers

Answer 1

该函数将像您提供的网格一样解析为一组节点（以原始网格中的坐标对形式存储），以及边缘字典（将每个节点映射到与其相邻的节点列表）。这是一个非常易于使用的图形表示，您应该可以毫不费力地使用它编写迷宫搜索。该代码使用的思想是迷宫的结构仅由边缘（-和|）描述，并且网格在水平和垂直方向上是双线间隔的。没有出入口的正方形将不会出现在图形中。

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

- user97370

---

我基本上编写了相同的代码并发布了...然后页面刷新，我看到你比我先完成了...除了删除我的代码并点赞你的代码之外，没有其他选择！;) - mac

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

这应该能工作，但我还没有测试过，现在就去测试一下。

- bigblind

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)

- kradem