hi guys i have a little problem. I need to access a database using vb.net to create a shortest path solver using vb.net. Say for example the shortest route for a product being sent from london to moscow. I can acess the database but dont know how to sort the cities in an adjacancy list.How does london for example know it is 2 vertices away from paris? i have a hunch it is a dimensional array, but unsure. any help would be greatly appreciated, thanks.
it sounds like an interesting task, but I suspect nobody has replied because a litte more info is required. I'm guessing it is some kind of assignment - so what kind of data are you given to start with, if any? In your database, do you have a list of cities? And is there any information regarding how far apart they are and which are to be considered adjacent? Perhaps you are dealing with longitude and latitude? Is "the shortest route" to be measured in distance or steps? When we have a rough idea of this, then we can begin talking about arrays
hi, all cities are to be given the same distance from each other, but they may not all be connected. for example london to paris a distance of one, if no direct link exists to moscow and i go to paris first the value will be 2. I can make the cities up of course,so in a nutshell they all have the same distance in relation to each other, but they not all connected and a shortest path must be found. This makes the shortest distance the number of steps taken. I know i need to make use of an adjacancy list, a que in the bfs and some kind of array.
Hi ppenno, many apologies for not replying. Are you still working on this? Happy to help if you are.
Hi ppenno here is some code that may help you/give you some ideas. Not the only way of doings things, but a simple and direct way.
WHen your app starts, call LoadCItyData. THis will create a collection of cities, each with its own collection of adjacent cities. We build the cities collection from the a table "Cities" that has a single text field "City". We populate the AdjacentCities of each city from a second table called "Connections" that has two text fields, "City1" and "City2", each record representing a connection between 2 cities. If there is a connection between London and Paris, for example, LoadCityData will add Paris to London's adjacent cities and vice versa. Every city must have at least one adjacent city.
Once this is complete we can forget about the database. Whenever we need to calculate the shortest journey between two of our cities, we create a new Journey object, passing a StartCIty and FinishCity to its constructor, and call the Calculate method. WHen complete, the Journey.Routes collection will contain the shortest route(s).
All our Journey object does, of course, is build all possible routes jumping from city to adjacent city, excluding those already included. WHen the last added city in any route matches the destination city of the journey, that route and the journey are complete.
Module CityData Public Cities As Collection Public Sub LoadCityData() Cities = New Collection Dim con As New OleDb.OleDbConnection("Provider=Microsoft.Jet.OLEDB.4.0;Data Source=|DataDirectory|\CityData.mdb") Dim cmdCities As New OleDb.OleDbCommand("SELECT City from Cities", con) Dim cmdConnections As New OleDb.OleDbCommand("SELECT City1,City2 FROM Connections", con) Try con.Open() Using drCities As OleDb.OleDbDataReader = cmdCities.ExecuteReader While drCities.Read Cities.Add(New City(drCities.GetString(0)), drCities.GetString(0)) End While End Using Dim City1, City2 As City Using drConnections As OleDb.OleDbDataReader = cmdConnections.ExecuteReader While drConnections.Read City1 = Cities.Item(drConnections.GetString(0)) City2 = Cities.Item(drConnections.GetString(1)) City1.AdjacentCities.Add(City2) City2.AdjacentCities.Add(City1) End While End Using Catch ex As Exception MsgBox(ex.Message) Finally cmdCities.Dispose() cmdConnections.Dispose() con.Close() con.Dispose() End Try End Sub End Module Public Class City Public Name As String Public AdjacentCities As New Collection Public Sub New(ByVal CityName As String) Me.Name = CityName End Sub End Class Public Class Route Public Cities As Collection Public LastCity As City Public Function Add(ByVal newCity As City) As Boolean Try Cities.Add(newCity, newCity.Name) LastCity = newCity Return True Catch ex As Exception Return False End Try End Function Public Function NextRoutes() As Collection Dim theNextRoutes As New Collection Dim newRoute As Route For Each adjacentCity As City In LastCity.AdjacentCities newRoute = New Route(Me.Cities) If newRoute.Add(adjacentCity) = True Then theNextRoutes.Add(newRoute) End If Next Return theNextRoutes End Function Public Sub New(ByVal ParentCities As Collection) Me.Cities = New Collection For Each cty As City In ParentCities Me.Add(cty) Next End Sub Public Sub New(ByVal StartCity As City) Cities = New Collection Me.Add(StartCity) End Sub End Class Public Class Journey Public Start As City Public Finish As City Public Routes As New Collection Public Complete As Boolean = False Public Sub Calculate() While Me.Complete = False Me.MoveNext() End While End Sub Private Sub MoveNext() Dim newRoutes As New Collection For Each oldRoute As Route In Routes For Each newRoute As Route In oldRoute.NextRoutes If newRoute.LastCity.Name <> Start.Name Then newRoutes.Add(newRoute) If newRoute.LastCity.Name = Finish.Name Then Complete = True End If End If Next Next If Complete = True Then Routes = New Collection For Each newRoute As Route In newRoutes If newRoute.LastCity.Name = Finish.Name Then Routes.Add(newRoute) End If Next Else Routes = newRoutes End If End Sub Public Sub New(ByVal StartCity As City, ByVal FinishCity As City) Routes.Add(New Route(StartCity)) Me.Start = StartCity Me.Finish = FinishCity End Sub End Class
For your ui, using two comboboxes (cmbFrom and cmbTo) a button (btnCalculate) and two listboxes (lsbRoutes and lsbRoute):
Public Class Form1 Private _currentJourney As Journey Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load CityData.LoadCityData() For Each cty As City In Cities cmbFrom.Items.Add(cty.Name) cmbTo.Items.Add(cty.Name) Next End Sub Private Sub btnCalculate_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnCalculate.Click Dim start As City = Cities(cmbFrom.Text) Dim finish As City = Cities(cmbTo.Text) If start.Name = finish.Name Then MsgBox("Cities are the same", MsgBoxStyle.Exclamation) Exit Sub End If lsbRoutes.Items.Clear() lsbRoute.Items.Clear() _currentJourney = New Journey(start, finish) _currentJourney.Calculate() Dim iIndex As Integer = 0 For Each completeRoute As Route In _currentJourney.Routes iIndex += 1 lsbRoutes.Items.Add("Route " & iIndex.ToString) Next lsbRoutes.SelectedIndex = 0 End Sub Private Sub lsbRoutes_SelectedIndexChanged(ByVal sender As Object, ByVal e As System.EventArgs) Handles lsbRoutes.SelectedIndexChanged lsbRoute.Items.Clear() Dim selectedRoute As Route = _currentJourney.Routes(lsbRoutes.SelectedIndex + 1) For Each cty As City In selectedRoute.Cities lsbRoute.Items.Add(cty.Name) Next End Sub End Class
sorry no comments or error handling. Hope it helps.