trunk/src/supersegments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.27 2009-02-06 20:23:33 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 "results.h"
#include "nodes.h"
#include "ways.h"
#include "segments.h"
#include "functions.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->number);
       fflush(stdout);
      }
   }

 printf("\rCreated Super-Segments: Nodes=%d Super-Segments=%d \n",nodesx->number,supersegmentsx->number);
 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->number);
       fflush(stdout);
      }
   }

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