trunk/src/superx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/superx.c,v 1.20 2009-07-08 17:35:15 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 <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.
  ++++++++++++++++++++++++++++++++++++++*/

void ChooseSuperNodes(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx)
{
 index_t i;
 int     segcount=0,difference=0,nnodes=0;
 node_t  node=0;
 WayX   *wayx1;

 assert(segmentsx->ndata);      /* Must have ndata filled in */

 /* Find super-nodes */

 node=segmentsx->ndata[0]->node1;
 wayx1=FindWayX(waysx,segmentsx->ndata[0]->way);

 for(i=0;i<segmentsx->number;i++)
   {
    WayX *wayx2=FindWayX(waysx,segmentsx->ndata[i]->way);

    if(segmentsx->ndata[i]->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=segmentsx->ndata[i]->node1;
       wayx1=wayx2;
      }
    else                        /* Same starting node */
      {
       if(WaysCompare(wayx2->way,wayx1->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)
{
 index_t i;
 SegmentsX *supersegmentsx;
 int ss=0;

 assert(nodesx->idata);         /* Must have idata filled in */

 supersegmentsx=NewSegmentList();

 /* Create super-segments for each super-node. */

 for(i=0;i<nodesx->number;i++)
   {
    if(nodesx->idata[i]->super>iteration)
      {
       SegmentX **segmentx,**first;

       segmentx=first=FindFirstSegmentX(segmentsx,nodesx->idata[i]->id);

       while(segmentx)
         {
          WayX *wayx=FindWayX(waysx,(*segmentx)->way);

          /* Check that this type of way hasn't already been routed */

          if(segmentx!=first)
            {
             SegmentX **othersegmentx=first;

             while(othersegmentx && othersegmentx!=segmentx)
               {
                WayX *otherwayx=FindWayX(waysx,(*othersegmentx)->way);

                if(!WaysCompare(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->idata[i]->id,wayx->way,iteration);
             Result *result=FirstResult(results);

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

                if(result->node!=nodesx->idata[i]->id && (*nodex)->super>iteration)
                  {
                   if(wayx->way->type&Way_OneWay)
                     {
                      AppendSegment(supersegmentsx,wayx->id,nodesx->idata[i]->id,result->node,DISTANCE((distance_t)result->score)|ONEWAY_1TO2);

                      AppendSegment(supersegmentsx,wayx->id,result->node,nodesx->idata[i]->id,DISTANCE((distance_t)result->score)|ONEWAY_2TO1);

                      ss+=2;
                     }
                   else
                     {
                      AppendSegment(supersegmentsx,wayx->id,result->node,nodesx->idata[i]->id,DISTANCE((distance_t)result->score));

                      ss++;
                     }
                  }

                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,ss);
       fflush(stdout);
      }
   }

 printf("\rCreated Super-Segments: Nodes=%d Super-Segments=%d \n",nodesx->number,ss);
 fflush(stdout);

 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)
{
 index_t i,j;
 int m=0,a=0;

 assert(segmentsx->sorted);      /* Must be sorted */
 assert(segmentsx->ndata);       /* Must have ndata filled in */
 assert(supersegmentsx->sorted); /* Must be sorted */
 assert(supersegmentsx->ndata);  /* Must have ndata filled in */

 for(i=0,j=0;i<segmentsx->number;i++)
   {
    while(j<supersegmentsx->number)
      {
       if(segmentsx->ndata[i]->node1==supersegmentsx->ndata[j]->node1 &&
          segmentsx->ndata[i]->node2==supersegmentsx->ndata[j]->node2 &&
          segmentsx->ndata[i]->distance==supersegmentsx->ndata[j]->distance)
         {
          segmentsx->ndata[i]->distance|=SEGMENT_SUPER; /* mark as super-segment */
          m++;
          j++;
          break;
         }
       else if((segmentsx->ndata[i]->node1==supersegmentsx->ndata[j]->node1 &&
                segmentsx->ndata[i]->node2==supersegmentsx->ndata[j]->node2) ||
               (segmentsx->ndata[i]->node1==supersegmentsx->ndata[j]->node1 &&
                segmentsx->ndata[i]->node2>supersegmentsx->ndata[j]->node2) ||
               (segmentsx->ndata[i]->node1>supersegmentsx->ndata[j]->node1))
         {
          supersegmentsx->ndata[j]->distance|=SEGMENT_SUPER; /* mark as super-segment */
          AppendSegment(segmentsx,supersegmentsx->ndata[j]->way,supersegmentsx->ndata[j]->node1,supersegmentsx->ndata[j]->node2,supersegmentsx->ndata[j]->distance);
          a++;
          j++;
         }
       else
          break;
      }

    segmentsx->ndata[i]->distance|=SEGMENT_NORMAL; /* mark as normal segment */

    if(!((i+1)%10000))
      {
       printf("\rMerging: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
       fflush(stdout);
      }
   }

 printf("\rMerged: Segments=%d Super-Segments=%d Merged=%d Added=%d \n",segmentsx->number,supersegmentsx->number,m,a);
 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;
 WayX *wayx;

 /* 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)->distance&ONEWAY_2TO1)
          goto endloop;

       node2=(*segmentx)->node2;

       if(result1->prev==node2)
          goto endloop;

       wayx=FindWayX(waysx,(*segmentx)->way);

       if(WaysCompare(wayx->way,match))
          goto endloop;

       cumulative_distance=(distance_t)result1->score+DISTANCE((*segmentx)->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.20 2009-07-08 17:35:15 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 <stdlib.h>
27	#include <stdio.h>
28
29	#include "results.h"
30	#include "nodesx.h"
31	#include "segmentsx.h"
32	#include "waysx.h"
33	#include "superx.h"
34
35
36	/*++++++++++++++++++++++++++++++++++++++
37	Select the super-segments from the list of segments.
38
39	NodesX *nodesx The nodes.
40
41	SegmentsX *segmentsx The segments.
42
43	WaysX *waysx The ways.
44	++++++++++++++++++++++++++++++++++++++*/
45
46	void ChooseSuperNodes(NodesX nodesx,SegmentsX segmentsx,WaysX *waysx)
47	{
48	index_t i;
49	int segcount=0,difference=0,nnodes=0;
50	node_t node=0;
51	WayX *wayx1;
52
53	assert(segmentsx->ndata); /* Must have ndata filled in */
54
55	/* Find super-nodes */
56
57	node=segmentsx->ndata[0]->node1;
58	wayx1=FindWayX(waysx,segmentsx->ndata[0]->way);
59
60	for(i=0;i<segmentsx->number;i++)
61	{
62	WayX *wayx2=FindWayX(waysx,segmentsx->ndata[i]->way);
63
64	if(segmentsx->ndata[i]->node1!=node)
65	{
66	/* Store the node if there is a difference in the ways that could affect routing.
67	Store the node if it is not a dead-end and if it isn't just the middle of a way. */
68
69	if(difference \|\| segcount>2)
70	{
71	NodeX **nodex=FindNodeX(nodesx,node);
72
73	(*nodex)->super++;
74
75	nnodes++;
76	}
77
78	segcount=1;
79	difference=0;
80
81	node=segmentsx->ndata[i]->node1;
82	wayx1=wayx2;
83	}
84	else /* Same starting node */
85	{
86	if(WaysCompare(wayx2->way,wayx1->way))
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	index_t i;
121	SegmentsX *supersegmentsx;
122	int ss=0;
123
124	assert(nodesx->idata); /* Must have idata filled in */
125
126	supersegmentsx=NewSegmentList();
127
128	/* Create super-segments for each super-node. */
129
130	for(i=0;i<nodesx->number;i++)
131	{
132	if(nodesx->idata[i]->super>iteration)
133	{
134	SegmentX segmentx,first;
135
136	segmentx=first=FindFirstSegmentX(segmentsx,nodesx->idata[i]->id);
137
138	while(segmentx)
139	{
140	WayX wayx=FindWayX(waysx,(segmentx)->way);
141
142	/* Check that this type of way hasn't already been routed */
143
144	if(segmentx!=first)
145	{
146	SegmentX **othersegmentx=first;
147
148	while(othersegmentx && othersegmentx!=segmentx)
149	{
150	WayX otherwayx=FindWayX(waysx,(othersegmentx)->way);
151
152	if(!WaysCompare(otherwayx->way,wayx->way))
153	{
154	wayx=NULL;
155	break;
156	}
157
158	othersegmentx=FindNextSegmentX(segmentsx,othersegmentx);
159	}
160	}
161
162	/* Route the way and store the super-segments. */
163
164	if(wayx)
165	{
166	Results *results=FindRoutesWay(nodesx,segmentsx,waysx,nodesx->idata[i]->id,wayx->way,iteration);
167	Result *result=FirstResult(results);
168
169	while(result)
170	{
171	NodeX **nodex=FindNodeX(nodesx,result->node);
172	WayX wayx =FindWayX (waysx ,(segmentx)->way);
173
174	if(result->node!=nodesx->idata[i]->id && (*nodex)->super>iteration)
175	{
176	if(wayx->way->type&Way_OneWay)
177	{
178	AppendSegment(supersegmentsx,wayx->id,nodesx->idata[i]->id,result->node,DISTANCE((distance_t)result->score)\|ONEWAY_1TO2);
179
180	AppendSegment(supersegmentsx,wayx->id,result->node,nodesx->idata[i]->id,DISTANCE((distance_t)result->score)\|ONEWAY_2TO1);
181
182	ss+=2;
183	}
184	else
185	{
186	AppendSegment(supersegmentsx,wayx->id,result->node,nodesx->idata[i]->id,DISTANCE((distance_t)result->score));
187
188	ss++;
189	}
190	}
191
192	result=NextResult(results,result);
193	}
194
195	FreeResultsList(results);
196	}
197
198	segmentx=FindNextSegmentX(segmentsx,segmentx);
199	}
200	}
201
202	if(!((i+1)%10000))
203	{
204	printf("\rCreating Super-Segments: Nodes=%d Super-Segments=%d",i+1,ss);
205	fflush(stdout);
206	}
207	}
208
209	printf("\rCreated Super-Segments: Nodes=%d Super-Segments=%d \n",nodesx->number,ss);
210	fflush(stdout);
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	index_t i,j;
227	int m=0,a=0;
228
229	assert(segmentsx->sorted); /* Must be sorted */
230	assert(segmentsx->ndata); /* Must have ndata filled in */
231	assert(supersegmentsx->sorted); /* Must be sorted */
232	assert(supersegmentsx->ndata); /* Must have ndata filled in */
233
234	for(i=0,j=0;i<segmentsx->number;i++)
235	{
236	while(j<supersegmentsx->number)
237	{
238	if(segmentsx->ndata[i]->node1==supersegmentsx->ndata[j]->node1 &&
239	segmentsx->ndata[i]->node2==supersegmentsx->ndata[j]->node2 &&
240	segmentsx->ndata[i]->distance==supersegmentsx->ndata[j]->distance)
241	{
242	segmentsx->ndata[i]->distance\|=SEGMENT_SUPER; /* mark as super-segment */
243	m++;
244	j++;
245	break;
246	}
247	else if((segmentsx->ndata[i]->node1==supersegmentsx->ndata[j]->node1 &&
248	segmentsx->ndata[i]->node2==supersegmentsx->ndata[j]->node2) \|\|
249	(segmentsx->ndata[i]->node1==supersegmentsx->ndata[j]->node1 &&
250	segmentsx->ndata[i]->node2>supersegmentsx->ndata[j]->node2) \|\|
251	(segmentsx->ndata[i]->node1>supersegmentsx->ndata[j]->node1))
252	{
253	supersegmentsx->ndata[j]->distance\|=SEGMENT_SUPER; /* mark as super-segment */
254	AppendSegment(segmentsx,supersegmentsx->ndata[j]->way,supersegmentsx->ndata[j]->node1,supersegmentsx->ndata[j]->node2,supersegmentsx->ndata[j]->distance);
255	a++;
256	j++;
257	}
258	else
259	break;
260	}
261
262	segmentsx->ndata[i]->distance\|=SEGMENT_NORMAL; /* mark as normal segment */
263
264	if(!((i+1)%10000))
265	{
266	printf("\rMerging: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
267	fflush(stdout);
268	}
269	}
270
271	printf("\rMerged: Segments=%d Super-Segments=%d Merged=%d Added=%d \n",segmentsx->number,supersegmentsx->number,m,a);
272	fflush(stdout);
273	}
274
275
276	/*++++++++++++++++++++++++++++++++++++++
277	Find all routes from a specified node to any node in the specified list that follows a certain type of way.
278
279	Results *FindRoutesWay Returns a set of results.
280
281	NodesX *nodesx The set of nodes to use.
282
283	SegmentsX *segmentsx The set of segments to use.
284
285	WaysX *waysx The set of ways to use.
286
287	node_t start The start node.
288
289	Way *match The way that the route must match.
290
291	int iteration The current super-node / super-segment iteration number.
292	++++++++++++++++++++++++++++++++++++++*/
293
294	Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,Way *match,int iteration)
295	{
296	Results *results;
297	index_t node1,node2;
298	Result result1,result2;
299	NodeX **nodex;
300	SegmentX **segmentx;
301	WayX *wayx;
302
303	/* Insert the first node into the queue */
304
305	results=NewResultsList(8);
306
307	result1=InsertResult(results,start);
308
309	ZeroResult(result1);
310
311	insert_in_queue(result1);
312
313	/* Loop across all nodes in the queue */
314
315	while((result1=pop_from_queue()))
316	{
317	node1=result1->node;
318
319	segmentx=FindFirstSegmentX(segmentsx,node1);
320
321	while(segmentx)
322	{
323	distance_t cumulative_distance;
324
325	if((*segmentx)->distance&ONEWAY_2TO1)
326	goto endloop;
327
328	node2=(*segmentx)->node2;
329
330	if(result1->prev==node2)
331	goto endloop;
332
333	wayx=FindWayX(waysx,(*segmentx)->way);
334
335	if(WaysCompare(wayx->way,match))
336	goto endloop;
337
338	cumulative_distance=(distance_t)result1->score+DISTANCE((*segmentx)->distance);
339
340	result2=FindResult(results,node2);
341
342	if(!result2) /* New end node */
343	{
344	result2=InsertResult(results,node2);
345	result2->prev=node1;
346	result2->next=NO_NODE;
347	result2->score=cumulative_distance;
348	result2->sortby=cumulative_distance;
349
350	nodex=FindNodeX(nodesx,node2);
351
352	if((*nodex)->super<=iteration)
353	insert_in_queue(result2);
354	}
355	else if(cumulative_distance<result2->score)
356	{
357	result2->prev=node1;
358	result2->score=cumulative_distance;
359	result2->sortby=cumulative_distance;
360
361	nodex=FindNodeX(nodesx,node2);
362
363	if((*nodex)->super<=iteration)
364	insert_in_queue(result2);
365	}
366
367	endloop:
368
369	segmentx=FindNextSegmentX(segmentsx,segmentx);
370	}
371	}
372
373	return(results);
374	}