парсинг из текстового файла в граф (python)

Question

У меня проблемы с выяснением того, как анализировать текстовый файл в граф на Python. Файл в следующем формате:

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

Целые числа вверху - это размеры (строка, столбец). Мне нужно учитывать расстояние между каждым персонажем. Предположим, это лабиринт, по которому мне нужно будет выполнить поиск, чтобы определить оптимальный путь с учетом начальной и конечной точек. Эту часть я выяснил. Мне просто нужна помощь в разборе этого текстового файла на график, чтобы я мог запустить поиск.

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

Answer 2

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

Answer 3

Реализация будет зависеть от того, как вы хотите представить граф в 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))

это должно работать, но я не проверялэто еще, собираюсь сделать это сейчас.