Программа "Поиск путей между точками по графам" (v.2)

В отличие от предыдущей версии в данной программе находятся не только прямые пути (т.е. содержащие обе точки сразу), но и пути через пары графов, имеющих пересечение.

Интерфейс программы (Tkinter)

 

Краткое описание программы "Search of paths"

Программа позволяет найти возможные пути от одной точки до другой. Описание графов (название и список точек, через которые он проходит) содержится в файле graphs.txt и загружается в момент запуска программы.

Как выглядят все графы можно посмотреть с помощью цветных кнопок в нижнем правом углу окна программы.

Для того, чтобы посмотреть, через какие графы можно попасть из одной точки в другую, следует ввести в текстовые строки название точек и нажать кнопку "Show paths". В отдельных метках будут показаны:

  • прямые пути, содержащие обе введенные точки;
  • пары путей, где первый граф пары содержит первую точку, второй - вторую точку, и оба графа имеют общие точки, т.е. пересекаются;
  • кратчайший путь из указанных выше. Выбирается их прямых путей при их наличии. Иначе выбор осуществляется среди пар путей.

Структура кода программы

Структура программы

 

Исходный код

def download_data():
    new_points = {}
    new_graphs = {}
    new_colors = []
    '''Задается смещение для графов, которое будет использоваться при прорисовке линий относительно 
    координат точек. Значение j зависит от количества графов. Если графов 8, то значения смещений должны
    быть приблизительно такими: -6, -4, -2, 0, 2, 4, 6, 8'''
    new_offset = {}
    for line in open('points.txt'):
        line = line.split('\n') # результат - ['данные', '']
        line = line[0] # изымаем строку данных
        line = line.split(' ') # получаем ['имя', 'x', 'y']
        line[1] = int(line[1])
        line[2] = int(line[2]) # результат ['имя', x, y]
        new_points[line[0]] = line[1:] # добавляем в словарь один элемент - 'имя': [x, y]
    for line in open('graphs.txt'):
        line = line.split('\n')
        line = line[0]
        line = line.split(' ')
        new_graphs[line[0]] = line[1:]  # добавляем в словарь один элемент - 'имя графа': ['список имен точек', ]
        new_colors.append(line[0]) # цвета нужны для нижних цветных кнопок
    j = -6
    for i in new_graphs:
        new_offset[i] = j
        j += 2
    return new_points, new_graphs, new_colors, new_offset
 
##################################
def process_search(event):
    w.draw_points() # очистка экрана
    point1 = w.ent_point_1.get()
    point2 = w.ent_point_2.get()
    if not point1 or not point2: # выход из функции, если в полях отсутствуют данные
        return
    # красные квадраты вокруг указанных точек. Удобство для навигации по рисунку.
    w.canvas.create_rectangle(points[point1][0]-10,points[point1][1]-10,points[point1][0]+10,points[point1][1]+10,outline="red")
    w.canvas.create_rectangle(points[point2][0]-10,points[point2][1]-10,points[point2][0]+10,points[point2][1]+10,outline="red")
 
    def direct_paths(): # возвращает список имен графов, которые содержат обе точки сразу, и текст для метки
        list_direct_paths = []
        str_direct_paths='' 
        for i in graphs:
            if (point1 in graphs[i]) and (point2 in graphs[i]):
                list_direct_paths.append(i)
        for i in list_direct_paths:
            str_direct_paths += i +';\n'
        return list_direct_paths, str_direct_paths
    #################
    def cross_paths(): 
        '''Возвращает словарь и строку для метки. Элемент словаря - 'пара графов': ['общие точки', ].
        В паре графов первый граф содержит первуют указанную точку, второй - вторую.'''
        list_pairs_paths = {}
        str_pairs_paths = ''
        point1_paths = []  # пути, содержащие только первую точку
        point2_paths = []  # пути, содержащие только вторую точку
        for i in graphs:
            if not(i in list_direct_paths): # если путь не содержит обе точки
                if point1 in graphs[i]:
                    point1_paths.append(i)
                elif point2 in graphs[i]:
                    point2_paths.append(i)
        for i in point1_paths: # каждый путь среди путей, содержащих только первую точку
            for j in point2_paths: # перебрать со всеми путями, содержащими только вторую точку
                list1 = graphs[i] # извлечь точки графа i
                list2 = graphs[j] # извлечь точки графа j
                set1 = set(list1) # преобразование во множество
                set2 = set(list2)
                intersect = set1 & set2 # пересечение множеств - общие точки
                if intersect: # если общие точки есть, то
                    list_key = i + ' ' + j # сформировать ключ элемента словаря их имен графов
                    list_points = list(intersect) # преобразовать множество в список
                    list_pairs_paths[list_key] = list_points # добавить элемент - 'пара графов': ['общие точки', ] - в словарь.
        for i in list_pairs_paths:
            str_pairs_paths += i + str(list_pairs_paths[i]) + ';\n'
        return list_pairs_paths, str_pairs_paths
    #################
    def shortest_path(list_paths): # поиск кратчайшего пути
        # в обоих поисках при равном количестве точек указывается только один путь
        if type(list_paths) == type([]): # если есть список прямых путей, а не словарь пар, то все проще
            short = list_paths[0] # предполагаем, что самый корокий - первый путь
            for i in list_paths[1:]: # перебираем все остальные графы в списке
                # если в списке точек очередного графа разница между первой и второй из указанных точек
                # меньше, чем разница в графе, хранимом в переменной short, то обновить short.
                if abs(graphs[i].index(point1)-graphs[i].index(point2)) < abs(graphs[short].index(point1)-graphs[short].index(point2)):
                    short = i
            w.lab_shortest_display.config(text=short)
        else:
            short = '' # здесь хранится имя (пара имен графов) кратчайшего пути
            length = 100 # длина пути
            for i in list_paths: # перебираем каждый элемент словаря
                pair_paths = i.split() # список пары, имеющей общие точки
                common_points = list_paths[i] # общие точки
                points_first_path = graphs[pair_paths[0]] # список точек первого графа
                points_second_path = graphs[pair_paths[1]] # список точек второго графа                
                """Алгоритм не совсем верен, из него бывают исключения, если графы имеют общие точки 
                не подряд (пересекаются в разных местах). 
                Ищется точка первого пути из общих точек, которая ближе всего расположена к 
                первой из указанных точек. Тоже самое для второго пути и второй точки.
                Находится сумма общих точек + точек первого пути до общих + второго пути до общих."""
                second_points_first_path = common_points[0] # ближайшая из общих
                for j in common_points[1:]:
                    # расстояние от первой точки до очередной сравнивается с расстоянием
                    # от точки, которая уже сохранена до первой точки
                    if ( abs(points_first_path.index(j) - points_first_path.index(point1)) < 
                        abs(points_first_path.index(second_points_first_path) - points_first_path.index(point1)) ):
                        second_points_first_path = j
                second_points_second_path = common_points[0]
                for j in common_points[1:]:
                    if ( abs(points_second_path.index(j) - points_second_path.index(point2)) < 
                        abs(points_second_path.index(second_points_second_path) - points_second_path.index(point2)) ):
                        second_points_second_path = j
                l = abs(points_first_path.index(second_points_first_path) - points_first_path.index(point1)) + abs(points_second_path.index(second_points_second_path) - points_second_path.index(point2)) + len(common_points)
                if length > l:
                    length = l
                    short = i
            w.lab_shortest_display.config(text=short)
 
    #################
    list_direct_paths, str_direct_paths = direct_paths()
    for i in list_direct_paths:
        w.draw_path(i, point1, point2)
    w.lab_paths_display.config(text=str_direct_paths)    
 
    list_pairs_paths, str_pairs_paths= cross_paths()
    for i in list_pairs_paths:
        pair_paths = i.split() # список пары, имеющей общие точки
        common_points = list_pairs_paths[i] # общие точки
        points_first_path = graphs[pair_paths[0]] # список точек первого графа
        points_second_path = graphs[pair_paths[1]] # список точек второго графа
        '''Надо определить откуда и докуда рисовать путь для каждого графа. Для первого графа: от первой точки, 
        указанной пользователем, до самой отдаленной от нее из списка общих точек. Как вычислить самую отдаленную?
        Находить модуль разницы между первой точкой и каждой точкой в списке общих точек. Наибольший модуль и 
        точку, которая его дала, запоминать в одтдельных переменных.
        То же самое сделать для второй точки.'''
        second_points_first_path = common_points[0]
        for j in common_points[1:]:
            if ( abs(points_first_path.index(j) - points_first_path.index(point1)) > 
                abs(points_first_path.index(second_points_first_path) - points_first_path.index(point1)) ):
                second_points_first_path = j
        second_points_second_path = common_points[0]
        for j in common_points[1:]:
            if ( abs(points_second_path.index(j) - points_second_path.index(point2)) > 
                abs(points_second_path.index(second_points_second_path) - points_second_path.index(point2)) ):
                second_points_second_path = j
        w.draw_path(pair_paths[0], point1, second_points_first_path)
        w.draw_path(pair_paths[1], point2, second_points_second_path)
    w.lab_two_paths_display.config(text=str_pairs_paths)
 
    if list_direct_paths:
        shortest_path(list_direct_paths)
    elif list_pairs_paths:
        shortest_path(list_pairs_paths)
 
#################################################
class Interface():
    def __init__(self, parent):
        parent.title("Search of paths")
        self.canvas = Canvas(parent,width=600,height=480,bg="white")
        self.lab_point_1 = Label(parent,text="First point:")
        self.ent_point_1 = Entry(parent,width=2)        
        self.lab_point_2 = Label(parent,text="Second point:")
        self.ent_point_2 = Entry(parent,width=2)        
        self.ent_point_1.bind('<KeyRelease>', lambda *a: self.update_entry(self.ent_point_1))
        self.ent_point_2.bind('<KeyRelease>', lambda *a: self.update_entry(self.ent_point_2))       
        self.but_paths = Button(parent,text="Show paths", width=15)
        self.lab_paths = Label(parent, text="Paths with two points")
        self.lab_paths_display = Label(parent, width=20, height=3,  bg = "white")
        self.lab_two_paths = Label(parent, text="Pairs of paths, each\ncontaining one point and\nintersect with each other")
        self.lab_two_paths_display = Label(parent, width=20, height=5, bg = "white")
        self.lab_shortest = Label(parent, text="The shortest path")
        self.lab_shortest_display = Label(parent, width=20, bg = "white")
        self.lab_graphs = Label(parent, text="Graphs")
        self.but_1 = Button(parent, width=1, bg=colors[0], activebackground=colors[0], command=lambda: self.draw_path(colors[0], graphs[colors[0]][0], graphs[colors[0]][-1]))
        self.but_2 = Button(parent, width=1, bg=colors[1], activebackground=colors[1], command=lambda: self.draw_path(colors[1], graphs[colors[1]][0], graphs[colors[1]][-1]))
        self.but_3 = Button(parent, width=1, bg=colors[2], activebackground=colors[2], command=lambda: self.draw_path(colors[2], graphs[colors[2]][0], graphs[colors[2]][-1]))
        self.but_4 = Button(parent, width=1, bg=colors[3], activebackground=colors[3], command=lambda: self.draw_path(colors[3], graphs[colors[3]][0], graphs[colors[3]][-1]))
        self.but_5 = Button(parent, width=1, bg=colors[4], activebackground=colors[4], command=lambda: self.draw_path(colors[4], graphs[colors[4]][0], graphs[colors[4]][-1]))
        self.but_6 = Button(parent, width=1, bg=colors[5], activebackground=colors[5], command=lambda: self.draw_path(colors[5], graphs[colors[5]][0], graphs[colors[5]][-1]))
        self.but_7 = Button(parent, width=1, bg=colors[6], activebackground=colors[6], command=lambda: self.draw_path(colors[6], graphs[colors[6]][0], graphs[colors[6]][-1]))
        self.but_8 = Button(parent, width=1, bg=colors[7], activebackground=colors[7], command=lambda: self.draw_path(colors[7], graphs[colors[7]][0], graphs[colors[7]][-1]))
        self.but_9 = Button(parent, width=1, bg=colors[8], activebackground=colors[8], command=lambda: self.draw_path(colors[8], graphs[colors[8]][0], graphs[colors[8]][-1]))
        self.but_all = Button(parent, width=1, text="del", bg="white", activebackground="white", command=self.draw_points)    
        self.but_help = Button(parent, bitmap="questhead", command=self.help_window)
        self.make_grid()
    def make_grid(self):
        self.canvas.grid(row=0,column=0,rowspan=12)
        self.lab_point_1.grid(row=0, column=1, columnspan=3, sticky=E)
        self.ent_point_1.grid(row=0, column=4, columnspan=1, sticky=W)
        self.lab_point_2.grid(row=1, column=1, columnspan=3, sticky=E)
        self.ent_point_2.grid(row=1, column=4, columnspan=2, sticky=W)
        self.but_paths.grid(row=2, column=1, columnspan=5)
        self.lab_paths.grid(row=3, column=1, columnspan=5, sticky=S)
        self.lab_paths_display.grid(row=4, column=1, columnspan=5, sticky=N)
        self.lab_two_paths.grid(row=5, column=1, columnspan=5, sticky=S)
        self.lab_two_paths_display.grid(row=6, column=1, columnspan=5, sticky=N)
        self.lab_shortest.grid(row=7, column=1, columnspan=5, sticky=S)
        self.lab_shortest_display.grid(row=8, column=1, columnspan=5, sticky=N)
        self.lab_graphs.grid(row=9, column=1, columnspan=5, sticky=S)
        self.but_1.grid(row=10, column=1, sticky=S)
        self.but_2.grid(row=10, column=2, sticky=S)
        self.but_3.grid(row=10, column=3, sticky=S)
        self.but_4.grid(row=10, column=4, sticky=S)
        self.but_5.grid(row=10, column=5, sticky=S)
        self.but_6.grid(row=11, column=1, sticky=N)
        self.but_7.grid(row=11, column=2, sticky=N)
        self.but_8.grid(row=11, column=3, sticky=N)
        self.but_9.grid(row=11, column=4, sticky=N)
        self.but_all.grid(row=11, column=5, sticky=N)
        self.but_help.grid(row=0, column=5, sticky=E+N)
    def update_entry(self, obj): # позволяет вводить в поле только один символ, входящий в допустимый диапазон
        s = obj.get() # то, что введено в поле
        s = s[-1] if s else '' # если в s что-то есть, то присвоить последний символ, если нет, то пустую строку
        obj.delete('0',END) # очистить поле
        if  'a'<= s <= 'z':        
            obj.insert(INSERT,s) # вставить содержимое s
    def draw_points(self):
        self.canvas.delete('all')
        for i in points:
            coords = points[i]
            x = coords[0]
            y = coords[1]
            self.canvas.create_rectangle(x,y,x+5,y+5,fill="black")
            self.canvas.create_text(x-5,y-5,text=i)
    def draw_path(self, pathname, point1, point2): # (имя графа, точка1, точка2)
        '''Рисует путь от точки1 до точки2 для графа pathname'''
        list_points = graphs[pathname] # список точек
        index1 = list_points.index(point1) # индекс указанных точек
        index2 = list_points.index(point2)
        if index1 > index2: # если первая точка расположена дальше, чем вторая, то
            a = index1          # первая становится второй, а вторая первой.
            index1=index2
            index2=a
        ofs = offset[pathname] # каково смещение для данного графа
        while index1 < index2: # перебирая все точки от первой до второй, рисуем линии по координатам точек
            # словарь_точек[точка_из_списка_точек_графа][координата]
            self.canvas.create_line(points[list_points[index1]][0]+ofs, points[list_points[index1]][1]+ofs,
                                                points[list_points[index1+1]][0]+ofs, points[list_points[index1+1]][1]+ofs,
                                                fill=pathname, width=2)
            index1 += 1
    def help_window(self):
        wah = Toplevel()
        wah.title('About&Help')
        wah.geometry('+600+250')
        wah.resizable(False,False)
        help_title = "Описание программы:"
        help_string ="""Программа позволяет найти возможные пути от одной точки до другой.\n\
Описание графов (название и список точек, через которые он проходит)\n\
содержится в файле graphs.txt и загружается в момент запуска программы.\n\
Как выглядят все графы можно посмотреть с помощью цветных кнопок в\n\
нижнем правом углу окна программы.\n\
Для того, чтобы посмотреть, через какие графы можно попасть из одной\n\
точки в другую, следует ввести в текстовые строки название точек и\n\
нажать кнопку \"Show paths\". В отдельных метках будут показаны:\n\
- прямые пути, содержащие обе введенные точки;\n\
- пары путей, где первый граф пары содержит первую точку, второй -\n\
вторую точку, и оба графа имеют общие точки, т.е. пересекаются;\n\
- кратчайший путь из указанных выше. Выбирается их прямых путей при\n\
их наличии. Иначе выбор осуществляется среди пар путей."""
        about_title = "О программе:"
        about_string = """Программа "Search of paths" подготовлена для ученического проекта.\n\
Авторы:\n\
- код и алгоритмы - Светлана Шапошникова (<a href="http://pythoner.name" title="http://pythoner.name">http://pythoner.name</a>),\n\
- идея - Иван Пашков.\n\
Программа распространяется по условиям GNU General Public License.\n\
Примечание. Существует другая версия программы, разработанная\n\
И. Пашковым на основе данной и адаптированная к транспортной системе\n\
города."""
        Label(wah, text=help_title, font='Times 14', fg='darkblue').grid(row=0, column=0, sticky=W, padx=5)
        Label(wah, text =help_string, justify=LEFT).grid(row=1, column=0, sticky=W, padx=20)
        Label(wah, text=about_title, font='Times 14', fg='darkblue').grid(row=2, column=0, sticky=W, padx=5)
        Label(wah, text =about_string, justify=LEFT).grid(row=3, column=0, sticky=W, padx=20)
        Frame(wah, height=20).grid(row=4, column=0)
        wah.focus_set()
        wah.grab_set()
        wah.wait_window()
#################################################
from tkinter import * #from random import random #from tkinter.ttk import *
points, graphs, colors, offset = download_data() # точки {'точка': [координаты], }, графы {'имя': ['точки', ], }, цвета ['цвет', ],  смещение {'имя': число, }
window = Tk()
w = Interface(window) # интерфейс
w.draw_points() # точки на холсте
w.but_paths.bind('<Button-1>', process_search) # запуск процесса поиска
w.but_paths.bind('<Return>', process_search)
window.mainloop()

 

Дополнительные файлы

points.txt

a 50 30
b 400 300
c 275 30
d 250 175
e 200 270
f 60 420
g 300 225
h 340 125
i 400 180
j 150 60
k 450 100
l 550 70
m 320 435
n 220 440
o 50 280
p 70 100
q 290 350
r 450 300
s 430 370
t 570 305
u 560 190
v 450 435
w 25 215
x 150 385
y 550 420
z 130 215

graphs.txt

red a p w o f n
green a j h i u k l c
blue a p z d g
yellow n q g h i r t
darkgreen f n m v s y
orange f x e g i u l
purple o x q m b s y
darkblue w p z d j c
brown o e q b r t

Создано