Results 1 to 17 of 17

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

  1. #1

    Thread Starter
    Junior Member
    Join Date
    Jul 2017
    Posts
    18

    Question 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.



    Name:  bbff0ce1d2f0ff51d7816af025f89585.jpg
Views: 385
Size:  10.0 KB

    Name:  13d3dbadc0dfda02c914c7971f5a4ee9.png
Views: 363
Size:  17.6 KB


    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 TempAdd() As Long
    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
    Attached Images Attached Images  
    Last edited by lucky9; Dec 13th, 2017 at 12:39 PM.

  2. #2
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,989

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

    Thread moved from CodeBank, which is for working examples.
    My usual boring signature: Nothing

  3. #3
    Don't Panic! Ecniv's Avatar
    Join Date
    Nov 2000
    Location
    Amsterdam...
    Posts
    5,343

    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...?

    BOFH Now, BOFH Past, Information on duplicates

    Feeling like a fly on the inside of a closed window (Thunk!)
    If I post a lot, it is because I am bored at work! ;D Or stuck...
    * Anything I post can be only my opinion. Advice etc is up to you to persue...

  4. #4

    Thread Starter
    Junior Member
    Join Date
    Jul 2017
    Posts
    18

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

    Quote Originally Posted by Ecniv View Post
    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.
    Last edited by lucky9; Dec 13th, 2017 at 01:35 PM.

  5. #5
    Fanatic Member
    Join Date
    Feb 2013
    Posts
    985

    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.
    Yes!!!
    Working from home is so much better than working in an office...
    Nothing can beat the combined stress of getting your work done on time whilst
    1. one toddler keeps pressing your AVR's power button
    2. one baby keeps crying for milk
    3. one child keeps running in and out of the house screaming and shouting
    4. one wife keeps nagging you to stop playing on the pc and do some real work.. house chores
    5. working at 1 O'clock in the morning because nobody is awake at that time
    6. being grossly underpaid for all your hard work


  6. #6
    Don't Panic! Ecniv's Avatar
    Join Date
    Nov 2000
    Location
    Amsterdam...
    Posts
    5,343

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

    Quote Originally Posted by lucky9 View Post
    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.

    BOFH Now, BOFH Past, Information on duplicates

    Feeling like a fly on the inside of a closed window (Thunk!)
    If I post a lot, it is because I am bored at work! ;D Or stuck...
    * Anything I post can be only my opinion. Advice etc is up to you to persue...

  7. #7

    Thread Starter
    Junior Member
    Join Date
    Jul 2017
    Posts
    18

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

    Quote Originally Posted by Ecniv View Post
    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.

    Name:  ab3f9ca8ea64a1f36552cf61fc5590b6.jpg
Views: 259
Size:  27.7 KB

  8. #8
    Don't Panic! Ecniv's Avatar
    Join Date
    Nov 2000
    Location
    Amsterdam...
    Posts
    5,343

    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

    BOFH Now, BOFH Past, Information on duplicates

    Feeling like a fly on the inside of a closed window (Thunk!)
    If I post a lot, it is because I am bored at work! ;D Or stuck...
    * Anything I post can be only my opinion. Advice etc is up to you to persue...

  9. #9

    Thread Starter
    Junior Member
    Join Date
    Jul 2017
    Posts
    18

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

    Quote Originally Posted by Ecniv View Post
    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.
    Last edited by lucky9; Dec 14th, 2017 at 09:19 AM.

  10. #10

    Thread Starter
    Junior Member
    Join Date
    Jul 2017
    Posts
    18

    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.
    Name:  0bbcaaec9d8bd7bf5b4df1917cd8f63f.png
Views: 225
Size:  2.6 KB

  11. #11
    Don't Panic! Ecniv's Avatar
    Join Date
    Nov 2000
    Location
    Amsterdam...
    Posts
    5,343

    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...

    BOFH Now, BOFH Past, Information on duplicates

    Feeling like a fly on the inside of a closed window (Thunk!)
    If I post a lot, it is because I am bored at work! ;D Or stuck...
    * Anything I post can be only my opinion. Advice etc is up to you to persue...

  12. #12
    Don't Panic! Ecniv's Avatar
    Join Date
    Nov 2000
    Location
    Amsterdam...
    Posts
    5,343

    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...
    Attached Files Attached Files

    BOFH Now, BOFH Past, Information on duplicates

    Feeling like a fly on the inside of a closed window (Thunk!)
    If I post a lot, it is because I am bored at work! ;D Or stuck...
    * Anything I post can be only my opinion. Advice etc is up to you to persue...

  13. #13

    Thread Starter
    Junior Member
    Join Date
    Jul 2017
    Posts
    18

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

    Quote Originally Posted by Ecniv View Post
    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. #14

    Thread Starter
    Junior Member
    Join Date
    Jul 2017
    Posts
    18

    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
    Attached Files Attached Files
    Last edited by lucky9; Dec 15th, 2017 at 03:46 AM.

  15. #15
    Don't Panic! Ecniv's Avatar
    Join Date
    Nov 2000
    Location
    Amsterdam...
    Posts
    5,343

    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.

    BOFH Now, BOFH Past, Information on duplicates

    Feeling like a fly on the inside of a closed window (Thunk!)
    If I post a lot, it is because I am bored at work! ;D Or stuck...
    * Anything I post can be only my opinion. Advice etc is up to you to persue...

  16. #16

    Thread Starter
    Junior Member
    Join Date
    Jul 2017
    Posts
    18

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

    Quote Originally Posted by Ecniv View Post
    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. #17

    Thread Starter
    Junior Member
    Join Date
    Jul 2017
    Posts
    18

    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
  •  



Click Here to Expand Forum to Full Width