Программное средство нахождения кратчайших путей в графе

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

Рассмотрим сам алгоритм.

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

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

3. В стек складывается текущая вершина, с которой начинается поиск.

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

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

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

I. из стека вершин текущего маршрута извлекается верхняя вершина;

II. из стека рёбер текущего маршрута извлекается верхнее ребро;

III. вес текущего маршрута уменьшается на вес извлечённого ребра;

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

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

I. вершина, в которую попадает ребро, добавляется в стек вершин и становится текущей;

II. ребро добавляется в стек, в котором хранится текущий маршрут;

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

c. После того, как все рёбра, выходящие из текущей вершины, проверены, делается шаг назад. Для этого

I. из стека вершин текущего маршрута извлекается верхняя вершина;

II. из стека рёбер текущего маршрута извлекается верхнее ребро;

III. вес текущего маршрута уменьшается на вес извлечённого ребра;

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

V. и так как мы ушли из текущей вершины, счётчик просмотренных из неё рёбер обнуляется, т.е. принимает значение минус единица.

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

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

1. отказаться от рекурсии (что и было сделано в рамках данного алгоритма);

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

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

3.4.4 Поиск в ширину (однопоточная версия)

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

Алгоритму на вход подаётся два параметра, номер стартовой вершины и номер конечной вершины.

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

Как и раньше текущий путь будет размещаться в структуре данных типа стек. Туда помещается стартовая вершина.

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

На самом деле будет использовать 4 очереди.

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

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

В третьей очереди будут храниться веса потенциальных маршрутов.

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

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

Основной цикл до опустения очереди вершин будет выглядеть следующим образом:

1. Из начала очереди маршрутов из вершин извлекается маршрут и делается текущим.

2. Из начала очереди маршрутов из рёбер извлекается маршрут и делается текущим.

3. Из начала очереди весов извлекается вес текущего маршрута.

4. Из начала очереди количества пересадок извлекается текущее количество пересадок.

5. Извлекаем с вершины стека вершин текущего маршрута вершину и делаем её текущей.

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

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

a. в стек вершин добавляется конечная вершина ребра;

b. в стек рёбер добавляется ребро;

c. пересчитывается текущий вес за счёт прибавления веса ребра, по которому осуществляется переход;

d. пересчитывается текущее количество пересадок, в соответствии с ребром по которому осуществляется переход;

e. копия стека вершин помещается в конец очереди стеков вершин;

f. копия стека рёбер помещается в конец очереди стеков рёбер;

g. вес текущего пути помещается в конец очереди весов;

h. количество пересадок текущего пути помещается в конец очереди количества пересадок;

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

3.4.5 Поиск в ширину (многопоточная версия)

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

В силу многопоточности для запуска алгоритма используются дополнительные построения.

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

2. Заводится вспомогательная структура данных, хранящая в себе полный набор параметров необходимых для алгоритма. Это делается в силу того, что функции-делегату представляющей собой тело потока может быть передан только один параметр типа object. В состав структуры входят следующие поля:

a. текущая вершина;

b. конечная вершина;

c. текущий вес;

d. текущее количество пересадок;

e. стек вершин, входящих в текущий путь;

f. стек рёбер, входящих в текущий путь.

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

Рассмотрим сам алгоритм:

1. Увеличивается количество активных потоков.

2. В локальный стек вершин помещается текущая вершина.

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

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

a. формируется копия текущего стека вершин;

b. формируется копия текущего стека рёбер;

c. формируется копия веса текущего пути;

d. формируется копия количества пересадок на текущем пути;

e. в копию стека вершин помещается конец ребра, по которому мы хотим идти;

f. в копию сетка рёбер помещается рёбро, по которому мы хотим идти;

g. копия веса текущего пути увеличивается на вес ребра, по которому мы хотим пойти;

h. копия количества пересадок на текущем пути, если ребро ведёт в другую транспортную сеть;

i. и вместо того чтобы помещать это всё в конец очереди, как это делалось в классическом поиске в ширину создаётся ещё один поток с только что сформированным набором параметров.

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

3.5 Пример работы алгоритма

Рассмотрим небольшой пример. Пусть необходимо найти путь из вершины A в вершину H. При двух разрешённых пересадках оптимальный путь (представленный на верхнем рисунке) состоит из четырёх рёбер и имеет вес равный 13. При трёх разрешённых пересадках оптимальный путь (представленный на нижнем рисунке) состоит из одиннадцати рёбер и имеет вес равный 11.

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

Рисунок 2.1 - Пример работы программы



ЗАКЛЮЧЕНИЕ

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

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

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

В качестве среды разработки был выбран пакет Visual Studio 2010. Реализация велась с использованием языка программирования высокого уровня C#. Для хранения транспортной сети использовались принципы сериализации объектов и формат XML.

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

1. Создание, модификация, загрузка, сохранение транспортной сети.

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

3. Задание условий поиска и критериев оптимальности поиска маршрута.

4. Осуществление поиска маршрутов с учётом заданных ограничений.

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

алгоритм транспортный маршрут граф



СПИСОК ЛИТЕРАТУРЫ

1. Оре, О. Теория графов. М.: Наука, 1968.

2. Харари, Ф. Теория графов. М.: Мир, 1973.

3. Уилсон, Р. Введение в теорию графов. Пер с англ. М: Мир, 1977.

4. Емеличев, В.А., Лекции по теории графов. М.: Наука, 1990.

5. Кормен, М. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ. М.: «Вильямс», 2006.

6. Сербин, В.Д. Основы логистики. Таганрог: ТРТУ, 2004.

7. Сток, Р. Стратегическое управление логистикой. М.: Инфра-М, 2005.

8. Хемди, А. Введение в исследование операций. М.: «Вильямс», 2007.

9. Вентцель, С.Е. Исследование операций: задачи, принципы, методология. М.: Наука, 1980.

10. Мудров, В.И. Задача о коммивояжере. М.: «Знание», 1969.

11. Ананий, В. Алгоритмы: введение в разработку и анализ. М.: «Вильямс», 2006.

12. Муртаф, Б. Современное линейное программирование. М.: Мир, 1984.

13. Стивен, С. Олимпиадные задачи по программированию. М.: ИД Кудиц-образ, 2005.

14. Меньшиков, Ф. Олимпиадные задачи по программированию. Спб.: Питер, 2006.

15. Дейтл, Х. C#. СПб.: БХВ-Петербург, 2006.

16. Павловская, Т.А. C#. Программирование на языке высокого уровня. СПб.: Питер, 2007.



ПРИЛОЖЕНИЕ А

Функция отрисовки транспортной сети

public void Draw(bool showInvisible, bool showDeleted)

{

//отрисовать граф

//перо для отрисовки

Pen dcPen = new Pen(Color.Black, 1);

//кисть для отрисовки

Brush dcBrush = new SolidBrush(Color.White);

//если необходимо изменить размер компонента перед отрисовкой

if (this.pb.Width != this.width || this.pb.Height != this.height)

{

this.pb.Width = this.width;

this.pb.Height = this.height;

this.pb.Image = new Bitmap(this.width, this.height);

this.dc = Graphics.FromImage(this.pb.Image);

}

//отрисовка вед?тся в высоком качестве

dc.SmoothingMode =

System.Drawing.Drawing2D.SmoothingMode.HighQuality;

dc.TextRenderingHint =

System.Drawing.Text.TextRenderingHint.SingleBitPerPixel;

//заливаем всю картинку белым цветом

this.dc.FillRectangle(dcBrush, 0, 0, this.width, this.height);

//перед тем как отрисовывать вершины, нужно отрисовать ребра

for (int i = 0; i < aEdge.Count; i++)

{

//отрисовываем только видимые и не помеченные как удаленные ребра

if ((aEdge[i].Visible == true || (aEdge[i].Visible == false && showInvisible

== true))

&& (aEdge[i].Deleted == false || (aEdge[i].Deleted == true &&

showDeleted == true)))

{

int x1 = aVertex[aEdge[i].srcVertex].X;

int y1 = aVertex[aEdge[i].srcVertex].Y;

int x2 = aVertex[aEdge[i].destVertex].X;

int y2 = aVertex[aEdge[i].destVertex].Y;

int xm = (x1 + x2) / 2;

int ym = (y1 + y2) / 2;

//цвет исходящий от первой вершины

dcPen.Width = 4;

dcPen.Color = aGraph[aVertex[aEdge[i].srcVertex].iGraph].Color;

dc.DrawLine(dcPen, x1, y1, xm, ym);

dcPen.Color = aGraph[aVertex[aEdge[i].destVertex].iGraph].Color;

dc.DrawLine(dcPen, x2, y2, xm, ym);

dcPen.Width = 2;

dcPen.Color = aEdge[i].Color;

dc.DrawLine(dcPen, x1, y1, x2, y2);

((SolidBrush)dcBrush).Color = aEdge[i].Color;

string suffix = "";

string prefix = "";

if (aEdge[i].Enabled == false) suffix += "Ч";

if (aEdge[i].Visible == false) suffix += "°";

if (aEdge[i].Deleted == true) suffix += "†";

if (aEdge[i].IsPartOfPath == true)

{

//suffix += " =";

//prefix = "= ";

((SolidBrush)dcBrush).Color = Color.FromArgb(200, 200, 200);

}

if (aEdge[i].Selected == true)

{

dcPen.Width = 2;

//рисуем кружочек за который можно таскать ребро

dc.FillEllipse(dcBrush, xm - rSize, ym - rSize, 2 * rSize, 2 * rSize);

dcPen.Color = aGraph[aVertex[aEdge[i].srcVertex].iGraph].Color;

dcPen.DashStyle = System.Drawing.Drawing2D.DashStyle.Dot;

dcPen.DashOffset = 0;

dc.DrawEllipse(dcPen, xm - rSize, ym - rSize, 2 * rSize, 2 * rSize);

dcPen.Color = aGraph[aVertex[aEdge[i].destVertex].iGraph].Color;

dcPen.DashOffset = 1;

dc.DrawEllipse(dcPen, xm - rSize, ym - rSize, 2 * rSize, 2 * rSize);

dcPen.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid;

//надпись на ребре

int x = xm;

int y = ym;

Size textSize = TextRenderer.MeasureText(prefix +

aEdge[i].Weight.ToString() + suffix, textFontBold);

x -= textSize.Width / 2;

y -= textSize.Height / 2;

Rectangle textRect = new Rectangle(x, y, textSize.Width, textSize.Height);

TextRenderer.DrawText(this.dc, prefix + aEdge[i].Weight.ToString() +

suffix, textFontBold, textRect, Color.Black);

}

else

{

dcPen.Width = 1;

//рисуем кружочек за который можно таскать ребро

dc.FillEllipse(dcBrush, xm - rSize, ym - rSize, 2 * rSize, 2 * rSize);

dcPen.Color = aGraph[aVertex[aEdge[i].srcVertex].iGraph].Color;

dcPen.DashStyle = System.Drawing.Drawing2D.DashStyle.Dot;

dcPen.DashOffset = 0;

dc.DrawEllipse(dcPen, xm - rSize, ym - rSize, 2 * rSize, 2 * rSize);

dcPen.Color = aGraph[aVertex[aEdge[i].destVertex].iGraph].Color;

dcPen.DashOffset = 1;

dc.DrawEllipse(dcPen, xm - rSize, ym - rSize, 2 * rSize, 2 * rSize);

dcPen.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid;

//надпись на ребре

int x = xm;

int y = ym;

Size textSize = TextRenderer.MeasureText(prefix +

aEdge[i].Weight.ToString() + suffix, textFontNormal);

x -= textSize.Width / 2;

y -= textSize.Height / 2;

Rectangle textRect = new Rectangle(x, y, textSize.Width, textSize.Height);

TextRenderer.DrawText(this.dc, prefix + aEdge[i].Weight.ToString() +

suffix, textFontNormal, textRect, Color.Black);

}

}

}

//теперь необходимо отрисовать вершины

for (int i = 0; i < aVertex.Count; i++)

{

//отрисовываем только видимые и не помеченные как удаленные

вершины

if ((aVertex[i].Visible == true || (aVertex[i].Visible == false &&

showInvisible == true))

&& (aVertex[i].Deleted == false || (aVertex[i].Deleted == true &&

showDeleted == true)))

{

//цвет границы

dcPen.Color = aGraph[aVertex[i].iGraph].Color;

//цвет заполнения

((SolidBrush)dcBrush).Color = aVertex[i].Color;

string suffix = "";

if (aVertex[i].Enabled == false) suffix += ".";

if (aVertex[i].Visible == false) suffix += "°";

if (aVertex[i].Deleted == true) suffix += "†";

if (aVertex[i].IsStart == true) suffix += " »";

if (aVertex[i].IsFinish == true) suffix += " «";

if (aVertex[i].IsPartOfPath == true)

{

((SolidBrush)dcBrush).Color = Color.FromArgb(200, 200, 200);

}

if (aVertex[i].Selected == true)

{

dcPen.Width = 2;

//рисуем квадратик за который можно таскать вершину

dc.FillRectangle(dcBrush, aVertex[i].X - dSize, aVertex[i].Y - dSize, 2 *

dSize, 2 * dSize);

dc.DrawRectangle(dcPen, aVertex[i].X - dSize, aVertex[i].Y - dSize, 2 *

dSize, 2 * dSize);

//надпись на вершине

int x = aVertex[i].X;

int y = aVertex[i].Y;

Size textSize = TextRenderer.MeasureText(aVertex[i].Title + suffix,

textFontBold);

x -= textSize.Width / 2;

y -= textSize.Height / 2;

Rectangle textRect = new Rectangle(x, y, textSize.Width, textSize.Height);

dc.FillRectangle(dcBrush, textRect);

dc.DrawRectangle(dcPen, textRect);

TextRenderer.DrawText(this.dc, aVertex[i].Title + suffix, textFontBold,

textRect, Color.Black);

}

else

{

dcPen.Width = 1;

//рисуем квадратик за который можно таскать вершину

dc.FillRectangle(dcBrush, aVertex[i].X - dSize, aVertex[i].Y - dSize, 2 *

dSize, 2 * dSize);

dc.DrawRectangle(dcPen, aVertex[i].X - dSize, aVertex[i].Y - dSize, 2 *

dSize, 2 * dSize);

//надпись на вершине

int x = aVertex[i].X;

int y = aVertex[i].Y;

Size textSize = TextRenderer.MeasureText(aVertex[i].Title + suffix,

textFontNormal);

x -= textSize.Width / 2;

y -= textSize.Height / 2;

Rectangle textRect = new Rectangle(x, y, textSize.Width, textSize.Height);

dc.FillRectangle(dcBrush, textRect);

dc.DrawRectangle(dcPen, textRect);

TextRenderer.DrawText(this.dc, aVertex[i].Title + suffix, textFontNormal,

textRect, Color.Black);

}

//обновляем картинку т.к. перерисовали

this.pb.Refresh();

ПРИЛОЖЕНИЕ Б

Свойство, реализующее признак видимости графа

new public bool Visible

{

get

{

return base.Visible;

}

set

{

base.Visible = value;

//наследовать свойство видимости всем принадлежащим графу

вершинам

for (int i = 0; i < this.iVertex.Count; i++)

{

tn.aVertex[this.iVertex[i]].Visible = value;

}

}

}



ПРИЛОЖЕНИЕ В

Свойство, реализующее признак видимости вершины

new public bool Visible

{

get

{

return base.Visible;

}

set

{

base.Visible = value;

//наследовать свойство видимости смежным ребрам

for (int i = 0; i < this.iEdge.Count; i++)

{

tn.aEdge[this.iEdge[i]].Visible = value;

}

}

}



ПРИЛОЖЕНИЕ Г

Свойство базового класса, реализующее свойство видимости

public bool Visible

{

get

{

return this.visible;

}

set

{

this.visible = value;

}

}



ПРИЛОЖЕНИЕ Д

Функции для сохранения/загрузки транспортной сети

private void menuItemСохранить_Click(object sender, EventArgs e)

{

if (saveFileDialogTN.ShowDialog() == DialogResult.OK)

{

//экземпляр xmlSer класса XmlSerializer нужен для сериализации

XmlSerializer xmlSer = new

XmlSerializer(typeof(TransportNetworkSerialization));

//имя файла в который будет сохраняться результат сериализации

//string fileName = System.Environment.CurrentDirectory + "\\tst.xml";

string fileName = saveFileDialogTN.FileName;

//поток fileStream для создания XML-файла

FileStream fileStream = new FileStream(fileName, FileMode.Create);

TransportNetworkSerialization tns = new TransportNetworkSerialization();

tn.PreSerialize(tns);

//сериализация

xmlSer.Serialize(fileStream, tns);

//закрываем поток

fileStream.Close();

}

} private void menuItemЗагрузить_Click(object sender, EventArgs e)

{

if (openFileDialogTN.ShowDialog() == DialogResult.OK)

{

//экземпляр xmlSer класса XmlSerializer нужен для десериализации

XmlSerializer xmlSer = new

XmlSerializer(typeof(TransportNetworkSerialization));

//имя файла из которого будет осуществляться десериализации

//string fileName = System.Environment.CurrentDirectory + "\\tst.xml";

string fileName = openFileDialogTN.FileName;

//поток fileStream для чтения XML-файла

FileStream fileStream = new FileStream(fileName, FileMode.Open);

TransportNetworkSerialization tns = new TransportNetworkSerialization();

//десериализация

tns = (TransportNetworkSerialization)xmlSer.Deserialize(fileStream);

//закрываем поток

fileStream.Close();

//теперь нужно развернуть транспортную сеть

//нужно очистить все списки

tn.aEdge.Clear();

tn.aVertex.Clear();

tn.aGraph.Clear();

//и визуальные списки тоже необходимо очистить

comboBoxEdge.Items.Clear();

comboBoxVertex.Items.Clear();

comboBoxGraph.Items.Clear();

//и поля ввода тоже необходимо очистить

textBoxGraphTitle.Text = "";

textBoxGraphDescription.Text = "";

checkBoxGraphDeleted.Checked = false;

checkBoxGraphEnabled.Checked = true;

checkBoxGraphVisible.Checked = true;

panelGraph.BackColor = Color.Black;

textBoxVertexTitle.Text = "";

textBoxVertexDescription.Text = "";

checkBoxVertexDeleted.Checked = false;

checkBoxVertexEnabled.Checked = true;

checkBoxVertexVisible.Checked = true;

panelVertex.BackColor = Color.White;

textBoxEdgeTitle.Text = "";

textBoxEdgeDescription.Text = "";

checkBoxEdgeDeleted.Checked = false;

checkBoxEdgeEnabled.Checked = true;

checkBoxEdgeVisible.Checked = true;

panelEdge.BackColor = Color.White;

numericUpDownEdge.Value = 0;

//а теперь в списки нужно добавлять значения

//сначала будем добавлять графы

for (int i = 0; i < tns.aGraph.Length; i++)

{

buttonGraphAdd_Click(sender, e);

textBoxGraphTitle.Text = tns.aGraph[i].title;

textBoxGraphDescription.Text = tns.aGraph[i].description;

checkBoxGraphDeleted.Checked = tns.aGraph[i].deleted;

checkBoxGraphEnabled.Checked = tns.aGraph[i].enabled;

checkBoxGraphVisible.Checked = tns.aGraph[i].visible;

panelGraph.BackColor = Color.FromArgb(tns.aGraph[i].colorR,

tns.aGraph[i].colorG, tns.aGraph[i].colorB);

tn.aGraph[i].Color = panelGraph.BackColor;

}

//теперь необходимо добавить вершины

for (int i = 0; i < tns.aVertex.Length; i++)

{

comboBoxGraph.SelectedIndex = tns.aVertex[i].iGraph;

buttonVertexAdd_Click(sender, e);

textBoxVertexTitle.Text = tns.aVertex[i].title;

textBoxVertexDescription.Text = tns.aVertex[i].description;

checkBoxVertexDeleted.Checked = tns.aVertex[i].deleted;

checkBoxVertexEnabled.Checked = tns.aVertex[i].enabled;

checkBoxVertexVisible.Checked = tns.aVertex[i].visible;

panelVertex.BackColor = Color.FromArgb(tns.aVertex[i].colorR,

tns.aVertex[i].colorG, tns.aVertex[i].colorB);

tn.aVertex[i].Color = panelVertex.BackColor;

tn.aVertex[i].X = tns.aVertex[i].x;

tn.aVertex[i].Y = tns.aVertex[i].y;

}

//и, наконец необходимо добавить р?бра

for (int i = 0; i < tns.aEdge.Length; i++)

{

if (tn.AddEdge(tns.aEdge[i].srcvertex, tns.aEdge[i].destvertex) == true)

{

//его имя записываем в список

comboBoxEdge.Items.Add(tn.aEdge[tn.aEdge.Count - 1].Title);

//и оно становится текущим

comboBoxEdge.SelectedIndex = tn.aEdge.Count - 1;

}

textBoxEdgeTitle.Text = tns.aEdge[i].title;

textBoxEdgeDescription.Text = tns.aEdge[i].description;

checkBoxEdgeDeleted.Checked = tns.aEdge[i].deleted;

checkBoxEdgeEnabled.Checked = tns.aEdge[i].enabled;

checkBoxEdgeVisible.Checked = tns.aEdge[i].visible;

panelEdge.BackColor = Color.FromArgb(tns.aEdge[i].colorR,

tns.aEdge[i].colorG, tns.aEdge[i].colorB);

tn.aEdge[i].Color = panelEdge.BackColor;

numericUpDownEdge.Value = tns.aEdge[i].weight;

}

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

this.numericUpDownWidth.Value = tns.width;

this.numericUpDownHeight.Value = tns.height;

}

}

public void PreSerialize(TransportNetworkSerialization tns)

{

//подготовить данные для сериализации

//сначала подготовить графы

tns.aGraph = new GraphSerialization[this.aGraph.Count];

for (int i = 0; i < tns.aGraph.Length; i++)

{

tns.aGraph[i] = new GraphSerialization();

tns.aGraph[i].colorR = this.aGraph[i].Color.R;

tns.aGraph[i].colorG = this.aGraph[i].Color.G;

tns.aGraph[i].colorB = this.aGraph[i].Color.B;

tns.aGraph[i].deleted = this.aGraph[i].Deleted;

tns.aGraph[i].description = this.aGraph[i].Description;

tns.aGraph[i].enabled = this.aGraph[i].Enabled;

tns.aGraph[i].selected = this.aGraph[i].Selected;

tns.aGraph[i].title = this.aGraph[i].Title;

tns.aGraph[i].visible = this.aGraph[i].Visible;

}

//потом подготовить вершины

tns.aVertex = new VertexSerialization[this.aVertex.Count];

for (int i = 0; i < tns.aVertex.Length; i++)

{

tns.aVertex[i] = new VertexSerialization();

tns.aVertex[i].colorR = this.aVertex[i].Color.R;

tns.aVertex[i].colorG = this.aVertex[i].Color.G;

tns.aVertex[i].colorB = this.aVertex[i].Color.B;

tns.aVertex[i].deleted = this.aVertex[i].Deleted;

tns.aVertex[i].description = this.aVertex[i].Description;

tns.aVertex[i].enabled = this.aVertex[i].Enabled;

tns.aVertex[i].selected = this.aVertex[i].Selected;

tns.aVertex[i].title = this.aVertex[i].Title;

tns.aVertex[i].visible = this.aVertex[i].Visible;

tns.aVertex[i].x = this.aVertex[i].X;

tns.aVertex[i].y = this.aVertex[i].Y;

tns.aVertex[i].iGraph = this.aVertex[i].iGraph;

}

//и, наконец подготовить р?бра

tns.aEdge = new EdgeSerialization[this.aEdge.Count];

for (int i = 0; i < tns.aEdge.Length; i++)

{

tns.aEdge[i] = new EdgeSerialization();

tns.aEdge[i].colorR = this.aEdge[i].Color.R;

tns.aEdge[i].colorG = this.aEdge[i].Color.G;

tns.aEdge[i].colorB = this.aEdge[i].Color.B;

tns.aEdge[i].deleted = this.aEdge[i].Deleted;

tns.aEdge[i].description = this.aEdge[i].Description;

tns.aEdge[i].enabled = this.aEdge[i].Enabled;

tns.aEdge[i].selected = this.aEdge[i].Selected;

tns.aEdge[i].title = this.aEdge[i].Title;

tns.aEdge[i].visible = this.aEdge[i].Visible;

tns.aEdge[i].srcvertex = this.aEdge[i].srcVertex;

tns.aEdge[i].destvertex = this.aEdge[i].destVertex;

tns.aEdge[i].weight = this.aEdge[i].Weight;

}

//и не забыть сохранить ширину и высоту транспортной сети

tns.width = this.Width;

tns.height = this.Height;

}



ПРИЛОЖЕНИЕ Е

Функции для осуществления поиска в глубину

//многопоточный поиск в ширину

public void tbfs(object p)

{

thread_count++; //увеличиваем количество запущенных потоков

ptbfs t = (ptbfs)p;

t.current_pathV.Push(t.start); //в стеке лежит путь, а путь мы начинаем с

стартовой вершины

int v; //номер текущей вершины

v = t.current_pathV.Peek(); //узнаем номер текущей вершины

if (v == t.finish)

{

//если дошли до финальной вершины

lock (locker)

{

if (t.current_weight < best_weight)

{

best_weight = t.current_weight;

best_path = new Stack<int>(t.current_pathV);

best_pathE = new Stack<int>(t.current_pathE);

}

}

//если дошли до финальной вершины

}

else

{

//если же мы не дошли еще до финальной вершины

//идти из этой вершины во все остальные по очереди

foreach (int iE in tn.aVertex[v].iEdge)

{

int vv; //один из вариантов, куда можно пойти

if (tn.aEdge[iE].srcVertex == v)

vv = tn.aEdge[iE].destVertex;

else

vv = tn.aEdge[iE].srcVertex;

if (t.current_pathV.Contains(vv) == true) //туда идти нельзя, мы там уже

были

continue; //и дальше можно эту вершину не обсчитывать

if (tn.aVertex[vv].Enabled == false) //в нее идти нельзя, она

заблокированная

continue; //и дальше можно эту вершину не обсчитывать

if (tn.aEdge[iE].Enabled == false)//по этому ребру идти нельзя, оно

заблокированное

continue; //и дальше можно эту вершину не обсчитывать

int w = tn.aEdge[iE].Weight; //вес того ребра по которому мы можем

пойти

lock (locker)

{

if (t.current_weight + w > best_weight)//есть более легкие пути

continue; //и дальше можно эту вершину не обсчитывать

}

int tr; //нужна ли пересадка для попадания в следующую

//она нужна если вершины принадлежат разным транспортным сетям

if (tn.aVertex[v].iGraph != tn.aVertex[vv].iGraph)

tr = 1;

else

tr = 0;

if (t.current_transfer + tr > numericUpDownTransfer.Value) //есть более

короткие пути

continue; //и дальше можно эту вершину не обсчитывать

ptbfs tt = new ptbfs();

tt.current_pathV = new Stack<int>(t.current_pathV);

tt.current_pathE = new Stack<int>(t.current_pathE);

//идти в эту вершину

//tt.current_pathV.Push(vv); //положить в стек вершину

tt.current_pathE.Push(iE); //положить в стек ребро

//идти в эту вершину

//пересчитать показатели

tt.current_transfer = t.current_transfer + tr; //увеличим количество

пересадок

tt.current_weight = t.current_weight + w; //увеличим стоимость пути

//пересчитать показатели

tt.start = vv;

tt.finish = t.finish;

Thread ttt = new Thread(tbfs); //создали поток

ttt.Start(tt); //пустили поток с параметом

}

//если же мы не дошли еще до финальной вершины

}

thread_count--; //не забыть уменьшить текущее количество потоков

}

//поиск в ширину

private void bfs(int s, int finish)

{

//отдельно нужно рассмотреть случай если стартовая вершина

совпадает с финальной

if (s == finish)

{ //конечно это редкий случай, но тем не менее

best_path.Push(s);

return;

}

current_path.Push(s); //в стеке лежит путь, а путь мы начинаем с

стартовой вершины

//очередь стеков вершин, а в каждом стеке лежит путь

Queue<Stack<int>> qV = new Queue<Stack<int>>();

qV.Enqueue(new Stack<int>(current_path)); //положили в очередь

текущий путь

//очередь стеков р?бер, а в каждом стеке лежит путь

Queue<Stack<int>> qE = new Queue<Stack<int>>();

qE.Enqueue(new Stack<int>(current_pathE)); //положили в очередь

текущий путь

Queue<int> qW = new Queue<int>(); //очередь весов для каждого пути

qW.Enqueue(0); //положили в очередь текущий нулевой вес

Queue<int> qT = new Queue<int>(); //очередь количества пересадок для

каждого пути

qT.Enqueue(0); //положили в очередь текущее нулевое количество

пересадок

while (qV.Count != 0) //пока мы не просмотрим все возможные пути

{

current_path = new Stack<int>(qV.Dequeue()); //достаем из стека

текущий путь вершин

current_pathE = new Stack<int>(qE.Dequeue()); // достаем из стека

текущий путь ребер

current_weight = qW.Dequeue(); //узнаем его вес

current_transfer = qT.Dequeue(); // узнаем сколько пересадок было на

этом пути

int v; //номер текущей вершины

v = current_path.Peek(); // узнаем номер текущей вершины

if (v == finish)

{

//если дошли до финальной вершины

if (current_weight < best_weight)

{

best_weight = current_weight;

best_path = new Stack<int>(current_path);

best_pathE = new Stack<int>(current_pathE);

}

//если дошли до финальной вершины

}

else

{

//если же мы не дошли еще до финальной вершины

//идти из этой вершины во все остальные по очереди

foreach (int iE in tn.aVertex[v].iEdge)

{

int vv; //один из вариантов, куда можно пойти

if (tn.aEdge[iE].srcVertex == v)

vv = tn.aEdge[iE].destVertex;

else

vv = tn.aEdge[iE].srcVertex;

if (current_path.Contains(vv) == true) //туда идти нельзя, мы там уже

были

continue; //и дальше можно эту вершину не обсчитывать

if (tn.aVertex[vv].Enabled == false) //в нее идти нельзя, она

заблокированная

continue; //и дальше можно эту вершину не обсчитывать

//по этому ребру идти нельзя, оно заблокированное

if (tn.aEdge[iE].Enabled == false)

continue; //и дальше можно эту вершину не обсчитывать

int w = tn.aEdge[iE].Weight; //вес того ребра по которому мы можем

пойти

if (current_weight + w > best_weight) //есть более легкие пути

continue; //и дальше можно эту вершину не обсчитывать

int t; //нужна ли пересадка для попадания в следующую

//она нужна если вершины принадлежат разным транспортным сетям

if (tn.aVertex[v].iGraph != tn.aVertex[vv].iGraph)

t = 1;

else

t = 0;

//есть более короткие пути

if (current_transfer + t > numericUpDownTransfer.Value)

continue; //и дальше можно эту вершину не обсчитывать

//идти в эту вершину

current_path.Push(vv); //положить в стек вершину

current_pathE.Push(iE); //положить в стек ребро

//идти в эту вершину

//пересчитать показатели

current_transfer += t; //увеличим количество пересадок

current_weight += w; //увеличим стоимость пути

//пересчитать показатели

//генерируем для очереди очередное направление движения

qV.Enqueue(new Stack<int>(current_path));

//генерируем для очереди очередное направление движения

qE.Enqueue(new Stack<int>(current_pathE));

//генерируем для очереди очередное направление движения

qW.Enqueue(current_weight);

//генерируем для очереди очередное направление движения

qT.Enqueue(current_transfer);

//вернуться

current_path.Pop(); //достать из стека вершину

current_pathE.Pop(); //достать из стека ребро

//вернуться

//вернуться и пересчитать показатели

current_transfer -= t; //уменьшим количество пересадок

current_weight -= w; //уменьшим стоимость пути

//вернуться и персчитать показатели

}

//если же мы не дошли еще до финальной вершины

}

}

}

//нерекурсивный поиск в глубину

private void dfs(int s, int finish)

{

//отдельно нужно рассмотреть случай если стартовая вершина

совпадает с финальной

if (s == finish)

{ //конечно это редкий случай, но тем не менее

best_path.Push(s);

return;

}

int v; //номер текущей вершины

//в этом всмпомогательном массиве мы будем помнить индекс ребра,

по которому ходили из этой

вершины в последний раз

int[] d = new int[tn.aVertex.Count];

//ни из одной вершины никуда ещ? не ходили

for (int i = 0; i < tn.aVertex.Count; i++) d[i] = -1;

current_path.Push(s); //в стеке лежит путь, а путь мы начинаем со

стартовой вершины

while (current_path.Count != 0) //пока мы не просмотрим все возможные

пути

{

v = current_path.Peek(); //узна?м номер текущей вершины

if (v == finish)

{

//если дошли до финальной вершины

if (current_weight < best_weight)

{

best_weight = current_weight;

best_path = new Stack<int>(current_path);

best_pathE = new Stack<int>(current_pathE);

}

//если дошли

int e; //по какому ребру дошли до финальной вершины

//узна?м его по вершине стека, т.к. в стеке что-то точно есть

e = current_pathE.Peek();

int v1 = tn.aEdge[e].srcVertex; //начало ребра, по которому пришли

int v2 = tn.aEdge[e].destVertex; //конец ребра, по которому пришли

int t; //нужна ли была пересадка для попадания в эту вершину

//она нужна если вершины принадлежат разным транспортным сетям

if (tn.aVertex[v1].iGraph != tn.aVertex[v2].iGraph)

t = 1;

else

t = 0;

int w = tn.aEdge[e].Weight; //вес ребра, по которому мы пришли в

финальную вершины

//пересчитать показатели

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

назад

current_transfer -= t;

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

current_weight -= w;

//пересчитать показатели

//выйти из этой вершины

current_path.Pop(); //делаем шаг назад

current_pathE.Pop(); //делаем шаг назад

//выйти из этой вершины

//и так как мы из этой вершины ушли, то счетчик ребер для нее

обнуляется

d[v] = -1;

//если дошли до финальной вершины

}

else

{

//если же мы не дошли еще до финальной вершины

d[v]++; //ищем дальше по списку куда можно пойти

while (d[v] < tn.aVertex[v].iEdge.Count)

{

int vv; //в эту вершину есть ребро из текущей

int e = tn.aVertex[v].iEdge[d[v]]; //вот как раз это ребро и идет из

текущей

if (tn.aEdge[e].srcVertex == v)

vv = tn.aEdge[e].destVertex;

else

vv = tn.aEdge[e].srcVertex;

if (current_path.Contains(vv) == true)//туда идти нельзя, мы там уже

были

{

d[v]++; //ищем дальше по списку куда можно пойти

continue; //и дальше можно эту вершину не обсчитывать

}

if (tn.aVertex[vv].Enabled == false) //в нее идти нельзя, она

заблокированная

{

d[v]++; //ищем дальше по списку куда можно пойти

continue; //и дальше можно эту вершину не обсчитывать

}

//по этому ребру идти нельзя, оно заблокированное

if (tn.aEdge[e].Enabled == false)

{

d[v]++; //ищем дальше по списку куда можно пойти

continue; //и дальше можно эту вершину не обсчитывать

}

int w = tn.aEdge[e].Weight; //вес того ребра по которому мы можем

пойти

if (current_weight + w > best_weight) //есть более легкие пути

{

d[v]++; //ищем дальше по списку куда можно пойти

continue; //и дальше можно эту вершину не обсчитывать

}

int t; //нужна ли пересадка для попадания в следующую

//она нужна если вершины принадлежат разным транспортным сетям

if (tn.aVertex[v].iGraph != tn.aVertex[vv].iGraph)

t = 1;

else

t = 0;

//есть более короткие пути

if (current_transfer + t > numericUpDownTransfer.Value)

{

d[v]++; //ищем дальше по списку куда можно пойти

continue; //и дальше можно эту вершину не обсчитывать

}

//идти в эту вершину

current_path.Push(vv); //положить в стек вершину

current_pathE.Push(e); //положить в стек ребро

//идти в эту вершину

//пересчитать показатели

current_transfer += t; //увеличим количество пересадок

current_weight += w; //увеличим стоимость пути

//пересчитать показатели

//и так как мы пошли в вершину, то у нас теперь другая текущая и цикл

нужно кончать

break;

}

if (v == current_path.Peek()) //если из вершины идти дальше некуда

{

if (v == s) current_path.Pop(); //делаем последний шаг назад

if (v == s) break; //именно последний шаг назад

int e; //по какому ребру дошли до этой вершины

//узна?м его по вершине стека, т.к. в стеке что-то точно есть

e = current_pathE.Peek();

int v1 = tn.aEdge[e].srcVertex; //начало ребра по которому пришли

int v2 = tn.aEdge[e].destVertex; //конец ребра по которому пришли

int t; //нужна ли была пересадка для попадания в эту вершину

//она нужна если вершины принадлежат разным транспортным сетям

if (tn.aVertex[v1].iGraph != tn.aVertex[v2].iGraph)

t = 1;

else

t = 0;

int w = tn.aEdge[e].Weight; //вес ребра по которому мы пришли в эту

вершины

//пересчитать показатели

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

назад

current_transfer -= t;

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

current_weight -= w;

//пересчитать показатели

//выйти из этой вершины

current_path.Pop(); //делаем шаг назад

current_pathE.Pop(); //делаем шаг назад

//выйти из этой вершины

//и так как мы из этой вершины ушли, то счетчик ребер для нее

обнуляется

d[v] = -1;

}

//если же мы не дошли ещ? до финальной вершины

}

}

}

//рекурсивный поиск в глубину

private void rdfs(int s, int v, int e, int finish)

{

//можно ли идти в эту вершину

if (current_path.Contains(v) == true) return; //мы в ней уже были

if (tn.aVertex[v].Enabled == false) return; //в нее идти нельзя

if (e != -1)

if (tn.aEdge[e].Enabled == false) return; //по этому ребру идти нельзя

//можно ли идти в эту вершину

//нужно ли идти в эту вершину

int w; //вес того ребра, по которому идем

if (e != -1)

w = tn.aEdge[e].Weight;

else

w = 0;

if (current_weight + w > best_weight) return; //есть более легкие пути

int t; //нужна ли пересадка

if (e != -1)

{

if (tn.aVertex[s].iGraph != tn.aVertex[v].iGraph)

t = 1;

else

t = 0;

}

else

t = 0;

if (current_transfer + t > numericUpDownTransfer.Value) //есть более

короткие пути

return;

//нужно ли идти в эту вершину

//идти в эту вершину

current_path.Push(v);

if (e != -1) current_pathE.Push(e);

//идти в эту вершину

//пересчитать показатели

current_transfer += t;

current_weight += w;

//пересчитать показатели

//если дошли

if (v == finish)

{

if (current_weight < best_weight)

{

best_weight = current_weight;

best_path = new Stack<int>(current_path);

best_pathE = new Stack<int>(current_pathE);

}

}

//если дошли

//идти из этой вершины во все остальные по очереди

foreach (int iE in tn.aVertex[v].iEdge)

{

int vv; //один из вариантов, куда можно пойти

if (tn.aEdge[iE].srcVertex == v)

vv = tn.aEdge[iE].destVertex;

else

vv = tn.aEdge[iE].srcVertex;

rdfs(v, vv, iE, finish);

}

//идти из этой вершины во все остальные по очереди

//пересчитать показатели

current_transfer -= t;

current_weight -= w;

//пересчитать показатели

//выйти из этой вершины

current_path.Pop();

if (e != -1) current_pathE.Pop();

//выйти из этой вершины

}



ПРИЛОЖЕНИЕ Ж

Функция поиска оптимального пути

private void buttonSearch_Click(object sender, EventArgs e)

{

int start=-1; //стартовая вершина

int finish=-1; //конечная вершина

//ищем стартовую и конечную вершину

for (int i = 0; i < tn.aVertex.Count; i++)

{

if (tn.aVertex[i].IsStart == true) start = i;

if (tn.aVertex[i].IsFinish == true) finish = i;

}

//если хотя бы одну не нашли

if (start == -1 || finish == -1)

{

//ошибка

MessageBox.Show("Не указана начальная или конечная вершина!",

"Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error);

//и выходим

return;

}

if (tn.aVertex[start].Enabled == false || tn.aVertex[finish].Enabled == false)

{

//ошибка

MessageBox.Show("Начальная или конечная вершина заблокированы!",

"Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error);

//и выходим

return;

}

//нужно снять отметку с старого пути

for (int i = 0; i < tn.aEdge.Count; i++)

{

tn.aEdge[i].IsPartOfPath = false;

}

//нужно снять отметку с старого пути

for (int i = 0; i < tn.aVertex.Count; i++)

{

tn.aVertex[i].IsPartOfPath = false;

}

best_path.Clear();

best_pathE.Clear();

best_weight = int.MaxValue;

current_path.Clear();

current_pathE.Clear();

current_weight = 0;

current_transfer = 0;

rdfs(-1, start, -1, finish);

//если не нашли путь

if (best_weight == int.MaxValue)

{

//ошибка

MessageBox.Show("Путь до конечной вершины не может быть

найден!", "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Error);

//и выходим

return;

}

//теперь нужно пометить путь

while (best_pathE.Count != 0)

{

int i = best_pathE.Pop();

tn.aEdge[i].IsPartOfPath = true;

tn.aVertex[tn.aEdge[i].srcVertex].IsPartOfPath = true;

tn.aVertex[tn.aEdge[i].destVertex].IsPartOfPath = true;

}

//отрисовать

tn.Draw(checkBoxShowInvisible.Checked,

checkBoxShowDeleted.Checked);}

Размещено на Allbest.ru