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?
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?
TommySzalapski
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.
ASKER
How do I know the loops "in" the loop? By the coordinates?
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.
If you find a loop that does not use all the nodes, then there must be a shortcut.
ASKER
I cannot see how to select those nodes.
What language are you writing this in? How is the network represented in your data? What is done when a loop is discarded?
ASKER
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.
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.
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
(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
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).
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).
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.
ASKER
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.
I do not see how geometry can help me pick this loop.
What problem are you having? What geometric information about the loop do you have? and how is that information represented in your data?
ASKER
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
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
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.
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.