Пояснительная записка к проекту по дисциплине "Технологии программирования" на тему"Автоматизированная система поиска оптимального пути на карте города по заданному критерию"

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО
ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ
УНИВЕРСИТЕТ имени акад. С. П. КОРОЛЕВА» (СГАУ)
Кафедра программных систем

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к проекту по дисциплине
"Технологии программирования" на тему "Автоматизированная система поиска оптимального пути на карте города по заданному критерию"

Выполнили:
студенты гр.643

Руководитель проекта:
доцент каф. ПС

Дата сдачи:

Оценка:

Самара 2008 г.

Р Е Ф Е Р А Т

Пояснительная записка: 35 c., 26 рис., 3 табл., 20 источников, 2 приложения

АВТОМАТИЗИРОВАННАЯ СИСТЕМА, ОПТИМАЛЬНЫЙ МАРШРУТ, РЕДАКТОР КАРТ, БАЗА ДАННЫХ, КРИТЕРИЙ ОПТИМАЛЬНОСТИ, ТЕХНОЛОГИЯ RAD

СОДЕРЖАНИЕ

Р Е Ф Е Р А Т...................................................................................................................................... 2

ВВЕДЕНИЕ........................................................................................................................................ 3

1 СИСТЕМОТЕХНИЧЕСКАЯ ЧАСТЬ.......................................................................................... 6

1.1 Описание и анализ предметной области................................................................................... 6

1.1.1 Описание структуры карты города......................................................................................... 6

1.1.2 Описание графовой модели..................................................................................................... 7

1.1.3 Анализ предметной области.................................................................................................... 8

1.2 Постановка задачи....................................................................................................................... 9

1.3 Структурная схема системы..................................................................................................... 11

1.4 Разработка спецификации системы......................................................................................... 12

1.4.1 Спецификация качества......................................................................................................... 12

1.4.2 Функциональная спецификация........................................................................................... 13

1.5 Разработка модели данных....................................................................................................... 19

1.6 Разработка классов и структур данных................................................................................... 21

1.7 Выбор и обоснование алгоритмов обработки данных.......................................................... 23

1.8 Выбор и обоснование комплекса программных средств...................................................... 25

1.8.1 Выбор среды разработки........................................................................................................ 25

1.8.2 Выбор языка программирования.......................................................................................... 25

1.8.3 Выбор операционной системы.............................................................................................. 26

1.8.4 Выбор СУБД............................................................................................................................ 26

2 КОНСТРУКТИВНО-ТЕХНОЛОГИЧЕСКАЯ ЧАСТЬ............................................................. 26

2.1 Разработка и описание интерфейса......................................................................................... 26

2.1.1 Разработка и описание меню................................................................................................. 28

2.1.2 Описание контрольного примера......................................................................................... 29

2.2 Реализация классов и структур данных.................................................................................. 30

2.3 Описание структуры моделей.................................................................................................. 31

2.4 Выбор и обоснование комплекса технических средств........................................................ 32

2.4.1 Расчет требуемых ресурсов.................................................................................................... 32

2.4.2 Минимальные требования к комплексу технических средств.......................................... 33

ЗАКЛЮЧЕНИЕ................................................................................................................................ 34

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ...................................................................... 35

ПРИЛОЖЕНИЕ А........................................................................................................................... 37

Руководство пользователя.............................................................................................................. 37

А.1 Назначение системы................................................................................................................. 37

А.2 Установка системы................................................................................................................... 37

А.3 Требования к аппаратным и программным средствам......................................................... 38

А.4 Описание основных действий пользователя......................................................................... 38

ПРИЛОЖЕНИЕ В........................................................................................................................... 42

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

ВВЕДЕНИЕ

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

Дорожная отрасль является одной из важнейших отраслей экономики любой промышленно развитой страны. Недаром автомобильные дороги называются «кровеносной системой» любого государства. Они играют огромную социально-экономическую роль в жизни современного общества. В Российской Федерации в силу огромной пространственной протяженности территории транспортные издержки существенно больше среднемировых показателей. Автомобильные дороги являются очень капиталоемкими, но в тоже время и очень рентабельными сооружениями. Известно, что каждый рубль, вложенный в автомобильные дороги, в перспективе многократно (в 3–5 раз) возвращается в различных других отраслях экономики за счет снижения транспортных (логистических) издержек, снижения аварийности, повышения подвижности населения [1].

Низкий уровень развития сети автомобильных дорог России является существенным сдерживающим фактором роста рыночной экономики, при которой автомобильный транспорт играет доминирующую роль [2]. К сожалению, строительство дорог идет недостаточно высокими темпами, и дорожно-транспортные сети города не справляются с постоянно возрастающей на них нагрузкой. Зачастую строительство дорог ограничено не только финансовыми рамками и строительными возможностями, но и архитектурой города. Последнее делает невозможным строительство новых или расширение имеющихся дорог в плотно застроенных или исторических местах города. Поэтому высока актуальность разработки и программной реализации алгоритмов, способных анализировать имеющуюся дорожно-транспортную сеть города и определять оптимальные с различных точек зрения маршруты движения.

Чтобы разгрузить некоторые дороги, выбрать наиболее выгодный и быстрый маршрут (например, минуя самые загруженные части города), задачу необходимо решать в комплексе, рассматривая её с точки зрения времени и стоимости. Поэтому необходимо разработать автоматизированную систему расчёта оптимальных маршрутов, которая позволяет пользователю моделировать различные ситуации. Её можно использовать как в личных целях, планируя маршрут своего движения на день, так и в качестве системы для организации движения транспортных средств, например, автобусов определённого маршрута.

Проект будет разрабатываться по технологии быстрой разработки приложений RAD (Rapid Application Development), которая поддерживается методологией структурного проектирования и включает элементы объектно-ориентированного проектирования и анализа предметной области.

1 СИСТЕМОТЕХНИЧЕСКАЯ ЧАСТЬ

1.1 Описание и анализ предметной области

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

1.1.1 Описание структуры карты города

Задача выбора оптимального маршрута постоянно встаёт перед автомобилистом в реальной жизни: нужно решить, по какому маршруту он доберется от дома до своей работы за кратчайшее время. На рисунке 1 приведен фрагмент карты города Самары.

Рисунок 1 – Карта города Самары

Двигаться автомобилист может только по дорогам (улицам), при этом должно учитываться расположение светофоров и знаков, которые будут влиять на среднюю скорость его передвижения. Если движение происходит утром, то, возможно, на самых оживленных улицах движение будет сильно затруднено, и передвигаться нужно будет объездными дорогами. Так как с дороги пользователь никуда свернуть не может, то маршрут однозначно определяется перекрестками, через которые он проехал.

1.1.2 Описание графовой модели

Для решения этой задачи удобно представить карту города в виде графа, где вершинами графа будут являться перекрестки, а дугами – дороги (см. рисунок 2).

Рисунок 2 – Пример карты города

Графом G мы будем называть пару (V(G), E(G)), где V(G) – непустое конечное множество элементов, называемых вершинами, а E(G) – конечное множество неупорядоченных пар элементов из V(G), называемых ребрами.

Мы будем рассматривать только конечные графы, то есть такие, у которых оба множества конечны. Вершины и ребра графа будем называть его элементами. Множество вершин графа G будем обозначать через VG, множество ребер – EG, число вершин – n(G), число ребер – m(G).

Ориентированным графом (орграфом) называется пара G=(V, E), где V – конечное множество, E – множество упорядоченных пар различных элементов из V.

Маршрут в графе – это последовательность вершин x1, x2… xn, такая, что для каждого i=1, 2… n−1 вершины xi и xi+1 соединены ребром. Путь – это маршрут, в котором все ребра различны, все вершины в нем различны.

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

Таким образом, получим весовой орграф, представленный на рисунок 3. Задача сводится к поиску кратчайшего пути между двумя вершинами, например A и B. Наиболее распространенным и эффективным алгоритмом решения такой задачи является алгоритм Дейкстры.

Рисунок 3 – Весовой орграф

1.1.3 Анализ предметной области

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

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

Рисунок 4 – Основные объекты

Рассмотрим основные характеристики объектов:

1) Карта:

размер по горизонтали и вертикали (в км);

масштаб (метров/пиксель);

количество перекрестков;

количество дуг;

2) Перекресток:

расположение на карте;

список связанных с ним перекрёстков;

список входящих/исходящих из него дорог;

наличие светофора;

3) Дорога:

номера связанных ею перекрёстков;

одностороннее/двустороннее движение;

наличие знака ограничения скорости;

наличие милиционера;

значение средней скорости;

тип покрытия;

название улицы;

4) Светофор:

фаза;

время горения каждого цвета;

1.2 Постановка задачи

Перед авторами поставлена задача - разработать АС, способную решать задачу поиска оптимального маршрута по заданному критерию.

Основные функции системы:

редактирование карт;

средства работы с базами данных;

средства моделирования.

Основным объектом является карта города. Пользователь должен иметь возможность наглядного создания и редактирования участка карты города, а также сохранения её в файл или загрузки её из файла. Работа с картой города должна включать в себя следующие функции: пользователь может добавлять и удалять перекрёстки (количество – от 2 до 1024); дороги с указанием средней скорости движения на них (от 0 до 60 км/ч); различные препятствия, такие как: знаки ограничения скорости, одностороннего движения, светофоры, наличие милиционера и наличие пробки; текстовые метки с названием улиц.

Для расширения возможностей системы в ней необходимо предусмотреть возможность ведения базы данных (БД). БД должна содержать информацию об автомобилях и их владельцах. В качестве информации об автомобилях необходимо учитывать название марки автомобиля; максимальную скорость, развиваемую им; расход топлива в литрах на 100 км; наличие в автомобиле антирадара. В качестве информации о владельцах необходимо учитывать фамилию владельца транспортного средства, название марки этого транспортного средства, а также информацию, является ли владелец нарушителем правил дорожного движения или нет. Для того чтобы промоделировать различные ситуации по разным критериям оптимальности, необходимо дать возможность пользователю изменять содержимое БД (добавлять, удалять, изменять записи). В процессе редактирования БД необходимо проверять записи на дублирование, а также контролировать её целостность. Также необходимо предоставить возможность добавления дополнительных полей к каждой таблице.

Моделирование движения автотранспорта в городе в соответствии с маршрутом является наиболее важной частью системы. Пользователь должен иметь возможность задавать критерий оптимальности (по длине маршрута, по времени или по стоимости), начальную и конечную точки маршрута, отметив их на карте, и выбирать из БД, для какого автомобилиста необходимо решить поставленную задачу.

Полученное решение должно визуализироваться подсветкой маршрута на карте города.

При возникновении затруднений у пользователя должна иметься возможность обратиться к информационной поддержке системы.

Таким образом, система должна реализовывать следующие функции:

1) поиск оптимального маршрута по выбранному критерию;

2) настройка параметров системы;

3) ведение справочников;

4) работа с картой города:

добавление объекта;

удаление объекта;

изменение свойств объекта;

перемещение объекта;

настраивание параметров объекта;

загрузка карты из базы;

сохранение карты в базу;

5) визуализация процессов работы с картой;

6) выдача справочной информации о системе.

1.3 Структурная схема системы

Структурная схема – это графическое изображение системы в виде совокупности частей, на которые её можно разделить по определенным признакам, и связей между частями с указанием направления передачи воздействия [3].

Разделим систему по функциональному признаку на основные подсистемы, укажем между ними информационные связи или связи по управлению и опишем основное назначение подсистем. На рисунке 5 представлена структурная схема системы.

Рисунок 5 – Структурная схема системы

В состав системы входят следующий подсистемы:

Подсистема управления отвечает за принятие команд и реакцию на них, т. е. за взаимодействие с пользователем.

Подсистема редактирования карты города отвечает за работу редактора карт.

Подсистема работы с базой данных отвечает за работу с базой данных.

Подсистема настройки отвечает за ввод исходных данных.

Подсистема моделирования отвечает за вычисление оптимального маршрута.

Подсистема визуализации отображает полученное из подсистемы моделирования решение на карте города.

Подсистема справки отвечает за выдачу справочной информации пользователю.

1.4 Разработка спецификации системы

1.4.1 Спецификация качества

Качество программы – это степень соответствия установленным для нее спецификациям; совокупность черт и характеристик программы, которые влияют на ее способность удовлетворить заданные потребности пользователя [4].

Надежность программного комплекса обеспечивается использованием на сервере файловой системы с журналированием (ext3), а также использованием базы данных (БД) с поддержкой транзакций и обеспечением ссылочной целостности.

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

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

Клиентская часть комплекса должна иметь возможность исполнения на различных аппаратно-программных платформах, что позволяет смягчить требования, предъявляемы к аппаратному и программному обеспечению заказчика.

Реализация программного комплекса по парадигме “клиент-сервер” предоставляет почти неограниченные возможности по масштабированию системы (возможность произвести шардинг БД посредством средства SkyTools, а также уже реализованную возможность достижения отказоустойчивости серверного ПО посредством запуска её на нескольких серверах с последующей реализацией распределения нагрузки, например, посредством алгоритма отдачи DNS записей -- RoundRobin ).

Легкость работы пользователя с программой достигается посредством наличия общей и контекстной справок.

Благодаря гибкой архитектуре с использованием виртуализации существует возможность запустить сервер программного комплекса на почти любой системе.

1.4.2 Функциональная спецификация

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

Функциональная спецификация должна в полном объёме отображать информационные связи проектируемой АС как с внешним миром, так и между подсистемами.

Функциональная спецификация системы включает в себя:

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

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

Таблица 1 – Перечень функций, выполняемых системой

Название подсистемы	Название функции	Информационная среда
Исходные данные	Результирующие данные
Назначение	Тип, ограничение	Назначение	Тип, ограничение
Загрузить подложку	список файлов формата png, svg	файл формата png, svg	фоновое изображение	матрица цветов в формате ARGB или векторное изображение
Расположить объект на карте:			положение объекта заданного типа на карте
(целый без знака, целый без знака), уникальны
Перекресток	координаты	(целый без знака, целый без знака)
Дорога	идентификаторы начального и конечного перекрестков	(целый без знака, целый без знака)	отрезок с целыми беззнаковыми координатами
определяется в процессе разработки
Светофор	идентификатор перекрестка	(целый без знака)
дорожный знак	идентификатор дороги	(целый без знака)
Пробка	идентификатор дороги	(целый без знака)
Милиционер	идентификатор дороги	(целый без знака)

Таблица 1 – Перечень функций, выполняемых системой

Название подсистемы	Название функции	Информационная среда
Исходные данные	Результирующие данные
Назначение	Тип, ограничение	Назначение	Тип, ограничение
Подсистема редактирования карты города	Выбрать объект на карте	объект какого-либо типа на карте	(целый без знака, целый без знака)	тип объекта	(целый без знака, целый без знака)
Настроить выбранный объект:			настройки объекта на карте
Дорога	тип покрытия	Уникальный беззнаковый идентификатор типа покрытия	текущий идентификатор типа покрытия	целый без знака
Светофор	время горения каждого из сигналов	целый без знака 10…100	текущее начальное состояние; текущая фаза переключения	перечислимый; целый без знака
дорожный знак	ограничение скорости; направление движения	целый без знака, 5…80; целый без знака, одностороннее/двустороннее	текущее значение ограничения скорости; текущее значение направления движения	целый без знака; определяется в процессе разработки
Пробка	средняя скорость движения	целый без знака, 5…30	текущее значение средней скорости	целый без знака
Милиционер	величина штрафа при превышении скорости на 1 км/ч	целый без знака, 1…200	текущее значение величины штрафа	целый без знака

Таблица 1 – Перечень функций, выполняемых системой

Название подсистемы	Название функции	Информационная среда
Исходные данные	Результирующие данные
Назначение	Тип, ограничение	Назначение	Тип, ограничение
Подсистема редактирования карты города	Переместить перекресток на карте	объект «перекресток» на карте	координаты (целый без знака, целый без знака)	объект «перекресток» на карте	изменение внутреннего состояния объекта «карта»
Удалить перекресток с карты	удаление перекрёстка	идентификатор (целое беззнаковое) и координаты (целое беззнаковое) перекрестка, а также идентификаторы связанных с ним дорог (целое беззнаковое)
Удалить дорогу с карты	удаление связи между перекрёстками	идентификатор начального перекрестка (целое беззнаковое) и идентификатор конечного перекрестка (целое беззнаковое)
Загрузить карту с сервера, из файла	Файл	строковый, *.json	карта города представлена в формате *.json
Сохранить карту в файл, загрузить на сервер	карта города представлена в формате *.json	строковый, *. json	файл	JSON-формат

Таблица 1 – Перечень функций, выполняемых системой

Название подсистемы	Название функции	Информационная среда
Исходные данные	Результирующие данные
Назначение	Тип, ограничение	Назначение	Тип, ограничение
Подсистема справки	Выдать справочную информацию о системе и ее назначении	информационная поддержка работы пользователя	файл в формате PDF	Визуальное отображение информации

Таблица 2 – Перечень исключительных ситуаций

Название подсистемы	Название исключительной ситуации	Реакция системы
Подсистема редактирования карты города	Попытка установить объект на место уже имеющегося	Выдача соответствующего информационного сообщения
Попытка ввода недопустимых значений в свойствах объекта
Подсистема управления БД	Попытка ввода недопустимых значений
Проблема при соединении с сервером
Подсистема работы с файловой системой	Невозможность выполнения операции с файлом

1.5 Разработка модели данных

В реализуемом проекте часть данных необходимо хранить в базе данных (БД). БД состоит из множества таблиц (в каждой из таблиц хранятся экземпляры классов, описанных выше), соединённых релятивным отношением один ко многим. Логическая модель данных представлена на рисунке 7.

Проанализируем предметную область и выделим основные сущности предметной области с принадлежащими им атрибутами:

водитель – человек, который имеет паспорт (серия, номер, Ф. И.О., прописка) и водительское удостоверение, а также владеет автомобилем, и может иметь существующие штрафы и антирадар;

автомобиль - характеризуется маркой, моделью, максимальной скоростью, типом потребляемого топлива, расходом топлива на 100 км;

милиционер – человек, который за превышение скорости на 1 км/ч взимает определенную сумму;

топливо - характеризуется октановым числом и ценой за 1 л;

участок дороги - характеризуется покрытием, установленными на нем ограничениями, названием улицы;

покрытие - характеризуется коэффициентом влияния на скорость автомобиля;

ограничители - светофоры, знаки ограничения скорости, одностороннего движения, заторы;

карта города – совокупность сущностей предметной области с установленными отношениями, ограничениями и взаимозависимостями.

У ограничителей можно выделить следующие атрибуты:

светофор - время горения фазы в сек.;

знак ограничения скорости - значение предела скорости;

знак одностороннего движения - направление движения;

затор - скорость движения.

Рисунок 6 – Логическая модель данных

1.6 Разработка классов и структур данных

Класс – это определенный разработчиком тип данных, который обладает внутренними данными и методами в форме процедур или функций и обычно описывает родовые признаки и способы поведения ряда похожих объектов.

Рисунок 7 – Диаграмма классов

В таблице 3 приведена спецификация основных классов, используемых в программе.

Таблица 3 – Спецификация класса Driver

Person
-	Имя	строка
-	Фамилия	строка
-	Отчество	строка
+	получить имя
+	получить фамилию
+	получить отчество
+	установить имя
+	установить фамилию
+	установить отчество
-	идентификатор автомобиля	класс «автомобиль»
-	наличие существующих нарушений	булевый
+	узнать о наличии нарушений
+	получить идентификатор автомобиля
+	установить идентификатор автомобиля
+	установить наличие нарушений

Таблица 4 – Спецификация класса Policeman

Policeman
–	цена превышения скорости на 1 км/ч	вещественный
–	склонность к взятке	булевый
+	получить склонность к взятке
+	установить склонность к взятке
+	получить цену превышения
+	установить цену превышения

Таблица 5 – Спецификация класса Car

Car
–	Производитель	строка
–	модель	строка
–	максимальная скорость	целый без знака
–	тип топлива	перечислимый
–	потребление топлива на 100 км	вещественный
+	получить марку
+	получить модель
+	получить максимальную скорость
+	получить потребление на 100 км
+	получить тип топлива
+	установить марка
+	установить модель
+	установить максимальную скорость
+	установить потребление на 100 км
+	установить тип топлива

Таблица 6 – Спецификация класса CoverageType

CoverageType
–	тип покрытия	перечислимый
–	коэффициент влияния	вещественный
+	получить тип покрытия
+	получить значение коэффициента влияния на скорость
+	установить тип покрытия
+	установить коэффициент влияния на скорость

Таблица 7 – Спецификация класса PetrolPrice

PetrolPrice
–	тип топлива	перечислимый
–	цена за 1 л	вещественный
+	получить тип топлива
+	получить значение цены
+	установить тип топлива
+	установить значение цены

1.7 Выбор и обоснование алгоритмов обработки данных

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

Для отображения результатов на экране был разработан и реализован алгоритм визуализации. Рисование производится посредством графической подсистемы Qt4 (рисование линий, прямоугольников, закрашивание области и т. д.), также возможен ускоренный вывод графики посредством OpenGL.

Основным алгоритмом в нашей системе является алгоритм Дейкстры. На рисунке 8 представлена схема алгоритма.

Пусть число вершин в графе равно N. Алгоритм использует три массива из N чисел каждый. Первый массив Flag содержит метки с двумя значениями: False (вершина еще не рассмотрена) и True (вершина уже рассмотрена); второй массив Way текущие кратчайшие расстояния от начальной до соответствующей вершины; третий массив Prev содержит номера вершин – k-ый элемент Prev есть номер предпоследней вершины на текущем кратчайшем пути из начальной вершины в k-ую. Используется также Matrix – матрица расстояний. Номер пункта отправления – start, пункта назначения – finish [10].

 

Рисунок 8 - Схема алгоритма Дейкстры

Описание алгоритма Дейкстры:

1 (инициализация). В цикле от 1 до N заполнить значением False массив Flag, заполнить нулями массив Prev, заполнить Matrix очень большими числами (превышающими суммарную длину всех ребер графа);

Flag[start] = True; Way [start] = 0; Prev [start] = 0;

Текущую вершину now приравнять к стартовой.

2 (общий шаг). В цикле проверяются все не отмеченные вершины, связанные с текущей. Пусть проверяется вершина k: если Way[k] > Way[now] + Matrix[now, k], то (Way[k] =Way[now] + Matrix[now, k]; Prev[k] = now). Т. е., если текущий кратчайший путь в вершину k больше суммы пути в текущую вершину now и пути из now в k, то запоминается новое значение кратчайшего пути в k и указывается, что предшествующая вершина для k – это now.

Найти минимум среди неотмеченных (т. е. тех k, для которых Flag[k] = False). Пусть минимум достигается на индексе j, т. е. Way[j] £ Way[k], тогда приравнять текущую вершину к минимальной (now = j).

3 (проверка условия завершения). Если текущая вершина является пунктом назначения (now = finish), то завершить работу алгоритма (найден кратчайший путь из start в finish, который хранится в массиве Prev). Иначе перейти на п. 2.

1.8 Выбор и обоснование комплекса программных средств

1.8.1 Выбор среды разработки

Для разработки визуальной части программного комплекса была использована интегрированная среда разработки для языка С++ Qt Creator производства компании Trolltech Software. Данная среда предназначена для быстрой (Rapid) разработки приложений, она включает в себя средство визуального редактирования форм, развитой редактор кода, встроенный механизм Unit тестирования, интеграцию в системы контроля версий, средство для локализации приложений, а также встроенную контекстную справку. Все это позволяет быстро и качественно разрабатывать различные приложения.

Для координации разработки была использована система управления версиями (VCS) Subversion, что позволило производить взаимодействие ещё более эффективно.

Для разработки схемы базы данных и серверного приложения был использован редактор gVIM, имеющий средства для подсветки SQL синтаксиса.

1.8.2 Выбор языка программирования

Для реализации пользовательского интерфейса и ядра системы был использован язык С++, т. к. приложения написанные на нём обладают высокими скоростными характеристиками. Также важную роль сыграло наличие качественных свободных библиотек, в частности для работы с графами (boost) и реализации пользовательского интерфейса(Qt).

Для работы с базой данных использовался язык SQL, а для написания регрессионных тестов -- динамический язык Perl, т. к. он позволяет очень быстро писать приложения, работающие со сложными структурами данных.

1.8.3 Выбор операционной системы

Клиентская часть нашего программного комплекса успешно работает на следующих семействах операционных систем: Linux, Windows, FreeBSD, а также MACOS. Программа была протестирована на них всех, за исключением MACOS по причине отсутствия ПК с данной системой. Серверная часть работает на операционных системах семейства *nix, т. к. они отличаются надежностью, безопасностью, гибкостью настройки и развертывания, очень эффективной работой с сетевой подсистемой, а также (часто) бесплатностью.

1.8.4 Выбор СУБД

Нами была выбрана сетевая реляционная объектная БД – PostgreSQL, т. к. она имеет очень мощную подсистему работы с географическими данными, легкий интерфейс для написания собственных хранимых процедур, библиотеки взаимодействия с С++ и Perl, а также развитой системой индексов и высокой скоростью работы.

2 КОНСТРУКТИВНО-ТЕХНОЛОГИЧЕСКАЯ ЧАСТЬ

2.1 Разработка и описание интерфейса

Интерфейс современного программного обеспечения должен отвечать требованиям дружественности и должен быть интуитивно понятным. К настоящему времени выработаны различные стандарты к принципам организации пользовательского интерфейса. Исходя из принципов удобства управления и навигации по карте, нами был разработан интерфейс, представленный на рисунке 9.

Рисунок 9 – Общий вид программы

Для организации главного окна программы авторами был использован подход SDI ( Single document interface). Окно состоит из трех панелей -- верхняя (панель управления), правая (панель справки) и центральная (карта).

Рисунок 10 – Интерфейс программы

2.1.1 Разработка и описание меню

Общий вид панели управления представлен на рисунке 11.

Рисунок 11 – Панель управления

Кнопки меню (слева направо) предназначены для:

1) управление справочниками

2) сохранения карты

3) загрузки карты на сервер (работает только при наличии сервера)

4) загрузки карты с сервера (работает только при наличии сервера)

5) Очистки карты

6) увеличения масштаба

7) уменьшения масштаба

8) перехода в режим просмотра карты

9) режим добавления / управления перекрестками

10) режим добавления дорог

11) запуск оптимизации (работает только при наличии сервера)

Строка меню не используется для работы с программой и содержит только пункты "файл -- выход" и "справка -- показать руководство пользователя".

2.1.2 Описание контрольного примера

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

1. Загружаем подложку карты из файла Samara_Map. svg, расположенного в директории программы;

2. Переходим в режим редактирования перекрестков посредством нажатия на кнопку ;

3. Щелкаем по свободной области карты и расставляем пять перекрестков;

4. Переходим в режим добавления дорог, для этого нажимаем кнопку . После этого поочередно соединяем все перекрестки дорогами, выбирая сначала исходный перекресток дороги, а затем конечный.

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

6. Теперь можно перейти в режим просмотра попробовать увеличить или уменьшить карту.

2.2 Реализация классов и структур данных

В связи с разработанными в пункте 1.6 структурой и классами и реализованные в среде описанной в пункте 1.8.1 мы составили следующую реализацию классов и структур:

Класс «Графическая сцена»

class QGScene : public QGraphicsScene

{

Q_OBJECT

public:

int idCounter;

enum QViewMode { mDrag, mNode, mEdge, mSolve };

Node *sourceNode;

QGScene(QObject * parent = 0, GraphWidget * Widget = 0);

// конструктор класса

void setViewMode(QViewMode mode);

// установка режима редактора

protected:

void mousePressEvent ( QGraphicsSceneMouseEvent * mouseEvent );

//обработка нажатия кнопки мыши

private:

QGraphicsTextItem * myText;

QMenu *myContextMenu;

QMenu *myEdgeMenu;

QAction *delAct;

QViewMode vMode;

GraphWidget *myWidget;

authDialog *optform;

public slots:

void deletenode();

// удаление узла

void traffnode(bool checked );

// установка светофора

void deleteedge();

// удаление дороги

void edgeoptions();

// настройка свойств дороги

};

2.3 Описание структуры моделей

Модуль – это автономно компилируемая программная единица, включающая в себя различные компоненты раздела описаний (типы, константы, переменные, процедуры и функции) и, возможно, некоторые исполняемые операторы инициируемой части. Модули представляют собой хороший инструмент для разработки библиотек прикладных программ и мощное средство модульного программирования.
Для реализации программы созданы необходимые программные модули (рисунок 12):

main. cpp: главный модуль программы, запускающий приложение;

mainwindow. h, mainwindow. cpp: содержат код класса главного окна приложения и код класса окна вывода графики;

QGScene. h, QGScene. cpp: содержат код класса графической сцены;

node. h, node. cpp: содержат код класса узла графа;

edge. h, edge. cpp: содержат код класса дуги графа;

model. h, model. cpp: отвечают за сериализацию / десериализацию данных для обмена информацией с сервером, а также содержит методы для работы с протоколом http;

QMainDialog. h: содержит код описания диалогов.

Рисунок 12 - Диаграмма модулей

2.4 Выбор и обоснование комплекса технических средств

2.4.1 Расчет требуемых ресурсов

Рассчитаем необходимый размер памяти для работы клиентской части нашего программного комплекса. Она складывается из объема, занимаемого ОС Windows XP, что составляет около 150 мегабайт, объема клиентского приложения около 60 мегабайт, а также объема памяти, занимаемой вспомогательными данными (файл справки), что составляет около 2 МБ. Итого необходимый объём оперативной памяти составляет около 210 мегабайт. Требование к жесткому диску минимальны -- лишь для хранения временной информации (около 20-40 мегабайт).

Рассчитаем необходимый размер памяти для работы серверной части нашего программного комплекса. Он складывается из объема памяти, требуемой ОС и непосредственно нашим приложением. ОС Линукс в холостом режиме (без запущенных прикладных приложений) потребляет около 120 мегабайт оперативной памяти.

Сервер баз данных PostgreSQL потребляет 50 мб оперативной памяти, сервер, обеспечивающий функционирование приложения (фронтэнд к БД), требует 20 мегабайт оперативной памяти. Итого: 190 мегабайт оперативной памяти. С учетом некоторого запаса по памяти выходит, что приложению необходимо 256 мегабайт оперативной памяти. Требование к размеру жесткого диска в районе 1-2 гигабайт (файлы БД + кэш запросов БД + кэш приложения).

2.4.2 Минимальные требования к комплексу технических средств

Для нормального функционирования системы необходимы:

Требования к серверной части:

Объем ОЗУ не менее чем 512 Мб;

Объем жесткого диска не менее 20 Гб.

Требования к клиентской части:

видеокарта уровня ATI Radeon 8500 / nVidia 5700;

монитор с разрешающей способностью не ниже 800 х 600;

манипулятор – мышь;

объем ОЗУ не менее чем 256 Мб.

ЗАКЛЮЧЕНИЕ

Разработан алгоритм и соответствующая ему программа, позволяющая автоматизировать процесс расчёта оптимального пути в городских условиях, а также реализована визуализация этого процесса. Программа содержит редактор карт и базы данных (транспортных средств, водителей и других настраиваемых справочников). Программный комплекс представляет собой клиент-серверное приложение, серверная часть написана с использованием Ruby, C, pgsql, а клиентская часть С++, Qt4. Операционная система для клиентского приложения Windows XP, Vista, Linux, MAC OS.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1)  Скворцов : Учеб. пособие. – Томск: Изд-во Том. ун-та, 2006. – 336 с.

2)  , , Пуркин проектирование автомобильных дорог (на примере IndorCAD/Road). – М.: Изд-во МАДИ (ГТУ), 2005. – 223 с.

3)  Большая советская энциклопедия [Электронный ресурс]. – Режим доступа: http://slovari. *****/dict/bse/article/00075/29200.htm, свободный.

4)  Зеленко по курсу Технологии программирования. Самара, СГАУ, 2005.

5)  СТО СГАУ 4-2007

6)  ГОСТ 19.701-90 (ИСО 5807-85). ЕСПД. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения. – М.: Изд-во стандартов, 19с.

7)  Новиков математика для программистов: Учебник для вузов. - Санкт-Петербург: Изд-во Питер, 20с.

8)  , , Шварц отношения, графы и коллективные решения: учебное пособие для вузов. - Москва: Изд-во Издательский дом ГУ ВШЭ, 20с.

9)  Приемы объектное-ориентированного проектирования. - Спб.: Изд-во Питер, 20с.

10)  , Таланов и алгоритмы. Структуры данных. Модели вычислений: учебник. - Москва: Изд-во Интернет-Университет Информационных технологий, 20с.

11)  Кормен, Лейзерсон, Ривест, Штайн, Клиффорд Алгоритмы: построение и анализ. - Москва: Изд-во Вильямс, 2007, 1296с.

ПРИЛОЖЕНИЕ А

Руководство пользователя

А.1 Назначение системы

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

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

А.2 Установка системы

Установка в ОС Windows XP заключается в запуске самораспаковывающегося RAR архива и выборе папки для извлечения. Все dll библиотеки включены в поставку, никаких дополнительных программ и записей в реестре не требуется.

Установка в Linux.

При работе в консоли установка заключается в распаковке tar bz2 архива командой tar - xjf smartgui. 2 и запуске проекта командой./project.

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

А.3 Требования к аппаратным и программным средствам

Требования к клиентской части, необходимые для нормальной работы системы:

видеокарта уровня ATI Radeon 8500 / nVidia 5700;

монитор с разрешающей способностью не ниже 800 х 600;

манипулятор – мышь;

объем ОЗУ не менее чем 256 Мб;

тип операционной - Windows XP, Vista, Linux, MAC OS;

А.4 Описание основных действий пользователя

После загрузки подложки карты, программа выглядит следующим образом.

Рисунок 13 – Загрузка карты

Рисунок 14 – Режим добавления/удаления перекрестков

В этом режиме добавление перекрестков осуществляется посредством щелчка левой кнопкой мыши на поле карты. Удаление перекрестков осуществляется выбором требуемого перекрестка и щелчком правкой кнопкой мыши на нём, там будет присутствовать пункт "удалить перекресток".

Рисунок 15 – Добавление светофора

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

Рисунок 16 – Режим добавления/удаления дорог

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

Рисунок 17 – Режим масштабирования

В режиме просмотра посредством колесика мыши или кнопок на панели управления существует возможность масштабирования и прокрутки карты по горизонтали и вертикали.

Рисунок 18 - Пример уменьшения масштаба

Рисунок 19 – Очистка карты

После работы можно очистить поле карты нажатием кнопки "5. очистка карты".

ПРИЛОЖЕНИЕ В

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

-- цены на бензин

DROP TABLE IF EXISTS petroleum_prices CASCADE;

CREATE TABLE petroleum_prices (

petroleum_id serial NOT NULL PRIMARY KEY,

title varchar(255) NOT NULL UNIQUE,

price numeric(9,2) NOT NULL

);

COPY petroleum_prices (petroleum_id, title, price) FROM stdin;

1 AI92 23.44

2 AI95 25.20

\.

-- марки автомобилей

DROP TABLE IF EXISTS car_models CASCADE;

CREATE TABLE car_models (

model_id serial NOT NULL PRIMARY KEY,

marka varchar(255) NOT NULL,

model varchar(255) NOT NULL,

max_speed numeric(9,2) NOT NULL,

liters_per_100_km numeric(9,2) NOT NULL,

petroleum_id integer NOT NULL REFERENCES petroleum_prices (petroleum_id)

);

COPY car_models (model_id, marka, model, max_speed, liters_per_100_km, petroleum_id) FROM stdin;

1 VAZ 2

2 VAZ 2

\.

-- водители

DROP TABLE IF EXISTS drivers CASCADE;

CREATE TABLE drivers (

driver_id serial NOT NULL PRIMARY KEY,

first_name varchar(100) NOT NULL,

second_name varchar(100) NOT NULL,

passport varchar(255) NOT NULL,

city varchar(50) NOT NULL,

has_a_problems boolean NOT NULL,

car_model_id integer NOT NULL REFERENCES car_models (model_id)

);

COPY drivers (driver_id, first_name, second_name, passport, city, has_a_problems, car_model_id) FROM stdin;

1 Ivan Ivanov Samara true 1

2 Iavn Petrov Moscow false 2

\.

-- перекрестки

DROP TABLE IF EXISTS nodes CASCADE;

CREATE TABLE nodes (

node_id serial NOT NULL PRIMARY KEY,

traffic_light_enabled boolean NOT NULL

);

COPY nodes (node_id, traffic_light_enabled) FROM stdin;

1 true

2 false

3 true

4 false

\.

-- типы покрытий дорог

DROP TABLE IF EXISTS coverage_types CASCADE;

CREATE TABLE coverage_types (

coverage_id serial NOT NULL PRIMARY KEY,

title varchar(255) NOT NULL UNIQUE,

koeff numeric(9,2) NOT NULL -- коэффициент торможения

);

COPY coverage_types(coverage_id, title, koeff) FROM stdin;

1 grunt 5

2 asfalt 2

3 highway 1

\.

-- ребра, дуги

DROP TABLE IF EXISTS edges CASCADE;

CREATE TABLE edges (

edge_id serial NOT NULL PRIMARY KEY,

source integer NOT NULL REFERENCES nodes(node_id),

target integer NOT NULL REFERENCES nodes(node_id),

--costs_id integer NOT NULL REFERENCES costs(cost_id),

cost numeric(9,2) NOT NULL,

length numeric(9,2) NOT NULL,

time numeric(9,2) NOT NULL

);

COPY edges(edge_id, source, target, cost, length, time) FROM stdin;

43.3

64.1

\.

-- детали дуг

DROP TABLE IF EXISTS edge_details CASCADE;

CREATE TABLE edge_details (

edge_id integer NOT NULL REFERENCES edges(edge_id),

max_speed integer NOT NULL,

coverage_type_id integer NOT NULL REFERENCES coverage_types(coverage_id),

pileup boolean NOT NULL -- пробка

);

COPY edge_details(edge_id, max_speed, coverage_type_id, pileup) FROM stdin;

1 60 1 true

2 40 1 false

3 25 2 false

4 40 3 true

\.

Движок отрисовки графов в редакторе

Файл QGScene. h

#ifndef QGSCENE_H

#define QGSCENE_H

#include <QtGui>

#include "node. h"

#include "edge. h"

#include <QtSvg/QGraphicsSvgItem>

class QGScene : public QGraphicsScene

{

Q_OBJECT

public:

int idCounter;

enum QViewMode { mDrag, mNode, mEdge, mSolve };

Node *sourceNode;

QGScene(QObject * parent = 0, GraphWidget * Widget = 0);

void setViewMode(QViewMode mode);

protected:

void mousePressEvent ( QGraphicsSceneMouseEvent * mouseEvent );

private:

QGraphicsTextItem * myText;

QMenu *myContextMenu;

QMenu *myEdgeMenu;

QAction *delAct;

QViewMode vMode;

GraphWidget *myWidget;

public slots:

void deletenode();

void traffnode(bool checked );

void deleteedge();

void edgeoptions();

};

#endif // QGSCENE_H

Файл QGScene. cpp

#include "QGScene. h"

#include "mainwindow. h"

#include "node. h"

#include "edge. h"

#include <QtGui>

QGScene::QGScene(QObject * parent, GraphWidget *Widget) : QGraphicsScene(parent) {

idCounter = 0;

myWidget = Widget;

vMode = mDrag;

sourceNode = 0;

// QFont serifFont("Times", 20, QFont::Bold);

// myText = addText("", serifFont);

// myText->setPos(-200, this->sceneRect().toRect().top());

myContextMenu = new QMenu(tr("NodeMenu");

delAct = new QAction(QIcon(":/images/delete. png",tr("Delete", this);

delAct->setStatusTip(tr("Delete node");

connect(delAct, SIGNAL(triggered()), SLOT(deletenode()));

myContextMenu->addAction(delAct);

myContextMenu->addSeparator();

delAct = new QAction(QIcon(":/images/traflt. png", tr("TraficLight", this);

delAct->setStatusTip(tr("traflt");

delAct->setCheckable ( true ) ;

connect(delAct, SIGNAL(toggled(bool)), this, SLOT(traffnode(bool)));

myContextMenu->addAction(delAct);

myEdgeMenu = new QMenu(tr("EdgeMenu");

delAct = new QAction(QIcon(":/images/delete. png",tr("Delete", this);

delAct->setStatusTip(tr("Delete edge");

connect(delAct, SIGNAL(triggered()), SLOT(deleteedge()));

myEdgeMenu->addAction(delAct);

myEdgeMenu->addSeparator();

delAct = new QAction(QIcon(":/images/open. png",tr("Options", this);

delAct->setStatusTip(tr("options");

connect(delAct, SIGNAL(triggered()), SLOT(edgeoptions()));

myEdgeMenu->addAction(delAct);

}

void QGScene::mousePressEvent ( QGraphicsSceneMouseEvent * mouseEvent )

{

switch (vMode){

case mDrag:

break;

case mNode:

if (mouseEvent->button() == Qt::LeftButton) {

if (QGraphicsItem *item = itemAt(mouseEvent->scenePos())) {

if (!(qgraphicsitem_cast<Node *>(item))) {

Node *tmpnode = new Node(myContextMenu, idCounter++);

this->addItem(tmpnode);

tmpnode->setPos(x, y);

}

}

}

break;

case mEdge:

if (mouseEvent->button() == Qt::LeftButton) {

if (QGraphicsItem *item = itemAt(mouseEvent->scenePos())) {

if (Node * tmpnode = qgraphicsitem_cast<Node *>(item)) {

if (sourceNode) {

if (sourceNode!= tmpnode) {

this->addItem(new Edge(sourceNode, tmpnode, myEdgeMenu));

sourceNode = tmpnode;

}

} else {

sourceNode = tmpnode;

}

} else

sourceNode = 0;

} else

sourceNode = 0;

}

break;

case mSolve:

break;

};

QGraphicsScene::mousePressEvent(mouseEvent);

}

void QGScene::deletenode() {

foreach (QGraphicsItem *item, selectedItems()) {

if (Node *node = qgraphicsitem_cast<Node *>(item)) {

foreach (Edge *edgeitem, node->edges()) {

// //Node *node = qgraphicsitem_cast<Node *>(item);

removeItem ( edgeitem );

//

}

this->removeItem(item);

}

}

}

void QGScene::deleteedge() {

foreach (QGraphicsItem *item, selectedItems()) {

if (Edge *edge = qgraphicsitem_cast<Edge *>(item)) {

this->removeItem(item);

}

}

}

void QGScene::traffnode(bool checked ) {

foreach (QGraphicsItem *item, selectedItems()) {

if (Node *node = qgraphicsitem_cast<Node *>(item)) {

node->isTrLt = checked;

node->update();

//node->setSelected(false);

}

}

}

void QGScene::edgeoptions() {

}

void QGScene::setViewMode(QViewMode mode) {

switch (mode){

case mDrag:

this->myWidget->setDragMode(QGraphicsView::ScrollHandDrag);

foreach (QGraphicsItem *item, this->items()) {

if (qgraphicsitem_cast<Node *>(item)) {

item->setFlag(QGraphicsItem::ItemIsMovable, true);

}

};

vMode = mode;

this->sourceNode = 0;

this->clearSelection();

break;

case mNode:

this->myWidget->setDragMode(QGraphicsView::NoDrag);

foreach (QGraphicsItem *item, this->items()) {

if (Node *node = qgraphicsitem_cast<Node *>(item)) {

node->setFlag(QGraphicsItem::ItemIsMovable, true);

}

};

vMode = mode;

this->sourceNode = 0;

this->clearSelection();

break;

case mEdge:

this->myWidget->setDragMode(QGraphicsView::NoDrag);

foreach (QGraphicsItem *item, this->items()) {

if (Node *node = qgraphicsitem_cast<Node *>(item)) {

node->setFlag(QGraphicsItem::ItemIsMovable, false);

}

};

vMode = mode;

this->sourceNode = 0;

this->clearSelection();

break;

case mSolve:

break;

};

}

Файл node. h

#ifndef NODE_H

#define NODE_H

#include <QGraphicsItem>

#include <QList>

#include <QtGui>

class Edge;

class GraphWidget;

class QGraphicsSceneMouseEvent;

class QMenu;

class Node : public QGraphicsItem

{

public:

int globalId;

bool isTrLt;

Node(QMenu * CtMenu, int id);

void addEdge(Edge *edge);

QList<Edge *> edges() const;

enum { Type = UserType + 1 };

int type() const { return Type; }

void calculateForces();

bool advance();

QRectF boundingRect() const;

QPainterPath shape() const;

void paint(QPainter *painter, const QStyleOptionGraphicsItem *option, QWidget *widget);

protected:

QVariant itemChange(GraphicsItemChange change, const QVariant &value);

void mousePressEvent(QGraphicsSceneMouseEvent *event);

void mouseReleaseEvent(QGraphicsSceneMouseEvent *event);

void contextMenuEvent(QGraphicsSceneContextMenuEvent *event);

private:

QList<Edge *> edgeList;

QPointF newPos;

//GraphWidget *graph;

QMenu *myContextMenu;

QPixmap *pm;

};

#endif

Файл node. cpp

#include <QGraphicsScene>

#include <QGraphicsSceneMouseEvent>

#include <QPainter>

#include <QStyleOption>

#include "edge. h"

#include "node. h"

#include "graphwidget. h"

Node::Node(QMenu * CtMenu, int id)

//: graph(graphWidget)

{

globalId = id;

this->setToolTip(QString::number(globalId));

setFlag(QGraphicsItem::ItemIsMovable, true);

setFlag(QGraphicsItem::ItemIsSelectable, true);

setZValue(1);

myContextMenu = CtMenu;

pm = new QPixmap(":/images/traflt. png";

isTrLt = false;

}

void Node::addEdge(Edge *edge)

{

edgeList << edge;

edge->adjust();

}

QList<Edge *> Node::edges() const

{

return edgeList;

}

void Node::calculateForces()

{

}

bool Node::advance()

{

if (newPos == pos())

return false;

setPos(newPos);

return true;

}

QRectF Node::boundingRect() const

{

qreal adjust = 2;

return QRectF(-10 - adjust, -22 - adjust,

33 + adjust, 33 + adjust);

}

QPainterPath Node::shape() const

{

QPainterPath path;

path. addEllipse(-10, -10, 20, 20);

return path;

}

void Node::paint(QPainter *painter, const QStyleOptionGraphicsItem *option, QWidget *)

{

//painter->setPen(Qt::NoPen);

//painter->setBrush(Qt::darkGray);

//painter->drawEllipse(-7, -7, 20, 20);

QRadialGradient gradient(-3, -3, 10);

if (option->state & QStyle::State_Sunken) {

gradient. setCenter(3, 3);

gradient. setFocalPoint(3, 3);

gradient. setColorAt(1, QColor(Qt::yellow).light(120));

gradient. setColorAt(0, QColor(Qt::darkYellow).light(120));

} else {

if (option->state & QStyle::State_Selected) {

gradient. setCenter(3, 3);

gradient. setFocalPoint(3, 3);

gradient. setColorAt(1, QColor(Qt::red).light(120));

gradient. setColorAt(0, QColor(Qt::darkRed).light(120));

} else {

gradient. setColorAt(0, Qt::yellow);

gradient. setColorAt(1, Qt::darkYellow);

}

}

painter->setBrush(gradient);

painter->setPen(QPen(Qt::black, 0));

painter->drawEllipse(-10, -10, 20, 20);

//QPixmap pm(":/images/traflt. png";

if (isTrLt)

painter->drawPixmap(-8, -25, *pm);

}

QVariant Node::itemChange(GraphicsItemChange change, const QVariant &value)

{

switch (change) {

case ItemPositionHasChanged:

foreach (Edge *edge, edgeList)

edge->adjust();

//graph->itemMoved();

break;

default:

break;

};

return QGraphicsItem::itemChange(change, value);

}

void Node::mousePressEvent(QGraphicsSceneMouseEvent *event)

{

//setSelected(true);

update();

QGraphicsItem::mousePressEvent(event);

}

void Node::mouseReleaseEvent(QGraphicsSceneMouseEvent *event)

{

update();

QGraphicsItem::mouseReleaseEvent(event);

}

void Node::contextMenuEvent(QGraphicsSceneContextMenuEvent *event)

{

//scene()->clearSelection();

setSelected(true);

foreach(QAction *act, myContextMenu->actions()) {

if (act->isCheckable()) {

act->setChecked(this->isTrLt);

myContextMenu->popup(event->screenPos());

}

}

//setSelected(false);

}