trunk/src/supersegments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.18 2009-01-25 12:09:15 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=LookupWay(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.
  ++++++++++++++++++++++++++++++++++++++*/

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

 /* 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=LookupWay(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=LookupWay(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);
          Result *result=FirstResult(results);

          while(result)
            {
             if(result->node!=supernodes->nodes[i].id && FindNode(supernodes,result->node))
               {
                Segment *supersegment=AppendSegment(supersegments,supernodes->nodes[i].id,result->node,IndexWay(ways,way));

                supersegment->distance=result->shortest.distance;

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

                   supersegment->distance=ONEWAY_OPPOSITE|result->shortest.distance;
                  }
               }

             result=NextResult(results,result);
            }

          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=LookupWay(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=j;
          break;
         }

    if(j==superways->number)
      {
       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=IndexWay(superways->ways,newway);
      }

    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.18 2009-01-25 12:09:15 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=LookupWay(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
122	SegmentsMem CreateSuperSegments(Nodes nodes,Segments segments,Ways ways,Nodes *supernodes)
123	{
124	SegmentsMem *supersegments;
125	int i;
126
127	/* Create super-segments */
128
129	supersegments=NewSegmentList();
130
131	/* Create super-segments for each super-node. */
132
133	for(i=0;i<supernodes->number;i++)
134	{
135	Segment segment,first;
136
137	segment=first=FindFirstSegment(segments,supernodes->nodes[i].id);
138
139	while(segment)
140	{
141	Way *way=LookupWay(ways,segment->way);
142
143	/* Check that this type of way hasn't already been routed */
144
145	if(segment!=first)
146	{
147	Segment *othersegment=first;
148
149	while(othersegment && othersegment!=segment)
150	{
151	Way *otherway=LookupWay(ways,othersegment->way);
152
153	if(otherway->type ==way->type &&
154	otherway->allow==way->allow &&
155	otherway->limit==way->limit)
156	{
157	way=NULL;
158	break;
159	}
160
161	othersegment=FindNextSegment(segments,othersegment);
162	}
163	}
164
165	/* Route the way and store the super-segments. */
166
167	if(way)
168	{
169	Results *results=FindRoutesWay(nodes,segments,ways,supernodes->nodes[i].id,supernodes,way);
170	Result *result=FirstResult(results);
171
172	while(result)
173	{
174	if(result->node!=supernodes->nodes[i].id && FindNode(supernodes,result->node))
175	{
176	Segment *supersegment=AppendSegment(supersegments,supernodes->nodes[i].id,result->node,IndexWay(ways,way));
177
178	supersegment->distance=result->shortest.distance;
179
180	if(way->type&Way_OneWay)
181	{
182	supersegment=AppendSegment(supersegments,result->node,supernodes->nodes[i].id,IndexWay(ways,way));
183
184	supersegment->distance=ONEWAY_OPPOSITE\|result->shortest.distance;
185	}
186	}
187
188	result=NextResult(results,result);
189	}
190
191	FreeResultsList(results);
192	}
193
194	segment=FindNextSegment(segments,segment);
195	}
196
197	if(!((i+1)%1000))
198	{
199	printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",i+1,supersegments->number);
200	fflush(stdout);
201	}
202	}
203
204	printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",supernodes->number,supersegments->number);
205	fflush(stdout);
206
207	return(supersegments);
208	}
209
210
211	/*++++++++++++++++++++++++++++++++++++++
212	Create the Super-Ways from the Super-Segments.
213
214	WaysMem *CreateSuperWays Returns the set of super-ways.
215
216	Ways *ways The list of ways.
217
218	SegmentsMem *supersegments The list of super-segments.
219	++++++++++++++++++++++++++++++++++++++*/
220
221	WaysMem CreateSuperWays(Ways ways,SegmentsMem *supersegments)
222	{
223	WaysMem *superways;
224	int i,j;
225
226	/* Create super-ways */
227
228	superways=NewWayList();
229
230	/* Create a new super-way to replace each existing way. */
231
232	for(i=0;i<supersegments->segments->number;i++)
233	{
234	Way *way=LookupWay(ways,supersegments->segments->segments[i].way);
235
236	supersegments->segments->segments[i].way=0;
237
238	for(j=0;j<superways->number;j++)
239	if(superways->ways->ways[j].type ==way->type &&
240	superways->ways->ways[j].allow==way->allow &&
241	superways->ways->ways[j].limit==way->limit)
242	{
243	supersegments->segments->segments[i].way=j;
244	break;
245	}
246
247	if(j==superways->number)
248	{
249	Way *newway=AppendWay(superways,superways->number+1,"Super-Way");
250
251	newway->limit=way->limit;
252	newway->type =way->type;
253	newway->allow=way->allow;
254
255	supersegments->segments->segments[i].way=IndexWay(superways->ways,newway);
256	}
257
258	if(!((i+1)%10000))
259	{
260	printf("\rCreating Super-Ways: Super-Segments=%d Super-Ways=%d",i+1,superways->number);
261	fflush(stdout);
262	}
263	}
264
265	printf("\rCreated Super-Ways: Super-Segments=%d Super-Ways=%d \n",supersegments->number,superways->number);
266	fflush(stdout);
267
268	return(superways);
269	}