trunk/src/superx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/superx.c,v 1.21 2009-07-12 08:38:12 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 <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.
  ++++++++++++++++++++++++++++++++++++++*/

void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
{
 index_t i;
 int     segcount=0,difference=0,nnodes=0;
 node_t  node=0;
 WayX   *wayx1;

 assert(segmentsx->ndata);      /* Must have ndata filled in */

 printf("Finding Super-Nodes: (Super-)Segments=0 Super-Nodes=0");
 fflush(stdout);

 /* Find super-nodes */

 node=segmentsx->ndata[0]->node1;
 wayx1=FindWayX(waysx,segmentsx->ndata[0]->way);

 for(i=0;i<segmentsx->number;i++)
   {
    WayX *wayx2=FindWayX(waysx,segmentsx->ndata[i]->way);

    if(segmentsx->ndata[i]->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=segmentsx->ndata[i]->node1;
       wayx1=wayx2;
      }
    else                        /* Same starting node */
      {
       if(WaysCompare(wayx2->way,wayx1->way))
          difference=1;

       segcount+=1;
      }

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

 printf("\rFound Super-Nodes: (Super-)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)
{
 index_t i;
 SegmentsX *supersegmentsx;
 int sn=0,ss=0;

 assert(nodesx->idata);         /* Must have idata filled in */

 printf("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
 fflush(stdout);

 supersegmentsx=NewSegmentList();

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

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

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

       while(segmentx)
         {
          WayX *wayx=FindWayX(waysx,(*segmentx)->way);

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

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

             while(othersegmentx && othersegmentx!=segmentx)
               {
                WayX *otherwayx=FindWayX(waysx,(*othersegmentx)->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->idata[i]->id,wayx->way,iteration);
             Result *result=FirstResult(results);

             while(result)
               {
                NodeX **nodex=FindNodeX(nodesx,result->node);
                WayX   *wayx =FindWayX (waysx ,(*segmentx)->way);

                if(result->node!=nodesx->idata[i]->id && (*nodex)->super>iteration)
                  {
                   if(wayx->way->type&Way_OneWay)
                     {
                      AppendSegment(supersegmentsx,wayx->id,nodesx->idata[i]->id,result->node,DISTANCE((distance_t)result->score)|ONEWAY_1TO2);

                      AppendSegment(supersegmentsx,wayx->id,result->node,nodesx->idata[i]->id,DISTANCE((distance_t)result->score)|ONEWAY_2TO1);

                      ss+=2;
                     }
                   else
                     {
                      AppendSegment(supersegmentsx,wayx->id,result->node,nodesx->idata[i]->id,DISTANCE((distance_t)result->score));

                      ss++;
                     }
                  }

                result=NextResult(results,result);
               }

             FreeResultsList(results);
            }

          segmentx=FindNextSegmentX(segmentsx,segmentx);
         }

       sn++;
      }

    if(!(sn%10000))
      {
       printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
       fflush(stdout);
      }
   }

 printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",sn,ss);
 fflush(stdout);

 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)
{
 index_t i,j;
 int m=0,a=0;

 assert(segmentsx->sorted);      /* Must be sorted */
 assert(segmentsx->ndata);       /* Must have ndata filled in */
 assert(supersegmentsx->sorted); /* Must be sorted */
 assert(supersegmentsx->ndata);  /* Must have ndata filled in */

 printf("Merging: Segments=0 Super-Segments=0 Merged=0 Added=0");
 fflush(stdout);

 for(i=0,j=0;i<segmentsx->number;i++)
   {
    while(j<supersegmentsx->number)
      {
       if(segmentsx->ndata[i]->node1==supersegmentsx->ndata[j]->node1 &&
          segmentsx->ndata[i]->node2==supersegmentsx->ndata[j]->node2 &&
          segmentsx->ndata[i]->distance==supersegmentsx->ndata[j]->distance)
         {
          segmentsx->ndata[i]->distance|=SEGMENT_SUPER; /* mark as super-segment */
          m++;
          j++;
          break;
         }
       else if((segmentsx->ndata[i]->node1==supersegmentsx->ndata[j]->node1 &&
                segmentsx->ndata[i]->node2==supersegmentsx->ndata[j]->node2) ||
               (segmentsx->ndata[i]->node1==supersegmentsx->ndata[j]->node1 &&
                segmentsx->ndata[i]->node2>supersegmentsx->ndata[j]->node2) ||
               (segmentsx->ndata[i]->node1>supersegmentsx->ndata[j]->node1))
         {
          supersegmentsx->ndata[j]->distance|=SEGMENT_SUPER; /* mark as super-segment */
          AppendSegment(segmentsx,supersegmentsx->ndata[j]->way,supersegmentsx->ndata[j]->node1,supersegmentsx->ndata[j]->node2,supersegmentsx->ndata[j]->distance);
          a++;
          j++;
         }
       else
          break;
      }

    segmentsx->ndata[i]->distance|=SEGMENT_NORMAL; /* mark as normal segment */

    if(!((i+1)%10000))
      {
       printf("\rMerging: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
       fflush(stdout);
      }
   }

 printf("\rMerged: Segments=%d Super-Segments=%d Merged=%d Added=%d \n",segmentsx->number,supersegmentsx->number,m,a);
 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.

  Way *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,Way *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)->distance&ONEWAY_2TO1)
          goto endloop;

       node2=(*segmentx)->node2;

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

       wayx=FindWayX(waysx,(*segmentx)->way);

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

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