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	amb	16	/***************************************
2	amb	76	$Header: /home/amb/CVS/routino/src/supersegments.c,v 1.16 2009-01-23 17:13:48 amb Exp $
3	amb	16
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	amb	26	#include "nodes.h"
20			#include "ways.h"
21			#include "segments.h"
22	amb	16	#include "functions.h"
23
24
25			/*++++++++++++++++++++++++++++++++++++++
26			Select the super-segments from the list of segments.
27
28	amb	33	NodesMem *ChooseSuperNodes Returns the list of super-nodes.
29	amb	16
30	amb	26	Nodes *nodes The nodes.
31	amb	16
32	amb	26	Segments *segments The existing segments.
33	amb	16
34	amb	26	Ways *ways The ways.
35	amb	16	++++++++++++++++++++++++++++++++++++++*/
36
37	amb	33	NodesMem ChooseSuperNodes(Nodes nodes,Segments segments,Ways ways)
38	amb	16	{
39	amb	31	int i;
40	amb	62	int segcount=0,difference=0;
41	amb	52	node_t node=0;
42			speed_t limit=0;
43			waytype_t type=0;
44			wayallow_t allow=0;
45	amb	33	NodesMem *supernodes;
46	amb	16
47	amb	54	/* Create super-nodes */
48	amb	31
49	amb	33	supernodes=NewNodeList();
50	amb	31
51	amb	54	/* Find super-nodes */
52
53	amb	52	node=segments->segments[0].node1;
54
55	amb	31	for(i=0;i<segments->number;i++)
56			{
57	amb	52	Segment *segment=&segments->segments[i];
58			Way *way=FindWay(ways,segment->way);
59	amb	31
60	amb	52	if(segment->node1!=node)
61	amb	31	{
62	amb	52	/* 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	amb	62	if(difference \|\| segcount>2)
66	amb	31	{
67			Node *oldnode=FindNode(nodes,node);
68
69	amb	33	AppendNode(supernodes,node,oldnode->latitude,oldnode->longitude);
70	amb	31	}
71
72	amb	62	segcount=1;
73	amb	52	difference=0;
74
75			node=segment->node1;
76	amb	68	type=way->type;
77	amb	52	limit=way->limit;
78			allow=way->allow;
79	amb	31	}
80	amb	52	else /* Same starting node */
81			{
82	amb	68	if(way->type!=type)
83	amb	52	difference=1;
84	amb	31
85	amb	52	if(way->limit!=limit)
86			difference=1;
87	amb	31
88	amb	52	if(way->allow!=allow)
89			difference=1;
90	amb	31
91	amb	62	segcount+=1;
92	amb	52	}
93	amb	31
94	amb	38	if(!((i+1)%10000))
95	amb	31	{
96	amb	38	printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i+1,supernodes->number);
97	amb	31	fflush(stdout);
98			}
99			}
100
101	amb	33	printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d \n",segments->number,supernodes->number);
102	amb	31	fflush(stdout);
103
104	amb	33	return(supernodes);
105	amb	16	}
106	amb	31
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	amb	33	Nodes *supernodes The list of super-nodes.
120	amb	31	++++++++++++++++++++++++++++++++++++++*/
121
122	amb	76	SegmentsMem CreateSuperSegments(Nodes nodes,Segments segments,Ways ways,Nodes *supernodes)
123	amb	31	{
124			SegmentsMem *supersegments;
125	amb	45	int i,j;
126	amb	31
127	amb	58	/* Create super-segments */
128	amb	31
129			supersegments=NewSegmentList();
130
131	amb	54	/* Create super-segments for each super-node. */
132
133	amb	33	for(i=0;i<supernodes->number;i++)
134	amb	31	{
135	amb	54	Segment segment,first;
136	amb	31
137	amb	54	segment=first=FindFirstSegment(segments,supernodes->nodes[i].id);
138	amb	31
139	amb	54	while(segment)
140			{
141			Way *way=FindWay(ways,segment->way);
142
143	amb	56	/* Check that this type of way hasn't already been routed */
144	amb	54
145	amb	56	if(segment!=first)
146			{
147			Segment *othersegment=first;
148
149			while(othersegment && othersegment!=segment)
150			{
151			Way *otherway=FindWay(ways,othersegment->way);
152
153	amb	68	if(otherway->type ==way->type &&
154	amb	56	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	amb	54	/* Route the way and store the super-segments. */
166
167			if(way)
168	amb	45	{
169	amb	76	Results *results=FindRoutesWay(nodes,segments,ways,supernodes->nodes[i].id,supernodes,way);
170	amb	31
171	amb	54	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	amb	62	Segment *supersegment=AppendSegment(supersegments,supernodes->nodes[i].id,results->results[j].node,way->id);
175	amb	31
176	amb	59	supersegment->distance=results->results[j].shortest.distance;
177	amb	62
178			if(way->type&Way_OneWay)
179			{
180			supersegment=AppendSegment(supersegments,results->results[j].node,supernodes->nodes[i].id,way->id);
181
182	amb	69	supersegment->distance=ONEWAY_OPPOSITE\|results->results[j].shortest.distance;
183	amb	62	}
184	amb	54	}
185
186			FreeResultsList(results);
187	amb	45	}
188
189	amb	54	segment=FindNextSegment(segments,segment);
190			}
191	amb	31
192	amb	38	if(!((i+1)%1000))
193	amb	31	{
194	amb	54	printf("\rCreating Super-Segments: Super-Nodes=%d Super-Segments=%d",i+1,supersegments->number);
195	amb	31	fflush(stdout);
196			}
197			}
198
199	amb	54	printf("\rCreated Super-Segments: Super-Nodes=%d Super-Segments=%d \n",supernodes->number,supersegments->number);
200	amb	31	fflush(stdout);
201
202			return(supersegments);
203			}
204	amb	54
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	amb	68	if(superways->ways->ways[j].type ==way->type &&
235	amb	54	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	amb	68	newway->type =way->type;
248	amb	54	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			}