trunk/src/superx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/superx.c,v 1.10 2009-06-15 19:06:03 amb Exp $

 Super-Segment data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008,2009 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ***************************************/


#include <assert.h>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>

#include "results.h"
#include "nodesx.h"
#include "segmentsx.h"
#include "waysx.h"
#include "superx.h"


/*++++++++++++++++++++++++++++++++++++++
  Select the super-segments from the list of segments.

  NodesX *nodesx The nodes.

  SegmentsX *segmentsx The segments.

  WaysX *waysx The ways.

  int iteration The current super-node / super-segment iteration number.
  ++++++++++++++++++++++++++++++++++++++*/

void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,int iteration)
{
 int i;
 int    segcount=0,difference=0,nnodes=0;
 node_t node=0;
 Way    way;

 /* Find super-nodes */

 node=segmentsx->sdata[0]->node1;

 for(i=0;i<segmentsx->number;i++)
   {
    SegmentX **segmentx=LookupSegmentX(segmentsx,i);
    WayX *wayx=LookupWayX(waysx,(*segmentx)->segment.way);

    if((*segmentx)->node1!=node)
      {
       /* Store the node if there is a difference in the ways that could affect routing.
          Store the node if it is not a dead-end and if it isn't just the middle of a way. */

       if(difference || segcount>2)
         {
          NodeX *nodex=FindNodeX(nodesx,node);

          nodex->super++;

          nnodes++;
         }

       segcount=1;
       difference=0;

       node=(*segmentx)->node1;
       way=wayx->way;
      }
    else                        /* Same starting node */
      {
       if(WaysCompare(&wayx->way,&way))
          difference=1;

       segcount+=1;
      }

    if(!((i+1)%10000))
      {
       printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i+1,nnodes);
       fflush(stdout);
      }
   }

 printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d  \n",segmentsx->number,nnodes);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Create the super-segments.

  SegmentsX *CreateSuperSegments Creates the super segments.

  NodesX *nodesx The nodes.

  SegmentsX *segmentsx The segments.

  WaysX *waysx The ways.

  int iteration The current super-node / super-segment iteration number.
  ++++++++++++++++++++++++++++++++++++++*/

SegmentsX *CreateSuperSegments(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,int iteration)
{
 int i;
 SegmentsX *supersegmentsx;

 supersegmentsx=NewSegmentList();

 /* Create super-segments for each super-node. */

 for(i=0;i<nodesx->number;i++)
   {
    if(nodesx->gdata[i]->super>iteration)
      {
       SegmentX **segmentx,**first;

       segmentx=first=FindFirstSegmentX(segmentsx,nodesx->gdata[i]->id);

       while(segmentx)
         {
          WayX *wayx=LookupWayX(waysx,(*segmentx)->segment.way);

          /* Check that this type of way hasn't already been routed */

          if(segmentx!=first)
            {
             SegmentX **othersegmentx=first;

             while(othersegmentx && othersegmentx!=segmentx)
               {
                WayX *otherwayx=LookupWayX(waysx,(*othersegmentx)->segment.way);

                if(!WaysCompare(&otherwayx->way,&wayx->way))
                  {
                   wayx=NULL;
                   break;
                  }

                othersegmentx=FindNextSegmentX(segmentsx,othersegmentx);
               }
            }

          /* Route the way and store the super-segments. */

          if(wayx)
            {
             Results *results=FindRoutesWay(nodesx,segmentsx,waysx,nodesx->gdata[i]->id,wayx,iteration);
             Result *result=FirstResult(results);

             while(result)
               {
                NodeX *nodex=FindNodeX(nodesx,result->node);

                if(result->node!=nodesx->gdata[i]->id && nodex->super>iteration)
                  {
                   Segment *supersegment=AppendSegment(supersegmentsx,nodesx->gdata[i]->id,result->node);

                   if(wayx->way.type&Way_OneWay)
                     {
                      supersegment->distance=ONEWAY_1TO2|(distance_t)result->score;
                      supersegment->way=IndexWayX(waysx,wayx);

                      supersegment=AppendSegment(supersegmentsx,result->node,nodesx->gdata[i]->id);

                      supersegment->distance=ONEWAY_2TO1|(distance_t)result->score;
                      supersegment->way=IndexWayX(waysx,wayx);
                     }
                   else
                     {
                      supersegment->distance=(distance_t)result->score;
                      supersegment->way=IndexWayX(waysx,wayx);
                     }
                  }

                result=NextResult(results,result);
               }

             FreeResultsList(results);
            }

          segmentx=FindNextSegmentX(segmentsx,segmentx);
         }
      }

    if(!((i+1)%10000))
      {
       printf("\rCreating Super-Segments: Nodes=%d Super-Segments=%d",i+1,supersegmentsx->xnumber);
       fflush(stdout);
      }
   }

 printf("\rCreated Super-Segments: Nodes=%d Super-Segments=%d \n",nodesx->number,supersegmentsx->xnumber);
 fflush(stdout);

 /* Append the new supersegments onto the segments. */

 return(supersegmentsx);
}


/*++++++++++++++++++++++++++++++++++++++
  Merge the super-segments into the segments.

  SegmentsX* segmentsx The set of segments to process.

  SegmentsX* supersegmentsx The set of super-segments to merge.
  ++++++++++++++++++++++++++++++++++++++*/

void MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx)
{
 int i,j,n;

 assert(segmentsx->sorted);      /* Must be sorted */
 assert(supersegmentsx->sorted); /* Must be sorted */

 n=segmentsx->number;

 for(i=0,j=0;i<n;i++)
   {
    segmentsx->sdata[i]->segment.node1=SUPER_FLAG; /* mark as normal segment */

    segmentsx->sdata[i]->segment.next2=NO_NODE;

    while(j<supersegmentsx->number)
      {
       if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
          segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2 &&
          segmentsx->sdata[i]->segment.distance==supersegmentsx->sdata[j]->segment.distance)
         {
          segmentsx->sdata[i]->segment.node2=SUPER_FLAG; /* mark as super-segment */
          supersegmentsx->sdata[j]=NULL;
          j++;
          break;
         }
       else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
               segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2)
         {
          supersegmentsx->sdata[j]->segment.node2=SUPER_FLAG; /* mark as super-segment */
          supersegmentsx->sdata[j]->segment.next2=NO_NODE;
         }
       else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
               segmentsx->sdata[i]->node2>supersegmentsx->sdata[j]->node2)
         {
          supersegmentsx->sdata[j]->segment.node2=SUPER_FLAG; /* mark as super-segment */
          supersegmentsx->sdata[j]->segment.next2=NO_NODE;
         }
       else if(segmentsx->sdata[i]->node1>supersegmentsx->sdata[j]->node1)
         {
          supersegmentsx->sdata[j]->segment.node2=SUPER_FLAG; /* mark as super-segment */
          supersegmentsx->sdata[j]->segment.next2=NO_NODE;
         }
       else
          break;

       j++;
      }

    if(!((i+1)%10000))
      {
       printf("\rMerging Segments: Segments=%d Super-Segment=%d Total=%d",i+1,j+1,segmentsx->xnumber);
       fflush(stdout);
      }
   }

 for(j=0;j<supersegmentsx->number;j++)
    if(supersegmentsx->sdata[j])
      {
       Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);

       *supersegment=supersegmentsx->sdata[j]->segment;
      }

 printf("\rMerged Segments: Segments=%d Super-Segment=%d Total=%d \n",n,supersegmentsx->number,segmentsx->xnumber);
 fflush(stdout);
}


/*++++++++++++++++++++++++++++++++++++++
  Find all routes from a specified node to any node in the specified list that follows a certain type of way.

  Results *FindRoutesWay Returns a set of results.

  NodesX *nodesx The set of nodes to use.

  SegmentsX *segmentsx The set of segments to use.

  WaysX *waysx The set of ways to use.

  node_t start The start node.

  WayX *match The way that the route must match.

  int iteration The current super-node / super-segment iteration number.
  ++++++++++++++++++++++++++++++++++++++*/

Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,WayX *match,int iteration)
{
 Results *results;
 index_t node1,node2;
 Result *result1,*result2;
 NodeX *nodex;
 SegmentX **segmentx;
 WayX *wayx;

 /* Insert the first node into the queue */

 results=NewResultsList(8);

 result1=InsertResult(results,start);

 ZeroResult(result1);

 insert_in_queue(result1);

 /* Loop across all nodes in the queue */

 while((result1=pop_from_queue()))
   {
    node1=result1->node;

    segmentx=FindFirstSegmentX(segmentsx,node1);

    while(segmentx)
      {
       distance_t cumulative_distance;

       if((*segmentx)->segment.distance&ONEWAY_2TO1)
          goto endloop;

       node2=(*segmentx)->node2;

       if(result1->prev==node2)
          goto endloop;

       wayx=LookupWayX(waysx,(*segmentx)->segment.way);

       if(WaysCompare(&wayx->way,&match->way))
          goto endloop;

       cumulative_distance=(distance_t)result1->score+DISTANCE((*segmentx)->segment.distance);

       result2=FindResult(results,node2);

       if(!result2)                         /* New end node */
         {
          result2=InsertResult(results,node2);
          result2->prev=node1;
          result2->next=NO_NODE;
          result2->score=cumulative_distance;
          result2->sortby=cumulative_distance;

          nodex=FindNodeX(nodesx,node2);

          if(nodex->super<=iteration)
             insert_in_queue(result2);
         }
       else if(cumulative_distance<result2->score)
         {
          result2->prev=node1;
          result2->score=cumulative_distance;
          result2->sortby=cumulative_distance;

          nodex=FindNodeX(nodesx,node2);

          if(nodex->super<=iteration)
             insert_in_queue(result2);
         }

      endloop:

       segmentx=FindNextSegmentX(segmentsx,segmentx);
      }
   }

 return(results);
}
1	amb	110	/***************************************
2	amb	201	$Header: /home/amb/CVS/routino/src/superx.c,v 1.10 2009-06-15 19:06:03 amb Exp $
3	amb	110
4			Super-Segment data type functions.
5	amb	151
6			Part of the Routino routing software.
7	amb	110	****************/ /****************
8	amb	151	This file Copyright 2008,2009 Andrew M. Bishop
9	amb	110
10	amb	151	This program is free software: you can redistribute it and/or modify
11			it under the terms of the GNU Affero General Public License as published by
12			the Free Software Foundation, either version 3 of the License, or
13			(at your option) any later version.
14
15			This program is distributed in the hope that it will be useful,
16			but WITHOUT ANY WARRANTY; without even the implied warranty of
17			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18			GNU Affero General Public License for more details.
19
20			You should have received a copy of the GNU Affero General Public License
21			along with this program. If not, see <http://www.gnu.org/licenses/>.
22	amb	110	***************************************/
23
24
25			#include <assert.h>
26			#include <math.h>
27			#include <stdlib.h>
28			#include <stdio.h>
29
30			#include "results.h"
31			#include "nodesx.h"
32			#include "segmentsx.h"
33			#include "waysx.h"
34			#include "superx.h"
35
36
37			/*++++++++++++++++++++++++++++++++++++++
38			Select the super-segments from the list of segments.
39
40			NodesX *nodesx The nodes.
41
42			SegmentsX *segmentsx The segments.
43
44			WaysX *waysx The ways.
45
46			int iteration The current super-node / super-segment iteration number.
47			++++++++++++++++++++++++++++++++++++++*/
48
49			void ChooseSuperNodes(NodesX nodesx,SegmentsX segmentsx,WaysX *waysx,int iteration)
50			{
51			int i;
52	amb	135	int segcount=0,difference=0,nnodes=0;
53			node_t node=0;
54			Way way;
55	amb	110
56			/* Find super-nodes */
57
58			node=segmentsx->sdata[0]->node1;
59
60			for(i=0;i<segmentsx->number;i++)
61			{
62	amb	128	SegmentX **segmentx=LookupSegmentX(segmentsx,i);
63			WayX wayx=LookupWayX(waysx,(segmentx)->segment.way);
64	amb	110
65	amb	128	if((*segmentx)->node1!=node)
66	amb	110	{
67			/* Store the node if there is a difference in the ways that could affect routing.
68			Store the node if it is not a dead-end and if it isn't just the middle of a way. */
69
70			if(difference \|\| segcount>2)
71			{
72			NodeX *nodex=FindNodeX(nodesx,node);
73
74			nodex->super++;
75
76			nnodes++;
77			}
78
79			segcount=1;
80			difference=0;
81
82	amb	128	node=(*segmentx)->node1;
83	amb	135	way=wayx->way;
84	amb	110	}
85			else /* Same starting node */
86			{
87	amb	201	if(WaysCompare(&wayx->way,&way))
88	amb	110	difference=1;
89
90			segcount+=1;
91			}
92
93			if(!((i+1)%10000))
94			{
95			printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i+1,nnodes);
96			fflush(stdout);
97			}
98			}
99
100			printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d \n",segmentsx->number,nnodes);
101			fflush(stdout);
102			}
103
104
105			/*++++++++++++++++++++++++++++++++++++++
106			Create the super-segments.
107
108			SegmentsX *CreateSuperSegments Creates the super segments.
109
110			NodesX *nodesx The nodes.
111
112			SegmentsX *segmentsx The segments.
113
114			WaysX *waysx The ways.
115
116			int iteration The current super-node / super-segment iteration number.
117			++++++++++++++++++++++++++++++++++++++*/
118
119			SegmentsX CreateSuperSegments(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,int iteration)
120			{
121			int i;
122			SegmentsX *supersegmentsx;
123
124			supersegmentsx=NewSegmentList();
125
126			/* Create super-segments for each super-node. */
127
128			for(i=0;i<nodesx->number;i++)
129			{
130			if(nodesx->gdata[i]->super>iteration)
131			{
132			SegmentX segmentx,first;
133
134			segmentx=first=FindFirstSegmentX(segmentsx,nodesx->gdata[i]->id);
135
136			while(segmentx)
137			{
138			WayX wayx=LookupWayX(waysx,(segmentx)->segment.way);
139
140			/* Check that this type of way hasn't already been routed */
141
142			if(segmentx!=first)
143			{
144			SegmentX **othersegmentx=first;
145
146			while(othersegmentx && othersegmentx!=segmentx)
147			{
148			WayX otherwayx=LookupWayX(waysx,(othersegmentx)->segment.way);
149
150	amb	201	if(!WaysCompare(&otherwayx->way,&wayx->way))
151	amb	110	{
152			wayx=NULL;
153			break;
154			}
155
156			othersegmentx=FindNextSegmentX(segmentsx,othersegmentx);
157			}
158			}
159
160			/* Route the way and store the super-segments. */
161
162			if(wayx)
163			{
164			Results *results=FindRoutesWay(nodesx,segmentsx,waysx,nodesx->gdata[i]->id,wayx,iteration);
165			Result *result=FirstResult(results);
166
167			while(result)
168			{
169			NodeX *nodex=FindNodeX(nodesx,result->node);
170
171			if(result->node!=nodesx->gdata[i]->id && nodex->super>iteration)
172			{
173			Segment *supersegment=AppendSegment(supersegmentsx,nodesx->gdata[i]->id,result->node);
174
175			if(wayx->way.type&Way_OneWay)
176			{
177	amb	172	supersegment->distance=ONEWAY_1TO2\|(distance_t)result->score;
178			supersegment->way=IndexWayX(waysx,wayx);
179	amb	110
180			supersegment=AppendSegment(supersegmentsx,result->node,nodesx->gdata[i]->id);
181
182	amb	172	supersegment->distance=ONEWAY_2TO1\|(distance_t)result->score;
183	amb	110	supersegment->way=IndexWayX(waysx,wayx);
184			}
185	amb	172	else
186			{
187			supersegment->distance=(distance_t)result->score;
188			supersegment->way=IndexWayX(waysx,wayx);
189			}
190	amb	110	}
191
192			result=NextResult(results,result);
193			}
194
195			FreeResultsList(results);
196			}
197
198			segmentx=FindNextSegmentX(segmentsx,segmentx);
199			}
200			}
201
202			if(!((i+1)%10000))
203			{
204			printf("\rCreating Super-Segments: Nodes=%d Super-Segments=%d",i+1,supersegmentsx->xnumber);
205			fflush(stdout);
206			}
207			}
208
209			printf("\rCreated Super-Segments: Nodes=%d Super-Segments=%d \n",nodesx->number,supersegmentsx->xnumber);
210			fflush(stdout);
211
212			/* Append the new supersegments onto the segments. */
213
214			return(supersegmentsx);
215			}
216
217
218			/*++++++++++++++++++++++++++++++++++++++
219			Merge the super-segments into the segments.
220
221			SegmentsX* segmentsx The set of segments to process.
222
223			SegmentsX* supersegmentsx The set of super-segments to merge.
224			++++++++++++++++++++++++++++++++++++++*/
225
226			void MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx)
227			{
228			int i,j,n;
229
230			assert(segmentsx->sorted); /* Must be sorted */
231			assert(supersegmentsx->sorted); /* Must be sorted */
232
233			n=segmentsx->number;
234
235			for(i=0,j=0;i<n;i++)
236			{
237			segmentsx->sdata[i]->segment.node1=SUPER_FLAG; /* mark as normal segment */
238
239	amb	176	segmentsx->sdata[i]->segment.next2=NO_NODE;
240	amb	110
241			while(j<supersegmentsx->number)
242			{
243			if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
244			segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2 &&
245			segmentsx->sdata[i]->segment.distance==supersegmentsx->sdata[j]->segment.distance)
246			{
247			segmentsx->sdata[i]->segment.node2=SUPER_FLAG; /* mark as super-segment */
248	amb	139	supersegmentsx->sdata[j]=NULL;
249	amb	110	j++;
250			break;
251			}
252			else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
253			segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2)
254			{
255	amb	139	supersegmentsx->sdata[j]->segment.node2=SUPER_FLAG; /* mark as super-segment */
256	amb	176	supersegmentsx->sdata[j]->segment.next2=NO_NODE;
257	amb	110	}
258			else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
259			segmentsx->sdata[i]->node2>supersegmentsx->sdata[j]->node2)
260			{
261	amb	139	supersegmentsx->sdata[j]->segment.node2=SUPER_FLAG; /* mark as super-segment */
262	amb	176	supersegmentsx->sdata[j]->segment.next2=NO_NODE;
263	amb	110	}
264			else if(segmentsx->sdata[i]->node1>supersegmentsx->sdata[j]->node1)
265			{
266	amb	139	supersegmentsx->sdata[j]->segment.node2=SUPER_FLAG; /* mark as super-segment */
267	amb	176	supersegmentsx->sdata[j]->segment.next2=NO_NODE;
268	amb	110	}
269			else
270			break;
271
272			j++;
273			}
274
275			if(!((i+1)%10000))
276			{
277			printf("\rMerging Segments: Segments=%d Super-Segment=%d Total=%d",i+1,j+1,segmentsx->xnumber);
278			fflush(stdout);
279			}
280			}
281
282	amb	139	for(j=0;j<supersegmentsx->number;j++)
283			if(supersegmentsx->sdata[j])
284			{
285			Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);
286
287			*supersegment=supersegmentsx->sdata[j]->segment;
288			}
289
290	amb	110	printf("\rMerged Segments: Segments=%d Super-Segment=%d Total=%d \n",n,supersegmentsx->number,segmentsx->xnumber);
291			fflush(stdout);
292			}
293
294
295			/*++++++++++++++++++++++++++++++++++++++
296			Find all routes from a specified node to any node in the specified list that follows a certain type of way.
297
298			Results *FindRoutesWay Returns a set of results.
299
300			NodesX *nodesx The set of nodes to use.
301
302			SegmentsX *segmentsx The set of segments to use.
303
304			WaysX *waysx The set of ways to use.
305
306			node_t start The start node.
307
308			WayX *match The way that the route must match.
309
310			int iteration The current super-node / super-segment iteration number.
311			++++++++++++++++++++++++++++++++++++++*/
312
313			Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,WayX *match,int iteration)
314			{
315			Results *results;
316			index_t node1,node2;
317			Result result1,result2;
318			NodeX *nodex;
319			SegmentX **segmentx;
320			WayX *wayx;
321
322			/* Insert the first node into the queue */
323
324			results=NewResultsList(8);
325
326			result1=InsertResult(results,start);
327
328	amb	166	ZeroResult(result1);
329	amb	110
330			insert_in_queue(result1);
331
332			/* Loop across all nodes in the queue */
333
334			while((result1=pop_from_queue()))
335			{
336			node1=result1->node;
337
338			segmentx=FindFirstSegmentX(segmentsx,node1);
339
340			while(segmentx)
341			{
342	amb	113	distance_t cumulative_distance;
343
344	amb	110	if((*segmentx)->segment.distance&ONEWAY_2TO1)
345			goto endloop;
346
347			node2=(*segmentx)->node2;
348
349	amb	113	if(result1->prev==node2)
350	amb	110	goto endloop;
351
352			wayx=LookupWayX(waysx,(*segmentx)->segment.way);
353
354	amb	201	if(WaysCompare(&wayx->way,&match->way))
355	amb	110	goto endloop;
356
357	amb	172	cumulative_distance=(distance_t)result1->score+DISTANCE((*segmentx)->segment.distance);
358	amb	110
359			result2=FindResult(results,node2);
360
361			if(!result2) /* New end node */
362			{
363			result2=InsertResult(results,node2);
364	amb	113	result2->prev=node1;
365	amb	176	result2->next=NO_NODE;
366	amb	172	result2->score=cumulative_distance;
367	amb	166	result2->sortby=cumulative_distance;
368	amb	110
369			nodex=FindNodeX(nodesx,node2);
370
371			if(nodex->super<=iteration)
372			insert_in_queue(result2);
373			}
374	amb	172	else if(cumulative_distance<result2->score)
375	amb	110	{
376	amb	166	result2->prev=node1;
377	amb	172	result2->score=cumulative_distance;
378	amb	166	result2->sortby=cumulative_distance;
379	amb	110
380	amb	166	nodex=FindNodeX(nodesx,node2);
381	amb	110
382	amb	166	if(nodex->super<=iteration)
383			insert_in_queue(result2);
384	amb	110	}
385
386			endloop:
387
388			segmentx=FindNextSegmentX(segmentsx,segmentx);
389			}
390			}
391
392			return(results);
393			}