trunk/src/supersegments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.24 2009-02-01 17:11:08 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=FindNode(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->xdata[i].super>iteration)
      {
       SegmentX *segmentx,*first;

       segmentx=first=FindFirstSegment(segmentsx,nodesx->xdata[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=FindNextSegment(segmentsx,othersegmentx);
               }
            }

          /* Route the way and store the super-segments. */

          if(wayx)
            {
             Results *results=FindRoutesWay(nodesx,segmentsx,waysx,nodesx->xdata[i].id,wayx,iteration);
             Result *result=FirstResult(results);

             while(result)
               {
                NodeX *nodex=FindNode(nodesx,result->node);

                if(result->node!=nodesx->xdata[i].id && nodex->super>iteration)
                  {
                   SegmentX *supersegmentx=AppendSegment(supersegmentsx,nodesx->xdata[i].id,result->node,IndexWayX(waysx,wayx));

                   supersegmentx->segment.distance=result->shortest.distance;

                   if(wayx->way.type&Way_OneWay)
                     {
                      supersegmentx=AppendSegment(supersegmentsx,result->node,nodesx->xdata[i].id,IndexWayX(waysx,wayx));

                      supersegmentx->segment.distance=ONEWAY_OPPOSITE|result->shortest.distance;
                     }
                  }

                result=NextResult(results,result);
               }

             FreeResultsList(results);
            }

          segmentx=FindNextSegment(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=FindFirstSegment(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=FindNode(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=FindNode(nodesx,node2);

             if(nodex->super<=iteration)
                insert_in_queue(result2);
            }
         }

      endloop:

       segmentx=FindNextSegment(segmentsx,segmentx);
      }
   }

 return(results);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/supersegments.c,v 1.24 2009-02-01 17:11:08 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=FindNode(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->xdata[i].super>iteration)
129	{
130	SegmentX segmentx,first;
131
132	segmentx=first=FindFirstSegment(segmentsx,nodesx->xdata[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=FindNextSegment(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->xdata[i].id,wayx,iteration);
165	Result *result=FirstResult(results);
166
167	while(result)
168	{
169	NodeX *nodex=FindNode(nodesx,result->node);
170
171	if(result->node!=nodesx->xdata[i].id && nodex->super>iteration)
172	{
173	SegmentX *supersegmentx=AppendSegment(supersegmentsx,nodesx->xdata[i].id,result->node,IndexWayX(waysx,wayx));
174
175	supersegmentx->segment.distance=result->shortest.distance;
176
177	if(wayx->way.type&Way_OneWay)
178	{
179	supersegmentx=AppendSegment(supersegmentsx,result->node,nodesx->xdata[i].id,IndexWayX(waysx,wayx));
180
181	supersegmentx->segment.distance=ONEWAY_OPPOSITE\|result->shortest.distance;
182	}
183	}
184
185	result=NextResult(results,result);
186	}
187
188	FreeResultsList(results);
189	}
190
191	segmentx=FindNextSegment(segmentsx,segmentx);
192	}
193	}
194
195	if(!((i+1)%10000))
196	{
197	printf("\rCreating Super-Segments: Nodes=%d Super-Segments=%d",i+1,supersegmentsx->number);
198	fflush(stdout);
199	}
200	}
201
202	printf("\rCreated Super-Segments: Nodes=%d Super-Segments=%d \n",nodesx->number,supersegmentsx->number);
203	fflush(stdout);
204
205	/* Append the new supersegments onto the segments. */
206
207	return(supersegmentsx);
208	}
209
210
211	/*++++++++++++++++++++++++++++++++++++++
212	Find all routes from a specified node to any node in the specified list that follows a certain type of way.
213
214	Results *FindRoutesWay Returns a set of results.
215
216	NodesX *nodesx The set of nodes to use.
217
218	SegmentsX *segmentsx The set of segments to use.
219
220	WaysX *waysx The set of ways to use.
221
222	node_t start The start node.
223
224	WayX *match The way that the route must match.
225
226	int iteration The current super-node / super-segment iteration number.
227	++++++++++++++++++++++++++++++++++++++*/
228
229	Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,WayX *match,int iteration)
230	{
231	Results *results;
232	index_t node1,node2;
233	HalfResult shortest2;
234	Result result1,result2;
235	NodeX *nodex;
236	SegmentX *segmentx;
237	WayX *wayx;
238
239	/* Insert the first node into the queue */
240
241	results=NewResultsList(8);
242
243	result1=InsertResult(results,start);
244
245	result1->node=start;
246	result1->shortest.prev=0;
247	result1->shortest.next=0;
248	result1->shortest.distance=0;
249
250	insert_in_queue(result1);
251
252	/* Loop across all nodes in the queue */
253
254	while((result1=pop_from_queue()))
255	{
256	node1=result1->node;
257
258	segmentx=FindFirstSegment(segmentsx,node1);
259
260	while(segmentx)
261	{
262	if(segmentx->segment.distance&ONEWAY_OPPOSITE)
263	goto endloop;
264
265	node2=segmentx->node2;
266
267	if(result1->shortest.prev==node2)
268	goto endloop;
269
270	wayx=LookupWayX(waysx,segmentx->segment.way);
271
272	if(wayx->way.type !=match->way.type \|\|
273	wayx->way.allow!=match->way.allow \|\|
274	wayx->way.limit!=match->way.limit)
275	goto endloop;
276
277	shortest2.distance=result1->shortest.distance+DISTANCE(segmentx->segment.distance);
278
279	result2=FindResult(results,node2);
280
281	if(!result2) /* New end node */
282	{
283	result2=InsertResult(results,node2);
284	result2->node=node2;
285	result2->shortest.prev=node1;
286	result2->shortest.next=0;
287	result2->shortest.distance=shortest2.distance;
288
289	nodex=FindNode(nodesx,node2);
290
291	if(nodex->super<=iteration)
292	insert_in_queue(result2);
293	}
294	else
295	{
296	if(shortest2.distance<result2->shortest.distance)
297	{
298	result2->shortest.prev=node1;
299	result2->shortest.distance=shortest2.distance;
300
301	nodex=FindNode(nodesx,node2);
302
303	if(nodex->super<=iteration)
304	insert_in_queue(result2);
305	}
306	}
307
308	endloop:
309
310	segmentx=FindNextSegment(segmentsx,segmentx);
311	}
312	}
313
314	return(results);
315	}