Skip to content

LexLippi/GraphLibrary

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Название задачи: Поиск в графе
Автор: Липаткин Алексей
Версия языка: Python 3.6.8
Программа анализирует 5 алгоритмов поиска пути на графе по времени и производительности.

Библиотека состоит из 10 модулей:
	main.py - модуль, который запускает алгоритм для поиска пути из стартовой вершины в конечную
	graph_parser.py - модуль для чтения графа из файла
	graph.py - модуль, содержащий класс граф в котором реализовано внутреннее представление графа
	graph_algo.py - модуль, содержащий алгоритмы для поиска путей на графе
	graph_factory.py - модуль, создающий граф определенного типа
	graph_generator.py - модуль, генерирующий графы
	graph_types.py - модуль, содержащий типы графов
	infinity.py - модуль, содержащий класс бесконечность, который больше всех числовых значений
	priority_queue.py - модуль, в котором реализована структура очередб с приоритетами
	tester.py - модуль, где реализовано тестирование алгоритмов по производительности и памяти

Тесты содержатся в каталоге tests и покрывают модули graph.py, graph_parser.py, graph_algo.py,
graph_generator.py, infinity.py, priority_queue.py

Примеры запуска:
	py main.py [--input/-i] input_filename [--output/-o] output_folder [--algorithm/-a] algorithm_name
	[--start] start_node [--end] finish_node
	start_node, finish_node - вершины между которыми надо искать путь
Для получения справки:
	py main.py --help

Формат ввода:
1 строка - заголовок, поясняющий в каком виде будет передан граф
	adjmat|adjlist|edlist [w] [o]
Далее, описывается в каком виде ожидается тот или иной тип графа:

1) adjacency matrix
		3 - количество вершин в графе
		0 2 4
		8 * 0
		7 0 *
		На пересечении i-й строки и j-го столбца стоит символ:
		Числа - вес ребра графа из i-й вершины в j-ю
		* - отсутствие ребра из i-й вершины в j-ю

2) adjacency list
		1: 2 1 3 1
		2: 1 1 3 1 - i-я строка показывает в какие вершины исходят ребра из i-й вершины
		3: 1 1 2 1 3 1
		Числа пишутся парами. В какую вершину есть ребро и сколько оно весит, вес всех ребер по умолчанию 1

3) edge list
		1 2 1
		1 3 1
		2 4 1
		Каждая строка показывает между какими вершинами есть ребро, вес всех ребер по умолчанию 1
		Третье число отвечает за вес ребра

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages