Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Extracting loops from a network

Posted on 2013-12-16
14
Medium Priority
?
259 Views
Last Modified: 2013-12-29
I a trying to extract nodes from a network model as shown in the attached diagram.Data for looping
The algorithm I am using is to select a node eg 8 and move along the lines to the nodes 9, 31, 30, 26, 15 to get the loop.

During this I am checking that if in a loop like 8, 9, 10, 16, 32, 31, 30, 26, 15 any two of the nodes 31,9 are connected then the loop is discarded.

But now I have a problem in 8, 9, 10, 16, 32, 35, 34, 33, 30, 26, 15 no two nodes are directly connected so the loop is not discarded.

How do I incorporate the exclusion of this last loop in my algorighm? Or is my algorithm not good for this type of work? In which case, what should be the approach?
0
Comment
Question by:Saqib Husain, Syed
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 6
  • 5
  • 3
14 Comments
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 39721723
For each loop, look at just the nodes in that loop and ignore all the others. If there is a loop within that loop that contains fewer nodes, discard the loop.
0
 
LVL 43

Author Comment

by:Saqib Husain, Syed
ID: 39721761
How do I know the loops "in" the loop? By the coordinates?
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 39721852
You just run your current algorithm on the subset of nodes that make up the big loop.
If you find a loop that does not use all the nodes, then there must be a shortcut.
0
Will your db performance match your db growth?

In Percona’s white paper “Performance at Scale: Keeping Your Database on Its Toes,” we take a high-level approach to what you need to think about when planning for database scalability.

 
LVL 43

Author Comment

by:Saqib Husain, Syed
ID: 39722015
I cannot see how to select those nodes.
0
 
LVL 84

Expert Comment

by:ozo
ID: 39722167
What language are you writing this in?  How is the network represented in your data?  What is done when a loop is discarded?
0
 
LVL 43

Author Comment

by:Saqib Husain, Syed
ID: 39722215
Language: VBA

The network is picked up from Autocad in the form of lines only

The nodes and lines are then identified and numbered as shown.

Loops (not having subloops) have to be identified.
0
 
LVL 84

Expert Comment

by:ozo
ID: 39722807
Given the lines
(1,2)
(2,3)
(3,4)
(4,1)
(1,5)
(5,3)
which loops are the sub-loops?
If it depends which node is inside and which are outside,
i.e. whether they are arranged as
  1
 /|\
245
 \|/
  3
or
  1
 /|\
425
 \|/
  3
or
  1
 /|\
254
 \|/
  3
then you would need geometry information in addition to topology information
0
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 39722854
Ozo asks a good question. Is it just the smallest number of nodes to make a loop counts as the real loop? i.e. if you have a loop, but can find a shortcut, then the shortcut is the real loop?

So the idea is you take a set of points and try to find the loops, right?
Any loop that has a shortcut in it gets discarded, right?

So you take nodes 1,2,3,4,5,6,7,8,9,10,etc
You find a loop using nodes 2,3,4,5,6,7

Now you want to know if you should discard that loop.
So you take the points that made that loop (2,3,4,5,6,7) and feed them back into the original algorithm. If it finds a loop that doesn't use all of those points, then there must be a shortcut and that main loop is discarded.

Note that the subloop you found will match one of the loops you find in the full graph.
Note that "loops" are typically called "cycles" in graph theory (at least the way I learned it).
0
 
LVL 84

Expert Comment

by:ozo
ID: 39722876
If you define which loops are sub based on path length, and you have information about the length of each line, then you might find the shortest path between each pair of nodes and then only find loop among those shortest paths.
0
 
LVL 43

Author Comment

by:Saqib Husain, Syed
ID: 39734395
I thought geometry would be the solution but I am having a problem here at loop 224, 225, 226, 244, 243, 239, 238.

I do not see how geometry can help me pick this loop.
Entire network
0
 
LVL 84

Expert Comment

by:ozo
ID: 39735179
What problem are you having?  What geometric information about the loop do you have? and how is that information represented in your data?
0
 
LVL 43

Author Comment

by:Saqib Husain, Syed
ID: 39735985
What problem are you having?  
I cannot see how to pick an L-shaped loop like 224, 225, 226, 244, 243, 239, 238 (see last figure) using geometry information.

What geometric information about the loop do you have?
A loop is an enclosure with no sub-loop (sub-enclosure). The question gives more details on this.

and how is that information represented in your data?

This I have described in #39722215
0
 
LVL 84

Accepted Solution

by:
ozo earned 2000 total points
ID: 39741545
http:#a39722215 does not say what geometric information you have in your data, or how that information is represented, nor does it say how you are using that information to construct your loops.

So instead of using your unknown data and algorithm, I will suggest a possible data structure and algorithm:

Assuming that lines do not cross, and that the network is planar, each node can have a list of the nodes joined to it, in clockwise (or counterclockwise) order.
For example, the nodes 224, 225, 226, 244, 243, 239, 238 might contain

224=> [217,225,238,223,],
225=> [218,226,224],
226=> [225,244],
238=> [224,239,237],
239=> [238,243],
243=> [239,244,251],
244=> [226,245,249,243],

Then you can just do a depth first traversal, vising the neighbors of a node in clockwise (or counterclockwise - as long as you're consistent) order from the node you just came from.

Note that there would still be an ambiguity between "inside" and "outside" so that a loop that goes around the outside of the entire network would be equivalent to a loop on the inside of an equivalent network after an inversion operation.
If you need to disambiguate that situation, you would need additional geometric information besides just the cyclic order of the neighbors around each node.
One possibility could be to tag one node in each connected component of the graph with a specially labeled "outside" neighbor.
e.g.

199=> [191,200,"outside",198]
0
 
LVL 43

Author Closing Comment

by:Saqib Husain, Syed
ID: 39744949
This is so much better than what I had been working at. And Fast!

Thanks a lot.

I pick up one node and move to a (numerically) larger node and then continue clockwise until I return to the first node. No anomalies; no ambiguities.
0

Featured Post

On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
In this video, Percona Solution Engineer Rick Golba discuss how (and why) you implement high availability in a database environment. To discuss how Percona Consulting can help with your design and architecture needs for your database and infrastr…

704 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question