Point handling for closed loop searching

Question

I have set of line segments. Each contains only 2 nodes. I want to find the available closed cycles which produces by joining line segments. Actually, I am looking for the smallest loop if there exist more than one occurrence. If can, please give me a good solution for this. So, for example I have added below line list together with their point indices to get idea about m case. (Where First value = line number, second 2 values are the point indices)

0 - 9 11  
1 - 9 18  
2 - 9 16  
3 - 11 26  
4 - 11 45  
5 - 16 25
6 - 16 49  
7 - 18 26 
8 - 18 25  
9 - 18 21  
10 - 25 49  
11 - 26 45

So, assume I have started from the line 1. That is I have started to find connected loops from point 9, 18. Then, could you please explain (step by step) how I can get the "closed loops" from that line.

Answer 1

Well, I don't see any C++ code, but I'll try to suggest a C++ solution (although I'm not going to write it for you).

If your graph is undirected (if it's directed, s/adjacent/in-edges' vertices/), and you want to find all the shortest cycles passing through some vertex N, then I think you could follow this procedure:

G <= a graph
N <= some vertex in G
P <= a path (set of vertexes/edges connecting them)
P_heap <= a priority queue, ascending by distance(P) where P is a path

for each vertex in adjacent(N):
  G' = G - edge(vertex, N)
  P = dijkstraShortestPath(vertex, N, G')
  push(P, P_heap)

You could also just throw out all but the shortest loop, but that's less succinct. As long as you don't allow negative edge weights (which, since you'll be using line segment length for weights, you don't), I think this should work. Also, fortunately Boost.Graph provides all of the necessary functionality to do this in C++ (you don't even have to implement Dijkstra's algorithm)! You can find documentation about it here:

http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/table_of_contents.html

EDIT: you will have to create the graph from that data you listed first before you can do this, so you'll just define your graph's property_map accordingly and make sure the distance between a vertex you're about to insert and all vertexes currently in the graph is greater than zero, because otherwise the vertex is already in the graph and you don't want to insert it again.

Happy graphing!