Ideas to find a route - (Moved)

[HurleyShanabarger]

I am trying to solve a "routing" problem.

• There is a given amount of gates (valves)
• Each gate either be open or closed
• Each gate is connected to one, two. three or four other gates

With two given gates I would like to know which gates in-between must be opened to have a connection. Not really sure how to approach this - could someone push me in the right direction?

 

I am aware that I could solve this task manually using a truth table, but that would neither be fun nor flexible Smile

Edited February 15, 2022 by HurleyShanabarger

[Jos]

Moved to the appropriate AutoIt General Help and Support forum, as the Developer General Discussion forum very clearly states:

Quote

General development and scripting discussions.

---

Do not create AutoIt-related topics here, use the AutoIt General Help and Support or AutoIt Technical Discussion forums.

Moderation Team

[HurleyShanabarger]

Thanks @Jos. Was not sure about the right place and as my request was without code I thought it might be better placed in the Developer General Discussion.

[Nine]

Could you give the input data of this ?  Or do you need us to figure out how this could be done ?

[HurleyShanabarger]

The input data I have is a drawing, I tried to abstract it.

I don't request someone to solve this for me, but any help is very much appreciated as well as any solution someone might come up with.
 

[Nine]

Ok, if I understand correctly your drawings, the problem was to open gate 1 to gate 8.  So there is 3 possible solutions, right ?

Since there is a bridge between 1 and 2, it means that 6 is linked to 4 gates (1,2,5,7), while you said max links is 3...

[HurleyShanabarger]

You are right, my mistake. I looked at this wrongly, but four gates is the maximum. I corrected this in my first post.

[Nine]

Here a suggestion how to represent the drawings numerically :

1(2,6)
2(1,3,6,8)
3(2,4,7)
4(3,5)
5(4,6)
6(5,7)
7(3,6)
8(2)

So everyone who wishes to play with your riddle can start with the same representation...

Edited February 15, 2022 by Nine
typo / corrected paths

[argumentum]

1 hour ago, HurleyShanabarger said:

The input data I have is a drawing, I tried to abstract it.
I don't request someone to solve this for me, but any help is very much appreciated

is it lemons ? is it car doors ? is it valves in a nuclear station ? is it a hardware or software thing ?
Being vague does not aid helping you. Just state what in real life is you need to get done.

[HurleyShanabarger]

That would be a really interesting car  But you got close, the gates are actually valves in a hydraulic system.

[Nine]

There you go.  That was fun .

#include <Array.au3>

Local $sGates = _
  "1(2,6)" & _
  "2(1,3,6,8)" & _
  "3(2,4,7)" & _
  "4(3,5)" & _
  "5(4,6)" & _
  "6(5,7)" & _
  "7(3,6)" & _
  "8(2)"

Local $aTemp = StringSplit($sGates, ")"), $aArr
Local $aGate[$aTemp[0]][2] = [[$aTemp[0] - 1, 0]]
For $i = 1 to $aTemp[0] - 1
  $aArr = StringSplit($aTemp[$i], "(,", $STR_NOCOUNT)
  $aGate[$i][0] = $aArr[0]
  _ArrayDelete($aArr, 0)
  $aGate[$i][1] = $aArr
Next

OpenGate(1, "1", 8)

Func OpenGate($iStart, $sPath, $iEnd)
  For $i = 0 to UBound($aGate[$iStart][1]) - 1
    If ($aGate[$iStart][1])[$i] = $iEnd Then Return ConsoleWrite($sPath & "|" & $iEnd & @CRLF)
    If StringInStr($sPath, String(($aGate[$iStart][1])[$i])) Then ContinueLoop
    OpenGate(($aGate[$iStart][1])[$i], $sPath & "|" & ($aGate[$iStart][1])[$i], $iEnd)
  Next
EndFunc

I needed to change the links a bit, since 6 cannot send to 1 and 2.  It can receive from 1 and 2, but not send.  Untested with other path than from 1 to 8.  I'll let you play with my riddle now 

[argumentum]

..some of my knowing comes from aviation. Make sure that if an error can create a safety problem, to take measures to attend to that too. Automated systems should include what to default to, or do, in case of failures. So the system may need more than just, send a signal, with the expectancy that what is intended will occur, as it may not behave as expected, outside the lab. with possible real world "oops" . My 2 cents. 

[jchd]

Your problem can be solved by well-known results established by the Graph Theory. Depending on characteristics of your devices/problem, generic solutions and algorithms are likely to apply.

For instance, is the flow of hydraulics between valves oriented in all/some/none of the valves?

Can cycles occur in the graph?

Do you want to get the shortest path between two valves, any path, all possible pathes?

Read on about DAGs, Trees, Forests, simple graphs and you'll learn howto tackle this kind of problem

[HurleyShanabarger]

Thank you all for thje input and your work.

 

12 hours ago, Nine said:

There you go.  That was fun .

I needed to change the links a bit, since 6 cannot send to 1 and 2.  It can receive from 1 and 2, but not send.  Untested with other path than from 1 to 8.  I'll let you play with my riddle now 

Glad that you enjoyed it, and this one approach that also crossed my mind. I will try to understand and adapt this for my porpose.

 

11 hours ago, argumentum said:

..some of my knowing comes from aviation. Make sure that if an error can create a safety problem, to take measures to attend to that too. Automated systems should include what to default to, or do, in case of failures. So the system may need more than just, send a signal, with the expectancy that what is intended will occur, as it may not behave as expected, outside the lab. with possible real world "oops" . My 2 cents. 

Thanks you for pointing this out. Due to covid and part shortage we are currently not able to the new scenarios on real hardware, which would be the pre-validation. Settings/control of valves ist done by and external control. Within a simulation we want to see in which scenarios sensors connected to the system would measure flow/pressure/temperature depending on the valve position. My goal is to determine this exactly by using some scripting apporach. But I will keep the real world "oopsies" in mind and will use any solution only as guide and have it reviewed/triple checked.

 

8 hours ago, jchd said:

Your problem can be solved by well-known results established by the Graph Theory. Depending on characteristics of your devices/problem, generic solutions and algorithms are likely to apply.

For instance, is the flow of hydraulics between valves oriented in all/some/none of the valves?

Can cycles occur in the graph?

Do you want to get the shortest path between two valves, any path, all possible pathes?

Read on about DAGs, Trees, Forests, simple graphs and you'll learn howto tackle this kind of problem

That looks interesting. Not really the kind of theory I like, but sometimes what someones likes and what is required to get the job done are completley different things. Thank you very much.

 

I also gave my simplification some thoughts and realized after the feedback from @argumentum and @jchd, that there is more to it than my simplification provides. Once I figured on how to show this I will share it with you!

[RTFC]

This is just a variant of TSP, see the simulated annealing thread for example code.

Edited February 16, 2022 by RTFC

[HurleyShanabarger]

After Istarted reading about TSP, Simulated Annealing, Graph Theory and Depth first search I found this: https://www.geeksforgeeks.org/find-paths-given-source-destination/
I think it will help to achieve my goal.

Edited February 17, 2022 by HurleyShanabarger