Sign in to follow this  
Followers 0
moviemadnessman

Determining Trees With Autoit

16 posts in this topic

#1 ·  Posted (edited)

Hi. My friend wants me to make him a program where he enters a string of number pairs, and it will tell him if it makes a valid tree graph or not. I've included a picture of a valid and invalid input, just to show an example.untitled.zip

I gather there cannot be any cycles, since you can only go through a prticular block one time. Entering the number string 1 2 2 3 3 5 5 2, for example, would make the whole thing not a tree, as you would have a loop through 2->3->5 and back to 2. Likewise, each number can only go to one other number. My thinking was to make a GUI requesting the input, then potentially make use of arrays of some sort to make sure each number only goes to one place and there are no cycles, however, I can't say I understand AutoIT enough to do that, so any help would be appreciated.

It's for some puzzle game or something that he has, and he hopes to use this to maximize his path through it, since you can't backtrack to any place you have already been. Don't remember the game.

[EDIT] The spaces are necessary to correctly identify between the numbers and the pairs, since the numbers are between 1 and 999.

Edited by moviemadnessman

Share this post


Link to post
Share on other sites



Hi. My friend wants me to make him a program where he enters a string of number pairs, and it will tell him if it makes a valid tree graph or not. I've included a picture of a valid and invalid input, just to show an example.untitled.zip

I gather there cannot be any cycles, since you can only go through a prticular block one time. Entering the number string 1 2 2 3 3 5 5 2, for example, would make the whole thing not a tree, as you would have a loop through 2->3->5 and back to 2. Likewise, each number can only go to one other number. My thinking was to make a GUI requesting the input, then potentially make use of arrays of some sort to make sure each number only goes to one place and there are no cycles, however, I can't say I understand AutoIT enough to do that, so any help would be appreciated.

It's for some puzzle game or something that he has, and he hopes to use this to maximize his path through it, since you can't backtrack to any place you have already been. Don't remember the game.

[EDIT] The spaces are necessary to correctly identify between the numbers and the pairs, since the numbers are between 1 and 999.

I don't get it. Any node you reuse makes it invalid, so can't you just test every new destination to see if it has been used before? Is that all there is to it?

:think:


Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law

Share this post


Link to post
Share on other sites

I don't get it. Any node you reuse makes it invalid, so can't you just test every new destination to see if it has been used before? Is that all there is to it?

:think:

The problem is that the destination can be used multiple times, but there can't be any loop arounds. Like, I could use the numbers 1-9 and have all the pairs go to 4, for example. I don't know how to explain what I'm looking for...the picture might help show the idea a little better, because I don't know how to convey the idea correctly.

I haven't actually seen this game; the picture that is attached is one they sent me. I know it could be done, but I'm not sure how.

Share this post


Link to post
Share on other sites

#4 ·  Posted (edited)

Personally, If you want to post pictures I would goto www.imageshack.us and upload them there, then use the IMG tags in your post.

If I have to download a zip file and then open the picture... I'll be a lot less likely to want to bother looking at it. But maybe that is just me and I'm lazy.

Edited by Simucal

AutoIt Scripts:Aimbot: Proof of Concept - PixelSearching Aimbot with several search/autoshoot/lock-on techniques.Sliding Toolbar - Add a nice Sliding Toolbar to your next script. Click the link to see an animation of it in action!FontInfo UDF - Get list of system fonts, or search to see if a particular font is installed.Get Extended Property UDF - Retrieve a files extended properties (e.g., video/image dimensions, file version, bitrate of song/video, etc)

Share this post


Link to post
Share on other sites

#5 ·  Posted (edited)

The problem is that the destination can be used multiple times, but there can't be any loop arounds. Like, I could use the numbers 1-9 and have all the pairs go to 4, for example. I don't know how to explain what I'm looking for...the picture might help show the idea a little better, because I don't know how to convey the idea correctly.

I haven't actually seen this game; the picture that is attached is one they sent me. I know it could be done, but I'm not sure how.

I looked at your diagram (next time just post it as a gif or jpg, a zipped bmp is a pain). First thing I notice is the input does not define the 'tree' structure, only movement through it. Second thing is that the input does not show all steps, so the program has to determine the route for itself. This all means that the 'tree' is predefined somehow. Can you post that?

If you contend the 'tree' is not predefined, but to be determined from the input, then how are you supposed to know from the sequence "3 5 6" that you have to go through node 2 to get from 5 to 6 (which is against the arrows of directionality, btw)?

The "trees" and sequences given:

4
               |
               |
               v   
   3 --> 5 --> 2 --> 7
         ^   ^
         |   |
         |   |
         1   6

Input = "3 5 6 2 5 2 1 5 4 2 7 2"
Output = "Tree"

3 <---------+
         ^         |
         |         |
         |         |
   1 --> 2 --> 4 --> 6
               |     ^
               |     |
               v     |
               5 ----+

Input = "1 2 5 6 2 3 6 3 4 5 2 4 4 6"
Output = "Not a tree"

Obviously, I'm not a programmer, so maybe I'm missing some beutiful "Tree Theory Logic" here...

:think:

Edited by PsaltyDS

Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law

Share this post


Link to post
Share on other sites

If i understand the picture correctly it's just about 3->5, 6->2... and not 3->5->6->2->5...! So no number is allowed as "starting point" more than once... But that sounds too easy...

Look what i mean:

Working example: 3 5 6 2 5 2 1 5 4 2 7 2

This would be 6 pairs: (3->5, 6->2, 5->2, 1->5, 4->2, 7->2)

Non-Working example: 1 2 5 6 2 3 6 3 4 5 2 4 4 6

This would be 7 pairs: (1->2, 5->6, 2->3, 6->3, 4->5, 2->4, 4->6)

So on the red and on the orange position we have the errors, because the same number is used twice. So you would only need to check if a number is on the first spot more than once... :(

If missed something here - please don't blame me... It's been a really long working day for me - just ignore me then... :)

BTW: What kind of game could that be? :think:

MattHouston

Share this post


Link to post
Share on other sites

#7 ·  Posted (edited)

I looked at your diagram (next time just post it as a gif or jpg, a zipped bmp is a pain).

My bad. I'll remember for next time.

First thing I notice is the input does not define the 'tree' structure, only movement through it. Second thing is that the input does not show all steps, so the program has to determine the route for itself. This all means that the 'tree' is predefined somehow. Can you post that?

The tree is not pre defined.

If you contend the 'tree' is not predefined, but to be determined from the input, then how are you supposed to know from the sequence "3 5 6" that you have to go through node 2 to get from 5 to 6 (which is against the arrows of directionality, btw)?

The "trees" and sequences given:

4
               |
               |
               v   
   3 --> 5 --> 2 --> 7
         ^   ^
         |   |
         |   |
         1   6

Input = "3 5 6 2 5 2 1 5 4 2 7 2"
Output = "Tree"

3 <---------+
         ^         |
         |         |
         |         |
   1 --> 2 --> 4 --> 6
               |     ^
               |     |
               v     |
               5 ----+

Input = "1 2 5 6 2 3 6 3 4 5 2 4 4 6"
Output = "Not a tree"

Obviously, I'm not a programmer, so maybe I'm missing some beutiful "Tree Theory Logic" here...

:think:

Well, in the case of knowing from the sequence "3 5 6" that you have to go through node 2 to get from 5 to 6, it would be written 3 5 5 2 2 6. Thus, it would know to go through node 2 to reach node 6 from node 5.

If i understand the picture correctly it's just about 3->5, 6->2... and not 3->5->6->2->5...! So no number is allowed as "starting point" more than once... But that sounds too easy...

No, that's correct. The numbers are entered in a long chain, but read as pairs.

Look what i mean:

Working example: 3 5 6 2 5 2 1 5 4 2 7 2

This would be 6 pairs: (3->5, 6->2, 5->2, 1->5, 4->2, 7->2)

Non-Working example: 1 2 5 6 2 3 6 3 4 5 2 4 4 6

This would be 7 pairs: (1->2, 5->6, 2->3, 6->3, 4->5, 2->4, 4->6)

So on the red and on the orange position we have the errors, because the same number is used twice. So you would only need to check if a number is on the first spot more than once... :)

If missed something here - please don't blame me... It's been a really long working day for me - just ignore me then... ;)

BTW: What kind of game could that be? :(

MattHouston

Basically, I can't figure out how to get AutoIT to determine if the starting number has been used multiple times. The idea of the tree is that you can enter 5 or 5000 pairs, and there will only be one possible route through all the numbers; no choice, in other words. If there is a choice in paths, then it is not a tree.

As to what type of game it is, I have no real knowledge of it myself. But the concept would be the same as say a haunted house, where there is only 1 way through the house.

Ah, the joys of programming for a person 3,000 miles away. Nothing like it...

Edited by moviemadnessman

Share this post


Link to post
Share on other sites

#8 ·  Posted (edited)

Getting closer. This version produces a list of limbs of the tree, and a list of nodes that include connected nodes. Just need to put it together for loop detection. :think:

; TreeDetect.au3
;
; Tree or Loop?
;   The input is a long string of node ID pairs.
;   Node IDs are space delimited, pairs are also space delimited.
;   Node pairs define limbs
;   Output is either "Tree" or "Not a tree", base on if the limbs form a loop or not.

#include<array.au3>

$Input_1 = "3 5 6 2 5 2 1 5 4 2 7 2"; Should be a tree
$Input_2 = "1 2 5 6 2 3 6 3 4 5 2 4 4 6"; Should not be a tree (contains a loop)

_TreeDetect($Input_1)

_TreeDetect($Input_2)

Func _TreeDetect($sInput)
; Split input string into array and test for valid pairs
;   $avPoints[0] = count of points
    Local $avPoints = StringSplit($sInput, " ")
    If $avPoints[0] < 2 Or Mod($avPoints[0], 2) <> 0 Then
        MsgBox(16, "Tree Detect", "Error: Input string too short or has odd number of elements!"
        Return 0
    EndIf
    
;Create list of unique nodes from the input points
;   $avNodes[0] = count of unique nodes
;   [$n] = node ID
    Local $avNodes[2]
    $avNodes[0] = 1
    $avNodes[1] = $avPoints[1]
    For $p = 2 To $avPoints[0]
        For $n = 1 To $avNodes[0]
            If $avPoints[$p] = $avNodes[$n] Then ContinueLoop 2
        Next
        _ArrayAdd($avNodes, $avPoints[$p])
        $avNodes[0] = UBound($avNodes) - 1
    Next
    
; Put pairs of points into 2D arrays of Limbs
;   $avLimbs[0][0] = count of pairs
;   [n][0] = 'from' node id
;   [n][1] = 'to' node id
    Local $avLimbs[ ($avPoints[0] / 2) + 1][2]
    $avLimbs[0][0] = UBound($avLimbs) - 1
    For $n = 1 To $avLimbs[0][0]
        $avLimbs[$n][0] = $avPoints[ ($n * 2) - 1]
        $avLimbs[$n][1] = $avPoints[$n * 2]
    Next
    
; Display resulting limbs
    Local $sMsg = "Result: " & $avLimbs[0][0] & " input limbs:"
    For $n = 1 To $avLimbs[0][0]
        $sMsg = $sMsg & @CRLF & @TAB & "From " & $avLimbs[$n][0] & " to " & $avLimbs[$n][1]
    Next
    MsgBox(64, "Tree Detect", $sMsg)
    
; Create tree map listing all known paths from each node
;   $avTreeMap[0][0] = count of mapped nodes
;   [n][0] = node id
;   [n][1] = "Node_1,Node_2,...,Node_n" list of connected nodes
    Local $avTreeMap[$avNodes[0] + 1][2]
    $avTreeMap[0][0] = $avNodes[0]
    For $n = 1 To $avTreeMap[0][0]
        $avTreeMap[$n][0] = $avNodes[$n]
        $avTreeMap[$n][1] = ""
        For $l = 1 To $avLimbs[0][0]
            If $avTreeMap[$n][0] = $avLimbs[$l][0] Then
                If Not StringInStr($avTreeMap[$n][1], $avLimbs[$l][1]) Then
                    $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avLimbs[$l][1]
                EndIf
            Else
                If $avTreeMap[$n][0] = $avLimbs[$l][1] Then
                    If Not StringInStr($avTreeMap[$n][1], $avLimbs[$l][0]) Then
                        $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avLimbs[$l][0]
                    EndIf
                EndIf
            EndIf
            If StringLeft($avTreeMap[$n][1], 1) = "," Then $avTreeMap[$n][1] = StringTrimLeft($avTreeMap[$n][1], 1)
        Next
    Next
    
; Display resulting tree map
    $sMsg = "Resulting tree map:"
    For $n = 1 To $avTreeMap[0][0]
        $sMsg = $sMsg & @TAB & @CRLF & "Node ID: " & $avTreeMap[$n][0] & "  Connected nodes: " & $avTreeMap[$n][1]
    Next
    MsgBox(64, "Tree Detect", $sMsg)
    
EndFunc  ;==>_TreeDetect
Edited by PsaltyDS

Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law

Share this post


Link to post
Share on other sites

Getting closer. This version produces a list of limbs of the tree, and a list of nodes that includes connected nodes. Just need to put it together for loop detection. :think:

Oops. Meant to edit and update the demo script in parent and replaced it instead. Anyway, arrived at new assumptions and tweaked the script. It seems now the input strings could not have come from a player path through a game, or a mouse-bot wandering a maze. Stopped looking for paths in the input string and only used them to define the limbs.

Still work'n it... (good educational drill for me)

:(


Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law

Share this post


Link to post
Share on other sites

Aha!

Came to me while walking the dog... :(

If it is a tree, then utimately all branches end in a dead end. So once I have my $avTreeMap array, I just need to recursively prune dead-end limbs until there are no limbs left, or there are only limbs that are not dead ends. At that point the only limbs left form (at least one) loop.

Code attempt coming... :think:


Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law

Share this post


Link to post
Share on other sites

Aha!

Came to me while walking the dog... :(

If it is a tree, then utimately all branches end in a dead end. So once I have my $avTreeMap array, I just need to recursively prune dead-end limbs until there are no limbs left, or there are only limbs that are not dead ends. At that point the only limbs left form (at least one) loop.

Code attempt coming... :think:

Tested the current existing code...it is very close to what I need. I think this step will, ultimately, end up being the breakthrough. While it is cool to actually see the tree, adding the pruning code to determine what, if any, loops occur will allow the program to also tell the user if the number pairs are a successful tree or not a successful tree. I'll also probably add a small GUI so that the user can enter the number combinations themselves, as well as giving them the option to turn off the visual tree if they so desire not to see it.

Thanks you greatly for your help...the arrays were definately throwing me off. Glad that you are using this as a learning experiance as well, and I can't wait to see the finished product. I'm sure my friend will appreciate your help as much as I do.

Share this post


Link to post
Share on other sites

#12 ·  Posted (edited)

EDIT: Nope, this was not the answer as I focused to much on the img and not enough on the text. Would have to detected closed loops in the given number sequence, to be correct.

If I understod your explanation, in the pictur, then your are not alowed to use a note as a starting point more than once (as in and point to another node twice). So basicaly all you have to do is to make a assosiative array and count occurances of a starting node?

Local $dataErr = "1 2 5 6 2 3 6 3 4 5 2 4 4 6"
Local $dataOK = "3 5 6 2 5 2 1 5 4 2 7 2"

TreeTest($dataErr)
TreeTest($dataOK)
exit

Func TreeTest($data)
   Local $arrFoo = TreeValidator($data)
   if $arrFoo[0] > 0 then 
      ConsoleWrite('NOT A TREE: $data:=' & $data & @LF)
   Else
      ConsoleWrite('IS  A TREE: $data:=' & $data & @LF)
   Endif
EndFunc 

Func TreeValidator($data)
; $data is pattern of type <start> <to> <start> <to> <start> <to>
   $arrData = StringSplit($data, " ")
   Local $arrTree[9999]; making 9999 the node limit, Culd optimise with some kind of sparse array
   Local $arrFailingNodes[100]
   Local $i
   For $i = 1 to $arrData[0] Step 2
      ConsoleWrite($arrData[$i] & @LF)
      $arrTree[$arrData[$i]] += 1
      If $arrTree[$arrData[$i]] > 1 then 
         ConsoleWrite("Failing node " & $arrData[$i] & " count:=" & $arrTree[$arrData[$i]] & @LF)
         $arrFailingNodes[0] += 1
;TODO Check and handel array overflow (grow if nescasarry)
         $arrFailingNodes[$arrFailingNodes[0]] = $arrData[$i]
      EndIf
   Next
   Redim $arrFailingNodes[$arrFailingNodes[0] + 1]
   Return $arrFailingNodes
EndFunc

Probably not exactly what you wanted, but I'l make it my contribution :think:

Edited by Uten

Share this post


Link to post
Share on other sites

EDIT: Nope, this was not the answer as I focused to much on the img and not enough on the text. Would have to detected closed loops in the given number sequence, to be correct.

If I understod your explanation, in the pictur, then your are not alowed to use a note as a starting point more than once (as in and point to another node twice). So basicaly all you have to do is to make a assosiative array and count occurances of a starting node?

Local $dataErr = "1 2 5 6 2 3 6 3 4 5 2 4 4 6"
Local $dataOK = "3 5 6 2 5 2 1 5 4 2 7 2"

TreeTest($dataErr)
TreeTest($dataOK)
exit

Func TreeTest($data)
   Local $arrFoo = TreeValidator($data)
   if $arrFoo[0] > 0 then 
      ConsoleWrite('NOT A TREE: $data:=' & $data & @LF)
   Else
      ConsoleWrite('IS  A TREE: $data:=' & $data & @LF)
   Endif
EndFunc 

Func TreeValidator($data)
; $data is pattern of type <start> <to> <start> <to> <start> <to>
   $arrData = StringSplit($data, " ")
   Local $arrTree[9999]; making 9999 the node limit, Culd optimise with some kind of sparse array
   Local $arrFailingNodes[100]
   Local $i
   For $i = 1 to $arrData[0] Step 2
      ConsoleWrite($arrData[$i] & @LF)
      $arrTree[$arrData[$i]] += 1
      If $arrTree[$arrData[$i]] > 1 then 
         ConsoleWrite("Failing node " & $arrData[$i] & " count:=" & $arrTree[$arrData[$i]] & @LF)
         $arrFailingNodes[0] += 1
;TODO Check and handel array overflow (grow if nescasarry)
         $arrFailingNodes[$arrFailingNodes[0]] = $arrData[$i]
      EndIf
   Next
   Redim $arrFailingNodes[$arrFailingNodes[0] + 1]
   Return $arrFailingNodes
EndFunc

Probably not exactly what you wanted, but I'l make it my contribution :think:

I can't confirm or deny anything regarding your code. When I run it on my machine, nothing happens.

Share this post


Link to post
Share on other sites

#14 ·  Posted

I can't confirm or deny anything regarding your code. When I run it on my machine, nothing happens.

What do you mean "nothing happens". It does not flash and beep if thats what your after :think:

Any how, as I wrote in my edit of the first attempt it would not cut it. Have been sleeping on it now and here is the second atempt. It will probably flash and beep :(

WARNING: It is not clever or optimized.

This is how it works:

1: Create a array with all starting nodes. Each starting node points to one or more nodes.

2: In the data array find starting nodes pointing to two or more nodes (we have two or more walking paths to follow)

3: When a node is found wallk all its paths, record all nodes we pass on the way.

4: In the resulting recording of passed nodes check if we pass any of them more than once.

#include <Array.au3>
Local $dataErr = "1 2 5 6 2 3 6 3 4 5 2 4 4 6"
Local $dataOK = "3 5 6 2 5 2 1 5 4 2 7 2"
ConsoleWrite("=== EXPECT 2 and 4 ===" & @LF)
Local $arrData = MakeStructure($dataErr)
TreeCheck($arrData)
;DataDump($arrData)
ConsoleWrite("=== EXPECT NONE ===" & @LF)
Local $arrData = MakeStructure($dataOK)
TreeCheck($arrData)
;DataDump($arrData)
;TreeTest($dataOK)
exit

Func MakeStructure($data, $delimiter = " ")
   local $arrData = StringSplit($data, $delimiter) 
   local $arrM[10000][10]; BIG and UGLY 9999 and 0 [?][0] = counter, [?][...] = node pointers
   local $i
   For $i = 1 to $arrData[0] Step 2
      $arrM[$arrData[$i]][0] += 1
      $arrM[$arrData[$i]][$arrM[$arrData[$i]][0]] = $arrData[$i + 1]
   Next
   Return $arrM
EndFunc 

Func TreeCheck(ByRef $arrData)
   Local $i
   For $i = 1 to UBound($arrData) -1 
      if $arrData[$i][0] > 1 Then 
         ConsoleWrite("Walking: " & $i & " : " )
         $pasedNodes = TreeWalk($arrData, $i) & " "
         ConsoleWrite("$pasedNodes:=" & $pasedNodes & @LF)
         Local $arrFoo = StringSplit($pasedNodes, " ")
         for $foo = 1 to $arrFoo[0]
            If StringInStr($pasedNodes, " " & $arrFoo[$foo] & " ",0,2) Then 
               ConsoleWrite("CYCLIC: $nodeID:=" & $i & " : " & $pasedNodes & @LF)
               Beep()
               msgbox(16, "WARNING CYCLIC NODE: $nodeID:=" & $i, "Passed nodes on walk: " & $pasedNodes & @LF)
               ExitLoop
            EndIf
         Next 
      EndIf
   Next 
EndFunc 

Func TreeWalk(ByRef $arrData, $nodeID)
   Local $i 
   Local $ret
   For $i = 1 to $arrData[$nodeID][0]
      $ret = $ret & " " & $arrData[$nodeID][$i]
      if $arrData[$arrData[$nodeID][$i]][0] > 1 Then 
        ; TODO: Could end up in never ending loop
         $ret = $ret & TreeWalk($arrData, $arrData[$nodeID][$i])
      Else 
         $ret = $ret & " " & $arrData[$arrData[$nodeID][$i]][1]
      EndIf
   Next 
   Return $ret
EndFunc

Func ArrayDump($arr, $header = "ArrayDump")
   Local $i, $ii
   
   for $i = 0 to Ubound($arr) - 1
      if $arr[$i][0] <> 0 then 
         ConsoleWrite($i & "(" & $arr[$i][0] & ") : ")
         for $ii = 1 to 9
            if NOT $arr[$i][$ii] Then ExitLoop
            ConsoleWrite(" " & $arr[$i][$ii])
         Next
         ConsoleWrite(@LF)
      endif
   Next 
EndFunc

Share this post


Link to post
Share on other sites

#15 ·  Posted

OK, I have not been able to work on this for a few days, but it has been a worthwhile learning exercise and I'm back at it. Here is what I have so far. It works with the inputs provided, and detects loops pretty quickly. The next thing to do is simplify it (probably could use single dimension arrays throughout, to begin with), but it is fully functional now. I looked at the discussion of "walking the tree", but I don't think that is required, and is bound to be slower if the node count is really high.

My solution went this way:

1. Split input string into node ID pairs.

2. Create a table of unique node IDs.

3. For each node ID, create a list of other nodes connected to it.

4. Any node ID with only one other node connected is a "deadend", and gets pruned out.

5. Repeat above pruning until:

a. No node pairs are left - means no loop, or

b. There are node pairs left, but no more deadends - means one or more loops

The node IDs, BTW, do not have to be nubers, but the original post specified they are space delimited and must be in pairs.

This is my current LoopDetect.au3:

;==============================================================================
; LoopDetect.au3
;
; Version 1.0 dated 04 May, 2006
; By PsaltyDS at the AutoIT3 Support Forum
;
; Loop Detector Exercise
;    The input is a long string of node ID pairs.
;    Node IDs are space delimited, pairs are not delimited.
;    Node pairs define limbs.
;     Limbs are not necesarily in order, and may or may not form a single tree.
;    Purpose is to determine if the limbs form a loop or not.
;==============================================================================

#include<array.au3>

;==============================================================================
; This section provides test inputs to the _LoopDetect() function
;==============================================================================
Dim $InputArray[1]

; Just add more _ArrayAdd() lines to try more inputs
_ArrayAdd($InputArray, "3 5 6 2 5 2 1 5 4 2 7 2"); Should be a tree
_ArrayAdd($InputArray, "1 2 5 6 2 3 6 3 4 5 2 4 4 6"); Should not be a tree (contains a loop)
$InputArray[0] = UBound($InputArray) - 1

For $In = 1 To $InputArray[0]
    If _LoopDetect($InputArray[$In]) Then
        $TreeMsg = "At least one loop detected in the following string!"
    Else
        $TreeMsg = "No loop present in the following string."
    EndIf
    MsgBox(64, "Tree Detection Complete", $TreeMsg & @CRLF & _
            "Input string was: " & $InputArray[$In])
Next
;==============================================================================


;========================================================
; Function _LoopDetect($sInput)
;   Receives a string of node ID pairs, space delimited
;   Returns 1 for a loop detected or 0 for no loop
;========================================================
Func _LoopDetect($sInput)
; Split input string into array and test for valid pairs
;    $avPoints[0] = count of points
    Local $avPoints = StringSplit($sInput, " ")
    If $avPoints[0] < 2 Or Mod($avPoints[0], 2) <> 0 Then
        MsgBox(16, "Tree Detect", "Error: Input string too short or has odd number of elements!")
        Return 0
    EndIf
    
;Create list of unique nodes from the input points
;    $avNodes[0] = count of unique nodes
;    [$n] = node ID
    Local $avNodes[2]
    $avNodes[0] = 1
    $avNodes[1] = $avPoints[1]
    For $p = 2 To $avPoints[0]
        For $n = 1 To $avNodes[0]
            If $avPoints[$p] = $avNodes[$n] Then ContinueLoop 2
        Next
        _ArrayAdd($avNodes, $avPoints[$p])
        $avNodes[0] = UBound($avNodes) - 1
    Next
    
; Put pairs of points into 2D arrays of Limbs
;    $avLimbs[0][0] = count of pairs
;    [n][0] = 'from' node id
;   [n][1] = 'to' node id
    Local $avLimbs[ ($avPoints[0] / 2) + 1][2]
    $avLimbs[0][0] = UBound($avLimbs) - 1
    For $n = 1 To $avLimbs[0][0]
        $avLimbs[$n][0] = $avPoints[ ($n * 2) - 1]
        $avLimbs[$n][1] = $avPoints[$n * 2]
    Next
    
; Create tree map listing all known paths from each node
;    $avTreeMap[0][0] = count of mapped nodes
;   [n][0] = node id
;   [n][1] = "Node_1,Node_2, ..., Node_n" list of connected nodes, comma delimited
    Local $avTreeMap[$avNodes[0] + 1][2]
    $avTreeMap[0][0] = $avNodes[0]
    For $n = 1 To $avTreeMap[0][0]
        $avTreeMap[$n][0] = $avNodes[$n]
        $avTreeMap[$n][1] = ""
        For $l = 1 To $avLimbs[0][0]
            If $avTreeMap[$n][0] = $avLimbs[$l][0] Then
                If Not StringInStr($avTreeMap[$n][1], $avLimbs[$l][1]) Then
                    $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avLimbs[$l][1]
                EndIf
            Else
                If $avTreeMap[$n][0] = $avLimbs[$l][1] Then
                    If Not StringInStr($avTreeMap[$n][1], $avLimbs[$l][0]) Then
                        $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avLimbs[$l][0]
                    EndIf
                EndIf
            EndIf
            If StringLeft($avTreeMap[$n][1], 1) = "," Then $avTreeMap[$n][1] = StringTrimLeft($avTreeMap[$n][1], 1)
        Next
    Next
    
; This while loop continues until no deadends are left or no nodes are left
    While 1
    ; Remove limbs with only 1 connecting node (deadends)
    ;   $avTreeMap[0][1] will hold cound of non-deadend limbs
        Local $iDeadEnd = 0
        $avTreeMap[0][1] = $avTreeMap[0][0]
        For $l = 1 To $avTreeMap[0][0]
            Local $avNodes = StringSplit($avTreeMap[$l][1], ",")
            If $avNodes[0] < 2 Then
            ; Deadend limb found, $avTreeMap[$l][0] is the deadend node
            ; The other end's node is in $avTreeMap [$l][1]
                $iDeadEnd = 1
            ;   Need to search for the other node ID and remove the deadend node from its list
                For $n = 1 To $avTreeMap[0][0]
                    If $avTreeMap[$n][0] = $avTreeMap[$l][1] Then
                    ; Remove the deadend node from the list for this node
                        $avNodes = StringSplit($avTreeMap[$n][1], ",")
                        $avTreeMap[$n][1] = ""
                        If $avNodes[0] > 1 Then
                            For $x = 1 To $avNodes[0]
                                If $avNodes[$x] <> $avTreeMap[$l][0] Then
                                    If $avTreeMap[$n][1] = "" Then
                                        $avTreeMap[$n][1] = $avNodes[$x]
                                    Else
                                        $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avNodes[$x]
                                    EndIf
                                EndIf
                            Next
                        EndIf
                        ExitLoop
                    EndIf
                Next
            ; Null the entries for the deadend node
                $avTreeMap[$l][0] = ""
                $avTreeMap[$l][1] = ""
            ; Reduce the count of non-deadends
                $avTreeMap[0][1] = $avTreeMap[0][1] - 1
            EndIf
        Next
        
    ; Test for done, if there are no nodes left, then no loops
        If $avTreeMap[0][1] = 0 Then Return 0
        
    ; Test for done, there are nodes left, if no deadends were found, there is at least one loop
        If $iDeadEnd = 0 Then Return 1
        
    ; Not done, delete null (pruned) entries from the table
        Local $avInterim[$avTreeMap[0][1] + 1][2]
        $avInterim[0][0] = $avTreeMap[0][1]
        $x = 1
        For $n = 1 To $avTreeMap[0][0]
            If $avTreeMap[$n][0] <> "" Then
                $avInterim[$x][0] = $avTreeMap[$n][0]
                $avInterim[$x][1] = $avTreeMap[$n][1]
                $x = $x + 1
            EndIf
        Next
        $avTreeMap = $avInterim
    WEnd
EndFunc  ;==>_LoopDetect
;========================================================

Trying to learn... :)


Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law

Share this post


Link to post
Share on other sites

#16 ·  Posted

OK, I have not been able to work on this for a few days, but it has been a worthwhile learning exercise and I'm back at it. Here is what I have so far. It works with the inputs provided, and detects loops pretty quickly. The next thing to do is simplify it (probably could use single dimension arrays throughout, to begin with), but it is fully functional now. I looked at the discussion of "walking the tree", but I don't think that is required, and is bound to be slower if the node count is really high.

My solution went this way:

1. Split input string into node ID pairs.

2. Create a table of unique node IDs.

3. For each node ID, create a list of other nodes connected to it.

4. Any node ID with only one other node connected is a "deadend", and gets pruned out.

5. Repeat above pruning until:

a. No node pairs are left - means no loop, or

b. There are node pairs left, but no more deadends - means one or more loops

The node IDs, BTW, do not have to be nubers, but the original post specified they are space delimited and must be in pairs.

This is my current LoopDetect.au3:

;==============================================================================
; LoopDetect.au3
;
; Version 1.0 dated 04 May, 2006
; By PsaltyDS at the AutoIT3 Support Forum
;
; Loop Detector Exercise
;    The input is a long string of node ID pairs.
;    Node IDs are space delimited, pairs are not delimited.
;    Node pairs define limbs.
;     Limbs are not necesarily in order, and may or may not form a single tree.
;    Purpose is to determine if the limbs form a loop or not.
;==============================================================================

#include<array.au3>

;==============================================================================
; This section provides test inputs to the _LoopDetect() function
;==============================================================================
Dim $InputArray[1]

; Just add more _ArrayAdd() lines to try more inputs
_ArrayAdd($InputArray, "3 5 6 2 5 2 1 5 4 2 7 2"); Should be a tree
_ArrayAdd($InputArray, "1 2 5 6 2 3 6 3 4 5 2 4 4 6"); Should not be a tree (contains a loop)
$InputArray[0] = UBound($InputArray) - 1

For $In = 1 To $InputArray[0]
    If _LoopDetect($InputArray[$In]) Then
        $TreeMsg = "At least one loop detected in the following string!"
    Else
        $TreeMsg = "No loop present in the following string."
    EndIf
    MsgBox(64, "Tree Detection Complete", $TreeMsg & @CRLF & _
            "Input string was: " & $InputArray[$In])
Next
;==============================================================================
;========================================================
; Function _LoopDetect($sInput)
;   Receives a string of node ID pairs, space delimited
;   Returns 1 for a loop detected or 0 for no loop
;========================================================
Func _LoopDetect($sInput)
; Split input string into array and test for valid pairs
;    $avPoints[0] = count of points
    Local $avPoints = StringSplit($sInput, " ")
    If $avPoints[0] < 2 Or Mod($avPoints[0], 2) <> 0 Then
        MsgBox(16, "Tree Detect", "Error: Input string too short or has odd number of elements!")
        Return 0
    EndIf
    
;Create list of unique nodes from the input points
;    $avNodes[0] = count of unique nodes
;    [$n] = node ID
    Local $avNodes[2]
    $avNodes[0] = 1
    $avNodes[1] = $avPoints[1]
    For $p = 2 To $avPoints[0]
        For $n = 1 To $avNodes[0]
            If $avPoints[$p] = $avNodes[$n] Then ContinueLoop 2
        Next
        _ArrayAdd($avNodes, $avPoints[$p])
        $avNodes[0] = UBound($avNodes) - 1
    Next
    
; Put pairs of points into 2D arrays of Limbs
;    $avLimbs[0][0] = count of pairs
;    [n][0] = 'from' node id
;   [n][1] = 'to' node id
    Local $avLimbs[ ($avPoints[0] / 2) + 1][2]
    $avLimbs[0][0] = UBound($avLimbs) - 1
    For $n = 1 To $avLimbs[0][0]
        $avLimbs[$n][0] = $avPoints[ ($n * 2) - 1]
        $avLimbs[$n][1] = $avPoints[$n * 2]
    Next
    
; Create tree map listing all known paths from each node
;    $avTreeMap[0][0] = count of mapped nodes
;   [n][0] = node id
;   [n][1] = "Node_1,Node_2, ..., Node_n" list of connected nodes, comma delimited
    Local $avTreeMap[$avNodes[0] + 1][2]
    $avTreeMap[0][0] = $avNodes[0]
    For $n = 1 To $avTreeMap[0][0]
        $avTreeMap[$n][0] = $avNodes[$n]
        $avTreeMap[$n][1] = ""
        For $l = 1 To $avLimbs[0][0]
            If $avTreeMap[$n][0] = $avLimbs[$l][0] Then
                If Not StringInStr($avTreeMap[$n][1], $avLimbs[$l][1]) Then
                    $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avLimbs[$l][1]
                EndIf
            Else
                If $avTreeMap[$n][0] = $avLimbs[$l][1] Then
                    If Not StringInStr($avTreeMap[$n][1], $avLimbs[$l][0]) Then
                        $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avLimbs[$l][0]
                    EndIf
                EndIf
            EndIf
            If StringLeft($avTreeMap[$n][1], 1) = "," Then $avTreeMap[$n][1] = StringTrimLeft($avTreeMap[$n][1], 1)
        Next
    Next
    
; This while loop continues until no deadends are left or no nodes are left
    While 1
; Remove limbs with only 1 connecting node (deadends)
;   $avTreeMap[0][1] will hold cound of non-deadend limbs
        Local $iDeadEnd = 0
        $avTreeMap[0][1] = $avTreeMap[0][0]
        For $l = 1 To $avTreeMap[0][0]
            Local $avNodes = StringSplit($avTreeMap[$l][1], ",")
            If $avNodes[0] < 2 Then
        ; Deadend limb found, $avTreeMap[$l][0] is the deadend node
        ; The other end's node is in $avTreeMap [$l][1]
                $iDeadEnd = 1
        ;   Need to search for the other node ID and remove the deadend node from its list
                For $n = 1 To $avTreeMap[0][0]
                    If $avTreeMap[$n][0] = $avTreeMap[$l][1] Then
                ; Remove the deadend node from the list for this node
                        $avNodes = StringSplit($avTreeMap[$n][1], ",")
                        $avTreeMap[$n][1] = ""
                        If $avNodes[0] > 1 Then
                            For $x = 1 To $avNodes[0]
                                If $avNodes[$x] <> $avTreeMap[$l][0] Then
                                    If $avTreeMap[$n][1] = "" Then
                                        $avTreeMap[$n][1] = $avNodes[$x]
                                    Else
                                        $avTreeMap[$n][1] = $avTreeMap[$n][1] & "," & $avNodes[$x]
                                    EndIf
                                EndIf
                            Next
                        EndIf
                        ExitLoop
                    EndIf
                Next
        ; Null the entries for the deadend node
                $avTreeMap[$l][0] = ""
                $avTreeMap[$l][1] = ""
        ; Reduce the count of non-deadends
                $avTreeMap[0][1] = $avTreeMap[0][1] - 1
            EndIf
        Next
        
; Test for done, if there are no nodes left, then no loops
        If $avTreeMap[0][1] = 0 Then Return 0
        
; Test for done, there are nodes left, if no deadends were found, there is at least one loop
        If $iDeadEnd = 0 Then Return 1
        
; Not done, delete null (pruned) entries from the table
        Local $avInterim[$avTreeMap[0][1] + 1][2]
        $avInterim[0][0] = $avTreeMap[0][1]
        $x = 1
        For $n = 1 To $avTreeMap[0][0]
            If $avTreeMap[$n][0] <> "" Then
                $avInterim[$x][0] = $avTreeMap[$n][0]
                $avInterim[$x][1] = $avTreeMap[$n][1]
                $x = $x + 1
            EndIf
        Next
        $avTreeMap = $avInterim
    WEnd
EndFunc ;==>_LoopDetect
;========================================================

Trying to learn... :)

That works exactly as it is needed to (except a user input, but that's easy enough to add). Thank you to everyone who helped with this, I hope everyone learned something from it. I know that I'll use this code to furthur understand arrays. Thanks again, guys. And especially PsaltyDS - thank you very much.

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