# Thread: A challenging question in Graph - help me find the algo for this

1. ## A challenging question in Graph - help me find the algo for this

I have this directed graph as shown in the figure given below.

All I need to find out is the "loop no" and "shared loop no" represented in the table given under.

I managed to able to extract the "loop no" form the given input but cannot figure out how to extract the "shared loop no"

I have written a code but its very nasty to understand. The code is attached below. I would really appreciate if someone Please help me figure out this. I'm working on this since a week and not able to fix it, please help.

Regards.

Code:
```Sub AutoAssignLoopNo()
Dim IL As Long
Dim JL As Long
Dim KL As Long
Dim Lastrow As Long
Dim AssignLoop As Long
Dim rFind As Range
Dim FindNode As Long
Dim closedNode As Long
Dim pipes() As Long

Rw = 7
IL = 19

'Clearing up  the Range
Worksheets("PipeNetworkData").Activate
Range("D" & Rw + 1 & ":E" & Rw + 1 + IL).Clear

' Pipes between two nodes
On Error Resume Next  ' Subscript out of range error when Node is greater than Line  - in case of branched node
For i = 1 To IL
pipes(Range("B" & Rw + i), Worksheets("PipeNetworkData").Range("C" & Rw + i)) = Worksheets("PipeNetworkData").Range("A" & Rw + i)
Next i

Dim getLowest As Long
Dim ClosedLoopNodeNo() As Long
Dim LoopStartCue() As Long
Dim LoopStartCuePipeNo() As Long
Dim ClosedLoopPipeNo() As Long

AssignLoop = 1
ReDim LoopStartCue(IL)
ReDim ClosedLoopNodeNo(IL)
ReDim LoopStartCuePipeNo(IL)
ReDim ClosedLoopPipeNo(IL)

LSQ = 1
For i = 1 To IL
If Range("B" & i + Rw) > Range("C" & i + Rw) Then
Range("D" & i + Rw).Value = AssignLoop

'|||||||||||||||||||||||||||||||||| ONE TIME RUN ONLY ||||||||||||||||||||||||||||||||||||||||||||
If AssignLoop = 1 Then
ClosedLoopNodeNo(LSQ) = Range("C" & i + Rw) 'added new
ClosedLoopPipeNo(LSQ) = Range("A" & i + Rw) 'added new

Lastrow = Cells(Rows.Count, "D").End(xlUp).Row
matchRow = Lastrow
Do While Range("B" & Lastrow).Value <> Range("C" & matchRow).Value
Worksheets("PipeNetworkData").Range("B" & Lastrow).Select
Lastrow = Lastrow - 1
Loop

Range("D" & Lastrow).Select

LoopStartCue(LSQ) = Range("B" & Lastrow)
LoopStartCuePipeNo(LSQ) = Range("A" & Lastrow)

Range("B" & i + Rw + 1).Select

'check for branched node
cnt = 1
FindAgain:
If Range("C" & i + Rw + cnt).Value = Empty Then GoTo blank2: 'Added new 2
FindNode = Range("C" & i + Rw + cnt).Value

With Range("B8", Cells(Rows.Count, "B"))
Set rFind = .Cells.Find(What:=FindNode, _
LookIn:=xlValues, _
Lookat:=xlWhole)
If rFind Is Nothing Then
cnt = cnt + 1
GoTo FindAgain
Else:
Range("D" & LoopStartCuePipeNo(LSQ) + Rw & ":D" & ClosedLoopPipeNo(LSQ) + Rw).Value = AssignLoop
End If
End With
LSQ = LSQ + 1
LoopStartCue(LSQ) = Range("B" & i + Rw + cnt)
LoopStartCuePipeNo(LSQ) = Range("A" & i + Rw + cnt)
AssignLoop = AssignLoop + 1
GoTo EndSpot

blank2:
LoopStartCue(LSQ) = ClosedLoopNodeNo(LSQ)
LoopStartCuePipeNo(LSQ) = LoopStartCuePipeNo(LSQ)
Range("D" & LoopStartCuePipeNo(LSQ) + Rw & ":D" & ClosedLoopPipeNo(LSQ) + Rw).Value = AssignLoop

GoTo EndSpot
'||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

End If
End If
Next i

EndSpot:
loopC = LoopStartCuePipeNo(2) + 1
For i = loopC To IL
Range("B" & i + Rw).Select
If Range("B" & i + Rw) > Range("C" & i + Rw) Then
Range("D" & i + Rw).Value = AssignLoop

ClosedLoopNodeNo(LSQ) = Range("C" & i + Rw) 'added new
ClosedLoopPipeNo(LSQ) = Range("A" & i + Rw) 'added new

cnt = 1
FindAgain2:
Range("C" & i + Rw + cnt).Select
If Range("C" & i + Rw + cnt).Value = Empty Then GoTo blank:

FindNode = Range("C" & i + Rw + cnt).Value

With Range("B" & i + Rw + cnt, Cells(Rows.Count, "B"))
Set rFind = .Cells.Find(What:=FindNode, _
LookIn:=xlValues, _
Lookat:=xlWhole)
If rFind Is Nothing Then
cnt = cnt + 1
GoTo FindAgain2
End If

LSQ = LSQ + 1
LoopStartCue(LSQ) = Range("B" & i + Rw + cnt)
LoopStartCuePipeNo(LSQ) = Range("A" & i + Rw + cnt)
AssignLoop = AssignLoop + 1
End With

End If

blank:
'     LoopStartCue(LSQ) = LoopStartCue(LSQ)
'     LoopStartCuePipeNo(LSQ) = LoopStartCuePipeNo(LSQ)

Next i

'||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Frun = True
AssignLoop = 1
'Printing Cues
cueNodeC = 1
For i = 1 To IL

Range("B" & i + Rw).Select
Range("C" & i + Rw).Select
If Range("B" & i + Rw) > Range("C" & i + Rw) Then

If Frun = True Then
getLineNo = Range("A" & i + Rw)
incr = getLineNo
Do While Range("B" & incr + Rw) <> ClosedLoopNodeNo(AssignLoop)
incr = incr - 1
Loop
Range("D" & incr + Rw & ":D" & getLineNo + Rw).Value = AssignLoop
Frun = False
AssignLoop = AssignLoop + 1
'||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Else:
getLineNo = Range("A" & i + Rw)
incr = getLineNo
Do While Range("A" & incr + Rw) <> LoopStartCuePipeNo(AssignLoop)
Range("B" & incr + Rw - 1).Select
If Range("D" & incr + Rw - 1) <> "" Then Exit Do

If Range("B" & incr + Rw) = ClosedLoopNodeNo(AssignLoop) Then
'ClosedLoopNodeNo(cueNodeC) = Range("B" & incr + Rw)
LoopStartCuePipeNo(AssignLoop) = Range("A" & incr + Rw)
LoopStartCue(AssignLoop) = Range("B" & incr + Rw)
Exit Do
End If
incr = incr - 1
Loop
Range("D" & incr + Rw & ":D" & getLineNo + Rw).Value = AssignLoop
AssignLoop = AssignLoop + 1
cueNodeC = cueNodeC + 1
End If
End If
Next i

'
'
''Shared loop assignment With the help of
'LoopStartCue (5)  ' Node of the start loopNo
'ClosedLoopNodeNo (5) ' Node of the closed loopNo

For i = 1 To AssignLoop
' Searching line in the network
FNode = LoopStartCue(i)
TNode = ClosedLoopNodeNo(i)

If FNode < TNode And TNode <> FNode Then '//////
For k = TNode To FNode Step -1
For j = 1 To IL
Range("B" & j + Rw).Select
Range("C" & j + Rw).Select
If Range("B" & j + Rw) = FNode And Range("C" & j + Rw) = k Then
Range("E" & j + Rw).Value = i
End If
Next j

Next k
End If   '//////
Next i

For i = 1 To AssignLoop
' Searching line in the network
FNode = LoopStartCue(i)
TNode = ClosedLoopNodeNo(i)

If FNode < TNode And TNode <> FNode Then '//////
For m = FNode To TNode
For j = 1 To IL
Range("B" & j + Rw).Select
Range("C" & j + Rw).Select
If Range("B" & j + Rw) = m And Range("C" & j + Rw) = TNode Then
Range("E" & j + Rw).Value = i
End If
Next j

Next m

End If   '//////
Next i

'Placing Zero  where cells are blank
For i = 1 To IL
If Range("D" & i + Rw) = "" Then
Range("D" & i + Rw) = 0
End If
If Range("E" & i + Rw) = "" Then
Range("E" & i + Rw) = 0
End If
Next i
End Sub```

2. ## Re: A challenging question in Graph - help me find the algo for this

Thread moved from CodeBank, which is for working examples.

3. ## Re: A challenging question in Graph - help me find the algo for this

make a pivot and see how many appear more than once?

also - shared as in arrived at more than once, or splits... or both these options...?

4. ## Re: A challenging question in Graph - help me find the algo for this

Originally Posted by Ecniv
make a pivot and see how many appear more than once?

also - shared as in arrived at more than once, or splits... or both these options...?
I do not understand your question.

5. ## Re: A challenging question in Graph - help me find the algo for this

I think what Ecniv is trying to say is this

if loop 1 has 3 points 1, 2 and 3 then
if loop 2 uses points 2, 3,4 and 5 then we can safely say its attached to the first loop

this is because 2 points are used on both loops which must mean that they share a side

if they only shared 1 point it would mean that their 2 corners would be touching

etc etc

so im looking at your graphical part here with the shapes, i would turn this into a list of shapes with coordinates (cartisan) and then use a simple algorithm to find matches between them and go from there...... once you find a match you then try to find out if the next point matches........don't forget to link the points with a reference to what other points its attached too....

something like that..... you might want to look at the gaming section and link this post there as this the kind of geometry problem gaming programmers might face.

6. ## Re: A challenging question in Graph - help me find the algo for this

Originally Posted by lucky9
I do not understand your question.
ok.. I meant...

from your diagram you start at position 1, then to 2, 3 then 4.
At point 4 you can go two ways, so is this classed as a shared point.
4 goes to 5 and goes to 13.
13 also goes to 5.
so at point 5 you are coimg from two directions. Is this what you meant as a shared point?

If it is the latter, pivot the data on tnode and count them...
If it is the former, pivot on fnode and count.

If you are doing the count in a loop, then you'll need a collection or array of nodes. each time you encounter a node, you check if it exists already; if so add one to the counter. if not add it with a count of 1.

7. ## Re: A challenging question in Graph - help me find the algo for this

Originally Posted by Ecniv
ok.. I meant...

from your diagram you start at position 1, then to 2, 3 then 4.
At point 4 you can go two ways, so is this classed as a shared point.
4 goes to 5 and goes to 13.
13 also goes to 5.
so at point 5 you are coimg from two directions. Is this what you meant as a shared point?

If it is the latter, pivot the data on tnode and count them...
If it is the former, pivot on fnode and count.

If you are doing the count in a loop, then you'll need a collection or array of nodes. each time you encounter a node, you check if it exists already; if so add one to the counter. if not add it with a count of 1.

Hi,

As per the diagram, We have to cover one loop at a time, and in a clockwise direction. we cannot go to another loop if the previous one is not covered.

At point 4 can go two ways but as we are coming from 2-3 we are already started covering loop [1] so we have to first finish covering it entirely then only we can cover the another one.

So we cannot move from 4 to 13 so we move from 4 to 5 then -6-7-8-9-10-11-12-2, this way loopp [1] is covered.

Now, we come back again to 4 as 5 is already covered when covering loop 1 we move to 4-13 here we find that 4-13 is in loop [2] so we have to finish covering loop [2] first, so we move from 13 to 5. now, loop [2] is covered.

At this point we again come back to Node 13 and can see 2 nodes are connected to node 13 ( 7,14) we can either move to 7 or 14 , if we decide to move to 14 we can see 14 is in loop 4 , now we have to finish covering loop 4 so we move 13 - 14 - 8,

Now coming back to 13 and moving 7 to cover loop [3]..

This is how the Input data sheet is created.

SharedLoop:

Shared Loop No. implies that the common line between two loops. loop attached to another loop.

here.. Please look at following example to understand it more clearly..

Here, Node 1 - 2 will not be considered as in loop because its a branch line which is attached to a loop.

As you can see that the common line between two loop is From Node 4 - 5 which is sharing loop 1 and loop 2.

It is represented as

line 4-5 is in loop 1 and is also attached to loop No 2 as a shared loop.

8. ## Re: A challenging question in Graph - help me find the algo for this

Just to see if I understand correctly.

So you are running a loop of enclosed points.
using the permitted connections (and direction?) given.

so your last example would be :
Code:
```- runs all points nothing connects back to 1
- runs all points from 2
-- 2 - 3
-- 3 - 4
-- 4 - 5
-- 5 - 6
-- 6 - 2 - loop/enclosed 1
- run all points from 3
-> no extra connections
- run all points from 4
- 4 - 7
- 7 - 8
- 8 - 5
- 5 - 4 -- loop/enclosed 2
...
... no extra connections no more loops/enclosed```
Thats with direction though.

I take it you have the points and lines that are connected, they can be specified differently and your code need to output which lines are used more than once and which loop?

Is it only for the smallest space though?
or based by the order of the points?

Example:
in the first one your loop 1 is 2 - 12,
but it could also have been 2,3,4,13,14,8,9,10,15,12,2.

Just trying to understand the rules you need to apply in the generation of the enclosed loops

9. ## Re: A challenging question in Graph - help me find the algo for this

Originally Posted by Ecniv
Just to see if I understand correctly.

So you are running a loop of enclosed points.
using the permitted connections (and direction?) given.

so your last example would be :
Code:
```- runs all points nothing connects back to 1
- runs all points from 2
-- 2 - 3
-- 3 - 4
-- 4 - 5
-- 5 - 6
-- 6 - 2 - loop/enclosed 1
- run all points from 3
-> no extra connections
- run all points from 4
- 4 - 7
- 7 - 8
- 8 - 5
- 5 - 4 -- loop/enclosed 2
...
... no extra connections no more loops/enclosed```
Thats with direction though.

I take it you have the points and lines that are connected, they can be specified differently and your code need to output which lines are used more than once and which loop?

Is it only for the smallest space though?
or based by the order of the points?

Example:
in the first one your loop 1 is 2 - 12,
but it could also have been 2,3,4,13,14,8,9,10,15,12,2.

Just trying to understand the rules you need to apply in the generation of the enclosed loops

so your last example would be :
Code:
```- runs all points nothing connects back to 1
- runs all points from 2
-- 2 - 3
-- 3 - 4
-- 4 - 5
-- 5 - 6
-- 6 - 2 - loop/enclosed 1
- run all points from 3
-> no extra connections
- run all points from 4
- 4 - 7
- 7 - 8
- 8 - 5
- 5 - 4 -- loop/enclosed 2
...
... no extra connections no more loops/enclosed```

You understood correctly.

I take it you have the points and lines that are connected, they can be specified differently and your code need to output which lines are used more than once and which loop?
You are right.
but the input sheet data will be generated keeping in mind the rules as I described above.

Is it only for the smallest space though?
or based by the order of the points?
We have to start from 1 to total no of nodes in the network. (moving in a clockwise direction) and cover loops as it comes. it does not matter if the loop is bigger or smaller.

also the loop can have branches but that need to be ignored.. like here in this example image. Line marked in red are not it any loop so it will be ignored.

Example:
in the first one your loop 1 is 2 - 12,
Yes! its 12 I made a mistake there..

Example:
but it could also have been 2,3,4,13,14,8,9,10,15,12,2.
We can take this direction but it will create a problem, We must have to cover the inner loop ( the very first loop encounters when traversing form node 1 ) first then move to outer loop as it comes.

And thank you for following this thread.

10. ## Re: A challenging question in Graph - help me find the algo for this

loop can have branches but that need to be ignored.. like here in this example image. Line marked in red are not it any loop so it will be ignored.

11. ## Re: A challenging question in Graph - help me find the algo for this

If there is no way to return to the start of the line - its a branch..?
I'll need to think on it a bit tonight, see what I can come up with...

12. ## Re: A challenging question in Graph - help me find the algo for this

Hi

I dont have a working solution yet. Still the thought that all possible routes need to be mapped...
Anyway - attached is the work in progress - started with arrays and added a collection for the points being used...

13. ## Re: A challenging question in Graph - help me find the algo for this

Originally Posted by Ecniv
If there is no way to return to the start of the line - its a branch..?
I'll need to think on it a bit tonight, see what I can come up with...
Yes!

14. ## Re: A challenging question in Graph - help me find the algo for this

Hi, Please have a look at the attached excel vba I have updated the code.

Please also look at the modules I have enclosed in the excel that might be helpful in achieving this.

Thanks

15. ## Re: A challenging question in Graph - help me find the algo for this

Its a pain in the ass/head sigh

I can see how to do it iif it were a human doing it. But translating to computer I only and repeatedly keep coming back to the idea of routes, map all routes and get the ones that are the shortest etc...

How... well thats the crutch of the problem. I tried the arrays - posted.
Moved towards collections, but cannot see how to make that work. And finally started to use a class module or two... Still not working.
I will try again soon, but I have work to do as well, deadlines etc...
If I come up with something, Ill post here.

16. ## Re: A challenging question in Graph - help me find the algo for this

Originally Posted by Ecniv
Its a pain in the ass/head sigh

I can see how to do it iif it were a human doing it. But translating to computer I only and repeatedly keep coming back to the idea of routes, map all routes and get the ones that are the shortest etc...

How... well thats the crutch of the problem. I tried the arrays - posted.
Moved towards collections, but cannot see how to make that work. And finally started to use a class module or two... Still not working.
I will try again soon, but I have work to do as well, deadlines etc...
If I come up with something, Ill post here.
I know its a tricky problem. It has given pain in my entire body lol..
I'm not in hurry please take you time as much as you like, no pressure at all.
I'm also trying to figuring this out if I ever get the solution first then I would post here if you ever get the solution then please post here..

Thank you!

17. ## Re: A challenging question in Graph - help me find the algo for this

Can anyone help! with solving this problem? Sorry for the bump!

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Featured