trunk/src/superx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/superx.c,v 1.36 2009-10-22 18:17:51 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 "functions.h"
#include "nodesx.h"
#include "segmentsx.h"
#include "waysx.h"
#include "superx.h"
#include "ways.h"


/* Variables */

/*+ The command line '--slim' option. +*/
extern int option_slim;

/* Local Functions */

static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration);


/*++++++++++++++++++++++++++++++++++++++
  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 nnodes=0;

 /* Check the start conditions */

 assert(segmentsx->firstnode); /* Must have firstnode filled in => segments are updated */

 /* Print the start message */

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

 /* Map into memory */

 if(!option_slim)
   {
    segmentsx->xdata=MapFile(segmentsx->filename);
    waysx->xdata=MapFile(waysx->filename);
   }

 /* Find super-nodes */

 for(i=0;i<nodesx->number;i++)
   {
    int     difference=0;
    index_t index;

    index=IndexFirstSegmentX(segmentsx,i);

    if(index!=NO_SEGMENT)
      {
       SegmentX *segmentx1=LookupSegmentX(segmentsx,index,1);
       WayX *wayx1=LookupWayX(waysx,segmentx1->way,1);

       index=IndexNextSegmentX(segmentsx,index,i);

       if(index!=NO_SEGMENT)
         {
          SegmentX *segmentx2=LookupSegmentX(segmentsx,index,2);
          WayX *wayx2=LookupWayX(waysx,segmentx2->way,2);

          if(WaysCompare(&wayx2->way,&wayx1->way))
             difference=1;

          index=IndexNextSegmentX(segmentsx,index,i);
         }

       /* Store the node if there is a difference in the first two ways that could affect routing.
          Store the node if it has at least three segments. */

       if(difference || index!=NO_SEGMENT)
         {
          nodesx->super[i]++;

          nnodes++;
         }
      }

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

 /* Unmap from memory */

 if(!option_slim)
   {
    segmentsx->xdata=UnmapFile(segmentsx->filename);
    waysx->xdata=UnmapFile(waysx->filename);
   }

 /* Print the final message */

 printf("\rFound Super-Nodes: Nodes=%d Super-Nodes=%d  \n",nodesx->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;

 /* Check the start conditions */

 assert(segmentsx->firstnode); /* Must have firstnode filled in => segments are updated */

 /* Print the start message */

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

 /* Map into memory */

 if(!option_slim)
   {
    segmentsx->xdata=MapFile(segmentsx->filename);
    waysx->xdata=MapFile(waysx->filename);
   }

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

 supersegmentsx=NewSegmentList();

 for(i=0;i<nodesx->number;i++)
   {
    if(nodesx->super[i]>iteration)
      {
       index_t index,first;

       index=first=IndexFirstSegmentX(segmentsx,i);

       while(index!=NO_SEGMENT)
         {
          SegmentX *segmentx=LookupSegmentX(segmentsx,index,1);
          WayX *wayx=LookupWayX(waysx,segmentx->way,1);

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

          if(index!=first)
            {
             index_t otherindex=first;

             while(otherindex!=NO_SEGMENT && otherindex!=index)
               {
                SegmentX *othersegmentx=LookupSegmentX(segmentsx,otherindex,2);
                WayX *otherwayx=LookupWayX(waysx,othersegmentx->way,2);

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

                otherindex=IndexNextSegmentX(segmentsx,otherindex,i);
               }
            }

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

          if(wayx)
            {
             Results *results=FindRoutesWay(nodesx,segmentsx,waysx,i,&wayx->way,iteration);
             Result *result=FirstResult(results);

             while(result)
               {
                if(result->node!=i && nodesx->super[result->node]>iteration)
                  {
                   if(wayx->way.type&Way_OneWay)
                     {
                      AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score)|ONEWAY_1TO2);
                      AppendSegment(supersegmentsx,segmentx->way,result->node,i,DISTANCE((distance_t)result->score)|ONEWAY_2TO1);
                     }
                   else
                      AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score));

                   ss++;
                  }

                result=NextResult(results,result);
               }

             FreeResultsList(results);
            }

          index=IndexNextSegmentX(segmentsx,index,i);
         }

       sn++;

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

 /* Unmap from memory */

 if(!option_slim)
   {
    segmentsx->xdata=UnmapFile(segmentsx->filename);
    waysx->xdata=UnmapFile(waysx->filename);
   }

 /* Print the final message */

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

 return(supersegmentsx);
}


/*++++++++++++++++++++++++++++++++++++++
  Merge the segments and super-segments into a new segment list.

  SegmentsX* MergeSuperSegments Returns a new set of merged segments.

  SegmentsX* segmentsx The set of segments to process.

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

SegmentsX *MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx)
{
 index_t i,j;
 int m=0,a=0;
 SegmentsX* mergedsegmentsx;

 /* Print the start message */

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

 /* Map into memory */

 if(!option_slim)
   {
    segmentsx->xdata=MapFile(segmentsx->filename);
    supersegmentsx->xdata=MapFile(supersegmentsx->filename);
   }

 /* Loop through and create a new list of combined segments */

 mergedsegmentsx=NewSegmentList();

 for(i=0,j=0;i<segmentsx->number;i++)
   {
    int super=0;
    SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);

    while(j<supersegmentsx->number)
      {
       SegmentX *supersegmentx=LookupSegmentX(supersegmentsx,j,1);

       if(segmentx->node1   ==supersegmentx->node1 &&
          segmentx->node2   ==supersegmentx->node2 &&
          segmentx->distance==supersegmentx->distance)
         {
          m++;
          j++;
          /* mark as super-segment and normal segment */
          super=1;
          break;
         }
       else if((segmentx->node1==supersegmentx->node1 &&
                segmentx->node2==supersegmentx->node2) ||
               (segmentx->node1==supersegmentx->node1 &&
                segmentx->node2>supersegmentx->node2) ||
               (segmentx->node1>supersegmentx->node1))
         {
          /* mark as super-segment */
          AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance|SEGMENT_SUPER);
          a++;
          j++;
         }
       else
         {
          /* mark as normal segment */
          break;
         }
      }

    if(super)
       AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_SUPER|SEGMENT_NORMAL);
    else
       AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_NORMAL);

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

 /* Unmap from memory */

 if(!option_slim)
   {
    segmentsx->xdata=UnmapFile(segmentsx->filename);
    supersegmentsx->xdata=UnmapFile(supersegmentsx->filename);
   }

 /* Print the final message */

 printf("\rMerged: Segments=%d Super-Segments=%d Merged=%d Added=%d \n",segmentsx->number,supersegmentsx->number,m,a);
 fflush(stdout);

 return(mergedsegmentsx);
}


/*++++++++++++++++++++++++++++++++++++++
  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.
  ++++++++++++++++++++++++++++++++++++++*/

static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration)
{
 Results *results;
 Queue *queue;
 index_t node1,node2;
 Result *result1,*result2;
 index_t index;
 WayX *wayx;

 /* Insert the first node into the queue */

 results=NewResultsList(8);

 queue=NewQueueList();

 result1=InsertResult(results,start);

 ZeroResult(result1);

 InsertInQueue(queue,result1);

 /* Loop across all nodes in the queue */

 while((result1=PopFromQueue(queue)))
   {
    node1=result1->node;

    index=IndexFirstSegmentX(segmentsx,node1);

    while(index!=NO_SEGMENT)
      {
       SegmentX *segmentx=LookupSegmentX(segmentsx,index,2); /* must use 2 here */
       distance_t cumulative_distance;

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

       node2=segmentx->node2;

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

       wayx=LookupWayX(waysx,segmentx->way,2);

       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;

          if(nodesx->super[node2]<=iteration)
             InsertInQueue(queue,result2);
         }
       else if(cumulative_distance<result2->score)
         {
          result2->prev=node1;
          result2->score=cumulative_distance;
          result2->sortby=cumulative_distance;

          if(nodesx->super[node2]<=iteration)
             InsertInQueue(queue,result2);
         }

      endloop:

       index=IndexNextSegmentX(segmentsx,index,node1);
      }
   }

 FreeQueueList(queue);

 return(results);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/superx.c,v 1.36 2009-10-22 18:17:51 amb Exp $
3
4	Super-Segment data type functions.
5
6	Part of the Routino routing software.
7	****************/ /****************
8	This file Copyright 2008,2009 Andrew M. Bishop
9
10	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	***************************************/
23
24
25	#include <assert.h>
26	#include <stdlib.h>
27	#include <stdio.h>
28
29	#include "results.h"
30	#include "functions.h"
31	#include "nodesx.h"
32	#include "segmentsx.h"
33	#include "waysx.h"
34	#include "superx.h"
35	#include "ways.h"
36
37
38	/* Variables */
39
40	/+ The command line '--slim' option. +/
41	extern int option_slim;
42
43	/* Local Functions */
44
45	static Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,Way *match,int iteration);
46
47
48	/*++++++++++++++++++++++++++++++++++++++
49	Select the super-segments from the list of segments.
50
51	NodesX *nodesx The nodes.
52
53	SegmentsX *segmentsx The segments.
54
55	WaysX *waysx The ways.
56	++++++++++++++++++++++++++++++++++++++*/
57
58	void ChooseSuperNodes(NodesX nodesx,SegmentsX segmentsx,WaysX *waysx)
59	{
60	index_t i;
61	int nnodes=0;
62
63	/* Check the start conditions */
64
65	assert(segmentsx->firstnode); /* Must have firstnode filled in => segments are updated */
66
67	/* Print the start message */
68
69	printf("Finding Super-Nodes: Nodes=0 Super-Nodes=0");
70	fflush(stdout);
71
72	/* Map into memory */
73
74	if(!option_slim)
75	{
76	segmentsx->xdata=MapFile(segmentsx->filename);
77	waysx->xdata=MapFile(waysx->filename);
78	}
79
80	/* Find super-nodes */
81
82	for(i=0;i<nodesx->number;i++)
83	{
84	int difference=0;
85	index_t index;
86
87	index=IndexFirstSegmentX(segmentsx,i);
88
89	if(index!=NO_SEGMENT)
90	{
91	SegmentX *segmentx1=LookupSegmentX(segmentsx,index,1);
92	WayX *wayx1=LookupWayX(waysx,segmentx1->way,1);
93
94	index=IndexNextSegmentX(segmentsx,index,i);
95
96	if(index!=NO_SEGMENT)
97	{
98	SegmentX *segmentx2=LookupSegmentX(segmentsx,index,2);
99	WayX *wayx2=LookupWayX(waysx,segmentx2->way,2);
100
101	if(WaysCompare(&wayx2->way,&wayx1->way))
102	difference=1;
103
104	index=IndexNextSegmentX(segmentsx,index,i);
105	}
106
107	/* Store the node if there is a difference in the first two ways that could affect routing.
108	Store the node if it has at least three segments. */
109
110	if(difference \|\| index!=NO_SEGMENT)
111	{
112	nodesx->super[i]++;
113
114	nnodes++;
115	}
116	}
117
118	if(!((i+1)%10000))
119	{
120	printf("\rFinding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
121	fflush(stdout);
122	}
123	}
124
125	/* Unmap from memory */
126
127	if(!option_slim)
128	{
129	segmentsx->xdata=UnmapFile(segmentsx->filename);
130	waysx->xdata=UnmapFile(waysx->filename);
131	}
132
133	/* Print the final message */
134
135	printf("\rFound Super-Nodes: Nodes=%d Super-Nodes=%d \n",nodesx->number,nnodes);
136	fflush(stdout);
137	}
138
139
140	/*++++++++++++++++++++++++++++++++++++++
141	Create the super-segments.
142
143	SegmentsX *CreateSuperSegments Creates the super segments.
144
145	NodesX *nodesx The nodes.
146
147	SegmentsX *segmentsx The segments.
148
149	WaysX *waysx The ways.
150
151	int iteration The current super-node / super-segment iteration number.
152	++++++++++++++++++++++++++++++++++++++*/
153
154	SegmentsX CreateSuperSegments(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,int iteration)
155	{
156	index_t i;
157	SegmentsX *supersegmentsx;
158	int sn=0,ss=0;
159
160	/* Check the start conditions */
161
162	assert(segmentsx->firstnode); /* Must have firstnode filled in => segments are updated */
163
164	/* Print the start message */
165
166	printf("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
167	fflush(stdout);
168
169	/* Map into memory */
170
171	if(!option_slim)
172	{
173	segmentsx->xdata=MapFile(segmentsx->filename);
174	waysx->xdata=MapFile(waysx->filename);
175	}
176
177	/* Create super-segments for each super-node. */
178
179	supersegmentsx=NewSegmentList();
180
181	for(i=0;i<nodesx->number;i++)
182	{
183	if(nodesx->super[i]>iteration)
184	{
185	index_t index,first;
186
187	index=first=IndexFirstSegmentX(segmentsx,i);
188
189	while(index!=NO_SEGMENT)
190	{
191	SegmentX *segmentx=LookupSegmentX(segmentsx,index,1);
192	WayX *wayx=LookupWayX(waysx,segmentx->way,1);
193
194	/* Check that this type of way hasn't already been routed */
195
196	if(index!=first)
197	{
198	index_t otherindex=first;
199
200	while(otherindex!=NO_SEGMENT && otherindex!=index)
201	{
202	SegmentX *othersegmentx=LookupSegmentX(segmentsx,otherindex,2);
203	WayX *otherwayx=LookupWayX(waysx,othersegmentx->way,2);
204
205	if(!WaysCompare(&otherwayx->way,&wayx->way))
206	{
207	wayx=NULL;
208	break;
209	}
210
211	otherindex=IndexNextSegmentX(segmentsx,otherindex,i);
212	}
213	}
214
215	/* Route the way and store the super-segments. */
216
217	if(wayx)
218	{
219	Results *results=FindRoutesWay(nodesx,segmentsx,waysx,i,&wayx->way,iteration);
220	Result *result=FirstResult(results);
221
222	while(result)
223	{
224	if(result->node!=i && nodesx->super[result->node]>iteration)
225	{
226	if(wayx->way.type&Way_OneWay)
227	{
228	AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score)\|ONEWAY_1TO2);
229	AppendSegment(supersegmentsx,segmentx->way,result->node,i,DISTANCE((distance_t)result->score)\|ONEWAY_2TO1);
230	}
231	else
232	AppendSegment(supersegmentsx,segmentx->way,i,result->node,DISTANCE((distance_t)result->score));
233
234	ss++;
235	}
236
237	result=NextResult(results,result);
238	}
239
240	FreeResultsList(results);
241	}
242
243	index=IndexNextSegmentX(segmentsx,index,i);
244	}
245
246	sn++;
247
248	if(!(sn%10000))
249	{
250	printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
251	fflush(stdout);
252	}
253	}
254	}
255
256	/* Unmap from memory */
257
258	if(!option_slim)
259	{
260	segmentsx->xdata=UnmapFile(segmentsx->filename);
261	waysx->xdata=UnmapFile(waysx->filename);
262	}
263
264	/* Print the final message */
265
266	printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",sn,ss);
267	fflush(stdout);
268
269	return(supersegmentsx);
270	}
271
272
273	/*++++++++++++++++++++++++++++++++++++++
274	Merge the segments and super-segments into a new segment list.
275
276	SegmentsX* MergeSuperSegments Returns a new set of merged segments.
277
278	SegmentsX* segmentsx The set of segments to process.
279
280	SegmentsX* supersegmentsx The set of super-segments to merge.
281	++++++++++++++++++++++++++++++++++++++*/
282
283	SegmentsX MergeSuperSegments(SegmentsX segmentsx,SegmentsX* supersegmentsx)
284	{
285	index_t i,j;
286	int m=0,a=0;
287	SegmentsX* mergedsegmentsx;
288
289	/* Print the start message */
290
291	printf("Merging: Segments=0 Super-Segments=0 Merged=0 Added=0");
292	fflush(stdout);
293
294	/* Map into memory */
295
296	if(!option_slim)
297	{
298	segmentsx->xdata=MapFile(segmentsx->filename);
299	supersegmentsx->xdata=MapFile(supersegmentsx->filename);
300	}
301
302	/* Loop through and create a new list of combined segments */
303
304	mergedsegmentsx=NewSegmentList();
305
306	for(i=0,j=0;i<segmentsx->number;i++)
307	{
308	int super=0;
309	SegmentX *segmentx=LookupSegmentX(segmentsx,i,1);
310
311	while(j<supersegmentsx->number)
312	{
313	SegmentX *supersegmentx=LookupSegmentX(supersegmentsx,j,1);
314
315	if(segmentx->node1 ==supersegmentx->node1 &&
316	segmentx->node2 ==supersegmentx->node2 &&
317	segmentx->distance==supersegmentx->distance)
318	{
319	m++;
320	j++;
321	/* mark as super-segment and normal segment */
322	super=1;
323	break;
324	}
325	else if((segmentx->node1==supersegmentx->node1 &&
326	segmentx->node2==supersegmentx->node2) \|\|
327	(segmentx->node1==supersegmentx->node1 &&
328	segmentx->node2>supersegmentx->node2) \|\|
329	(segmentx->node1>supersegmentx->node1))
330	{
331	/* mark as super-segment */
332	AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance\|SEGMENT_SUPER);
333	a++;
334	j++;
335	}
336	else
337	{
338	/* mark as normal segment */
339	break;
340	}
341	}
342
343	if(super)
344	AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance\|SEGMENT_SUPER\|SEGMENT_NORMAL);
345	else
346	AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance\|SEGMENT_NORMAL);
347
348	if(!((i+1)%10000))
349	{
350	printf("\rMerging: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
351	fflush(stdout);
352	}
353	}
354
355	/* Unmap from memory */
356
357	if(!option_slim)
358	{
359	segmentsx->xdata=UnmapFile(segmentsx->filename);
360	supersegmentsx->xdata=UnmapFile(supersegmentsx->filename);
361	}
362
363	/* Print the final message */
364
365	printf("\rMerged: Segments=%d Super-Segments=%d Merged=%d Added=%d \n",segmentsx->number,supersegmentsx->number,m,a);
366	fflush(stdout);
367
368	return(mergedsegmentsx);
369	}
370
371
372	/*++++++++++++++++++++++++++++++++++++++
373	Find all routes from a specified node to any node in the specified list that follows a certain type of way.
374
375	Results *FindRoutesWay Returns a set of results.
376
377	NodesX *nodesx The set of nodes to use.
378
379	SegmentsX *segmentsx The set of segments to use.
380
381	WaysX *waysx The set of ways to use.
382
383	node_t start The start node.
384
385	Way *match The way that the route must match.
386
387	int iteration The current super-node / super-segment iteration number.
388	++++++++++++++++++++++++++++++++++++++*/
389
390	static Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,Way *match,int iteration)
391	{
392	Results *results;
393	Queue *queue;
394	index_t node1,node2;
395	Result result1,result2;
396	index_t index;
397	WayX *wayx;
398
399	/* Insert the first node into the queue */
400
401	results=NewResultsList(8);
402
403	queue=NewQueueList();
404
405	result1=InsertResult(results,start);
406
407	ZeroResult(result1);
408
409	InsertInQueue(queue,result1);
410
411	/* Loop across all nodes in the queue */
412
413	while((result1=PopFromQueue(queue)))
414	{
415	node1=result1->node;
416
417	index=IndexFirstSegmentX(segmentsx,node1);
418
419	while(index!=NO_SEGMENT)
420	{
421	SegmentX segmentx=LookupSegmentX(segmentsx,index,2); / must use 2 here */
422	distance_t cumulative_distance;
423
424	if(segmentx->distance&ONEWAY_2TO1)
425	goto endloop;
426
427	node2=segmentx->node2;
428
429	if(result1->prev==node2)
430	goto endloop;
431
432	wayx=LookupWayX(waysx,segmentx->way,2);
433
434	if(WaysCompare(&wayx->way,match))
435	goto endloop;
436
437	cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance);
438
439	result2=FindResult(results,node2);
440
441	if(!result2) /* New end node */
442	{
443	result2=InsertResult(results,node2);
444	result2->prev=node1;
445	result2->next=NO_NODE;
446	result2->score=cumulative_distance;
447	result2->sortby=cumulative_distance;
448
449	if(nodesx->super[node2]<=iteration)
450	InsertInQueue(queue,result2);
451	}
452	else if(cumulative_distance<result2->score)
453	{
454	result2->prev=node1;
455	result2->score=cumulative_distance;
456	result2->sortby=cumulative_distance;
457
458	if(nodesx->super[node2]<=iteration)
459	InsertInQueue(queue,result2);
460	}
461
462	endloop:
463
464	index=IndexNextSegmentX(segmentsx,index,node1);
465	}
466	}
467
468	FreeQueueList(queue);
469
470	return(results);
471	}