Shortest path in graph

[jackyyll]

Okay, i have a graph file (Map.ini) that looks like this:

expandcollapse popup

[map1]
Id=100001
Zone=0
Name=Mapname
NodeNum=13
Node0=79,66,100032
Node1=79,72,100000
Node2=102,81,100033
Node3=100,74,100034
Node4=62,79,100031
Node5=81,23,100014
Node6=4,63,100011
Node7=112,75,100030
Node8=61,84,100091
Node9=-1,1,100089
Node10=-1,25,100002
Node11=-1,26,100003
Node12=-1,27,100009

[map2]
Id=100002
Zone=2
Name=name
NodeNum=10
Node0=107,95,100021
Node1=31,26,100058
Node2=84,75,100057
Node3=62,29,100056
Node4=52,85,100060
Node5=19,42,100059
Node6=22,37,100055
Node7=-1,22,100001
Node8=-1,23,100003
Node9=-1,24,100009


---SNIP---

Basically it shows the map, and all other maps(the map id's i.e. 100055) that this map connects to. As you can see, map1 leads to map 2 (100001, 100002) and vice versa. Each node is another map that you can goto from the current map, the first two parameters are coordinates, the last and important one is the map id the node goes to.

I want to find the shortest path between two maps. I've been able to do this in python, but am struggling with translating it into autoit...

This is the python code that i have:

expandcollapse popup

graph = {}

import ConfigParser

cp = ConfigParser.ConfigParser()
cp.readfp (open('Files/map.ini'))
maps = cp.get('Main', 'mapnum')
x = 0
while x <= int(maps)-1:
    id = cp.get("map" + str(x), "Id")
    graph.update({id: []})
    nodenum = cp.get("map" + str(x), "NodeNum")
    i = 0
    while i <= int(nodenum)-1:
        n = cp.get("map" + str(x), "Node" + str(i))
        n_split = n.split(",")
        graph[id].append(str(n_split[2]))
        i = i+1
        
    x = x+1

def find_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if not graph.has_key(start):
        return None
    shortest = None
    for node in graph[start]:
        if node not in path:
            newpath = find_path(graph, node, end, path)
            if newpath:
                if not shortest or len(newpath) < len(shortest):
                    shortest = newpath
    return shortest
    
print find_path(graph, '100001', '100095')

This will output

>>>
['100001', '100009', '100094', '100095']

And this is what i've translated it into:

expandcollapse popup

#include <Array.au3>

Global $Graph = ObjCreate("Scripting.Dictionary")
Global $Path  = _ArrayCreate("")
$mCount = IniRead(@ScriptDir & "\Files\map.ini", "Main", "MapNum", "")

For $i = 0 To $mCount - 1
    $mId = IniRead(@ScriptDir & "\Files\map.ini", "map" & $i, "Id", "")
    $Graph.Add($mId, "")
    
    $nCount = IniRead(@ScriptDir & "\Files\map.ini", "map" & $i, "NodeNum", "")
    For $n = 0 To $nCount - 1
        $Node = IniRead(@ScriptDir & "\Files\map.ini", "map" & $i, "Node" & $n, "")
        $nSplit = StringSplit($Node, ",")
        $Graph.Item($mId) = $Graph.Item($mId) & $nSplit[3] & ","
    Next
Next

Func FindPath($graph, $start, $end)
    _ArrayAdd($Path, $Path & $start)
    If $start == $end Then
        Return $Path
    EndIf
    
    $Shortest = 0
    
    If $graph.Exists($start) Then
        $mNodes = StringSplit($graph.Item($start), ",")
        For $node In $mNodes
            If _ArraySearch($Path, $node) == -1 Then
                $newpath = FindPath($graph, $node, $end)
                If $Shortest == 0 Or Ubound($newpath) < Ubound($Shortest) Then
                    $Shortest = $newpath
                EndIf
            EndIf
        Next
    EndIf
    
    Return $Shortest
EndFunc

ConsoleWrite(FindPath($Graph, 100001, 100095))

But, that's not working out as i hoped

Any help/ideas is very appreciated.

Thanks

Edited April 24, 2008 by jackyyll