МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение высшего образования

«САНКТ-ПЕТЕРБУРГСКИЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ»

КАФЕДРА № 41

ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ

ПРЕПОДАВАТЕЛЬ

Доц., канд. техн. наук				Е.А. Бакин
должность, уч. степень, звание		подпись, дата		инициалы, фамилия

ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №2

Базовые алгоритмы на графах.

по курсу: Построение и анализ графовых моделей

РАБОТУ ВЫПОЛНИЛ

СТУДЕНТ ГР. №	4616				А.В.Павлов
			подпись, дата		инициалы, фамилия

Санкт-Петербург 2019

Цель работы

Реализовать и проверить на тестовом примере базовый алгоритм на графе. Сравнить быстродействие реализованного алгоритма на специальных графах.

Вариант 4-1

Алгоритм Дейкстры, правильная квадратная решетка

Описание разработанной программы

Листинг программы

from collections import deque, namedtuple

import igraph

import os

import numpy as np

import time

from sys import getsizeof

import matplotlib.pyplot as plt

inf = float('inf')

Edge = namedtuple('Edge', 'start, end, cost')

def make_edge(start, end, cost=1):

return Edge(start, end, cost)

class Graph:

def __init__(self, edges):

# let's check that the data is right

wrong_edges = [i for i in edges if len(i) not in [2, 3]]

if wrong_edges:

raise ValueError('Неправильные данные: {}'.format(wrong_edges))

self.edges = [make_edge(*edge) for edge in edges]

@property

def vertices(self):

return set(

sum(

([edge.start, edge.end] for edge in self.edges), []

)

)

def get_node_pairs(self, n1, n2, both_ends=True):

if both_ends:

node_pairs = [[n1, n2], [n2, n1]]

else:

node_pairs = [[n1, n2]]

return node_pairs

def remove_edge(self, n1, n2, both_ends=True):

node_pairs = self.get_node_pairs(n1, n2, both_ends)

edges = self.edges[:]

for edge in edges:

if [edge.start, edge.end] in node_pairs:

self.edges.remove(edge)

def add_edge(self, n1, n2, cost=1, both_ends=True):

node_pairs = self.get_node_pairs(n1, n2, both_ends)

for edge in self.edges:

if [edge.start, edge.end] in node_pairs:

return ValueError('Нет выхода'.format(n1, n2))

self.edges.append(Edge(start=n1, end=n2, cost=cost))

if both_ends:

self.edges.append(Edge(start=n2, end=n1, cost=cost))

@property

def neighbours(self):

neighbours = {vertex: set() for vertex in self.vertices}

for edge in self.edges:

neighbours[edge.start].add((edge.end, edge.cost))

return neighbours

def dijkstra(self, source, dest):

assert source in self.vertices, 'Нет выхода'

distances = {vertex: inf for vertex in self.vertices}

previous_vertices = {

vertex: None for vertex in self.vertices

}

distances[source] = 0

vertices = self.vertices.copy()

while vertices:

current_vertex = min(

vertices, key=lambda vertex: distances[vertex])

vertices.remove(current_vertex)

if distances[current_vertex] == inf:

break

for neighbour, cost in self.neighbours[current_vertex]:

alternative_route = distances[current_vertex] + cost

if alternative_route < distances[neighbour]:

distances[neighbour] = alternative_route

previous_vertices[neighbour] = current_vertex

path, current_vertex = deque(), dest

while previous_vertices[current_vertex] is not None:

path.appendleft(current_vertex)

current_vertex = previous_vertices[current_vertex]

if path:

path.appendleft(current_vertex)

return path

matrix=[

("0", "1", 6), ("0", "2", 6), ("1", "4", 4), ("2", "5", 4),

("3", "1", 10), ("3", "2", 10), ("3", "4", 10), ("3", "5", 10),

("4", "5", 2),("4", "6", 4),("5", "6", 2)]

x=np.delete(matrix,())

x = x.astype(np.int)

test=[]

for i in range(2,len(x),3):

test.append([(x[i-2],x[i-1]),x[i]])

print(test)

matrix = []

for el in test:

matrix.append( (str(el[0][0]), str(el[0][1]) , el[1]) )

print(matrix)

graph = Graph(matrix)

label=["0","1","2","3","4","5","6"]

print(graph.dijkstra("0", "6"))

G = igraph.Graph(directed=True)

G.add_vertices(7)

G.vs['label'] = [label[i] for i in range(len(label))]

G.add_edges([i[0] for i in test])

G.es['weight'] = [i[1] for i in test]

G.es['label'] = [i[1] for i in test]

layout = G.layout('kk')

igraph.plot(G, 'graph.png', bbox=(1000, 1000), layout=layout, vertex_size=40,

vertex_label_size=10, edge_width=[edge for edge in G.es['weight']])

os.startfile(r'graph.png')

times = []

sizes=[]

number=np.arange(1,10,1)

for i in range(1,10):

size=i

start_time = time.time()

N=size*size

matrix=([])

for i in range(N):

row = (np.zeros(N))

for j in range(N):

if i+1!=size and i+1!=size*2 and i+1!=size*3 and i+1!=size*4 and i+1!=size*5 and i+1!=size*3 and i+1!=size*6 and i+1!=size*7 and i+1!=size*8 and i+1!=size*9 and i+1!=size*10 and i+1!=size*11 and i+1!=size*12 and i+1!=size*13:

if i+1==j:

row[j]=1

elif i+size==j:

row[j] = 1

elif i+size==j:

row[j] = 1

# matrix=np.append(matrix,row,axis=0)

matrix.append(row)

#print(row)

# print(matrix)

#getsizeof(adj_list)

exec_time = time.time() - start_time

times.append(exec_time*1000)

sizes.append(getsizeof(matrix))

print("Размер",getsizeof(matrix))

print('Время выполнения:', exec_time)

plt.plot(number,sizes)

plt.xlabel('Размер матрицы')

plt.ylabel('Размер в битах')

plt.show()

plt.plot(number,times)

plt.xlabel('Размер матрицы')

plt.ylabel('Время в милисекунда')

plt.show()

adj_matrix=matrix

def Adjacency_List(matrix):

adj_list = []

for i in range(len(matrix)):

for j in range(len(matrix[i])):

if matrix[i][j] != 0:

adj_list += [[tuple([i, j]), adj_matrix[i][j]]]

print(adj_list)

return adj_list, print('Размер списка смежности: ', getsizeof(adj_list))

Adjacency_List(matrix)

Изображения графа

Рисунок 1- Граф полученный программой

Рисунок 2 – Граф полученный программой для квадратной матрицы

Графики зависимости

Рисунок 3 – График зависимости времени от размера матрицы

Рисунок 4 – График зависимости размера в байтах от размера матрицы

Выводы:

В ходе лабораторной работы, я научился работать с алгоритмом Дейкстры. А так же создавать правильную квадратную решетку матрицы.

Время создания квадратной решетки от времени растет по экспоненциальному закону. Для первых 4 размеров время остается неизменным тогда как для последующих размеров, время растет очень быстро.

Доп. Вопрос

По заданному весу найти связи.

def dopvopros(adj_list):

sosedi=[]

number=10

print(adj_list[0][1])

for i in range(len(adj_list)):

if adj_list[i][1] == number:

sosedi.append(adj_list[i][0])

print(sosedi)