Sign in to follow this  
Followers 0
jackyyll

Shortest path in graph

1 post in this topic

#1 ·  Posted (edited)

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

[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:

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:

#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 :D

Any help/ideas is very appreciated.

Thanks :D

Edited by jackyyll

Share this post


Link to post
Share on other sites



Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0