GraphLibrary/README.txt at master · LexLippi/GraphLibrary · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
Название задачи: Поиск в графе
Автор: Липаткин Алексей
Версия языка: 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
		Третье число отвечает за вес ребра