}
//сначала устанавливаем ширину и высоту транспортной сети this.numericUpDownWidth.Value = tns.width; this.numericUpDownHeight.Value = tns.height;
} }void PreSerialize(TransportNetworkSerialization tns) {
//подготовить данные для сериализации
//сначала подготовить графы
tns.aGraph = new GraphSerialization[this.aGraph.Count]; for (int i = 0; i < tns.aGraph.Length; i++)
{.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;
}
//потом подготовить вершины.aVertex = new VertexSerialization[this.aVertex.Count]; for (int i = 0; i < tns.aVertex.Length; i++)
{.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;.aVertex[i].y = this.aVertex[i].Y; tns.aVertex[i].iGraph = this.aVertex[i].iGraph;
}
//и, наконец подготовить рѐбра.aEdge = new EdgeSerialization[this.aEdge.Count]; for (int i = 0; i < tns.aEdge.Length; i++)
{.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;.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;.height = this.Height; }
Функции для осуществления поиска в глубину
//многопоточный поиск в ширину public void tbfs(object p)
{_count++;t = (ptbfs)p;.current_pathV.Push(t.start);v;= t.current_pathV.Peek();
//увеличиваем количество запущенных потоков
//в стеке лежит путь, а путь мы начинаем с стартовой вершины
//номер текущей вершины //узнаѐм номер текущей вершины(v == t.finish) {
//если дошли до финальной вершины lock (locker)
{(t.current_weight < best_weight) {_weight = t.current_weight;_path = new Stack<int>(t.current_pathV); best_pathE = new Stack<int>(t.current_pathE);
} }
//если дошли до финальной вершины }{
//если же мы не дошли ещѐ до финальной вершины
//идти из этой вершины во все остальные по очереди foreach (int iE in tn.aVertex[v].iEdge)
{
int vv; //один из вариантов, куда можно пойти if (tn.aEdge[iE].srcVertex == v)
vv = tn.aEdge[iE].destVertex; else= 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; //и дальше можно эту вершину не обсчитыватьw = tn.aEdge[iE].Weight; //вес того ребра по которому мы можем пойти lock (locker)
{(t.current_weight + w > best_weight)//есть более лѐгкие пути
continue; //и дальше можно эту вершину не обсчитывать }
int tr; //нужна ли пересадка для попадания в следующую //она нужна если вершины принадлежат разным транспортным сетям
if (tn.aVertex[v].iGraph != tn.aVertex[vv].iGraph) tr = 1;= 0;(t.current_transfer + tr > numericUpDownTransfer.Value) //есть более короткие пути
continue; //и дальше можно эту вершину не обсчитывать
ptbfs tt = new ptbfs();.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); //идти в эту вершину
//пересчитать показатели.current_transfer = t.current_transfer + tr; tt.current_weight = t.current_weight + w; //пересчитать показатели.start = vv; tt.finish = t.finish;
//положить в стек вершину //положить в стек ребро
//увеличим количество пересадок //увеличим стоимость пути
Thread ttt = new Thread(tbfs); //создали поток ttt.Start(tt); //пустили поток с параметом
}
//если же мы не дошли ещѐ до финальной вершины }
thread_count--; //не забыть уменьшить текущее количество потоков }
//поиск в ширину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);<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;= current_path.Peek();(v == finish) {
//если дошли до финальной вершины if (current_weight < best_weight) {_weight = current_weight;_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= tn.aEdge[iE].srcVertex;
if (current_path.Contains(vv) == true) //туда идти нельзя, мы там уже были continue; //и дальше можно эту вершину не обсчитывать(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= 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;_path.Push(s);(current_path.Count != 0) {= current_path.Peek();
//в стеке лежит путь, а путь мы начинаем с стартовой вершины //пока мы не просмотрим все возможные пути
//узнаѐм номер текущей вершины
if (v == finish) {
//если дошли до финальной вершины if (current_weight < best_weight) {_weight = current_weight;_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= 0;
int w = tn.aEdge[e].Weight; //вес ребра по которому мы пришли в финальную вершины
//пересчитать показатели
//уменьшить количество пересадок, т.к. мы собираемся делать шаг назад current_transfer -= t;
//уменьшить вес текущего пути, т.к. мы собираемся делать шаг назад current_weight -= w;
//пересчитать показатели
//выйти из этой вершины current_path.Pop(); current_pathE.Pop(); //выйти из этой вершины
//делаем шаг назад //делаем шаг назад
//и так как мы из этой вершины ушли, то счѐтчик рѐбер для неѐ обнуляется d[v] = -1;
//если дошли до финальной вершины }{
//если же мы не дошли ещѐ до финальной вершины
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= tn.aEdge[e].srcVertex;
if (current_path.Contains(vv) == true)//туда идти нельзя, мы там уже были {
d[v]++; //ищем дальше по списку куда можно пойти continue; //и дальше можно эту вершину не обсчитывать
}(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= 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; }(v == current_path.Peek()) {(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= 0;
int w = tn.aEdge[e].Weight; //вес ребра по которому мы пришли в эту вершины //пересчитать показатели
//уменьшить количество пересадок, т.к. мы собираемся делать шаг назад current_transfer -= t;
//уменьшить вес текущего пути, т.к. мы собираемся делать шаг назад current_weight -= w;
//пересчитать показатели
//выйти из этой вершины
current_path.Pop(); //делаем шаг назад current_pathE.Pop(); //делаем шаг назад //выйти из этой вершины
//и так как мы из этой вершины ушли, то счѐтчик рѐбер для неѐ обнуляется d[v] = -1;
}
//если же мы не дошли ещѐ до финальной вершины }
} }
//рекурсивный поиск в глубину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)= tn.aEdge[e].Weight; else= 0;(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; //пересчитать показатели
//если дошли(v == finish) {(current_weight < best_weight) {_weight = current_weight;_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= tn.aEdge[iE].srcVertex;(v, vv, iE, finish); }
//идти из этой вершины во все остальные по очереди
//пересчитать показатели current_transfer -= t; current_weight -= w; //пересчитать показатели
}
Функция поиска оптимального пути
private void buttonSearch_Click(object sender, EventArgs e) {
int start=-1; //стартовая вершина int finish=-1; //конечная вершина
//ищем стартовую и конечную вершину
for (int i = 0; i < tn.aVertex.Count; i++) {(tn.aVertex[i].IsStart == true) start = i; if (tn.aVertex[i].IsFinish == true) finish = i;