trunk/src/supersegments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.7 2009-01-18 09:08:57 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;

 /* Find super-nodes */

 supernodes=NewNodeList();

 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.
  ++++++++++++++++++++++++++++++++++++++*/

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

 /* Create super-segments */

 supersegments=NewSegmentList();

 for(i=0;i<supernodes->number;i++)
   {
    Results *results;

    results=FindRoutes(nodes,segments,supernodes->nodes[i].id,supernodes);

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

          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",segment->node1,segment->node2,distance_to_km(distance));
             distance=INVALID_SHORT_DISTANCE;
            }

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

          segment->distance=distance;
          segment->duration=duration;
         }

    FreeResultsList(results);

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

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

 return(supersegments);
}
1	amb	16	/***************************************
2	amb	52	$Header: /home/amb/CVS/routino/src/supersegments.c,v 1.7 2009-01-18 09:08:57 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	52	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	amb	33	NodesMem *supernodes;
46	amb	16
47	amb	33	/* Find super-nodes */
48	amb	31
49	amb	33	supernodes=NewNodeList();
50	amb	31
51	amb	52	node=segments->segments[0].node1;
52
53	amb	31	for(i=0;i<segments->number;i++)
54			{
55	amb	52	Segment *segment=&segments->segments[i];
56			Way *way=FindWay(ways,segment->way);
57	amb	31
58	amb	52	if(segment->node1!=node)
59	amb	31	{
60	amb	52	/* Store the node if there is a difference in the ways that could affect routing.
61			Store the node if it is not a dead-end and if it isn't just the middle of a way. */
62
63			if(difference \|\| exitcount>2)
64	amb	31	{
65			Node *oldnode=FindNode(nodes,node);
66
67	amb	33	AppendNode(supernodes,node,oldnode->latitude,oldnode->longitude);
68	amb	31	}
69
70	amb	52	exitcount=0;
71			difference=0;
72
73			node=segment->node1;
74			type=Way_TYPE(way->type);
75			limit=way->limit;
76			allow=way->allow;
77	amb	31	}
78	amb	52	else /* Same starting node */
79			{
80			if(Way_TYPE(way->type)!=type)
81			difference=1;
82	amb	31
83	amb	52	if(way->limit!=limit)
84			difference=1;
85	amb	31
86	amb	52	if(way->allow!=allow)
87			difference=1;
88			}
89	amb	31
90	amb	52	if(segment->distance!=INVALID_SHORT_DISTANCE)
91			{
92			if(way->type&Way_OneWay)
93			exitcount+=2;
94			else
95			exitcount+=1;
96			}
97	amb	31
98	amb	38	if(!((i+1)%10000))
99	amb	31	{
100	amb	38	printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i+1,supernodes->number);
101	amb	31	fflush(stdout);
102			}
103			}
104
105	amb	33	printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d \n",segments->number,supernodes->number);
106	amb	31	fflush(stdout);
107
108	amb	33	return(supernodes);
109	amb	16	}
110	amb	31
111
112			/*++++++++++++++++++++++++++++++++++++++
113			Create the super-segments.
114
115			SegmentsMem *CreateSuperSegments Returns the set of super-segments.
116
117			Nodes *nodes The list of nodes.
118
119			Segments *segments The list of segments.
120
121			Ways *ways The list of ways.
122
123	amb	33	Nodes *supernodes The list of super-nodes.
124	amb	31	++++++++++++++++++++++++++++++++++++++*/
125
126	amb	33	SegmentsMem CreateSuperSegments(Nodes nodes,Segments segments,Ways ways,Nodes *supernodes)
127	amb	31	{
128			SegmentsMem *supersegments;
129	amb	45	int i,j;
130	amb	31
131			/* Create super-segments */
132
133			supersegments=NewSegmentList();
134
135	amb	33	for(i=0;i<supernodes->number;i++)
136	amb	31	{
137			Results *results;
138
139	amb	33	results=FindRoutes(nodes,segments,supernodes->nodes[i].id,supernodes);
140	amb	31
141	amb	45	for(j=0;j<results->number;j++)
142			if(FindNode(supernodes,results->results[j].node))
143			{
144			distance_t distance;
145			duration_t duration;
146			Segment *segment=AppendSegment(supersegments,supernodes->nodes[i].id,results->results[j].node,0);
147	amb	31
148	amb	45	distance=results->results[j].shortest.distance;
149			duration=results->results[j].quickest.duration;
150	amb	31
151	amb	45	if(distance>=INVALID_SHORT_DISTANCE)
152			{
153			fprintf(stderr,"\nSuper-Segment too long (%d->%d) = %.1f km\n",segment->node1,segment->node2,distance_to_km(distance));
154			distance=INVALID_SHORT_DISTANCE;
155			}
156	amb	31
157	amb	45	if(duration>INVALID_SHORT_DURATION)
158			{
159			fprintf(stderr,"\nSuper-Segment too long (%d->%d) = %.1f mins\n",segment->node1,segment->node2,duration_to_minutes(duration));
160			duration=INVALID_SHORT_DURATION;
161	amb	31	}
162
163	amb	45	segment->distance=distance;
164			segment->duration=duration;
165			}
166
167	amb	31	FreeResultsList(results);
168
169	amb	38	if(!((i+1)%1000))
170	amb	31	{
171	amb	38	printf("\rFinding Super-Segments: Super-Nodes=%d Super-Segments=%d",i+1,supersegments->number);
172	amb	31	fflush(stdout);
173			}
174			}
175
176	amb	33	printf("\rFound Super-Segments: Super-Nodes=%d Super-Segments=%d \n",supernodes->number,supersegments->number);
177	amb	31	fflush(stdout);
178
179			return(supersegments);
180			}