trunk/src/superx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/superx.c,v 1.3 2009-02-24 19:59:37 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.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->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->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->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	128	$Header: /home/amb/CVS/routino/src/superx.c,v 1.3 2009-02-24 19:59:37 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	amb	128	SegmentX **segmentx=LookupSegmentX(segmentsx,i);
55			WayX wayx=LookupWayX(waysx,(segmentx)->segment.way);
56	amb	110
57	amb	128	if((*segmentx)->node1!=node)
58	amb	110	{
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	amb	128	node=(*segmentx)->node1;
75	amb	110	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.next2=~0;
239
240			while(j<supersegmentsx->number)
241			{
242			if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
243			segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2 &&
244			segmentsx->sdata[i]->segment.distance==supersegmentsx->sdata[j]->segment.distance)
245			{
246			segmentsx->sdata[i]->segment.node2=SUPER_FLAG; /* mark as super-segment */
247			j++;
248			break;
249			}
250			else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
251			segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2)
252			{
253			Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);
254
255			*supersegment=supersegmentsx->sdata[j]->segment;
256			supersegment->node2=SUPER_FLAG; /* mark as super-segment */
257			supersegment->next2=~0;
258			}
259			else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
260			segmentsx->sdata[i]->node2>supersegmentsx->sdata[j]->node2)
261			{
262			Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);
263
264			*supersegment=supersegmentsx->sdata[j]->segment;
265			supersegment->node2=SUPER_FLAG; /* mark as super-segment */
266			supersegment->next2=~0;
267			}
268			else if(segmentsx->sdata[i]->node1>supersegmentsx->sdata[j]->node1)
269			{
270			Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);
271
272			*supersegment=supersegmentsx->sdata[j]->segment;
273			supersegment->node2=SUPER_FLAG; /* mark as super-segment */
274			supersegment->next2=~0;
275			}
276			else
277			break;
278
279			j++;
280			}
281
282			if(!((i+1)%10000))
283			{
284			printf("\rMerging Segments: Segments=%d Super-Segment=%d Total=%d",i+1,j+1,segmentsx->xnumber);
285			fflush(stdout);
286			}
287			}
288
289			printf("\rMerged Segments: Segments=%d Super-Segment=%d Total=%d \n",n,supersegmentsx->number,segmentsx->xnumber);
290			fflush(stdout);
291			}
292
293
294			/*++++++++++++++++++++++++++++++++++++++
295			Find all routes from a specified node to any node in the specified list that follows a certain type of way.
296
297			Results *FindRoutesWay Returns a set of results.
298
299			NodesX *nodesx The set of nodes to use.
300
301			SegmentsX *segmentsx The set of segments to use.
302
303			WaysX *waysx The set of ways to use.
304
305			node_t start The start node.
306
307			WayX *match The way that the route must match.
308
309			int iteration The current super-node / super-segment iteration number.
310			++++++++++++++++++++++++++++++++++++++*/
311
312			Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,WayX *match,int iteration)
313			{
314			Results *results;
315			index_t node1,node2;
316			Result result1,result2;
317			NodeX *nodex;
318			SegmentX **segmentx;
319			WayX *wayx;
320
321			/* Insert the first node into the queue */
322
323			results=NewResultsList(8);
324
325			result1=InsertResult(results,start);
326
327			result1->node=start;
328	amb	113	result1->prev=0;
329			result1->next=0;
330			result1->distance=0;
331	amb	110
332			insert_in_queue(result1);
333
334			/* Loop across all nodes in the queue */
335
336			while((result1=pop_from_queue()))
337			{
338			node1=result1->node;
339
340			segmentx=FindFirstSegmentX(segmentsx,node1);
341
342			while(segmentx)
343			{
344	amb	113	distance_t cumulative_distance;
345
346	amb	110	if((*segmentx)->segment.distance&ONEWAY_2TO1)
347			goto endloop;
348
349			node2=(*segmentx)->node2;
350
351	amb	113	if(result1->prev==node2)
352	amb	110	goto endloop;
353
354			wayx=LookupWayX(waysx,(*segmentx)->segment.way);
355
356			if(wayx->way.type !=match->way.type \|\|
357			wayx->way.allow!=match->way.allow \|\|
358			wayx->way.limit!=match->way.limit)
359			goto endloop;
360
361	amb	113	cumulative_distance=result1->distance+DISTANCE((*segmentx)->segment.distance);
362	amb	110
363			result2=FindResult(results,node2);
364
365			if(!result2) /* New end node */
366			{
367			result2=InsertResult(results,node2);
368			result2->node=node2;
369	amb	113	result2->prev=node1;
370			result2->next=0;
371			result2->distance=cumulative_distance;
372	amb	110
373			nodex=FindNodeX(nodesx,node2);
374
375			if(nodex->super<=iteration)
376			insert_in_queue(result2);
377			}
378			else
379			{
380	amb	113	if(cumulative_distance<result2->distance)
381	amb	110	{
382	amb	113	result2->prev=node1;
383			result2->distance=cumulative_distance;
384	amb	110
385			nodex=FindNodeX(nodesx,node2);
386
387			if(nodex->super<=iteration)
388			insert_in_queue(result2);
389			}
390			}
391
392			endloop:
393
394			segmentx=FindNextSegmentX(segmentsx,segmentx);
395			}
396			}
397
398			return(results);
399			}