简易地图—python数据结构

大二数据结构课程设计,老师要求做一个地图,能添加或删除地点和路径,能够输出最短路径(这里我用的是dijkstra),然后还能输出任意两点之间全部路径(这里我用的是递归),后面老师提要求还做了一个简易的可视化,因为一直在网上找不到参考,所以我做完之后留给后来人。

代码有点乱凑合着看下,提供一下思路。

import networkx as nx
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np
plt.rc("font",family='YouYuan')


class Map():
    def __init__(self, n=0):
        '''
        这里创建邻接矩阵
        '''
        self.n = n
        self.edges = []
        self.peak = []
        self.name = 0
        self.information = []
        self.path = 0

    def load_edges(self):
        '''这里噢,有个大坑用loc'''
        print("Loading data from excel...", end="")
        vex_data = pd.read_excel(r'D:\pythonProject\Map_Sys\vexdata.xlsx', index_col=0)
        for i in range(len(vex_data)):
            for j in range(len(vex_data)):
                if vex_data.loc[i,j] == 0:
                    vex_data.loc[i,j] = float('inf')
        k = vex_data.values.tolist()
        for a in k:
            self.edges.append(a)
        map_data = pd.read_excel(r'D:\pythonProject\Map_Sys\Mapdata.xlsx',index_col=0)
        for i in map_data.values.tolist():
            self.information.append(i)
        self.peak = list(map_data.index)
        self.n = len(self.peak)
        print(self.peak)
        print(self.information)

    def Add_v(self,name,coordinate,reation):
        '''
        这里使用了解包,第一次使用解包,解包是将前一个和前面的变量来对应,后面与后一个对应
        '''

        self.n = len(self.edges)
        self.edges.append(reation)
        for i in range(self.n):
            a = int(reation[i])
            if a == 0:
                a = float('inf')
            self.edges[i].append(a)
        self.n += 1
        self.information.append(coordinate)
        self.peak.append(name)
        print(self.edges)

    def Add_road(self,first,end,data):
        '''添加路径'''
        i = self.peak.index(first)
        j = self.peak.index(end)
        self.edges[i][j] = data
        self.edges[j][i] = data


    def del_v(self, place):
        '''这里是删除节点'''
        node1 = self.peak.index(place)
        self.edges.pop(node1)
        for i in range(self.n-1):
            self.edges[i].pop(node1)
        self.n = self.n - 1
        self.information.pop(node1)
        self.peak.pop(node1)
        print(self.information)
        print(self.edges)
        print(self.peak)

    def del_road(self,first,end):
        '''删除路径'''
        self.edges[first][end] = float('inf')
        self.edges[end][first] = float('inf')

    def connect_peak(self):
        print(self.n)
        for i in range(self.n):
            for j in range(self.n):
                if self.edges[i][j] != 0 and i != j and self.edges[i][j] != float('inf'):
                    weight = self.information[i][0]-self.information[j][0]
                    highter = self.information[i][1] - self.information[j][1]
                    distance = round((weight**2+highter**2)**0.5,2)
                    self.edges[i][j] = self.edges[j][i] = distance
                else:
                    self.edges[i][j] == float('inf')
        print(self.edges)

    def display_edges(self):
        '''这里展示邻接矩阵'''
        print(self.n)
        a = self.edges
        for i in range(len(self.edges)):
            for j in range(len(self.edges)):
                if a[i][j] == 0:
                    a[i][j] = float('inf')
        df = pd.DataFrame(a,index=self.peak,columns=self.peak)
        print(df)


    def dijkstra(self,begin,end):
        self.n = len(self.edges)
        S = [0]*self.n #存已经遍历过的节点
        dist = [-1]*self.n #与其余点间最短距离,注意这里的距离是说初始点与该点的距离,而是不是上一个与下一个的距离
        rear_road = [-1]*self.n #后置节点
        for i in range(self.n):
            dist[i] = self.edges[begin][i]
            if self.edges[begin][i] < float('inf') :
                rear_road[i] = begin
            else:
                rear_road[i] = -1
        S[begin] = 1
        u = -1#这个就是个工具变量 ,让它变成接下来有值的后置节点
        for i in range(self.n-1):
            mindis = float('inf')
            for j in range(self.n):
                #这里最主要是要判断顶点有没有被遍历过,然后是不是与出发点有路径
                if S[j] == 0 and dist[j]<mindis:
                    u = j
                    mindis = dist[j]
            S[u] = 1
            for j in range(self.n):
                #判断是否j有没有被遍历
                if S[j] == 0:
                    #这里是在看这个后置节点与它的后置节点是否有路径,同时判断begin-->j 是否大于 begin-->u+u-->j,如果要是小于的话就应该替换了
                    if self.edges[u][j]<float('inf') and dist[u]+self.edges[u][j] <dist[j]:
                        dist[j] = dist[u]+self.edges[u][j]
                        rear_road[j] = u
        self.display_min_road(dist,rear_road,S,begin,end)


        #这里还要进行一个排序
    def display_min_road(self,dist,rear_road,S,begin,end):
            min_road = []
            min_node = []
            min_dist = dist[end]
            if S[begin] == 1 and begin != end:
                min_road.append(end)
                end = rear_road[end]
                if end == -1:
                    raise Exception('似乎没有这个点耶')
                while end != begin :
                    min_road.append(end)
                    end = rear_road[end]
            min_road.append(begin)
            min_road.reverse()
            for i in min_road:
                min_node.append(self.peak[i])
            self.path = min_node
            print(min_dist)
            print(min_node)

    def all_road(self,begin,end,road=[]):
        '''
        这里我想写一个全部路径,想法是遍历过的节点不能再次遍历。
        '''
        self.n = len(self.edges)
        new_road = []
        new_nodes = []
        road = road + [begin]#这里如果用append的话会一直存D
        data_begin = self.peak.index(begin)
        if begin == end:
            return road
        for node in self.peak:
            data_node = self.peak.index(node)
            if self.edges[data_begin][data_node] != float('inf'):
                if node not in road:
                    new_nodes = self.all_road(node, end, road)
                for new_node in new_nodes:
                    if new_node == end:
                        road.append(new_node)
                        new_road.append(road)
                        print(new_road)
        return new_road

    def save_map(self):
        '''这里我在考虑是否用mysql还是单纯的excel来存,不用想了,用excel'''
        for i in range(self.n):
            for j in range(self.n):
                if self.edges[i][j] == float('inf'):
                    print(self.edges[i][j])
                    self.edges[i][j] = self.edges[j][i] = 0
        f = open('vexdata.xlsx', 'w')
        d = open('Mapdata.xlsx', 'w')
        print(self.edges)
        df_save = pd.DataFrame(self.edges)
        fd_save = pd.DataFrame(self.information,columns=['x','y'])
        df_save.to_excel('vexdata.xlsx')
        fd_save.to_excel('Mapdata.xlsx')
        f.close()
        d.close()


    def visualizatiom(self):
        graph = nx.Graph()
        graph_edges = []
        graph.add_nodes_from(self.peak)
        for i in range(self.n):
            print(1)
            for j in range(i + 1, self.n):
                print(1)
                if self.edges[i][j] != float('inf') and self.edges[i][j] != 0:
                    graph_edges.append(
                        (self.peak[i], self.peak[j], self.edges[i][j]))
                    print(1)
        print(graph_edges)
        graph.add_weighted_edges_from(graph_edges)
        pos = nx.circular_layout(graph)
        weights = nx.get_edge_attributes(graph, "weight")
        nx.draw(graph, pos, with_labels=True, font_weight='bold')
        nx.draw_networkx_edge_labels(graph, pos, edge_labels=weights)
        plt.title('无向图')
        plt.show()






    def main(self):
        while True:
            print("-------------------------")
            print("|     1、添加地点        |")
            print("|     2、添加路线        |")
            print("|     3、查询最优路径    |")
            print("|     4、删除地点        |")
            print("|     5、删除路径        |")
            print("|     6、展示邻接矩阵        |")
            print("|     7、全部路径        |")
            print("|     8、储存数据        |")
            print("|     9、观看地图       |")
            print("|     10、结束进程       |")
            print("-------------------------")

            a = int(input('请输入你要选择的操作:'))
            if a == 1:
                reation = []
                name = input('请输入你要添加的点的名称')
                coordianx = int(input('请输入你要添加的点的x坐标'))
                coordiany = int(input('请输入你要添加的点的y坐标'))
                coordian = [coordianx,coordiany]
                for i in self.peak:
                    print(f'新的节点与{i}的关系'.format(i = i))
                    j = int(input('请输入:'))
                    reation.append(j)
                reation.append(0)
                self.Add_v(name,coordian,reation)
                print(self.information)
                self.connect_peak()
            elif a == 2:
                frist = input('请输入你要修改两点中的第一点')
                end = input('请输入你要修改两点中的第二点')
                data = int(input('请输入你要修改的值'))
                self.Add_road(frist,end,data)
            elif a == 3:
                frist = input('请输入最短两点中的第一点')
                end = input('请输入最短两点中的第二点')
                i = self.peak.index(frist)
                j = self.peak.index(end)
                self.dijkstra(i,j)
            elif a == 4:
                place = input('请输入你要修改的点')
                self.del_v(place)
            elif a == 5:
                frist = input('请输入删除路径两点中的第一点')
                end = input('请输入删除路径两点中的第二点')
                i = self.peak.index(frist)
                j = self.peak.index(end)
                self.del_road(i,j)
            elif a == 6:
                self.display_edges()
            elif a == 7:
                frist = input('请输入全部路径两点中的第一点')
                end = input('请输入全部路径两点中的第二点')
                self.all_road(frist,end)
            elif a == 8:
                self.save_map()
            elif a == 9:
                self.visualizatiom()
            elif a == 10:
                break

if __name__ == '__main__':
    data = Map()
    data.load_edges()
    data.main()

一个遗憾,没有用mysql,一直用pandas将数据存储在xlsx

 

 

 同样,要运行本程序需要在同文件下创建一个vexdata.xlsx文件和Mapdata.xlsx文件,同时这里面需要数据

1.vexdata.xlsx需要邻接矩阵的数据,如下为参考

2.Mapdata.xlsx需要每个点的坐标,如下为参考

如果还有什么问题可以评论区提出来,本人基本上可以隔天回复

 

 

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
上一篇 2022年5月26日 上午11:38
下一篇 2022年5月26日 上午11:43

相关推荐

本站注重文章个人版权,不会主动收集付费或者带有商业版权的文章,如果出现侵权情况只可能是作者后期更改了版权声明,如果出现这种情况请主动联系我们,我们看到会在第一时间删除!本站专注于人工智能高质量优质文章收集,方便各位学者快速找到学习资源,本站收集的文章都会附上文章出处,如果不愿意分享到本平台,我们会第一时间删除!