traveling salesman problem.cs

Sample program for demonstrating Hopfield Neural Network to solve popular TSP

						case 56: city.name = "Louisville"; break;
						case 57: city.name = "Richmond"; break;
						case 58: city.name = "Charlotte"; break;
						case 59: city.name = "Savannah"; break;
						case 60: city.name = "Stalingrad"; break;
						case 61: city.name = "Leningrad"; break;
						case 62: city.name = "Moscow"; break;
						case 63: city.name = "Baghdad"; break;
						case 64: city.name = "Grand Rapids"; break;
						case 65: city.name = "Ottawa"; break;
						case 66: city.name = "Guatemala City"; break;
						case 67: city.name = "Mexico City"; break;
						case 68: city.name = "Havana"; break;
						case 69: city.name = "San Juan"; break;
						case 70: city.name = "Rio de Janeiro"; break;
						case 71: city.name = "Madrid"; break;
						case 72: city.name = "Barcelona"; break;
						case 73: city.name = "Marseilles"; break;
						case 74: city.name = "Amsterdam"; break;
						case 75: city.name = "Dublin"; break;
						case 76: city.name = "Glasgow"; break;
						case 77: city.name = "Frankfurt"; break;
						case 78: city.name = "Hamburg"; break;
						case 79: city.name = "Munich"; break;
						case 80: city.name = "Milan"; break;
						case 81: city.name = "Rome"; break;
						case 82: city.name = "Naples"; break;
						case 83: city.name = "Genoa"; break;
						case 84: city.name = "Belgrade"; break;
						case 85: city.name = "Zagreb"; break;
						case 86: city.name = "Sofia"; break;
						case 87: city.name = "Athens"; break;
						case 88: city.name = "Istanbul"; break;
						case 89: city.name = "Budapest"; break;
						case 90: city.name = "Warsaw"; break;
						case 91: city.name = "Kiev"; break;
						case 92: city.name = "Belarus"; break;
						case 93: city.name = "Stockholm"; break;
						case 94: city.name = "Oslo"; break;
						case 95: city.name = "Minsk"; break;
						case 96: city.name = "Kolkata"; break;
						case 97: city.name = "Beijing"; break;
						case 98: city.name = "Hong Kong"; break;
						case 99: city.name = "Tokyo"; break;
						case 100: city.name = "Mumbai"; break;
						case 101: city.name = "Bhopal"; break;
						case 102: city.name = "Delhi"; break;
						case 103: city.name = "Kabul"; break;
						case 104: city.name = "Mosul"; break;
						case 105: city.name = "Jerusalem"; break;
						case 106: city.name = "Damascus"; break;
						case 107: city.name = "Riyadh"; break;
						case 108: city.name = "Mecca"; break;
						case 109: city.name = "Dubai"; break;
						case 110: city.name = "Alexandria"; break;
						case 111: city.name = "Cairo"; break;
						case 112: city.name = "Tunis"; break;
						case 113: city.name = "Tripoli"; break;
						case 114: city.name = "Algiers"; break;
						case 115: city.name = "Beirut"; break;
						case 116: city.name = "Bangkok"; break;
						case 117: city.name = "Ho Chi Minh City"; break;
						case 118: city.name = "Hanoi"; break;
						case 119: city.name = "Chengdu"; break;
						case 120: city.name = "Guangzhou"; break;
						case 121: city.name = "Seoul"; break;
						case 122: city.name = "Shanghai"; break;
						case 123: city.name = "Phnom Penh"; break;
						case 124: city.name = "Mandalay"; break;
						case 125: city.name = "Kuala Lumpur"; break;
						case 126: city.name = "Singapore"; break;
						case 127: city.name = "Jakarta"; break;
						case 128: city.name = "Perth"; break;
						case 129: city.name = "Melbourne"; break;
						case 130: city.name = "Sydney"; break;
						case 131: city.name = "Brisbane"; break;
						case 132: city.name = "Hokkaido"; break;
						case 133: city.name = "Kyoto"; break;
						case 134: city.name = "Kagashima"; break;
						case 135: city.name = "Fukuoka"; break;
						case 136: city.name = "Murmansk"; break;
						case 137: city.name = "Turin"; break;
						case 138: city.name = "Lisbon"; break;
						default: city.name = "Cleveland"; break;
					}
					network.cities.Add(city);
				}
				network.Initialize(r.Next());
				SetDistanceList();
				SetNetworkLists();
			}
			else if ((e.Button == MouseButtons.Right) && (clickedCity != null))  // start moving city
				movingCity = clickedCity;
			picMap.Refresh();
		}

		private void picMap_MouseUp(object sender, System.Windows.Forms.MouseEventArgs e) {
			if ((e.Button == MouseButtons.Right) && (movingCity != null)) {
				movingCity = null;
				network.Initialize(r.Next());
				SetDistanceList();
				SetNetworkLists();
				picMap.Refresh();
			}
		}

		private void picMap_Paint(object sender, System.Windows.Forms.PaintEventArgs e) {
			Font font = new Font("Times New Roman", 7.0f);
			StringFormat format = new StringFormat();
			format.Alignment = StringAlignment.Center;
			Graphics g = e.Graphics;
			g.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;
			g.FillRectangle(System.Drawing.Brushes.BlanchedAlmond, e.ClipRectangle);

			// draw routes
			if (network.cities.Count > 1) {

				int iNextCity = 0;
				for (int X = 1; X < network.cities.Count; X++) {
					if (network.V[X, 0] > network.V[iNextCity, 0])
						iNextCity = X;
				}
				int iCurrentCity;
				for (int i = network.cities.Count - 1; i >= 0; i--) {
					iCurrentCity = 0;
					for (int X = 1; X < network.cities.Count; X++) {
						if (network.V[X, i] > network.V[iCurrentCity, i])
							iCurrentCity = X;
					}
					if ((network.V[iNextCity, (i + 1) % network.cities.Count] > 0.05) && (network.V[iCurrentCity, i] > 0.05)) {
						Pen pen = new Pen(Color.FromArgb((int) (network.V[iNextCity, (i + 1) % network.cities.Count] * 128) + 127, 0, 255, 0));
						if (network.V[iNextCity, (i + 1) % network.cities.Count] > 0.95)
							pen = new Pen(Color.FromArgb(255, 0, 0));
						g.DrawLine(pen, (int) ((City) network.cities[iCurrentCity]).x, (int) ((City) network.cities[iCurrentCity]).y, (int) ((City) network.cities[iNextCity]).x, (int) ((City) network.cities[iNextCity]).y);
					}
					iNextCity = iCurrentCity;
				}
			}

			// draw cities
			foreach (object cityobject in network.cities) {
				City city = (City) cityobject;
				g.FillEllipse(Brushes.Tan, (int) (city.x - 5), (int) (city.y - 5), 10, 10);
				g.DrawEllipse(Pens.Black, (int) (city.x - 5), (int) (city.y - 5), 10, 10);
				g.DrawString(city.name, font, Brushes.Black, (int) (city.x), (int) (city.y - 20), format);
			}
		}

		private void timerUpdate_Elapsed(object sender, System.Timers.ElapsedEventArgs e) {
			if (thread != null) {
				picMap.Refresh();
				txtStatus.Text = strCurrentStatus;
				txtStatus.Refresh();
			}
		}

		private void TravelingSalesmanProblem_Closing(object sender, System.ComponentModel.CancelEventArgs e) {
			if (thread != null)
				thread.Abort();
		}

		private void listNetworkV_Resize(object sender, System.EventArgs e) {
			SetNetworkLists();
		}

		private void groupBox1_Resize(object sender, System.EventArgs e) {
			SetNetworkLists();
		}

		private void TravelingSalesmanProblem_Resize(object sender, System.EventArgs e) {
			SetDistanceList();
			SetNetworkLists();
		}

		#endregion

		#region Helper functions

		private void SetDistanceList() {
			listDistances.BeginUpdate();
			if (network.cities.Count == 0) {  // zero the list
				listDistances.Columns.Clear();
				listDistances.Items.Clear();
			}
			else {
				// setup list columns
				int width = listDistances.Width / (network.cities.Count + 1);
				listDistances.Columns.Clear();
				ColumnHeader ch = new ColumnHeader();
				ch.Width = width;
				ch.Text = "Name";
				listDistances.Columns.Add(ch);
				foreach (object cityobject in network.cities) {
					ColumnHeader c = new ColumnHeader();
					c.Width = width;
					c.Text = ((City) cityobject).name;
					listDistances.Columns.Add(c);
				}
				// setup list rows
				listDistances.Items.Clear();
				for (int i = 0; i < network.cities.Count; i++) {
					City city = (City) network.cities[i];
					ListViewItem row = new ListViewItem(city.name);
					for (int j = 0; j < network.cities.Count; j++)
						row.SubItems.Add("" + network.distances[i, j]);
					listDistances.Items.Add(row);
				}
			}
			listDistances.EndUpdate();
			listDistances.Refresh();
		}

		private void SetNetworkLists() {
			// update network V
			listNetworkV.BeginUpdate();
			if (network.cities.Count == 0) {  // zero the list
				listNetworkV.Columns.Clear();
				listNetworkV.Items.Clear();
			}
			else {
				// setup list columns
				int width = listNetworkV.Width / (network.cities.Count + 1);
				listNetworkV.Columns.Clear();
				ColumnHeader ch = new ColumnHeader();
				ch.Width = width;
				ch.Text = "Name";
				listNetworkV.Columns.Add(ch);
				for (int i = 0; i < network.cities.Count; i++) {
					ColumnHeader c = new ColumnHeader();
					c.Text = "" + (i + 1);
					c.Width = width;
					listNetworkV.Columns.Add(c);
				}
				// setup list rows
				listNetworkV.Items.Clear();
				for (int i = 0; i < network.cities.Count; i++) {
					City city = (City) network.cities[i];
					ListViewItem row = new ListViewItem(city.name);
					for (int j = 0; j < network.cities.Count; j++)
						row.SubItems.Add("" + Math.Round(network.V[i,j], 3));
					listNetworkV.Items.Add(row);
				}
				listNetworkV.Items.Add(new ListViewItem(new string[] {} ));
				for (int i = 0; i < network.cities.Count; i++) {
					City city = (City) network.cities[i];
					ListViewItem row = new ListViewItem(city.name);
					for (int j = 0; j < network.cities.Count; j++)
						row.SubItems.Add("" + Math.Round(network.u[i,j], 3));
					listNetworkV.Items.Add(row);
				}
			}
			listNetworkV.EndUpdate();
			listNetworkV.Refresh();
		}

		private void AnalyzeFull() {
			int totalsteps = 0;
			do {
				totalsteps++;
				network.Analyze();
			} while ((network.E != 0.0) && (totalsteps < 10000));
		}

		private void AnalyzeFullThread() {
			int totalsteps = 0;
			do {
				totalsteps++;
				network.Analyze();
				strCurrentStatus = "Status: Analyzing. Steps = " + totalsteps + ". Total distance = " + network.TotalDistance();
			} while ((network.E != 0.0) && (totalsteps < 50000));
			if (network.E == 0.0)
				txtStatus.Text = strCurrentStatus = "Status: Finished. Total distance = " + network.TotalDistance();
			else
				txtStatus.Text = strCurrentStatus = "Status: Terminated after " + totalsteps + " steps. Total distance = " + network.TotalDistance() + ".";
			txtStatus.Refresh();
			btnAnalyzeFull.Text = "Analyze (Full)";
			btnAnalyzeFull.Refresh();
			picMap.Refresh();
			SetNetworkLists();
			thread = null;
		}

		#endregion

		private void TravelingSalesmanProblem_Load(object sender, System.EventArgs e)
		{
		
		}

		private void picMap_Click(object sender, System.EventArgs e)
		{
		
		}

	}
}