trunk/src/supersegments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.16 2009-01-23 17:13:48 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.
  ++++++++++++++++++++++++++++++++++++++*/

SegmentsMem *CreateSuperSegments(Nodes *nodes,Segments *segments,Ways *ways,Nodes *supernodes)
{
 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);

          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=ONEWAY_OPPOSITE|results->results[j].shortest.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.16 2009-01-23 17:13:48 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
122	SegmentsMem CreateSuperSegments(Nodes nodes,Segments segments,Ways ways,Nodes *supernodes)
123	{
124	SegmentsMem *supersegments;
125	int i,j;
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=FindWay(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=FindWay(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
171	for(j=0;j<results->number;j++)
172	if(results->results[j].node!=supernodes->nodes[i].id && FindNode(supernodes,results->results[j].node))
173	{
174	Segment *supersegment=AppendSegment(supersegments,supernodes->nodes[i].id,results->results[j].node,way->id);
175
176	supersegment->distance=results->results[j].shortest.distance;
177
178	if(way->type&Way_OneWay)
179	{
180	supersegment=AppendSegment(supersegments,results->results[j].node,supernodes->nodes[i].id,way->id);
181
182	supersegment->distance=ONEWAY_OPPOSITE\|results->results[j].shortest.distance;
183	}
184	}
185
186	FreeResultsList(results);
187	}
188
189	segment=FindNextSegment(segments,segment);
190	}
191
192	if(!((i+1)%1000))
193	{
194	printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",i+1,supersegments->number);
195	fflush(stdout);
196	}
197	}
198
199	printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",supernodes->number,supersegments->number);
200	fflush(stdout);
201
202	return(supersegments);
203	}
204
205
206	/*++++++++++++++++++++++++++++++++++++++
207	Create the Super-Ways from the Super-Segments.
208
209	WaysMem *CreateSuperWays Returns the set of super-ways.
210
211	Ways *ways The list of ways.
212
213	SegmentsMem *supersegments The list of super-segments.
214	++++++++++++++++++++++++++++++++++++++*/
215
216	WaysMem CreateSuperWays(Ways ways,SegmentsMem *supersegments)
217	{
218	WaysMem *superways;
219	int i,j;
220
221	/* Create super-ways */
222
223	superways=NewWayList();
224
225	/* Create a new super-way to replace each existing way. */
226
227	for(i=0;i<supersegments->segments->number;i++)
228	{
229	Way *way=FindWay(ways,supersegments->segments->segments[i].way);
230
231	supersegments->segments->segments[i].way=0;
232
233	for(j=0;j<superways->number;j++)
234	if(superways->ways->ways[j].type ==way->type &&
235	superways->ways->ways[j].allow==way->allow &&
236	superways->ways->ways[j].limit==way->limit)
237	{
238	supersegments->segments->segments[i].way=superways->ways->ways[j].id;
239	break;
240	}
241
242	if(!supersegments->segments->segments[i].way)
243	{
244	Way *newway=AppendWay(superways,superways->number+1,"Super-Way");
245
246	newway->limit=way->limit;
247	newway->type =way->type;
248	newway->allow=way->allow;
249
250	supersegments->segments->segments[i].way=newway->id;
251	}
252
253	if(!((i+1)%10000))
254	{
255	printf("\rCreating Super-Ways: Super-Segments=%d Super-Ways=%d",i+1,superways->number);
256	fflush(stdout);
257	}
258	}
259
260	printf("\rCreated Super-Ways: Super-Segments=%d Super-Ways=%d \n",supersegments->number,superways->number);
261	fflush(stdout);
262
263	return(superways);
264	}