trunk/src/superx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/superx.c,v 1.1 2009-02-07 15:57:34 amb Exp $

 Super-Segment data type functions.
 ******************/ /******************
 Written by Andrew M. Bishop

 This file Copyright 2008,2009 Andrew M. Bishop
 It may be distributed under the GNU Public License, version 2, or
 any higher version.  See section COPYING of the GNU Public license
 for conditions under which this file may be redistributed.
 ***************************************/


#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;
 speed_t    limit=0;
 waytype_t  type=0;
 wayallow_t allow=0;

 /* 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;
       type=wayx->way.type;
       limit=wayx->way.limit;
       allow=wayx->way.allow;
      }
    else                        /* Same starting node */
      {
       if(wayx->way.type!=type)
          difference=1;

       if(wayx->way.limit!=limit)
          difference=1;

       if(wayx->way.allow!=allow)
          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(otherwayx->way.type ==wayx->way.type  &&
                   otherwayx->way.allow==wayx->way.allow &&
                   otherwayx->way.limit==wayx->way.limit)
                  {
                   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);

                   supersegment->distance=result->shortest.distance;
                   supersegment->way=IndexWayX(waysx,wayx);

                   if(wayx->way.type&Way_OneWay)
                     {
                      supersegment->distance=ONEWAY_1TO2|result->shortest.distance;

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

                      supersegment->distance=ONEWAY_2TO1|result->shortest.distance;
                      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.next1=~0;
    segmentsx->sdata[i]->segment.next2=~0;

    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 */
          j++;
          break;
         }
       else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
               segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2)
         {
          Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);

          *supersegment=supersegmentsx->sdata[j]->segment;
          supersegment->node2=SUPER_FLAG; /* mark as super-segment */
          supersegment->next1=~0;
          supersegment->next2=~0;
         }
       else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
               segmentsx->sdata[i]->node2>supersegmentsx->sdata[j]->node2)
         {
          Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);

          *supersegment=supersegmentsx->sdata[j]->segment;
          supersegment->node2=SUPER_FLAG; /* mark as super-segment */
          supersegment->next1=~0;
          supersegment->next2=~0;
         }
       else if(segmentsx->sdata[i]->node1>supersegmentsx->sdata[j]->node1)
         {
          Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);

          *supersegment=supersegmentsx->sdata[j]->segment;
          supersegment->node2=SUPER_FLAG; /* mark as super-segment */
          supersegment->next1=~0;
          supersegment->next2=~0;
         }
       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);
      }
   }

 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;
 HalfResult shortest2;
 Result *result1,*result2;
 NodeX *nodex;
 SegmentX **segmentx;
 WayX *wayx;

 /* Insert the first node into the queue */

 results=NewResultsList(8);

 result1=InsertResult(results,start);

 result1->node=start;
 result1->shortest.prev=0;
 result1->shortest.next=0;
 result1->shortest.distance=0;

 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)
      {
       if((*segmentx)->segment.distance&ONEWAY_2TO1)
          goto endloop;

       node2=(*segmentx)->node2;

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

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

       if(wayx->way.type !=match->way.type  ||
          wayx->way.allow!=match->way.allow ||
          wayx->way.limit!=match->way.limit)
          goto endloop;

       shortest2.distance=result1->shortest.distance+DISTANCE((*segmentx)->segment.distance);

       result2=FindResult(results,node2);

       if(!result2)                         /* New end node */
         {
          result2=InsertResult(results,node2);
          result2->node=node2;
          result2->shortest.prev=node1;
          result2->shortest.next=0;
          result2->shortest.distance=shortest2.distance;

          nodex=FindNodeX(nodesx,node2);

          if(nodex->super<=iteration)
             insert_in_queue(result2);
         }
       else
         {
          if(shortest2.distance<result2->shortest.distance)
            {
             result2->shortest.prev=node1;
             result2->shortest.distance=shortest2.distance;

             nodex=FindNodeX(nodesx,node2);

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

      endloop:

       segmentx=FindNextSegmentX(segmentsx,segmentx);
      }
   }

 return(results);
}
1	amb	110	/***************************************
2			$Header: /home/amb/CVS/routino/src/superx.c,v 1.1 2009-02-07 15:57:34 amb Exp $
3
4			Super-Segment data type functions.
5			****************/ /****************
6			Written by Andrew M. Bishop
7
8			This file Copyright 2008,2009 Andrew M. Bishop
9			It may be distributed under the GNU Public License, version 2, or
10			any higher version. See section COPYING of the GNU Public license
11			for conditions under which this file may be redistributed.
12			***************************************/
13
14
15			#include <assert.h>
16			#include <math.h>
17			#include <stdlib.h>
18			#include <stdio.h>
19
20			#include "results.h"
21			#include "nodesx.h"
22			#include "segmentsx.h"
23			#include "waysx.h"
24			#include "superx.h"
25
26
27			/*++++++++++++++++++++++++++++++++++++++
28			Select the super-segments from the list of segments.
29
30			NodesX *nodesx The nodes.
31
32			SegmentsX *segmentsx The segments.
33
34			WaysX *waysx The ways.
35
36			int iteration The current super-node / super-segment iteration number.
37			++++++++++++++++++++++++++++++++++++++*/
38
39			void ChooseSuperNodes(NodesX nodesx,SegmentsX segmentsx,WaysX *waysx,int iteration)
40			{
41			int i;
42			int segcount=0,difference=0,nnodes=0;
43			node_t node=0;
44			speed_t limit=0;
45			waytype_t type=0;
46			wayallow_t allow=0;
47
48			/* Find super-nodes */
49
50			node=segmentsx->sdata[0]->node1;
51
52			for(i=0;i<segmentsx->number;i++)
53			{
54			SegmentX *segmentx=LookupSegmentX(segmentsx,i);
55			WayX *wayx=LookupWayX(waysx,segmentx->segment.way);
56
57			if(segmentx->node1!=node)
58			{
59			/* Store the node if there is a difference in the ways that could affect routing.
60			Store the node if it is not a dead-end and if it isn't just the middle of a way. */
61
62			if(difference \|\| segcount>2)
63			{
64			NodeX *nodex=FindNodeX(nodesx,node);
65
66			nodex->super++;
67
68			nnodes++;
69			}
70
71			segcount=1;
72			difference=0;
73
74			node=segmentx->node1;
75			type=wayx->way.type;
76			limit=wayx->way.limit;
77			allow=wayx->way.allow;
78			}
79			else /* Same starting node */
80			{
81			if(wayx->way.type!=type)
82			difference=1;
83
84			if(wayx->way.limit!=limit)
85			difference=1;
86
87			if(wayx->way.allow!=allow)
88			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			if(otherwayx->way.type ==wayx->way.type &&
151			otherwayx->way.allow==wayx->way.allow &&
152			otherwayx->way.limit==wayx->way.limit)
153			{
154			wayx=NULL;
155			break;
156			}
157
158			othersegmentx=FindNextSegmentX(segmentsx,othersegmentx);
159			}
160			}
161
162			/* Route the way and store the super-segments. */
163
164			if(wayx)
165			{
166			Results *results=FindRoutesWay(nodesx,segmentsx,waysx,nodesx->gdata[i]->id,wayx,iteration);
167			Result *result=FirstResult(results);
168
169			while(result)
170			{
171			NodeX *nodex=FindNodeX(nodesx,result->node);
172
173			if(result->node!=nodesx->gdata[i]->id && nodex->super>iteration)
174			{
175			Segment *supersegment=AppendSegment(supersegmentsx,nodesx->gdata[i]->id,result->node);
176
177			supersegment->distance=result->shortest.distance;
178			supersegment->way=IndexWayX(waysx,wayx);
179
180			if(wayx->way.type&Way_OneWay)
181			{
182			supersegment->distance=ONEWAY_1TO2\|result->shortest.distance;
183
184			supersegment=AppendSegment(supersegmentsx,result->node,nodesx->gdata[i]->id);
185
186			supersegment->distance=ONEWAY_2TO1\|result->shortest.distance;
187			supersegment->way=IndexWayX(waysx,wayx);
188			}
189			}
190
191			result=NextResult(results,result);
192			}
193
194			FreeResultsList(results);
195			}
196
197			segmentx=FindNextSegmentX(segmentsx,segmentx);
198			}
199			}
200
201			if(!((i+1)%10000))
202			{
203			printf("\rCreating Super-Segments: Nodes=%d Super-Segments=%d",i+1,supersegmentsx->xnumber);
204			fflush(stdout);
205			}
206			}
207
208			printf("\rCreated Super-Segments: Nodes=%d Super-Segments=%d \n",nodesx->number,supersegmentsx->xnumber);
209			fflush(stdout);
210
211			/* Append the new supersegments onto the segments. */
212
213			return(supersegmentsx);
214			}
215
216
217			/*++++++++++++++++++++++++++++++++++++++
218			Merge the super-segments into the segments.
219
220			SegmentsX* segmentsx The set of segments to process.
221
222			SegmentsX* supersegmentsx The set of super-segments to merge.
223			++++++++++++++++++++++++++++++++++++++*/
224
225			void MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx)
226			{
227			int i,j,n;
228
229			assert(segmentsx->sorted); /* Must be sorted */
230			assert(supersegmentsx->sorted); /* Must be sorted */
231
232			n=segmentsx->number;
233
234			for(i=0,j=0;i<n;i++)
235			{
236			segmentsx->sdata[i]->segment.node1=SUPER_FLAG; /* mark as normal segment */
237
238			segmentsx->sdata[i]->segment.next1=~0;
239			segmentsx->sdata[i]->segment.next2=~0;
240
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			j++;
249			break;
250			}
251			else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
252			segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2)
253			{
254			Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);
255
256			*supersegment=supersegmentsx->sdata[j]->segment;
257			supersegment->node2=SUPER_FLAG; /* mark as super-segment */
258			supersegment->next1=~0;
259			supersegment->next2=~0;
260			}
261			else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
262			segmentsx->sdata[i]->node2>supersegmentsx->sdata[j]->node2)
263			{
264			Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);
265
266			*supersegment=supersegmentsx->sdata[j]->segment;
267			supersegment->node2=SUPER_FLAG; /* mark as super-segment */
268			supersegment->next1=~0;
269			supersegment->next2=~0;
270			}
271			else if(segmentsx->sdata[i]->node1>supersegmentsx->sdata[j]->node1)
272			{
273			Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);
274
275			*supersegment=supersegmentsx->sdata[j]->segment;
276			supersegment->node2=SUPER_FLAG; /* mark as super-segment */
277			supersegment->next1=~0;
278			supersegment->next2=~0;
279			}
280			else
281			break;
282
283			j++;
284			}
285
286			if(!((i+1)%10000))
287			{
288			printf("\rMerging Segments: Segments=%d Super-Segment=%d Total=%d",i+1,j+1,segmentsx->xnumber);
289			fflush(stdout);
290			}
291			}
292
293			printf("\rMerged Segments: Segments=%d Super-Segment=%d Total=%d \n",n,supersegmentsx->number,segmentsx->xnumber);
294			fflush(stdout);
295			}
296
297
298			/*++++++++++++++++++++++++++++++++++++++
299			Find all routes from a specified node to any node in the specified list that follows a certain type of way.
300
301			Results *FindRoutesWay Returns a set of results.
302
303			NodesX *nodesx The set of nodes to use.
304
305			SegmentsX *segmentsx The set of segments to use.
306
307			WaysX *waysx The set of ways to use.
308
309			node_t start The start node.
310
311			WayX *match The way that the route must match.
312
313			int iteration The current super-node / super-segment iteration number.
314			++++++++++++++++++++++++++++++++++++++*/
315
316			Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,WayX *match,int iteration)
317			{
318			Results *results;
319			index_t node1,node2;
320			HalfResult shortest2;
321			Result result1,result2;
322			NodeX *nodex;
323			SegmentX **segmentx;
324			WayX *wayx;
325
326			/* Insert the first node into the queue */
327
328			results=NewResultsList(8);
329
330			result1=InsertResult(results,start);
331
332			result1->node=start;
333			result1->shortest.prev=0;
334			result1->shortest.next=0;
335			result1->shortest.distance=0;
336
337			insert_in_queue(result1);
338
339			/* Loop across all nodes in the queue */
340
341			while((result1=pop_from_queue()))
342			{
343			node1=result1->node;
344
345			segmentx=FindFirstSegmentX(segmentsx,node1);
346
347			while(segmentx)
348			{
349			if((*segmentx)->segment.distance&ONEWAY_2TO1)
350			goto endloop;
351
352			node2=(*segmentx)->node2;
353
354			if(result1->shortest.prev==node2)
355			goto endloop;
356
357			wayx=LookupWayX(waysx,(*segmentx)->segment.way);
358
359			if(wayx->way.type !=match->way.type \|\|
360			wayx->way.allow!=match->way.allow \|\|
361			wayx->way.limit!=match->way.limit)
362			goto endloop;
363
364			shortest2.distance=result1->shortest.distance+DISTANCE((*segmentx)->segment.distance);
365
366			result2=FindResult(results,node2);
367
368			if(!result2) /* New end node */
369			{
370			result2=InsertResult(results,node2);
371			result2->node=node2;
372			result2->shortest.prev=node1;
373			result2->shortest.next=0;
374			result2->shortest.distance=shortest2.distance;
375
376			nodex=FindNodeX(nodesx,node2);
377
378			if(nodex->super<=iteration)
379			insert_in_queue(result2);
380			}
381			else
382			{
383			if(shortest2.distance<result2->shortest.distance)
384			{
385			result2->shortest.prev=node1;
386			result2->shortest.distance=shortest2.distance;
387
388			nodex=FindNodeX(nodesx,node2);
389
390			if(nodex->super<=iteration)
391			insert_in_queue(result2);
392			}
393			}
394
395			endloop:
396
397			segmentx=FindNextSegmentX(segmentsx,segmentx);
398			}
399			}
400
401			return(results);
402			}