trunk/src/supersegments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.26 2009-02-04 18: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 "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->xdata[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=AppendSegment(supersegmentsx,result->node,nodesx->gdata[i].id);

                      supersegment->distance=ONEWAY_OPPOSITE|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);
}


/*++++++++++++++++++++++++++++++++++++++
  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_OPPOSITE)
          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.26 2009-02-04 18: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 "nodes.h"
20	#include "ways.h"
21	#include "segments.h"
22	#include "functions.h"
23
24
25	/*++++++++++++++++++++++++++++++++++++++
26	Select the super-segments from the list of segments.
27
28	NodesX *nodesx The nodes.
29
30	SegmentsX *segmentsx The segments.
31
32	WaysX *waysx The ways.
33
34	int iteration The current super-node / super-segment iteration number.
35	++++++++++++++++++++++++++++++++++++++*/
36
37	void ChooseSuperNodes(NodesX nodesx,SegmentsX segmentsx,WaysX *waysx,int iteration)
38	{
39	int i;
40	int segcount=0,difference=0,nnodes=0;
41	node_t node=0;
42	speed_t limit=0;
43	waytype_t type=0;
44	wayallow_t allow=0;
45
46	/* Find super-nodes */
47
48	node=segmentsx->xdata[0].node1;
49
50	for(i=0;i<segmentsx->number;i++)
51	{
52	SegmentX *segmentx=LookupSegmentX(segmentsx,i);
53	WayX *wayx=LookupWayX(waysx,segmentx->segment.way);
54
55	if(segmentx->node1!=node)
56	{
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	node=segmentx->node1;
73	type=wayx->way.type;
74	limit=wayx->way.limit;
75	allow=wayx->way.allow;
76	}
77	else /* Same starting node */
78	{
79	if(wayx->way.type!=type)
80	difference=1;
81
82	if(wayx->way.limit!=limit)
83	difference=1;
84
85	if(wayx->way.allow!=allow)
86	difference=1;
87
88	segcount+=1;
89	}
90
91	if(!((i+1)%10000))
92	{
93	printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i+1,nnodes);
94	fflush(stdout);
95	}
96	}
97
98	printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d \n",segmentsx->number,nnodes);
99	fflush(stdout);
100	}
101
102
103	/*++++++++++++++++++++++++++++++++++++++
104	Create the super-segments.
105
106	SegmentsX *CreateSuperSegments Creates the super segments.
107
108	NodesX *nodesx The nodes.
109
110	SegmentsX *segmentsx The segments.
111
112	WaysX *waysx The ways.
113
114	int iteration The current super-node / super-segment iteration number.
115	++++++++++++++++++++++++++++++++++++++*/
116
117	SegmentsX CreateSuperSegments(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,int iteration)
118	{
119	int i;
120	SegmentsX *supersegmentsx;
121
122	supersegmentsx=NewSegmentList();
123
124	/* Create super-segments for each super-node. */
125
126	for(i=0;i<nodesx->number;i++)
127	{
128	if(nodesx->gdata[i].super>iteration)
129	{
130	SegmentX segmentx,first;
131
132	segmentx=first=FindFirstSegmentX(segmentsx,nodesx->gdata[i].id);
133
134	while(segmentx)
135	{
136	WayX *wayx=LookupWayX(waysx,segmentx->segment.way);
137
138	/* Check that this type of way hasn't already been routed */
139
140	if(segmentx!=first)
141	{
142	SegmentX *othersegmentx=first;
143
144	while(othersegmentx && othersegmentx!=segmentx)
145	{
146	WayX *otherwayx=LookupWayX(waysx,othersegmentx->segment.way);
147
148	if(otherwayx->way.type ==wayx->way.type &&
149	otherwayx->way.allow==wayx->way.allow &&
150	otherwayx->way.limit==wayx->way.limit)
151	{
152	wayx=NULL;
153	break;
154	}
155
156	othersegmentx=FindNextSegmentX(segmentsx,othersegmentx);
157	}
158	}
159
160	/* Route the way and store the super-segments. */
161
162	if(wayx)
163	{
164	Results *results=FindRoutesWay(nodesx,segmentsx,waysx,nodesx->gdata[i].id,wayx,iteration);
165	Result *result=FirstResult(results);
166
167	while(result)
168	{
169	NodeX *nodex=FindNodeX(nodesx,result->node);
170
171	if(result->node!=nodesx->gdata[i].id && nodex->super>iteration)
172	{
173	Segment *supersegment=AppendSegment(supersegmentsx,nodesx->gdata[i].id,result->node);
174
175	supersegment->distance=result->shortest.distance;
176	supersegment->way=IndexWayX(waysx,wayx);
177
178	if(wayx->way.type&Way_OneWay)
179	{
180	supersegment=AppendSegment(supersegmentsx,result->node,nodesx->gdata[i].id);
181
182	supersegment->distance=ONEWAY_OPPOSITE\|result->shortest.distance;
183	supersegment->way=IndexWayX(waysx,wayx);
184	}
185	}
186
187	result=NextResult(results,result);
188	}
189
190	FreeResultsList(results);
191	}
192
193	segmentx=FindNextSegmentX(segmentsx,segmentx);
194	}
195	}
196
197	if(!((i+1)%10000))
198	{
199	printf("\rCreating Super-Segments: Nodes=%d Super-Segments=%d",i+1,supersegmentsx->number);
200	fflush(stdout);
201	}
202	}
203
204	printf("\rCreated Super-Segments: Nodes=%d Super-Segments=%d \n",nodesx->number,supersegmentsx->number);
205	fflush(stdout);
206
207	/* Append the new supersegments onto the segments. */
208
209	return(supersegmentsx);
210	}
211
212
213	/*++++++++++++++++++++++++++++++++++++++
214	Find all routes from a specified node to any node in the specified list that follows a certain type of way.
215
216	Results *FindRoutesWay Returns a set of results.
217
218	NodesX *nodesx The set of nodes to use.
219
220	SegmentsX *segmentsx The set of segments to use.
221
222	WaysX *waysx The set of ways to use.
223
224	node_t start The start node.
225
226	WayX *match The way that the route must match.
227
228	int iteration The current super-node / super-segment iteration number.
229	++++++++++++++++++++++++++++++++++++++*/
230
231	Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,WayX *match,int iteration)
232	{
233	Results *results;
234	index_t node1,node2;
235	HalfResult shortest2;
236	Result result1,result2;
237	NodeX *nodex;
238	SegmentX *segmentx;
239	WayX *wayx;
240
241	/* Insert the first node into the queue */
242
243	results=NewResultsList(8);
244
245	result1=InsertResult(results,start);
246
247	result1->node=start;
248	result1->shortest.prev=0;
249	result1->shortest.next=0;
250	result1->shortest.distance=0;
251
252	insert_in_queue(result1);
253
254	/* Loop across all nodes in the queue */
255
256	while((result1=pop_from_queue()))
257	{
258	node1=result1->node;
259
260	segmentx=FindFirstSegmentX(segmentsx,node1);
261
262	while(segmentx)
263	{
264	if(segmentx->segment.distance&ONEWAY_OPPOSITE)
265	goto endloop;
266
267	node2=segmentx->node2;
268
269	if(result1->shortest.prev==node2)
270	goto endloop;
271
272	wayx=LookupWayX(waysx,segmentx->segment.way);
273
274	if(wayx->way.type !=match->way.type \|\|
275	wayx->way.allow!=match->way.allow \|\|
276	wayx->way.limit!=match->way.limit)
277	goto endloop;
278
279	shortest2.distance=result1->shortest.distance+DISTANCE(segmentx->segment.distance);
280
281	result2=FindResult(results,node2);
282
283	if(!result2) /* New end node */
284	{
285	result2=InsertResult(results,node2);
286	result2->node=node2;
287	result2->shortest.prev=node1;
288	result2->shortest.next=0;
289	result2->shortest.distance=shortest2.distance;
290
291	nodex=FindNodeX(nodesx,node2);
292
293	if(nodex->super<=iteration)
294	insert_in_queue(result2);
295	}
296	else
297	{
298	if(shortest2.distance<result2->shortest.distance)
299	{
300	result2->shortest.prev=node1;
301	result2->shortest.distance=shortest2.distance;
302
303	nodex=FindNodeX(nodesx,node2);
304
305	if(nodex->super<=iteration)
306	insert_in_queue(result2);
307	}
308	}
309
310	endloop:
311
312	segmentx=FindNextSegmentX(segmentsx,segmentx);
313	}
314	}
315
316	return(results);
317	}