trunk/src/superx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/superx.c,v 1.4 2009-03-01 17:24:21 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;
 Way    way;

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