trunk/src/supersegments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.14 2009-01-22 19:39:30 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        segcount=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 || segcount>2)
         {
          Node *oldnode=FindNode(nodes,node);

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

       segcount=1;
       difference=0;

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

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

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

       segcount+=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(otherway->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,way->id);

                supersegment->distance=results->results[j].shortest.distance;

                if(way->type&Way_OneWay)
                  {
                   supersegment=AppendSegment(supersegments,results->results[j].node,supernodes->nodes[i].id,way->id);

                   supersegment->distance=INVALID_DISTANCE;
                  }
               }

          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(superways->ways->ways[j].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;
       newway->allow=way->allow;

       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.14 2009-01-22 19:39:30 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 segcount=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 \|\| segcount>2)
66	{
67	Node *oldnode=FindNode(nodes,node);
68
69	AppendNode(supernodes,node,oldnode->latitude,oldnode->longitude);
70	}
71
72	segcount=1;
73	difference=0;
74
75	node=segment->node1;
76	type=way->type;
77	limit=way->limit;
78	allow=way->allow;
79	}
80	else /* Same starting node */
81	{
82	if(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	segcount+=1;
92	}
93
94	if(!((i+1)%10000))
95	{
96	printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i+1,supernodes->number);
97	fflush(stdout);
98	}
99	}
100
101	printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d \n",segments->number,supernodes->number);
102	fflush(stdout);
103
104	return(supernodes);
105	}
106
107
108	/*++++++++++++++++++++++++++++++++++++++
109	Create the super-segments.
110
111	SegmentsMem *CreateSuperSegments Returns the set of super-segments.
112
113	Nodes *nodes The list of nodes.
114
115	Segments *segments The list of segments.
116
117	Ways *ways The list of ways.
118
119	Nodes *supernodes The list of super-nodes.
120
121	int iteration The iteration number of super-segment generation.
122	++++++++++++++++++++++++++++++++++++++*/
123
124	SegmentsMem CreateSuperSegments(Nodes nodes,Segments segments,Ways ways,Nodes *supernodes,int iteration)
125	{
126	SegmentsMem *supersegments;
127	int i,j;
128
129	/* Create super-segments */
130
131	supersegments=NewSegmentList();
132
133	/* Create super-segments for each super-node. */
134
135	for(i=0;i<supernodes->number;i++)
136	{
137	Segment segment,first;
138
139	segment=first=FindFirstSegment(segments,supernodes->nodes[i].id);
140
141	while(segment)
142	{
143	Way *way=FindWay(ways,segment->way);
144
145	/* Check that this type of way hasn't already been routed */
146
147	if(segment!=first)
148	{
149	Segment *othersegment=first;
150
151	while(othersegment && othersegment!=segment)
152	{
153	Way *otherway=FindWay(ways,othersegment->way);
154
155	if(otherway->type ==way->type &&
156	otherway->allow==way->allow &&
157	otherway->limit==way->limit)
158	{
159	way=NULL;
160	break;
161	}
162
163	othersegment=FindNextSegment(segments,othersegment);
164	}
165	}
166
167	/* Route the way and store the super-segments. */
168
169	if(way)
170	{
171	Results *results=FindRoutesWay(nodes,segments,ways,supernodes->nodes[i].id,supernodes,way,iteration);
172
173	for(j=0;j<results->number;j++)
174	if(results->results[j].node!=supernodes->nodes[i].id && FindNode(supernodes,results->results[j].node))
175	{
176	Segment *supersegment=AppendSegment(supersegments,supernodes->nodes[i].id,results->results[j].node,way->id);
177
178	supersegment->distance=results->results[j].shortest.distance;
179
180	if(way->type&Way_OneWay)
181	{
182	supersegment=AppendSegment(supersegments,results->results[j].node,supernodes->nodes[i].id,way->id);
183
184	supersegment->distance=INVALID_DISTANCE;
185	}
186	}
187
188	FreeResultsList(results);
189	}
190
191	segment=FindNextSegment(segments,segment);
192	}
193
194	if(!((i+1)%1000))
195	{
196	printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",i+1,supersegments->number);
197	fflush(stdout);
198	}
199	}
200
201	printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",supernodes->number,supersegments->number);
202	fflush(stdout);
203
204	return(supersegments);
205	}
206
207
208	/*++++++++++++++++++++++++++++++++++++++
209	Create the Super-Ways from the Super-Segments.
210
211	WaysMem *CreateSuperWays Returns the set of super-ways.
212
213	Ways *ways The list of ways.
214
215	SegmentsMem *supersegments The list of super-segments.
216	++++++++++++++++++++++++++++++++++++++*/
217
218	WaysMem CreateSuperWays(Ways ways,SegmentsMem *supersegments)
219	{
220	WaysMem *superways;
221	int i,j;
222
223	/* Create super-ways */
224
225	superways=NewWayList();
226
227	/* Create a new super-way to replace each existing way. */
228
229	for(i=0;i<supersegments->segments->number;i++)
230	{
231	Way *way=FindWay(ways,supersegments->segments->segments[i].way);
232
233	supersegments->segments->segments[i].way=0;
234
235	for(j=0;j<superways->number;j++)
236	if(superways->ways->ways[j].type ==way->type &&
237	superways->ways->ways[j].allow==way->allow &&
238	superways->ways->ways[j].limit==way->limit)
239	{
240	supersegments->segments->segments[i].way=superways->ways->ways[j].id;
241	break;
242	}
243
244	if(!supersegments->segments->segments[i].way)
245	{
246	Way *newway=AppendWay(superways,superways->number+1,"Super-Way");
247
248	newway->limit=way->limit;
249	newway->type =way->type;
250	newway->allow=way->allow;
251
252	supersegments->segments->segments[i].way=newway->id;
253	}
254
255	if(!((i+1)%10000))
256	{
257	printf("\rCreating Super-Ways: Super-Segments=%d Super-Ways=%d",i+1,superways->number);
258	fflush(stdout);
259	}
260	}
261
262	printf("\rCreated Super-Ways: Super-Segments=%d Super-Ways=%d \n",supersegments->number,superways->number);
263	fflush(stdout);
264
265	return(superways);
266	}