breadth first search

[ppenno1981]

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.

[crapulency]

hi ppenno

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

[ppenno1981]

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.
cheers

[crapulency]

Hi ppenno, many apologies for not replying. Are you still working on this? Happy to help if you are.

[crapulency]

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.