# Extracting loops from a network

I a trying to extract nodes from a network model as shown in the attached diagram.
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?
LVL 43
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
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

EngineerAuthor Commented:
How do I know the loops "in" the loop? By the coordinates?
0

Commented:
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

EngineerAuthor Commented:
I cannot see how to select those nodes.
0

Commented:
What language are you writing this in?  How is the network represented in your data?  What is done when a loop is discarded?
0

EngineerAuthor Commented:
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

Commented:
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

Commented:
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

Commented:
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

EngineerAuthor Commented:
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.
0

Commented:
What problem are you having?  What geometric information about the loop do you have? and how is that information represented in your data?
0

EngineerAuthor Commented:
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

Commented:
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

Experts Exchange Solution brought to you by ConnectWise

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

EngineerAuthor Commented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.