trunk/src/superx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/superx.c,v 1.11 2009-06-25 17:46:45 amb Exp $

 Super-Segment data type functions.

 Part of the Routino routing software.
 ******************/ /******************
 This file Copyright 2008,2009 Andrew M. Bishop

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU Affero General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Affero General Public License for more details.

 You should have received a copy of the GNU Affero General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 ***************************************/


#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   *way1;

 /* Find super-nodes */

 node=segmentsx->sdata[0]->node1;
 way1=LookupWayInWayX(waysx,segmentsx->sdata[0]->segment.way);

 for(i=0;i<segmentsx->number;i++)
   {
    SegmentX **segmentx=LookupSegmentX(segmentsx,i);
    Way *way2=LookupWayInWayX(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;
       way1=way2;
      }
    else                        /* Same starting node */
      {
       if(WaysCompare(way2,way1))
          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)
         {
          Way *way=LookupWayInWayX(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)
               {
                Way *otherway=LookupWayInWayX(waysx,(*othersegmentx)->segment.way);

                if(!WaysCompare(otherway,way))
                  {
                   way=NULL;
                   break;
                  }

                othersegmentx=FindNextSegmentX(segmentsx,othersegmentx);
               }
            }

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

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

             while(result)
               {
                NodeX *nodex=FindNodeX(nodesx,result->node);
                WayX  *wayx =FindWayX (waysx ,(*segmentx)->way);

                if(result->node!=nodesx->gdata[i]->id && nodex->super>iteration)
                  {
                   Segment *supersegment=AppendSegment(supersegmentsx,wayx->id,nodesx->gdata[i]->id,result->node);

                   if(wayx->way->type&Way_OneWay)
                     {
                      supersegment->distance=ONEWAY_1TO2|(distance_t)result->score;
                      supersegment->way=IndexWayInWayX(waysx,wayx);

                      supersegment=AppendSegment(supersegmentsx,wayx->id,result->node,nodesx->gdata[i]->id);

                      supersegment->distance=ONEWAY_2TO1|(distance_t)result->score;
                      supersegment->way=IndexWayInWayX(waysx,wayx);
                     }
                   else
                     {
                      supersegment->distance=(distance_t)result->score;
                      supersegment->way=IndexWayInWayX(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=NO_NODE;

    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 */
          supersegmentsx->sdata[j]=NULL;
          j++;
          break;
         }
       else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
               segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2)
         {
          supersegmentsx->sdata[j]->segment.node2=SUPER_FLAG; /* mark as super-segment */
          supersegmentsx->sdata[j]->segment.next2=NO_NODE;
         }
       else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
               segmentsx->sdata[i]->node2>supersegmentsx->sdata[j]->node2)
         {
          supersegmentsx->sdata[j]->segment.node2=SUPER_FLAG; /* mark as super-segment */
          supersegmentsx->sdata[j]->segment.next2=NO_NODE;
         }
       else if(segmentsx->sdata[i]->node1>supersegmentsx->sdata[j]->node1)
         {
          supersegmentsx->sdata[j]->segment.node2=SUPER_FLAG; /* mark as super-segment */
          supersegmentsx->sdata[j]->segment.next2=NO_NODE;
         }
       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);
      }
   }

 for(j=0;j<supersegmentsx->number;j++)
    if(supersegmentsx->sdata[j])
      {
       Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->way,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);

       *supersegment=supersegmentsx->sdata[j]->segment;
      }

 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.

  Way *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,Way *match,int iteration)
{
 Results *results;
 index_t node1,node2;
 Result *result1,*result2;
 NodeX *nodex;
 SegmentX **segmentx;
 Way *way;

 /* Insert the first node into the queue */

 results=NewResultsList(8);

 result1=InsertResult(results,start);

 ZeroResult(result1);

 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;

       way=LookupWayInWayX(waysx,(*segmentx)->segment.way);

       if(WaysCompare(way,match))
          goto endloop;

       cumulative_distance=(distance_t)result1->score+DISTANCE((*segmentx)->segment.distance);

       result2=FindResult(results,node2);

       if(!result2)                         /* New end node */
         {
          result2=InsertResult(results,node2);
          result2->prev=node1;
          result2->next=NO_NODE;
          result2->score=cumulative_distance;
          result2->sortby=cumulative_distance;

          nodex=FindNodeX(nodesx,node2);

          if(nodex->super<=iteration)
             insert_in_queue(result2);
         }
       else if(cumulative_distance<result2->score)
         {
          result2->prev=node1;
          result2->score=cumulative_distance;
          result2->sortby=cumulative_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/superx.c,v 1.11 2009-06-25 17:46:45 amb Exp $
3
4	Super-Segment data type functions.
5
6	Part of the Routino routing software.
7	****************/ /****************
8	This file Copyright 2008,2009 Andrew M. Bishop
9
10	This program is free software: you can redistribute it and/or modify
11	it under the terms of the GNU Affero General Public License as published by
12	the Free Software Foundation, either version 3 of the License, or
13	(at your option) any later version.
14
15	This program is distributed in the hope that it will be useful,
16	but WITHOUT ANY WARRANTY; without even the implied warranty of
17	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18	GNU Affero General Public License for more details.
19
20	You should have received a copy of the GNU Affero General Public License
21	along with this program. If not, see <http://www.gnu.org/licenses/>.
22	***************************************/
23
24
25	#include <assert.h>
26	#include <math.h>
27	#include <stdlib.h>
28	#include <stdio.h>
29
30	#include "results.h"
31	#include "nodesx.h"
32	#include "segmentsx.h"
33	#include "waysx.h"
34	#include "superx.h"
35
36
37	/*++++++++++++++++++++++++++++++++++++++
38	Select the super-segments from the list of segments.
39
40	NodesX *nodesx The nodes.
41
42	SegmentsX *segmentsx The segments.
43
44	WaysX *waysx The ways.
45
46	int iteration The current super-node / super-segment iteration number.
47	++++++++++++++++++++++++++++++++++++++*/
48
49	void ChooseSuperNodes(NodesX nodesx,SegmentsX segmentsx,WaysX *waysx,int iteration)
50	{
51	int i;
52	int segcount=0,difference=0,nnodes=0;
53	node_t node=0;
54	Way *way1;
55
56	/* Find super-nodes */
57
58	node=segmentsx->sdata[0]->node1;
59	way1=LookupWayInWayX(waysx,segmentsx->sdata[0]->segment.way);
60
61	for(i=0;i<segmentsx->number;i++)
62	{
63	SegmentX **segmentx=LookupSegmentX(segmentsx,i);
64	Way way2=LookupWayInWayX(waysx,(segmentx)->segment.way);
65
66	if((*segmentx)->node1!=node)
67	{
68	/* Store the node if there is a difference in the ways that could affect routing.
69	Store the node if it is not a dead-end and if it isn't just the middle of a way. */
70
71	if(difference \|\| segcount>2)
72	{
73	NodeX *nodex=FindNodeX(nodesx,node);
74
75	nodex->super++;
76
77	nnodes++;
78	}
79
80	segcount=1;
81	difference=0;
82
83	node=(*segmentx)->node1;
84	way1=way2;
85	}
86	else /* Same starting node */
87	{
88	if(WaysCompare(way2,way1))
89	difference=1;
90
91	segcount+=1;
92	}
93
94	if(!((i+1)%10000))
95	{
96	printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i+1,nnodes);
97	fflush(stdout);
98	}
99	}
100
101	printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d \n",segmentsx->number,nnodes);
102	fflush(stdout);
103	}
104
105
106	/*++++++++++++++++++++++++++++++++++++++
107	Create the super-segments.
108
109	SegmentsX *CreateSuperSegments Creates the super segments.
110
111	NodesX *nodesx The nodes.
112
113	SegmentsX *segmentsx The segments.
114
115	WaysX *waysx The ways.
116
117	int iteration The current super-node / super-segment iteration number.
118	++++++++++++++++++++++++++++++++++++++*/
119
120	SegmentsX CreateSuperSegments(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,int iteration)
121	{
122	int i;
123	SegmentsX *supersegmentsx;
124
125	supersegmentsx=NewSegmentList();
126
127	/* Create super-segments for each super-node. */
128
129	for(i=0;i<nodesx->number;i++)
130	{
131	if(nodesx->gdata[i]->super>iteration)
132	{
133	SegmentX segmentx,first;
134
135	segmentx=first=FindFirstSegmentX(segmentsx,nodesx->gdata[i]->id);
136
137	while(segmentx)
138	{
139	Way way=LookupWayInWayX(waysx,(segmentx)->segment.way);
140
141	/* Check that this type of way hasn't already been routed */
142
143	if(segmentx!=first)
144	{
145	SegmentX **othersegmentx=first;
146
147	while(othersegmentx && othersegmentx!=segmentx)
148	{
149	Way otherway=LookupWayInWayX(waysx,(othersegmentx)->segment.way);
150
151	if(!WaysCompare(otherway,way))
152	{
153	way=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(way)
164	{
165	Results *results=FindRoutesWay(nodesx,segmentsx,waysx,nodesx->gdata[i]->id,way,iteration);
166	Result *result=FirstResult(results);
167
168	while(result)
169	{
170	NodeX *nodex=FindNodeX(nodesx,result->node);
171	WayX wayx =FindWayX (waysx ,(segmentx)->way);
172
173	if(result->node!=nodesx->gdata[i]->id && nodex->super>iteration)
174	{
175	Segment *supersegment=AppendSegment(supersegmentsx,wayx->id,nodesx->gdata[i]->id,result->node);
176
177	if(wayx->way->type&Way_OneWay)
178	{
179	supersegment->distance=ONEWAY_1TO2\|(distance_t)result->score;
180	supersegment->way=IndexWayInWayX(waysx,wayx);
181
182	supersegment=AppendSegment(supersegmentsx,wayx->id,result->node,nodesx->gdata[i]->id);
183
184	supersegment->distance=ONEWAY_2TO1\|(distance_t)result->score;
185	supersegment->way=IndexWayInWayX(waysx,wayx);
186	}
187	else
188	{
189	supersegment->distance=(distance_t)result->score;
190	supersegment->way=IndexWayInWayX(waysx,wayx);
191	}
192	}
193
194	result=NextResult(results,result);
195	}
196
197	FreeResultsList(results);
198	}
199
200	segmentx=FindNextSegmentX(segmentsx,segmentx);
201	}
202	}
203
204	if(!((i+1)%10000))
205	{
206	printf("\rCreating Super-Segments: Nodes=%d Super-Segments=%d",i+1,supersegmentsx->xnumber);
207	fflush(stdout);
208	}
209	}
210
211	printf("\rCreated Super-Segments: Nodes=%d Super-Segments=%d \n",nodesx->number,supersegmentsx->xnumber);
212	fflush(stdout);
213
214	/* Append the new supersegments onto the segments. */
215
216	return(supersegmentsx);
217	}
218
219
220	/*++++++++++++++++++++++++++++++++++++++
221	Merge the super-segments into the segments.
222
223	SegmentsX* segmentsx The set of segments to process.
224
225	SegmentsX* supersegmentsx The set of super-segments to merge.
226	++++++++++++++++++++++++++++++++++++++*/
227
228	void MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx)
229	{
230	int i,j,n;
231
232	assert(segmentsx->sorted); /* Must be sorted */
233	assert(supersegmentsx->sorted); /* Must be sorted */
234
235	n=segmentsx->number;
236
237	for(i=0,j=0;i<n;i++)
238	{
239	segmentsx->sdata[i]->segment.node1=SUPER_FLAG; /* mark as normal segment */
240
241	segmentsx->sdata[i]->segment.next2=NO_NODE;
242
243	while(j<supersegmentsx->number)
244	{
245	if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
246	segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2 &&
247	segmentsx->sdata[i]->segment.distance==supersegmentsx->sdata[j]->segment.distance)
248	{
249	segmentsx->sdata[i]->segment.node2=SUPER_FLAG; /* mark as super-segment */
250	supersegmentsx->sdata[j]=NULL;
251	j++;
252	break;
253	}
254	else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
255	segmentsx->sdata[i]->node2==supersegmentsx->sdata[j]->node2)
256	{
257	supersegmentsx->sdata[j]->segment.node2=SUPER_FLAG; /* mark as super-segment */
258	supersegmentsx->sdata[j]->segment.next2=NO_NODE;
259	}
260	else if(segmentsx->sdata[i]->node1==supersegmentsx->sdata[j]->node1 &&
261	segmentsx->sdata[i]->node2>supersegmentsx->sdata[j]->node2)
262	{
263	supersegmentsx->sdata[j]->segment.node2=SUPER_FLAG; /* mark as super-segment */
264	supersegmentsx->sdata[j]->segment.next2=NO_NODE;
265	}
266	else if(segmentsx->sdata[i]->node1>supersegmentsx->sdata[j]->node1)
267	{
268	supersegmentsx->sdata[j]->segment.node2=SUPER_FLAG; /* mark as super-segment */
269	supersegmentsx->sdata[j]->segment.next2=NO_NODE;
270	}
271	else
272	break;
273
274	j++;
275	}
276
277	if(!((i+1)%10000))
278	{
279	printf("\rMerging Segments: Segments=%d Super-Segment=%d Total=%d",i+1,j+1,segmentsx->xnumber);
280	fflush(stdout);
281	}
282	}
283
284	for(j=0;j<supersegmentsx->number;j++)
285	if(supersegmentsx->sdata[j])
286	{
287	Segment *supersegment=AppendSegment(segmentsx,supersegmentsx->sdata[j]->way,supersegmentsx->sdata[j]->node1,supersegmentsx->sdata[j]->node2);
288
289	*supersegment=supersegmentsx->sdata[j]->segment;
290	}
291
292	printf("\rMerged Segments: Segments=%d Super-Segment=%d Total=%d \n",n,supersegmentsx->number,segmentsx->xnumber);
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	Way *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,Way *match,int iteration)
316	{
317	Results *results;
318	index_t node1,node2;
319	Result result1,result2;
320	NodeX *nodex;
321	SegmentX **segmentx;
322	Way *way;
323
324	/* Insert the first node into the queue */
325
326	results=NewResultsList(8);
327
328	result1=InsertResult(results,start);
329
330	ZeroResult(result1);
331
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	distance_t cumulative_distance;
345
346	if((*segmentx)->segment.distance&ONEWAY_2TO1)
347	goto endloop;
348
349	node2=(*segmentx)->node2;
350
351	if(result1->prev==node2)
352	goto endloop;
353
354	way=LookupWayInWayX(waysx,(*segmentx)->segment.way);
355
356	if(WaysCompare(way,match))
357	goto endloop;
358
359	cumulative_distance=(distance_t)result1->score+DISTANCE((*segmentx)->segment.distance);
360
361	result2=FindResult(results,node2);
362
363	if(!result2) /* New end node */
364	{
365	result2=InsertResult(results,node2);
366	result2->prev=node1;
367	result2->next=NO_NODE;
368	result2->score=cumulative_distance;
369	result2->sortby=cumulative_distance;
370
371	nodex=FindNodeX(nodesx,node2);
372
373	if(nodex->super<=iteration)
374	insert_in_queue(result2);
375	}
376	else if(cumulative_distance<result2->score)
377	{
378	result2->prev=node1;
379	result2->score=cumulative_distance;
380	result2->sortby=cumulative_distance;
381
382	nodex=FindNodeX(nodesx,node2);
383
384	if(nodex->super<=iteration)
385	insert_in_queue(result2);
386	}
387
388	endloop:
389
390	segmentx=FindNextSegmentX(segmentsx,segmentx);
391	}
392	}
393
394	return(results);
395	}