trunk/src/superx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/superx.c,v 1.2 2009-02-08 15:30:07 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->distance;
                   supersegment->way=IndexWayX(waysx,wayx);

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

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

                      supersegment->distance=ONEWAY_2TO1|result->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;
 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->prev=0;
 result1->next=0;
 result1->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)
      {
       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(wayx->way.type !=match->way.type  ||
          wayx->way.allow!=match->way.allow ||
          wayx->way.limit!=match->way.limit)
          goto endloop;

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

       result2=FindResult(results,node2);

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

          nodex=FindNodeX(nodesx,node2);

          if(nodex->super<=iteration)
             insert_in_queue(result2);
         }
       else
         {
          if(cumulative_distance<result2->distance)
            {
             result2->prev=node1;
             result2->distance=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	113	$Header: /home/amb/CVS/routino/src/superx.c,v 1.2 2009-02-08 15:30:07 amb Exp $
3	amb	110
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	amb	113	supersegment->distance=result->distance;
178	amb	110	supersegment->way=IndexWayX(waysx,wayx);
179
180			if(wayx->way.type&Way_OneWay)
181			{
182	amb	113	supersegment->distance=ONEWAY_1TO2\|result->distance;
183	amb	110
184			supersegment=AppendSegment(supersegmentsx,result->node,nodesx->gdata[i]->id);
185
186	amb	113	supersegment->distance=ONEWAY_2TO1\|result->distance;
187	amb	110	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			Result result1,result2;
321			NodeX *nodex;
322			SegmentX **segmentx;
323			WayX *wayx;
324
325			/* Insert the first node into the queue */
326
327			results=NewResultsList(8);
328
329			result1=InsertResult(results,start);
330
331			result1->node=start;
332	amb	113	result1->prev=0;
333			result1->next=0;
334			result1->distance=0;
335	amb	110
336			insert_in_queue(result1);
337
338			/* Loop across all nodes in the queue */
339
340			while((result1=pop_from_queue()))
341			{
342			node1=result1->node;
343
344			segmentx=FindFirstSegmentX(segmentsx,node1);
345
346			while(segmentx)
347			{
348	amb	113	distance_t cumulative_distance;
349
350	amb	110	if((*segmentx)->segment.distance&ONEWAY_2TO1)
351			goto endloop;
352
353			node2=(*segmentx)->node2;
354
355	amb	113	if(result1->prev==node2)
356	amb	110	goto endloop;
357
358			wayx=LookupWayX(waysx,(*segmentx)->segment.way);
359
360			if(wayx->way.type !=match->way.type \|\|
361			wayx->way.allow!=match->way.allow \|\|
362			wayx->way.limit!=match->way.limit)
363			goto endloop;
364
365	amb	113	cumulative_distance=result1->distance+DISTANCE((*segmentx)->segment.distance);
366	amb	110
367			result2=FindResult(results,node2);
368
369			if(!result2) /* New end node */
370			{
371			result2=InsertResult(results,node2);
372			result2->node=node2;
373	amb	113	result2->prev=node1;
374			result2->next=0;
375			result2->distance=cumulative_distance;
376	amb	110
377			nodex=FindNodeX(nodesx,node2);
378
379			if(nodex->super<=iteration)
380			insert_in_queue(result2);
381			}
382			else
383			{
384	amb	113	if(cumulative_distance<result2->distance)
385	amb	110	{
386	amb	113	result2->prev=node1;
387			result2->distance=cumulative_distance;
388	amb	110
389			nodex=FindNodeX(nodesx,node2);
390
391			if(nodex->super<=iteration)
392			insert_in_queue(result2);
393			}
394			}
395
396			endloop:
397
398			segmentx=FindNextSegmentX(segmentsx,segmentx);
399			}
400			}
401
402			return(results);
403			}