trunk/src/superx.c

/***************************************
 $Header: /home/amb/CVS/routino/src/superx.c,v 1.30 2009-09-06 15:51:09 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"
#include "ways.h"


/* Local Functions */

static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration);


/*++++++++++++++++++++++++++++++++++++++
  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 nnodes=0;

 assert(nodesx->idata);         /* Must have idata filled in => sorted by id */

 printf("Finding Super-Nodes: Nodes=0 Super-Nodes=0");
 fflush(stdout);

 /* Find super-nodes */

 for(i=0;i<nodesx->number;i++)
   {
    int      difference=0;
    index_t *index;

    index=IndexFirstSegmentX(segmentsx,nodesx->idata[i]);

    if(index)
      {
       SegmentX *segmentx=FindSegmentX(segmentsx,*index);
       WayX *wayx1=FindWayX(waysx,segmentx->way);

       index=IndexNextSegmentX(segmentsx,index);

       if(index)
         {
          segmentx=FindSegmentX(segmentsx,*index);
          WayX *wayx2=FindWayX(waysx,segmentx->way);

          if(WaysCompare(wayx2->way,wayx1->way))
             difference=1;

          index=IndexNextSegmentX(segmentsx,index);
         }

       /* Store the node if there is a difference in the first two ways that could affect routing.
          Store the node if it has at least three segments. */

       if(difference || index)
         {
          nodesx->super[i]++;

          nnodes++;
         }
      }

    if(!((i+1)%10000))
      {
       printf("\rFinding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
       fflush(stdout);
      }
   }

 printf("\rFound Super-Nodes: Nodes=%d Super-Nodes=%d  \n",nodesx->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 sn=0,ss=0;

 assert(nodesx->idata);         /* Must have idata filled in => sorted by id */

 printf("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
 fflush(stdout);

 supersegmentsx=NewSegmentList();

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

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

       index=first=IndexFirstSegmentX(segmentsx,nodesx->idata[i]);

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

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

          if(index!=first)
            {
             index_t *otherindex=first;

             while(otherindex && otherindex!=index)
               {
                SegmentX *othersegmentx=FindSegmentX(segmentsx,*otherindex);
                WayX *otherwayx=FindWayX(waysx,othersegmentx->way);

                if(!WaysCompare(otherwayx->way,wayx->way))
                  {
                   wayx=NULL;
                   break;
                  }

                otherindex=IndexNextSegmentX(segmentsx,otherindex);
               }
            }

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

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

             while(result)
               {
                index_t nindex=IndexNodeX(nodesx,result->node);

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

                   ss++;
                  }

                result=NextResult(results,result);
               }

             FreeResultsList(results);
            }

          index=IndexNextSegmentX(segmentsx,index);
         }

       sn++;

       if(!(sn%10000))
         {
          printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
          fflush(stdout);
         }
      }
   }

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

 return(supersegmentsx);
}


/*++++++++++++++++++++++++++++++++++++++
  Merge the segments and super-segments into a new segment list.

  SegmentsX* MergeSuperSegments Returns a new set of merged segments.

  SegmentsX* segmentsx The set of segments to process.

  SegmentsX* supersegmentsx The set of super-segments to merge.
  ++++++++++++++++++++++++++++++++++++++*/

SegmentsX *MergeSuperSegments(SegmentsX* segmentsx,SegmentsX* supersegmentsx)
{
 index_t i,j;
 int m=0,a=0;
 SegmentsX* mergedsegmentsx;

 assert(segmentsx->n1data);      /* Must have n1data filled in => sorted by node 1 */
 assert(supersegmentsx->n1data); /* Must have n1data filled in => sorted by node 1 */

 printf("Merging: Segments=0 Super-Segments=0 Merged=0 Added=0");
 fflush(stdout);

 mergedsegmentsx=NewSegmentList();

 for(i=0,j=0;i<segmentsx->number;i++)
   {
    int super=0;
    SegmentX *segmentx=FindSegmentX(segmentsx,segmentsx->n1data[i]);

    while(j<supersegmentsx->number)
      {
       SegmentX *supersegmentx=FindSegmentX(supersegmentsx,supersegmentsx->n1data[j]);

       if(segmentx->node1   ==supersegmentx->node1 &&
          segmentx->node2   ==supersegmentx->node2 &&
          segmentx->distance==supersegmentx->distance)
         {
          /* mark as super-segment and normal segment */
          super=1;
          m++;
          j++;
          break;
         }
       else if((segmentx->node1==supersegmentx->node1 &&
                segmentx->node2==supersegmentx->node2) ||
               (segmentx->node1==supersegmentx->node1 &&
                segmentx->node2>supersegmentx->node2) ||
               (segmentx->node1>supersegmentx->node1))
         {
          /* mark as super-segment */
          AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance|SEGMENT_SUPER);
          a++;
          j++;
         }
       else
          break;
      }

    if(super)
       AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_SUPER|SEGMENT_NORMAL);
    else
       AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance|SEGMENT_NORMAL);

    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);

 return(mergedsegmentsx);
}


/*++++++++++++++++++++++++++++++++++++++
  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.
  ++++++++++++++++++++++++++++++++++++++*/

static Results *FindRoutesWay(NodesX *nodesx,SegmentsX *segmentsx,WaysX *waysx,node_t start,Way *match,int iteration)
{
 Results *results;
 Queue *queue;
 index_t node1,node2;
 Result *result1,*result2;
 index_t *index;
 WayX *wayx;

 /* Insert the first node into the queue */

 results=NewResultsList(8);

 queue=NewQueueList();

 result1=InsertResult(results,start);

 ZeroResult(result1);

 InsertInQueue(queue,result1);

 /* Loop across all nodes in the queue */

 while((result1=PopFromQueue(queue)))
   {
    node1=result1->node;

    index=IndexFirstSegmentX(segmentsx,node1);

    while(index)
      {
       SegmentX *segmentx=FindSegmentX(segmentsx,*index);
       distance_t cumulative_distance;

       if(segmentx->node1==node1) /* Correct way round */
         {
          if(segmentx->distance&ONEWAY_2TO1)
             goto endloop;

          node2=segmentx->node2;
         }
       else                          /* Opposite way round */
         {
          if(segmentx->distance&ONEWAY_1TO2)
             goto endloop;

          node2=segmentx->node1;
         }

       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;

          if(nodesx->super[IndexNodeX(nodesx,node2)]<=iteration)
             InsertInQueue(queue,result2);
         }
       else if(cumulative_distance<result2->score)
         {
          result2->prev=node1;
          result2->score=cumulative_distance;
          result2->sortby=cumulative_distance;

          if(nodesx->super[IndexNodeX(nodesx,node2)]<=iteration)
             InsertInQueue(queue,result2);
         }

      endloop:

       index=IndexNextSegmentX(segmentsx,index);
      }
   }

 FreeQueueList(queue);

 return(results);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/superx.c,v 1.30 2009-09-06 15:51:09 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	#include "ways.h"
35
36
37	/* Local Functions */
38
39	static Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,Way *match,int iteration);
40
41
42	/*++++++++++++++++++++++++++++++++++++++
43	Select the super-segments from the list of segments.
44
45	NodesX *nodesx The nodes.
46
47	SegmentsX *segmentsx The segments.
48
49	WaysX *waysx The ways.
50	++++++++++++++++++++++++++++++++++++++*/
51
52	void ChooseSuperNodes(NodesX nodesx,SegmentsX segmentsx,WaysX *waysx)
53	{
54	index_t i;
55	int nnodes=0;
56
57	assert(nodesx->idata); /* Must have idata filled in => sorted by id */
58
59	printf("Finding Super-Nodes: Nodes=0 Super-Nodes=0");
60	fflush(stdout);
61
62	/* Find super-nodes */
63
64	for(i=0;i<nodesx->number;i++)
65	{
66	int difference=0;
67	index_t *index;
68
69	index=IndexFirstSegmentX(segmentsx,nodesx->idata[i]);
70
71	if(index)
72	{
73	SegmentX segmentx=FindSegmentX(segmentsx,index);
74	WayX *wayx1=FindWayX(waysx,segmentx->way);
75
76	index=IndexNextSegmentX(segmentsx,index);
77
78	if(index)
79	{
80	segmentx=FindSegmentX(segmentsx,*index);
81	WayX *wayx2=FindWayX(waysx,segmentx->way);
82
83	if(WaysCompare(wayx2->way,wayx1->way))
84	difference=1;
85
86	index=IndexNextSegmentX(segmentsx,index);
87	}
88
89	/* Store the node if there is a difference in the first two ways that could affect routing.
90	Store the node if it has at least three segments. */
91
92	if(difference \|\| index)
93	{
94	nodesx->super[i]++;
95
96	nnodes++;
97	}
98	}
99
100	if(!((i+1)%10000))
101	{
102	printf("\rFinding Super-Nodes: Nodes=%d Super-Nodes=%d",i+1,nnodes);
103	fflush(stdout);
104	}
105	}
106
107	printf("\rFound Super-Nodes: Nodes=%d Super-Nodes=%d \n",nodesx->number,nnodes);
108	fflush(stdout);
109	}
110
111
112	/*++++++++++++++++++++++++++++++++++++++
113	Create the super-segments.
114
115	SegmentsX *CreateSuperSegments Creates the super segments.
116
117	NodesX *nodesx The nodes.
118
119	SegmentsX *segmentsx The segments.
120
121	WaysX *waysx The ways.
122
123	int iteration The current super-node / super-segment iteration number.
124	++++++++++++++++++++++++++++++++++++++*/
125
126	SegmentsX CreateSuperSegments(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,int iteration)
127	{
128	index_t i;
129	SegmentsX *supersegmentsx;
130	int sn=0,ss=0;
131
132	assert(nodesx->idata); /* Must have idata filled in => sorted by id */
133
134	printf("Creating Super-Segments: Super-Nodes=0 Super-Segments=0");
135	fflush(stdout);
136
137	supersegmentsx=NewSegmentList();
138
139	/* Create super-segments for each super-node. */
140
141	for(i=0;i<nodesx->number;i++)
142	{
143	if(nodesx->super[i]>iteration)
144	{
145	index_t index,first;
146
147	index=first=IndexFirstSegmentX(segmentsx,nodesx->idata[i]);
148
149	while(index)
150	{
151	SegmentX segmentx=FindSegmentX(segmentsx,index);
152	WayX *wayx=FindWayX(waysx,segmentx->way);
153
154	/* Check that this type of way hasn't already been routed */
155
156	if(index!=first)
157	{
158	index_t *otherindex=first;
159
160	while(otherindex && otherindex!=index)
161	{
162	SegmentX othersegmentx=FindSegmentX(segmentsx,otherindex);
163	WayX *otherwayx=FindWayX(waysx,othersegmentx->way);
164
165	if(!WaysCompare(otherwayx->way,wayx->way))
166	{
167	wayx=NULL;
168	break;
169	}
170
171	otherindex=IndexNextSegmentX(segmentsx,otherindex);
172	}
173	}
174
175	/* Route the way and store the super-segments. */
176
177	if(wayx)
178	{
179	Results *results=FindRoutesWay(nodesx,segmentsx,waysx,nodesx->idata[i],wayx->way,iteration);
180	Result *result=FirstResult(results);
181
182	while(result)
183	{
184	index_t nindex=IndexNodeX(nodesx,result->node);
185
186	if(result->node!=nodesx->idata[i] && nodesx->super[nindex]>iteration)
187	{
188	if(wayx->way->type&Way_OneWay)
189	AppendSegment(supersegmentsx,wayx->id,nodesx->idata[i],result->node,DISTANCE((distance_t)result->score)\|ONEWAY_1TO2);
190	else
191	AppendSegment(supersegmentsx,wayx->id,nodesx->idata[i],result->node,DISTANCE((distance_t)result->score));
192
193	ss++;
194	}
195
196	result=NextResult(results,result);
197	}
198
199	FreeResultsList(results);
200	}
201
202	index=IndexNextSegmentX(segmentsx,index);
203	}
204
205	sn++;
206
207	if(!(sn%10000))
208	{
209	printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",sn,ss);
210	fflush(stdout);
211	}
212	}
213	}
214
215	printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",sn,ss);
216	fflush(stdout);
217
218	return(supersegmentsx);
219	}
220
221
222	/*++++++++++++++++++++++++++++++++++++++
223	Merge the segments and super-segments into a new segment list.
224
225	SegmentsX* MergeSuperSegments Returns a new set of merged segments.
226
227	SegmentsX* segmentsx The set of segments to process.
228
229	SegmentsX* supersegmentsx The set of super-segments to merge.
230	++++++++++++++++++++++++++++++++++++++*/
231
232	SegmentsX MergeSuperSegments(SegmentsX segmentsx,SegmentsX* supersegmentsx)
233	{
234	index_t i,j;
235	int m=0,a=0;
236	SegmentsX* mergedsegmentsx;
237
238	assert(segmentsx->n1data); /* Must have n1data filled in => sorted by node 1 */
239	assert(supersegmentsx->n1data); /* Must have n1data filled in => sorted by node 1 */
240
241	printf("Merging: Segments=0 Super-Segments=0 Merged=0 Added=0");
242	fflush(stdout);
243
244	mergedsegmentsx=NewSegmentList();
245
246	for(i=0,j=0;i<segmentsx->number;i++)
247	{
248	int super=0;
249	SegmentX *segmentx=FindSegmentX(segmentsx,segmentsx->n1data[i]);
250
251	while(j<supersegmentsx->number)
252	{
253	SegmentX *supersegmentx=FindSegmentX(supersegmentsx,supersegmentsx->n1data[j]);
254
255	if(segmentx->node1 ==supersegmentx->node1 &&
256	segmentx->node2 ==supersegmentx->node2 &&
257	segmentx->distance==supersegmentx->distance)
258	{
259	/* mark as super-segment and normal segment */
260	super=1;
261	m++;
262	j++;
263	break;
264	}
265	else if((segmentx->node1==supersegmentx->node1 &&
266	segmentx->node2==supersegmentx->node2) \|\|
267	(segmentx->node1==supersegmentx->node1 &&
268	segmentx->node2>supersegmentx->node2) \|\|
269	(segmentx->node1>supersegmentx->node1))
270	{
271	/* mark as super-segment */
272	AppendSegment(mergedsegmentsx,supersegmentx->way,supersegmentx->node1,supersegmentx->node2,supersegmentx->distance\|SEGMENT_SUPER);
273	a++;
274	j++;
275	}
276	else
277	break;
278	}
279
280	if(super)
281	AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance\|SEGMENT_SUPER\|SEGMENT_NORMAL);
282	else
283	AppendSegment(mergedsegmentsx,segmentx->way,segmentx->node1,segmentx->node2,segmentx->distance\|SEGMENT_NORMAL);
284
285	if(!((i+1)%10000))
286	{
287	printf("\rMerging: Segments=%d Super-Segments=%d Merged=%d Added=%d",i+1,j,m,a);
288	fflush(stdout);
289	}
290	}
291
292	printf("\rMerged: Segments=%d Super-Segments=%d Merged=%d Added=%d \n",segmentsx->number,supersegmentsx->number,m,a);
293	fflush(stdout);
294
295	return(mergedsegmentsx);
296	}
297
298
299	/*++++++++++++++++++++++++++++++++++++++
300	Find all routes from a specified node to any node in the specified list that follows a certain type of way.
301
302	Results *FindRoutesWay Returns a set of results.
303
304	NodesX *nodesx The set of nodes to use.
305
306	SegmentsX *segmentsx The set of segments to use.
307
308	WaysX *waysx The set of ways to use.
309
310	node_t start The start node.
311
312	Way *match The way that the route must match.
313
314	int iteration The current super-node / super-segment iteration number.
315	++++++++++++++++++++++++++++++++++++++*/
316
317	static Results FindRoutesWay(NodesX nodesx,SegmentsX segmentsx,WaysX waysx,node_t start,Way *match,int iteration)
318	{
319	Results *results;
320	Queue *queue;
321	index_t node1,node2;
322	Result result1,result2;
323	index_t *index;
324	WayX *wayx;
325
326	/* Insert the first node into the queue */
327
328	results=NewResultsList(8);
329
330	queue=NewQueueList();
331
332	result1=InsertResult(results,start);
333
334	ZeroResult(result1);
335
336	InsertInQueue(queue,result1);
337
338	/* Loop across all nodes in the queue */
339
340	while((result1=PopFromQueue(queue)))
341	{
342	node1=result1->node;
343
344	index=IndexFirstSegmentX(segmentsx,node1);
345
346	while(index)
347	{
348	SegmentX segmentx=FindSegmentX(segmentsx,index);
349	distance_t cumulative_distance;
350
351	if(segmentx->node1==node1) /* Correct way round */
352	{
353	if(segmentx->distance&ONEWAY_2TO1)
354	goto endloop;
355
356	node2=segmentx->node2;
357	}
358	else /* Opposite way round */
359	{
360	if(segmentx->distance&ONEWAY_1TO2)
361	goto endloop;
362
363	node2=segmentx->node1;
364	}
365
366	if(result1->prev==node2)
367	goto endloop;
368
369	wayx=FindWayX(waysx,segmentx->way);
370
371	if(WaysCompare(wayx->way,match))
372	goto endloop;
373
374	cumulative_distance=(distance_t)result1->score+DISTANCE(segmentx->distance);
375
376	result2=FindResult(results,node2);
377
378	if(!result2) /* New end node */
379	{
380	result2=InsertResult(results,node2);
381	result2->prev=node1;
382	result2->next=NO_NODE;
383	result2->score=cumulative_distance;
384	result2->sortby=cumulative_distance;
385
386	if(nodesx->super[IndexNodeX(nodesx,node2)]<=iteration)
387	InsertInQueue(queue,result2);
388	}
389	else if(cumulative_distance<result2->score)
390	{
391	result2->prev=node1;
392	result2->score=cumulative_distance;
393	result2->sortby=cumulative_distance;
394
395	if(nodesx->super[IndexNodeX(nodesx,node2)]<=iteration)
396	InsertInQueue(queue,result2);
397	}
398
399	endloop:
400
401	index=IndexNextSegmentX(segmentsx,index);
402	}
403	}
404
405	FreeQueueList(queue);
406
407	return(results);
408	}