9 replies to this topic

[twitchyliquid64]

Hi all,

This is a short program I wrote to demonstrate the power of graph theory and its potential in Autoit.




Ultimately, graph theory is about dynamically creating records about specific ‘things’ in your program, and mapping how they relate, to allow your program to make inferences and do something smart.

Credit must be given to toady for the idea, and for minor internal management (I used his string regexp expression, and some array popping) Here is his one: http://www.autoitscript.com/forum/topic/...rtificial-intelligence-bot-pat

I would encourage you to first download the script and try it out. Place nodes around the place, then use the link tool to link nodes of your choosing together. Then, press setup, choose the start and end nodes, then press go. Then the program will find the shortest path from start to end, traversing the links you created.

If you want to find out what graph theory is, I encourage you to look at the Wikipedia entry and Google ‘shortest path problem’.

LEMME KNOW OF YOUR OPINIONS/COMMENTS!!!

Downloads:
The Program:  Node Graph Simulator.au3   8.47KB   263 downloads
My Node-Graph Theory UDF (you will need it to run):  node_graph UDF.au3   7.7KB   261 downloads

Regards,

Hypoz.

Edited by hyperzap, 09 February 2011 - 02:40 AM.

[spudw2k]

Wow, very cool! I'd like to see a network tool built around this. Thanks for sharing!

[twitchyliquid64]

Wow, very cool! I'd like to see a network tool built around this. Thanks for sharing!

Thanks. I'm building a wikipedia relation algorithm ATM but after that I'll rewrite my p2p udf to use this for message routing.

[tobject]

can this be used for a portfolio of stocks to decide which stock to remove and which to add to minimize losses or maximize gains?

[twitchyliquid64]

I'm not sure how you would use this for that: that sounds more like dynamic thresholding (using standard deviation) and a genetic algorithm.

[Manadar]

This is based on this right: http://www.autoitscript.com/forum/topic/47161-artificial-intelligence-bot-path-finding/ ?

Might want to give credit.

[Mat]

How about going through and adding the chinese postman / eulerian graphs solutions, and the minimum spanning trees algorithms... I was thinking about doing something just like it a while ago, but wanted to build in all kinds of fancy user interfaces which I suck at. The only thing I'd add though is being able to weight the arcs.

@tobject

You are looking at linear programming there, for which you need simplex. Here is what I use to do all the working for me. Since it has to print the workings, there is a lot in there that can be stripped (there is a fair bit of code for using the letters, and an extra row and column in the tableau.

AutoIt        expandcollapse  popup

#AutoIt3Wrapper_Change2CUI=y
#AutoIt3Wrapper_Res_LegalCopyright=Matt Diesel (Mat) 2010 - 2011

Local $iNumVars = 2

Local $sObjectiveVarName = "P"
Local $aVarNames[$iNumVars] = ["x", "y"]
Local $aSlackNames[$iNumVars] = ["s", "t"]

Local $aMaxEquation[$iNumVars] = [-6, -8]
Local $aSubjectTo[$iNumVars][$iNumVars + 1] = [[4, 3, 1500],[1, 2, 500]]

_Simplex_Working($iNumVars, $sObjectiveVarName, $aVarNames, $aSlackNames, $aMaxEquation, $aSubjectTo)

Func _Simplex_Working($iNumVars, $sObjectiveVarName, $aVarNames, $aSlackNames, $aMaxEquation, $aSubjectTo)
    ; 1.1 :: Print it
    Local $sProblem = "Maximise " & $sObjectiveVarName & " = "
    For $i = 0 To $iNumVars - 1
        $sProblem &= $aMaxEquation[$i] * -1 & $aVarNames[$i] & " + "
    Next
    $sProblem = StringTrimRight($sProblem, 3)

    $sProblem &= @LF & "Subject to: " & @LF
    For $n = 0 To $iNumVars - 1
        $sProblem &= "    "

        For $i = 0 To $iNumVars - 1
            $sProblem &= $aSubjectTo[$n][$i] & $aVarNames[$i] & " + "
        Next

        $sProblem &= $aSlackNames[$n] & " = " & $aSubjectTo[$n][$iNumVars] & @LF
    Next
    ConsoleWrite($sProblem & @LF)

    ; 2 :: Initial Tableau
    $aTableau = _Simplex_CreateTableau($iNumVars)

    ; 2.1 :: Headers
    $aTableau[0][0] = "Basic var"
    For $i = 1 To $iNumVars
        $aTableau[$i][0] = $aSlackNames[$i - 1]
    Next
    $aTableau[$iNumVars + 1][0] = $sObjectiveVarName
    For $i = 1 To $iNumVars
        $aTableau[0][$i] = $aVarNames[$i - 1]
    Next
    For $i = 1 To $iNumVars
        $aTableau[0][$iNumVars + $i] = $aSlackNames[$i - 1]
    Next
    $aTableau[0][$iNumVars * 2 + 1] = "Value"

    ; 2.2 :: Values
    For $n = 0 To $iNumVars - 1
        For $i = 0 To $iNumVars - 1
            $aTableau[$n + 1][$i + 1] = $aSubjectTo[$n][$i]
        Next
        For $i = $iNumVars To $iNumVars * 2
            $aTableau[$n + 1][$i + 1] = 0
        Next
        $aTableau[$n + 1][$iNumVars + 1 + $n] = 1
        $aTableau[$n + 1][$iNumVars * 2 + 1] = $aSubjectTo[$n][$iNumVars]
    Next

    For $i = 1 To $iNumVars
        $aTableau[$iNumVars + 1][$i] = $aMaxEquation[$i - 1]
    Next
    For $i = $iNumVars To $iNumVars * 2
        $aTableau[$iNumVars + 1][$i + 1] = 0
    Next

    ConsoleWrite(_Simplex_TableauToString($aTableau) & @LF)


    Do
        _Simplex_Next($aTableau)
        ConsoleWrite(_Simplex_TableauToString($aTableau) & @LF)
        ; 7.1 :: Check optimal
    Until _Simplex_Optimal($aTableau)

    ; 7.2 :: Print solution
    Local $sSolution = "Solution: " & @LF
    For $n = 0 To $iNumVars
        $sSolution &= $aTableau[$n + 1][0] & " = " & $aTableau[$n + 1][UBound($aTableau, 2) - 2] & @LF
    Next
    $sSolution &= "Everything else = 0" & @LF
    ConsoleWrite($sSolution)
EndFunc


Func _Simplex_Next(ByRef $aTableau)
    Local $iPivotRow = -1
    Local $iPivotCol = -1

    ; 3 :: Get pivot col
    Local $r = UBound($aTableau) - 1
    For $c = 1 To UBound($aTableau, 2) - 1
        If $iPivotCol < 0 Or $aTableau[$r][$c] < $aTableau[$r][$iPivotCol] Then $iPivotCol = $c
    Next

    ; 4 :: Get pivot row
    $c = UBound($aTableau, 2) - 2
    Local $iTheta
    For $r = 1 To UBound($aTableau) - 2
        $iTheta = $aTableau[$r][$c] / $aTableau[$r][$iPivotCol] ; Theta = Value / Pivot value

        If $iTheta < 0 Then
            $aTableau[$r][$c + 1] = "--"
        Else
            $aTableau[$r][$c + 1] = "Theta = " & $iTheta

            If $iPivotRow < 0 Or $iTheta < $aTableau[$iPivotRow][$c] / $aTableau[$iPivotRow][$iPivotCol] Then $iPivotRow = $r
        EndIf
    Next
    $aTableau[UBound($aTableau) - 1][UBound($aTableau, 2) - 1] = ""

    $aTableau[0][UBound($aTableau, 2) - 1] = "Pivot: " & $iPivotRow & "," & $iPivotCol ;;;;;

    ; leaves the basis:
    $aTableau[$iPivotRow][0] = $aTableau[0][$iPivotCol]

    ConsoleWrite(_Simplex_TableauToString($aTableau) & @LF)

    ; 5 :: Divide row by pivot:
    Local $iPivot = $aTableau[$iPivotRow][$iPivotCol]
    For $c = 1 To UBound($aTableau, 2) - 2
        $aTableau[$iPivotRow][$c] /= $iPivot
    Next

    ; 6 :: Zero other rows
    Local $iTimes
    For $r = 1 To UBound($aTableau) - 1
        If $r = $iPivotRow Then ContinueLoop

        $iTimes = $aTableau[$r][$iPivotCol] / $aTableau[$iPivotRow][$iPivotCol]
        For $c = 1 To UBound($aTableau, 2) - 2
            $aTableau[$r][$c] -= $iTimes * $aTableau[$iPivotRow][$c]
        Next
        $aTableau[$r][UBound($aTableau, 2) - 1] = StringFormat("[%d] = [%d] - (%d * [%d])", $r, $r, $iTimes, $iPivotRow)
    Next
    $aTableau[$iPivotRow][UBound($aTableau, 2) - 1] = StringFormat("[%d] = [%d] / %d", $iPivotRow, $iPivotRow, $iPivot)
EndFunc   ;==>_Simplex_Next

Func _Simplex_Optimal($aTableau)
    Local $r = UBound($aTableau) - 1

    For $c = 1 To UBound($aTableau) - 1
        If $aTableau[$r][$c] < 0 Then Return False
    Next

    Return True
EndFunc   ;==>_Simplex_Optimal

Func _Simplex_TableauToString($aTableau)
    Local $sRet = ""

    For $r = 0 To UBound($aTableau) - 1
        For $c = 0 To UBound($aTableau, 2) - 2
            $sRet &= StringFormat("| %-10.10s", $aTableau[$r][$c])
        Next
        $sRet &= "| " & $aTableau[$r][UBound($aTableau, 2) - 1] & @LF
    Next

    Return $sRet
EndFunc   ;==>_Simplex_TableauToString

Func _Simplex_CreateTableau($iNumVars)
;~ Rows: $iNumVars + 2
;~ Cols: $iNumVars * 2 + 2
    Local $aTableau[$iNumVars + 2][$iNumVars * 2 + 3]

    Return $aTableau
EndFunc   ;==>_Simplex_CreateTableau

Mat

[twitchyliquid64]

This is based on this right: http://www.autoitscript.com/forum/topic/47161-artificial-intelligence-bot-path-finding/ ?

Might want to give credit.

I will/have updated the main post.

True, I did draw inspiration and stringregexp from toady, but a breadth first search algorithm with unlimited edges is a world of difference to a star with heuristics and limited edges.

In any case I do owe credit to toady.

[Manadar]

I will/have updated the main post.

True, I did draw inspiration and stringregexp from toady, but a breadth first search algorithm with unlimited edges is a world of difference to a star with heuristics and limited edges.

In any case I do owe credit to toady.

I hear you and I agree. There are lots of changes in your script, but the likeness between your code and toady was quite apparent. I didn't actually compare number of lines or anything like that, so I had no idea how much there is actually alike. On behalf of toady, I thank you. 8) Maybe a link to his A* topic would both serve toady and anyone else looking for path finding algorithms.

[twitchyliquid64]

I hear you and I agree. There are lots of changes in your script, but the likeness between your code and toady was quite apparent. I didn't actually compare number of lines or anything like that, so I had no idea how much there is actually alike. On behalf of toady, I thank you. 8) Maybe a link to his A* topic would both serve toady and anyone else looking for path finding algorithms.

Yea a link would help others lookin for path finding mechanisms.

Toadys A* is alot better for geometric purposes, cause it allows heuristics to influence the order of searching nodes, increasing speed.

However, you can only have max 8 neighbours and it only works when there are geometry relations, so its not good for dynamic things like networking.

Thats why I made this script; To develop my P2P UDF into an onion router.

(FULL STOP =])