Solved

Extracting loops from a network

Posted on 2013-12-16
14
250 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
  • 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
 
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
Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
Sending a Secure fax is easy with eFax Corporate (http://www.enterprise.efax.com). First, Just open a new email message.  In the To field, type your recipient's fax number @efaxsend.com. You can even send a secure international fax — just include t…
Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…

762 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

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now