Shortest Route of converters between two different

2019-09-22 08:18发布

站内文章 / 前端开发
26 0 0

问题:

I've got an Access document where I can list out all the converters available for different size fittings on pipes. An example of going from Pipe A to Pipe B might be: They display as (Incoming Port -> outgoing port)

Pipe A -> type 1

type 1 -> type c2

type c2 -> type 7

type 7 -> Pipe B

There are multiple routes and types that will allow you to go from Pipe A to Pipe B. However, I'd like to use a method in VBA or through Access directly to go from Pipe A to Pipe B, and have it find the shortest method.

Any ideas? ashleedawg posted this picture that perfectly represents what I'm trying to do. Hopefully this narrows down my request:

[Question has been edited. Should be taken off-hold as per this.]

回答1:

The code below is messy and un-commented, but I'm glad it was able to get you in the right direction, so you were able to figure out the solution! Downloadable MDB on JumpShare here.

Option Compare Database: Option Explicit
'I had a theory which I implemented and later commented out in order to handle "two-direction searches" since connectors probably aren't in alphabetical order
'I was going to use [cfromsSofar] to :
'     - track connector "from's" that we've already been to, so it can,
'     - prevent endless loops like:  connectors A>B B>C C>A  over and over
'but when I used that, it would stop after one possible route
'also need to ensure functionality of forward-back-forward routes like A>D D>B B>Z


Type connector
    cFrom As String
    cTo As String
    cID As Long
End Type

'Const connQuery = "qConn_bothdirections" 'a union query with the connectors listed in both forward & backward directions
Const connQuery = "qConn_onedirection"

Const cStart = "A": Const cFinish = "Z"
Public cfromsSofar As String, successfulMatchSets As String

Sub connTest()    ' >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> RUN THIS SUB TO TEST <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
'go from A to Z

Debug.Print "*** BEGIN FINDING ROUTE FROM " & cStart & " to " & cFinish & " ***"
successfulMatchSets = ""
cfromsSofar = ","

listMatches cStart, "", ""

Debug.Print "Finished searching for routes."
Debug.Print
Debug.Print "*** FINISHED FINDING ROUTE FROM " & cStart & " to " & cFinish & " ***"
Debug.Print "Successful Match Sets: " & vbCrLf & successfulMatchSets
If successfulMatchSets = "" Then Debug.Print "No Matches Found."
Debug.Print "Done."
End Sub


Sub listMatches(sStart As String, indent As String, previousFind As String)
Dim rs As Recordset, x As Integer, y As Integer, clause_NotIn As String

If Len(cfromsSofar) = 1 Then
    clause_NotIn = ""
Else
    clause_NotIn = " AND cTo NOT IN (" & Mid(cfromsSofar, 2, Len(cfromsSofar) - 2) & ")"
End If

'list everything that connects to "A"
Set rs = CurrentDb.OpenRecordset("select * from " & connQuery & " WHERE cFrom = '" & sStart & "' " & clause_NotIn) '*** where cTo isn't in list of cFrom's we've had yet

Dim matches() As connector  'array of connectors
Dim noMatchesFound As Boolean
With rs
    If .EOF Then
        Debug.Print indent & "No matches found ""From " & sStart & """"

        noMatchesFound = True
    Else
        noMatchesFound = False
        .MoveLast

        Debug.Print indent & .RecordCount & " matches found ""From " & sStart & """"

        ReDim matches(.RecordCount)

        x = 0
        .MoveFirst
        Do While Not .EOF  ' populate array [matches] with [connector] objects
            x = x + 1

            'Debug.Print !cFrom, !cTo, !cID
            matches(x).cFrom = rs!cFrom
            add_cFrom_to_cFromsSoFar (matches(x).cFrom)  'keep global list of cFroms so we don't go backwards
            matches(x).cTo = rs!cTo
            matches(x).cID = rs!cID


            .MoveNext
        Loop

    End If
    .Close

End With


'got list of possible connectors.  Now enumerate the list

If Not noMatchesFound Then

    For y = 1 To UBound(matches)

        'Debug.Print indent & matches(y).cFrom, matches(y).cTo, matches(y).cID
        'we've found matches up to [matches(y).cTo]. what matches can we find FROM there?
        Debug.Print previousFind

        Dim matchSet As String

        If matches(y).cTo = cFinish Then
            matchSet = previousFind & " {" & matches(y).cFrom & "-to-" & matches(y).cTo & "#" & matches(y).cID & "}"
            successfulMatchSets = successfulMatchSets & vbCrLf & matchSet
        End If
        listMatches matches(y).cTo, indent & "->  ", previousFind & " {" & matches(y).cFrom & "-to-" & matches(y).cTo & "#" & matches(y).cID & "}"  'check next level (recursive!)

    Next y

End If

End Sub


Sub add_cFrom_to_cFromsSoFar(cFrom As String)
'keep global list of cFroms so we don't go backwards

If InStr(cfromsSofar, ",'" & cFrom & "',") > 0 Then
    'already exists in list

Else
    'doesn't exist in list -- add it
    cfromsSofar = cfromsSofar & "'" & cFrom & "',"
End If

'Debug.Print "             WHERE cTO NOT IN: " & cFrom

End Sub

Update:

While troubleshooting the recursion error you discovered in the previous code, I realized that there is another way to accomplish this, potentially much simpler than the other method (depending on the scale of implementation).

Just one query:

SELECT Hop1.end1 & IIf([Hop1].[end1] Is Null,'',Chr(187)) & Hop1.end2 As C1, 
Hop2.end1 & IIf([Hop2].[end1] Is Null,'',Chr(187)) & Hop2.end2 As C2, 
Hop3.end1 & IIf([Hop3].[end1] Is Null,'',Chr(187)) & Hop3.end2 As C3, 
Hop4.end1 & IIf([Hop4].[end1] Is Null,'',Chr(187)) & Hop4.end2 As C4, 
Hop5.end1 & IIf([Hop5].[end1] Is Null,'',Chr(187)) & Hop5.end2 As C5, 
Hop6.end1 & IIf([Hop6].[end1] Is Null,'',Chr(187)) & Hop6.end2 As C6, 
Hop7.end1 & IIf([Hop7].[end1] Is Null,'',Chr(187)) & Hop7.end2 As C7, 
Hop8.end1 & IIf([Hop8].[end1] Is Null,'',Chr(187)) & Hop8.end2 As C8, 
Hop9.end1 & IIf([Hop9].[end1] Is Null,'',Chr(187)) & Hop9.end2 As C9, 
Hop10.end1 & IIf([Hop10].[end1] Is Null,'',Chr(187)) & Hop10.end2 As C10, 
Hop11.end1 & IIf([Hop11].[end1] Is Null,'',Chr(187)) & Hop11.end2 As C11, 
Hop12.end1 & IIf([Hop12].[end1] Is Null,'',Chr(187)) & Hop12.end2 As C12, 
Hop13.end1 & IIf([Hop13].[end1] Is Null,'',Chr(187)) & Hop13.end2 As C13, 
Hop14.end1 & IIf([Hop14].[end1] Is Null,'',Chr(187)) & Hop14.end2 As C14, 
Hop15.end1 & IIf([Hop15].[end1] Is Null,'',Chr(187)) & Hop15.end2 As C15, 
Hop16.end1 & IIf([Hop16].[end1] Is Null,'',Chr(187)) & Hop16.end2 As C16, 
Hop17.end1 & IIf([Hop17].[end1] Is Null,'',Chr(187)) & Hop17.end2 As C17, 
Hop18.end1 & IIf([Hop18].[end1] Is Null,'',Chr(187)) & Hop18.end2 As C18, 
Hop19.end1 & IIf([Hop19].[end1] Is Null,'',Chr(187)) & Hop19.end2 As C19, 
Hop20.end1 & IIf([Hop20].[end1] Is Null,'',Chr(187)) & Hop20.end2 As C20, 
Hop21.end1 & IIf([Hop21].[end1] Is Null,'',Chr(187)) & Hop21.end2 As C21, 
Hop22.end1 & IIf([Hop22].[end1] Is Null,'',Chr(187)) & Hop22.end2 As C22, 
Hop23.end1 & IIf([Hop23].[end1] Is Null,'',Chr(187)) & Hop23.end2 As C23, 
Hop24.end1 & IIf([Hop24].[end1] Is Null,'',Chr(187)) & Hop24.end2 As C24, 
Hop25.end1 & IIf([Hop25].[end1] Is Null,'',Chr(187)) & Hop25.end2 As C25, 
Hop26.end1 & IIf([Hop26].[end1] Is Null,'',Chr(187)) & Hop26.end2 As C26, 
Hop27.end1 & IIf([Hop27].[end1] Is Null,'',Chr(187)) & Hop27.end2 As C27, 
Hop28.end1 & IIf([Hop28].[end1] Is Null,'',Chr(187)) & Hop28.end2 As C28, 
Hop29.end1 & IIf([Hop29].[end1] Is Null,'',Chr(187)) & Hop29.end2 As C29, 
Hop30.end1 & IIf([Hop30].[end1] Is Null,'',Chr(187)) & Hop30.end2 As C30, 
Hop31.end1 & IIf([Hop31].[end1] Is Null,'',Chr(187)) & Hop31.end2 As C31, 
Hop32.end1 & IIf([Hop32].[end1] Is Null,'',Chr(187)) & Hop32.end2 As C32 
FROM ((((((((((((((((((((((((((((((connectors AS Hop1
 LEFT JOIN connectors AS Hop2 ON Hop1.end2 = Hop2.end1)
 LEFT JOIN connectors AS Hop3 ON Hop2.end2 = Hop3.end1)
 LEFT JOIN connectors AS Hop4 ON Hop3.end2 = Hop4.end1)
 LEFT JOIN connectors AS Hop5 ON Hop4.end2 = Hop5.end1)
 LEFT JOIN connectors AS Hop6 ON Hop5.end2 = Hop6.end1)
 LEFT JOIN connectors AS Hop7 ON Hop6.end2 = Hop7.end1)
 LEFT JOIN connectors AS Hop8 ON Hop7.end2 = Hop8.end1)
 LEFT JOIN connectors AS Hop9 ON Hop8.end2 = Hop9.end1)
 LEFT JOIN connectors AS Hop10 ON Hop9.end2 = Hop10.end1)
 LEFT JOIN connectors AS Hop11 ON Hop10.end2 = Hop11.end1)
 LEFT JOIN connectors AS Hop12 ON Hop11.end2 = Hop12.end1)
 LEFT JOIN connectors AS Hop13 ON Hop12.end2 = Hop13.end1)
 LEFT JOIN connectors AS Hop14 ON Hop13.end2 = Hop14.end1)
 LEFT JOIN connectors AS Hop15 ON Hop14.end2 = Hop15.end1)
 LEFT JOIN connectors AS Hop16 ON Hop15.end2 = Hop16.end1)
 LEFT JOIN connectors AS Hop17 ON Hop16.end2 = Hop17.end1)
 LEFT JOIN connectors AS Hop18 ON Hop17.end2 = Hop18.end1)
 LEFT JOIN connectors AS Hop19 ON Hop18.end2 = Hop19.end1)
 LEFT JOIN connectors AS Hop20 ON Hop19.end2 = Hop20.end1)
 LEFT JOIN connectors AS Hop21 ON Hop20.end2 = Hop21.end1)
 LEFT JOIN connectors AS Hop22 ON Hop21.end2 = Hop22.end1)
 LEFT JOIN connectors AS Hop23 ON Hop22.end2 = Hop23.end1)
 LEFT JOIN connectors AS Hop24 ON Hop23.end2 = Hop24.end1)
 LEFT JOIN connectors AS Hop25 ON Hop24.end2 = Hop25.end1)
 LEFT JOIN connectors AS Hop26 ON Hop25.end2 = Hop26.end1)
 LEFT JOIN connectors AS Hop27 ON Hop26.end2 = Hop27.end1)
 LEFT JOIN connectors AS Hop28 ON Hop27.end2 = Hop28.end1)
 LEFT JOIN connectors AS Hop29 ON Hop28.end2 = Hop29.end1)
 LEFT JOIN connectors AS Hop30 ON Hop29.end2 = Hop30.end1)
 LEFT JOIN connectors AS Hop31 ON Hop30.end2 = Hop31.end1)
 LEFT JOIN connectors AS Hop32 ON Hop31.end2 = Hop32.end1 
ORDER BY Hop1.end1, Hop1.end2, Hop2.end1, Hop2.end2, Hop3.end1, Hop3.end2, Hop4.end1, Hop4.end2, Hop5.end1, Hop5.end2, Hop6.end1, Hop6.end2, Hop7.end1, Hop7.end2, Hop8.end1, Hop8.end2, Hop9.end1, Hop9.end2, Hop10.end1, Hop10.end2, Hop11.end1, Hop11.end2, Hop12.end1, Hop12.end2, Hop13.end1, Hop13.end2, Hop14.end1, Hop14.end2, Hop15.end1, Hop15.end2, Hop16.end1, Hop16.end2, Hop17.end1, Hop17.end2, Hop18.end1, Hop18.end2, Hop19.end1, Hop19.end2, Hop20.end1, Hop20.end2, Hop21.end1, Hop21.end2, Hop22.end1, Hop22.end2, Hop23.end1, Hop23.end2, Hop24.end1, Hop24.end2, Hop25.end1, Hop25.end2, Hop26.end1, Hop26.end2, Hop27.end1, Hop27.end2, Hop28.end1, Hop28.end2, Hop29.end1, Hop29.end2, Hop30.end1, Hop30.end2, Hop31.end1, Hop31.end2, Hop32.end1, Hop32.end2

(I didn't say it was a small query!) It basically lists every possible combination of "paths" between the connectors, up to 32 possible connections (since that is the maximum number of joins allowed in an Access 2016 query).

...and the output:

Rather than building it manually, and going through it all if a change is necessary, I had VBA write it for me:

Sub buildSQL_qryConnPaths()  'builds SQL query for tracing possible connection paths

    Const maxHops = 32 'as per "[Access 2016 Maximum Number of enforced relationships][4]" 
    Dim hSELECT As String, hFROM As String, hWHERE As String, hORDERBY As String, hSQL As String, x As Long

    hSELECT = "SELECT "
    hFROM = "FROM " & String(maxHops - 2, "(")
    hORDERBY = "ORDER BY "

    For x = 1 To maxHops
        hSELECT = hSELECT & "Hop" & x & ".end1 & IIf([Hop" & x & "].[end1] Is Null,'',Chr(187)) & Hop" & x & ".end2 As C" & x & ", " & vbLf
        hFROM = hFROM & IIf(x = 1, "", vbLf & " LEFT JOIN ") & "connectors AS Hop" & x & IIf(x = 1, "", " ON Hop" & x - 1 & ".end2 = Hop" & x & ".end1" & IIf(x <> maxHops, ")", ""))
        hORDERBY = hORDERBY & "Hop" & x & ".end1, Hop" & x & ".end2, "
    Next x

    hSELECT = Left(hSELECT, Len(hSELECT) - 3) & " " & vbLf
    hFROM = Left(hFROM, Len(hFROM)) & " " & vbLf
    hORDERBY = Left(hORDERBY, Len(hORDERBY) - 2)
    hSQL = hSELECT & hFROM & hWHERE & hORDERBY

    Debug.Print hSQL

End Sub

Let me know if you have any questions. I'm still very curious how large your data set actually is...



标签： ms-access recursion access-vba
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~