Буслаев А.П., Лебедев А.А., Яшина М.В. Моделирование потоков на графах. Теоретические и вычислительные аспекты. Часть 1. NODE-модель трафика

Подождите немного. Документ загружается.

Рис. 98. Диалоговое окно изменения функции интенсивности емкости

ный граф?

4) Как производится масштабирование изображения графа

и карты?

5) Как производится импорт информации о ребрах и узлах

из другого файла?

6) Какие три режима можно указать при импорте инфор-

мации о ребрах и узлах из другого файла? Покажите на

примерах отличия этих режимов (создайте несколько гра-

фов, сохраните их в файлы, а затем, открыв один файл,

произведите импорт из другого файла).

7) Какими параметрами описывается ребро в данном прило-

жении?

8) Какие параметры можно указать для узла?

Рис. 99. Вкладка "Внутренние источники и стоки"

9) Как указать, что узел является истоком или стоком? Что

означают понятия истока и стока применительно к узлу?

10) Как задать функцию изменения интенсивности истока?

Какие виды функций можно задать в данной программе?

Какова продолжительность цикла изменения интенсивно-

сти истока?

11) Можно ли указать интенсивности для стоков аналогично

тому, как это делается для истоков? Почему?

12) Как во время моделирования просмотреть текущие ин-

тенсивности истоков (фактически мгновенные значения

функций изменения интенсивности источников)?

13) Как производится моделирование движения транспорта

по дорожной сети? Останавливается ли моделирование

при возникновении затора?

14) Что такое емкости? Каким реальным объектам соответ-

ствуют емкости в модели дорожной сети?

15) Как создать емкость? Оказывает ли только что создан-

ная емкость какое-либо влияние на модель дорожной се-

ти? Как указать, с каким ребром будет ассоциироваться

емкость?

16) Какими параметрами характеризуется емкость? В чем от-

личия емкостей от узлов, являющихся одновременно и ис-

точниками, и стоками?

17) Где в модели дорожной сети, как правило, располагаются

узлы-источники/стоки? Где, по-Вашему, должны обычно

располагаться емкости?

18) Как во время моделирования просмотреть текущие зна-

чения параметров емкостей?

5. Комментарии к реализации приложения

FlowNetworkMoskow.exe

Здесь приводятся комментарии к исходному коду прило-

жения FlowNetworkMoskow.exe для моделирования дорожной

сети, которое описывалось в предыдущей главе. Приложение

разрабатывалось на языке C# в среде Visual Studio 2008. Це-

левая платформа: .Net Framework 2.0, Any CPU.

Исходный код распределен по файлам. Каждый файл со-

держит один класс, изредка несколько классов, реализующих

общую функциональность. Здесь приведено описание для всех

файлов, за исключением файлов, автоматически сгенериро-

ванных средой разработки (файлы дизайнера форм *.Designer.cs).

В процессе разработки приложение имело внутреннее на-

именование "TransportNet что отражается в имени основного

пространства имен (namespace) и названии генерируемого ис-

полняемого файла - также "TransportNet".

5.1. Файл Program.cs

Содержит класс Program с функцией main — точкой входа

программы.

Функция main запускается при начале работы приложения.

Она создает и выводит на экран основное окно программы.

5.2. Файл AnyClassesAndFunctions.cs

Содержит некоторые вспомогательные классы.

Класс RefDouble - Класс-обертка, инкапсулирующая значе-

ние типа Double. Применяется в тех случаях, когда необходи-

ма ссылка на double, а не значение double.

Класс AnyFunctions - содержит различные вспомогатель-

ные функции (вычисление евклидова расстояния, длины пер-

пендикуляра, опущенного на прямую и т. п.), применяющиеся

при отрисовке узлов и ребер графа.

5.3. Файл ValidatorsLibrary.cs

Содержит множество классов-валидаторов, которые при-

меняются при проверке корректности ввода значений в поля

ввода. Так, есть валидаторы, пропускающие ввод целых чисел

и блокирующие ввод дробных, и т. д.

5.4. Файл Styles.cs

Включает в себя классы, отвечающие за стиль отрисовки

элементов графа.

NodeStyle - стиль узлов (радиус, цвет...).

CapacityStyle - стиль отрисовки емкостей (аналогично цвет,

радус, шрифт подписи).

EdgeStyle - стиль отрисовки ребра. Здесь множество пара-

метров, таких, как ширина линии, которой рисуется ребро и

стрелка на конце, ширина линии, обозначающей пробку, цвет

потока на свободном пространстве в прямом направлении, в

обратном направлении и т. п.

GraphSettings - различные опции для всего графа: рассто-

яние захвата для узлов (например, при перетаскивании узла

мышью), расстояние захвата для ребер и прочее.

5.5. Файл Node.cs

Содержит класс Node, представляющий узел графа.

Объекты этого класса имеют такие свойства, как положе-

ние X, Y, имя (просто строка, идентифицирующая узел, обыч-

но это его номер), стиль отрисовки (класс NodeStyle, см. опи-

сание файла Styles.cs), таблицу распределения (список объек-

тов класса Distributor), списки входящих и исходящих ребер,

флаги, указывающие, является ли этот узел стоком или ис-

током (isSource, isDrain) и др.

Также каждый объект класса Node имеет ссылку Owner-

Graph на объект класса Graph, представляющий граф, кото-

рому принадлежит этот узел.

Некоторые значимые методы класса Node.

Группа методов, добавляющих и удаляющих входящие и

исходящие ребра:

public void AddInputEdge(RealEdge AddingEdge)

public void AddOutputEdge(RealEdge AddingEdge)

public void DeleteInputEdge(RealEdge EdgeToDelete)

public void DeleteOutputEdge(RealEdge EdgeToDelete).

Метод, отрисовывающий узел:

public void Draw(Graphics g, ﬂoat ViewScale)

Метод изменения имени узла:

public string ChangeName(string NewName)

Метод, производящий расчет количества АТС, поступаю-

щих в узел с каждого из входящих ребер на данном цикле мо-

делирования (вызываются соответствующие методы для рас-

пределителей - Distributor - для каждого из ребер:

public void CalculateDistribution

(double dt, List<RealEdge> ClogedEdges).

При этом поступающее с каждого входящего ребра количе-

ство АТС делится между выходящими ребрами и сохраняет-

ся в ассоциативном массиве AddingCForOutputEdges. В этом

массиве части приходящего количества АТС со входящих ре-

бер суммируются для каждого исходящего ребра. В итоге

работы данного метода в AddingCForOutputEdges будет для

каждого выходного ребра суммарное количество АТС, кото-

рое отправляется на это выходное ребро.

Метод, производящий фактическую переброску в выход-

ные ребраа рассчитанных методом CalculateDistribution сум-

марных количеств АТС, сохраненных в массиве

AddingCForOutputEdges:

public void Distribution(List<RealEdge> ClogedEdges).

5.6. Файл EdgeBase.cs

Этот файл содержит исходный код базового класса EdgeBa-

se. Производными от EdgeBase являются классы ребер (Real-

Edge), источников (SourceEdge) и стоков (DrainEdge). Начнем

с рассмотрения класса ребра.

5.7. Файл RealEdge.cs

Файл, содержащий класс RealEdge, который реализует реб-

ро графа.

Каждый объект этого класса имеет ссылки на объекты на-

чального и конечного узлов (beginNode, endNode), на объект

ownerGraph класса Graph - граф, которому принадлежит дан-

ное ребро, ссылку на отрисовщик (объект класса EdgePainter).

Основные данные ребра хранятся в полях

double len; //Длина ребра;

uint lanesCount; //Число полос;

double c; //Количество АТС на ребре;

double lambda; //Параметр Lambda.

Доступ к полям организован через свойства Lambda, C,

LanesCount, Len, в которых проверяется корректность уста-

навливаемых значений и в случае некорректности выбрасы-

вается исключение.

5.8. Файл Distributor.cs

Содержит класс Distributor (распределитель), отвечающий

за распределение потока с ребра по выходящим ребрам узла.

Наиболее значимые данные объекта класса Distributor: in-

putEdge — ссылка на входящее ребро, outputEdgesCoeﬀs —

таблица коэффициентов распределения входящего потока АТС

по исходящим ребрам, quantum — часть АТС со входящего

ребра, распределяемая на данном цикле моделирования, drain

— ссылка на сток, если он есть, ownerNode — ссылка на узел,

которому принадлежит данный распределитель.

В каждом узле есть список распределителей — по одному

для каждого входящего ребра. Каждый распределитель хра-

нит список коэффициентов распределения для своего входя-

щего ребра. Таким образом, каждый распределитель соответ-

ствует одной строке таблицы распределения, которую поль-

зователь может задать в окне настроек параметров узла.

Как уже отмечалось, метод CalculateDistribution класса уз-

ла обращается поочередно к каждому из распределителей ×

при "сборе"поступающей массы АТС в ассоциативный массив

AddingCForOutputEdges.

5.9. Файл SourceEdge.cs

Содержит класс SourceEdge, представляющий источник.

Как уже отмечалось, SourceEdge является наследником Ed-

geBase, фактически это ребро с зафиксированной выходной

интенсивностью, которое постоянно генерирует поток АТС

(можно представить себе как приходящую в дорожную сеть

откуда-то извне магистраль). Фактически у каждого узла есть

такой источник, но он может быть включен или отключен (со-

ответствующая переменная-флаг в классе Node), таким обра-

зом, узел является либо не является источником.

В целом же при разработке была сделана относительно

успешная попытка программно обрабатывать источники на-

равне с обычными ребрами (например, в таблице распределе-

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

же, как и сток — с выходными).

5.10. Файл DrainEdge.cs

Содержит класс DrainEdge, представляющий сток. Он так-

же является наследником EdgeBase, это также некое вирту-

альное ребро, которое постоянно поглощает АТС, никогда не

насыщаясь, не образуя затор (уходящая вовне из дорожной

сети магистраль). Стоки также есть у каждого объекта уз-

ла и в зависимости от соответствующего флага могут быть

включены или выключены, при этом узел будет или не будет

стоком.

5.11. Файл Capacity.cs

Содержит класс Capacity, реализующий емкость.

Основные данные:

private ﬂoat x; //координата x

private ﬂoat y; //координата y

private string name; //имя

private double _Bmax; //максимальная емкость

private double _b; //текущее количество АТС

Graph ownerGraph; //ссылка на граф

private CapacityStyle style; //стиль отрисовки

double drainIntensity; //интенсивность прихода АТС

double sourceIntensity; //интенсивность ухода АТС.

5.12. Файл EdgePainter.cs

Содержит класс EdgePainter — отрисовщик ребер. Класс

отвечает за отображение ребер. Поскольку отрисовка ребер

— достаточно сложный процесс, эта функциональность выне-

сена в отдельный класс, чтобы не загромождать класс ребра

RealEdge.

5.13. Файл Graph.cs

Содержит класс графа Graph. Этот класс реализует граф

транспортной сети и инкапсулирует все вышеперечисленные

объекты.

Основные данные (по большей части это списки различных

объектов, составляющих граф):

string Name; //Имя графа

BindingList<RealEdge> Edges; //Список ребер

List<EdgePainter> EdgePainters; //Отрисовщики

List<Node> Nodes; //Список узлов

BindingList<Capacity> capacities; //Емкости

NodeStyle nodesStyle; //Стиль узлов

CapacityStyle capacitiesStyle; //Стиль емкостей

EdgeStyle edgesStyle; //Стиль ребер

GraphSettings settings; //Опции графа

BindingList<SourceEdge> sources; //Источники.

Класс графа выполняет координирующие функции по от-

ношению ко всем объектам графа (узлам, ребрам и т. п.).

100

5.14. Другие файлы

На этом описание основных сущностей программы мож-

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

содержащие реализацию пользовательского интерфейса: это

ChildForm.cs, который содержит класс формы главного ок-

на программы, класс формы диалогового окна настройки па-

раметров узлов содержится в файле InputDistributionsInNo-

des.cs, и некоторые другие файлы.

6. Задачи по реализации дополнительных функций

приложения FlowNetworkMoskow.exe

6.1. Расчет длины графа

Добавьте в приложение FlowNetworkMoskow.exe возмож-

ность вывода общей длины графа (суммы длин ребер). Для

этого нужно добавить в класс Graph функцию, рассчитыва-

ющую длину графа. Функция должна производить суммиро-

вание длин ребер в км и возвращать результат.

Прототип функции: public double FullLen().

Нужно обеспечить вывод в основное окно приложения ве-

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

При модификациях графа, изменяющих его длину (при до-

бавлении/удалении ребер, изменении геометрии), выводимая

длина графа должна также соответствующим образом изме-

няться. Для этого при каждом изменении длины графа сле-

дует вызывать созданную функцию и выводить новое рассчи-

танное значение общей длины графа.

6.2. Статистика: распределение ребер в графе по длине и

количеству полос

Добавьте в приложение FlowNetworkMoskow.exe возмож-

ность вывода графика, иллюстрирующего распределение ре-

бер графа по длине. На этом графике горизонтальная ось со-

ответствует длине ребра и разделена на небольшие отрезки

(диапазоны), а вертикальная – доле ребер от общего количе-

101

Рис. 100. Пример гистограммы распределения значения какого-либо параметра ребер

ства, имеющих длину в пределах соответствующего диапазо-

на.

Реализуйте также вывод подобного графика (гистограм-

мы), отражающего распределение ребер по количеству полос.

Можно выводить графики в диалоговых окнах или в одном

диалоговом окне, вызываемом из меню "Статистика"(нужно

добавить такое меню в главное окно приложения).

На рис. 100 и рис. 101 даны примеры возможных графиков.

В метках на вертикальной оси имеет смысл выводить как

долю в процентах, так и собственно количество ребер.

6.3. Авторазделение ребер

При создании графа чаще всего получается, что в нем встре-

чаются как маленькие ребра, так и ребра с очень большой

длиной. Была бы полезна функция автоматического разделе-

ния длинных ребер на более мелкие (путем вставки узлов).

Добавьте в программу такую возможность.

Предполагаемая реализация: из меню вызывается диалого-

вое окно "Авторазбиение ребер". В нем пользователь должен

задать параметр – максимально допустимую длину ребра –

и подтвердить операцию. После подтверждения выполняется