trunk/src/supersegments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.10 2009-01-19 19:51:42 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.

  NodesMem *ChooseSuperNodes Returns the list of super-nodes.

  Nodes *nodes The nodes.

  Segments *segments The existing segments.

  Ways *ways The ways.
  ++++++++++++++++++++++++++++++++++++++*/

NodesMem *ChooseSuperNodes(Nodes *nodes,Segments *segments,Ways *ways)
{
 int i;
 int        exitcount=0,difference=0;
 node_t     node=0;
 speed_t    limit=0;
 waytype_t  type=0;
 wayallow_t allow=0;
 NodesMem *supernodes;

 /* Create super-nodes */

 supernodes=NewNodeList();

 /* Find super-nodes */

 node=segments->segments[0].node1;

 for(i=0;i<segments->number;i++)
   {
    Segment *segment=&segments->segments[i];
    Way *way=FindWay(ways,segment->way);

    if(segment->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 || exitcount>2)
         {
          Node *oldnode=FindNode(nodes,node);

          AppendNode(supernodes,node,oldnode->latitude,oldnode->longitude);
         }

       exitcount=0;
       difference=0;

       node=segment->node1;
       type=Way_TYPE(way->type);
       limit=way->limit;
       allow=way->allow;
      }
    else                        /* Same starting node */
      {
       if(Way_TYPE(way->type)!=type)
          difference=1;

       if(way->limit!=limit)
          difference=1;

       if(way->allow!=allow)
          difference=1;
      }

    if(segment->distance!=INVALID_SHORT_DISTANCE)
      {
       if(way->type&Way_OneWay)
          exitcount+=2;
       else
          exitcount+=1;
      }

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

 printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d  \n",segments->number,supernodes->number);
 fflush(stdout);

 return(supernodes);
}


/*++++++++++++++++++++++++++++++++++++++
  Create the super-segments.

  SegmentsMem *CreateSuperSegments Returns the set of super-segments.

  Nodes *nodes The list of nodes.

  Segments *segments The list of segments.

  Ways *ways The list of ways.

  Nodes *supernodes The list of super-nodes.

  int iteration The iteration number of super-segment generation.
  ++++++++++++++++++++++++++++++++++++++*/

SegmentsMem *CreateSuperSegments(Nodes *nodes,Segments *segments,Ways *ways,Nodes *supernodes,int iteration)
{
 SegmentsMem *supersegments;
 int i,j;

 /* Create super-segments */

 supersegments=NewSegmentList();

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

 for(i=0;i<supernodes->number;i++)
   {
    Segment *segment,*first;

    segment=first=FindFirstSegment(segments,supernodes->nodes[i].id);

    while(segment)
      {
       Way *way=FindWay(ways,segment->way);

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

       if(segment!=first)
         {
          Segment *othersegment=first;

          while(othersegment && othersegment!=segment)
            {
             Way *otherway=FindWay(ways,othersegment->way);

             if(Way_TYPE(otherway->type)==Way_TYPE(way->type) &&
                otherway->allow==way->allow &&
                otherway->limit==way->limit)
               {
                way=NULL;
                break;
               }

             othersegment=FindNextSegment(segments,othersegment);
            }
         }

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

       if(way)
         {
          Results *results=FindRoutesWay(nodes,segments,ways,supernodes->nodes[i].id,supernodes,way,iteration);

          for(j=0;j<results->number;j++)
             if(results->results[j].node!=supernodes->nodes[i].id && FindNode(supernodes,results->results[j].node))
               {
                Segment *supersegment=AppendSegment(supersegments,supernodes->nodes[i].id,results->results[j].node,segment->way);
                distance_t distance;
                duration_t duration;

                if(iteration)
                  {
                   distance=1+results->results[j].shortest.distance/10;
                   duration=1+results->results[j].quickest.duration/10;
                  }
                else
                  {
                   distance=results->results[j].shortest.distance;
                   duration=results->results[j].quickest.duration;
                  }

                if(distance>=INVALID_SHORT_DISTANCE)
                  {
                   fprintf(stderr,"\nSuper-Segment too long (%d->%d) = %.1f km\n",supersegment->node1,supersegment->node2,distance_to_km(distance*(iteration?10:1)));
                   distance=INVALID_SHORT_DISTANCE;
                  }

                if(duration>INVALID_SHORT_DURATION)
                  {
                   fprintf(stderr,"\nSuper-Segment too long (%d->%d) = %.1f mins\n",supersegment->node1,supersegment->node2,duration_to_minutes(duration*(iteration?10:1)));
                   duration=INVALID_SHORT_DURATION;
                  }

                supersegment->distance=distance;
                supersegment->duration=duration;
               }

          FreeResultsList(results);
         }

       segment=FindNextSegment(segments,segment);
      }

    if(!((i+1)%1000))
      {
       printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",i+1,supersegments->number);
       fflush(stdout);
      }
   }

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

 return(supersegments);
}


/*++++++++++++++++++++++++++++++++++++++
  Create the Super-Ways from the Super-Segments.

  WaysMem *CreateSuperWays Returns the set of super-ways.

  Ways *ways The list of ways.

  SegmentsMem *supersegments The list of super-segments.
  ++++++++++++++++++++++++++++++++++++++*/

WaysMem *CreateSuperWays(Ways *ways,SegmentsMem *supersegments)
{
 WaysMem *superways;
 int i,j;

 /* Create super-ways */

 superways=NewWayList();

 /* Create a new super-way to replace each existing way. */

 for(i=0;i<supersegments->segments->number;i++)
   {
    Way *way=FindWay(ways,supersegments->segments->segments[i].way);

    supersegments->segments->segments[i].way=0;

    for(j=0;j<superways->number;j++)
       if(Way_TYPE(superways->ways->ways[j].type)==Way_TYPE(way->type) &&
          superways->ways->ways[j].allow==way->allow &&
          superways->ways->ways[j].limit==way->limit)
         {
          supersegments->segments->segments[i].way=superways->ways->ways[j].id;
          break;
         }

    if(!supersegments->segments->segments[i].way)
      {
       Way *newway=AppendWay(superways,superways->number+1,"Super-Way");

       newway->limit=way->limit;
       newway->type =Way_TYPE(way->type);
       newway->allow=way->allow;
       newway->speed=way->speed;

       supersegments->segments->segments[i].way=newway->id;
      }

    if(!((i+1)%10000))
      {
       printf("\rCreating Super-Ways: Super-Segments=%d Super-Ways=%d",i+1,superways->number);
       fflush(stdout);
      }
   }

 printf("\rCreated Super-Ways: Super-Segments=%d Super-Ways=%d \n",supersegments->number,superways->number);
 fflush(stdout);

 return(superways);
}
1	/***************************************
2	$Header: /home/amb/CVS/routino/src/supersegments.c,v 1.10 2009-01-19 19:51:42 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	NodesMem *ChooseSuperNodes Returns the list of super-nodes.
29
30	Nodes *nodes The nodes.
31
32	Segments *segments The existing segments.
33
34	Ways *ways The ways.
35	++++++++++++++++++++++++++++++++++++++*/
36
37	NodesMem ChooseSuperNodes(Nodes nodes,Segments segments,Ways ways)
38	{
39	int i;
40	int exitcount=0,difference=0;
41	node_t node=0;
42	speed_t limit=0;
43	waytype_t type=0;
44	wayallow_t allow=0;
45	NodesMem *supernodes;
46
47	/* Create super-nodes */
48
49	supernodes=NewNodeList();
50
51	/* Find super-nodes */
52
53	node=segments->segments[0].node1;
54
55	for(i=0;i<segments->number;i++)
56	{
57	Segment *segment=&segments->segments[i];
58	Way *way=FindWay(ways,segment->way);
59
60	if(segment->node1!=node)
61	{
62	/* Store the node if there is a difference in the ways that could affect routing.
63	Store the node if it is not a dead-end and if it isn't just the middle of a way. */
64
65	if(difference \|\| exitcount>2)
66	{
67	Node *oldnode=FindNode(nodes,node);
68
69	AppendNode(supernodes,node,oldnode->latitude,oldnode->longitude);
70	}
71
72	exitcount=0;
73	difference=0;
74
75	node=segment->node1;
76	type=Way_TYPE(way->type);
77	limit=way->limit;
78	allow=way->allow;
79	}
80	else /* Same starting node */
81	{
82	if(Way_TYPE(way->type)!=type)
83	difference=1;
84
85	if(way->limit!=limit)
86	difference=1;
87
88	if(way->allow!=allow)
89	difference=1;
90	}
91
92	if(segment->distance!=INVALID_SHORT_DISTANCE)
93	{
94	if(way->type&Way_OneWay)
95	exitcount+=2;
96	else
97	exitcount+=1;
98	}
99
100	if(!((i+1)%10000))
101	{
102	printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i+1,supernodes->number);
103	fflush(stdout);
104	}
105	}
106
107	printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d \n",segments->number,supernodes->number);
108	fflush(stdout);
109
110	return(supernodes);
111	}
112
113
114	/*++++++++++++++++++++++++++++++++++++++
115	Create the super-segments.
116
117	SegmentsMem *CreateSuperSegments Returns the set of super-segments.
118
119	Nodes *nodes The list of nodes.
120
121	Segments *segments The list of segments.
122
123	Ways *ways The list of ways.
124
125	Nodes *supernodes The list of super-nodes.
126
127	int iteration The iteration number of super-segment generation.
128	++++++++++++++++++++++++++++++++++++++*/
129
130	SegmentsMem CreateSuperSegments(Nodes nodes,Segments segments,Ways ways,Nodes *supernodes,int iteration)
131	{
132	SegmentsMem *supersegments;
133	int i,j;
134
135	/* Create super-segments */
136
137	supersegments=NewSegmentList();
138
139	/* Create super-segments for each super-node. */
140
141	for(i=0;i<supernodes->number;i++)
142	{
143	Segment segment,first;
144
145	segment=first=FindFirstSegment(segments,supernodes->nodes[i].id);
146
147	while(segment)
148	{
149	Way *way=FindWay(ways,segment->way);
150
151	/* Check that this type of way hasn't already been routed */
152
153	if(segment!=first)
154	{
155	Segment *othersegment=first;
156
157	while(othersegment && othersegment!=segment)
158	{
159	Way *otherway=FindWay(ways,othersegment->way);
160
161	if(Way_TYPE(otherway->type)==Way_TYPE(way->type) &&
162	otherway->allow==way->allow &&
163	otherway->limit==way->limit)
164	{
165	way=NULL;
166	break;
167	}
168
169	othersegment=FindNextSegment(segments,othersegment);
170	}
171	}
172
173	/* Route the way and store the super-segments. */
174
175	if(way)
176	{
177	Results *results=FindRoutesWay(nodes,segments,ways,supernodes->nodes[i].id,supernodes,way,iteration);
178
179	for(j=0;j<results->number;j++)
180	if(results->results[j].node!=supernodes->nodes[i].id && FindNode(supernodes,results->results[j].node))
181	{
182	Segment *supersegment=AppendSegment(supersegments,supernodes->nodes[i].id,results->results[j].node,segment->way);
183	distance_t distance;
184	duration_t duration;
185
186	if(iteration)
187	{
188	distance=1+results->results[j].shortest.distance/10;
189	duration=1+results->results[j].quickest.duration/10;
190	}
191	else
192	{
193	distance=results->results[j].shortest.distance;
194	duration=results->results[j].quickest.duration;
195	}
196
197	if(distance>=INVALID_SHORT_DISTANCE)
198	{
199	fprintf(stderr,"\nSuper-Segment too long (%d->%d) = %.1f km\n",supersegment->node1,supersegment->node2,distance_to_km(distance*(iteration?10:1)));
200	distance=INVALID_SHORT_DISTANCE;
201	}
202
203	if(duration>INVALID_SHORT_DURATION)
204	{
205	fprintf(stderr,"\nSuper-Segment too long (%d->%d) = %.1f mins\n",supersegment->node1,supersegment->node2,duration_to_minutes(duration*(iteration?10:1)));
206	duration=INVALID_SHORT_DURATION;
207	}
208
209	supersegment->distance=distance;
210	supersegment->duration=duration;
211	}
212
213	FreeResultsList(results);
214	}
215
216	segment=FindNextSegment(segments,segment);
217	}
218
219	if(!((i+1)%1000))
220	{
221	printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",i+1,supersegments->number);
222	fflush(stdout);
223	}
224	}
225
226	printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",supernodes->number,supersegments->number);
227	fflush(stdout);
228
229	return(supersegments);
230	}
231
232
233	/*++++++++++++++++++++++++++++++++++++++
234	Create the Super-Ways from the Super-Segments.
235
236	WaysMem *CreateSuperWays Returns the set of super-ways.
237
238	Ways *ways The list of ways.
239
240	SegmentsMem *supersegments The list of super-segments.
241	++++++++++++++++++++++++++++++++++++++*/
242
243	WaysMem CreateSuperWays(Ways ways,SegmentsMem *supersegments)
244	{
245	WaysMem *superways;
246	int i,j;
247
248	/* Create super-ways */
249
250	superways=NewWayList();
251
252	/* Create a new super-way to replace each existing way. */
253
254	for(i=0;i<supersegments->segments->number;i++)
255	{
256	Way *way=FindWay(ways,supersegments->segments->segments[i].way);
257
258	supersegments->segments->segments[i].way=0;
259
260	for(j=0;j<superways->number;j++)
261	if(Way_TYPE(superways->ways->ways[j].type)==Way_TYPE(way->type) &&
262	superways->ways->ways[j].allow==way->allow &&
263	superways->ways->ways[j].limit==way->limit)
264	{
265	supersegments->segments->segments[i].way=superways->ways->ways[j].id;
266	break;
267	}
268
269	if(!supersegments->segments->segments[i].way)
270	{
271	Way *newway=AppendWay(superways,superways->number+1,"Super-Way");
272
273	newway->limit=way->limit;
274	newway->type =Way_TYPE(way->type);
275	newway->allow=way->allow;
276	newway->speed=way->speed;
277
278	supersegments->segments->segments[i].way=newway->id;
279	}
280
281	if(!((i+1)%10000))
282	{
283	printf("\rCreating Super-Ways: Super-Segments=%d Super-Ways=%d",i+1,superways->number);
284	fflush(stdout);
285	}
286	}
287
288	printf("\rCreated Super-Ways: Super-Segments=%d Super-Ways=%d \n",supersegments->number,superways->number);
289	fflush(stdout);
290
291	return(superways);
292	}