trunk/src/supersegments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.6 2009-01-17 17:49:58 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 count_oneway=0,count_twoway=0;
 node_t node=0;
 NodesMem *supernodes;

 /* Find super-nodes */

 supernodes=NewNodeList();

 for(i=0;i<segments->number;i++)
   {
    Way *way;

    if(i>0 && segments->segments[i].node1!=node)
      {
       if((count_oneway*2+count_twoway)>2)
         {
          Node *oldnode=FindNode(nodes,node);

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

       count_oneway=0;
       count_twoway=0;
      }

    way=FindWay(ways,segments->segments[i].way);

    if(way->type&Way_ONEWAY)
       count_oneway++;
    else
       count_twoway++;

    node=segments->segments[i].node1;

    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	45	$Header: /home/amb/CVS/routino/src/supersegments.c,v 1.6 2009-01-17 17:49:58 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			int count_oneway=0,count_twoway=0;
41			node_t node=0;
42	amb	33	NodesMem *supernodes;
43	amb	16
44	amb	33	/* Find super-nodes */
45	amb	31
46	amb	33	supernodes=NewNodeList();
47	amb	31
48			for(i=0;i<segments->number;i++)
49			{
50			Way *way;
51
52			if(i>0 && segments->segments[i].node1!=node)
53			{
54			if((count_oneway*2+count_twoway)>2)
55			{
56			Node *oldnode=FindNode(nodes,node);
57
58	amb	33	AppendNode(supernodes,node,oldnode->latitude,oldnode->longitude);
59	amb	31	}
60
61			count_oneway=0;
62			count_twoway=0;
63			}
64
65			way=FindWay(ways,segments->segments[i].way);
66
67			if(way->type&Way_ONEWAY)
68			count_oneway++;
69			else
70			count_twoway++;
71
72			node=segments->segments[i].node1;
73
74	amb	38	if(!((i+1)%10000))
75	amb	31	{
76	amb	38	printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i+1,supernodes->number);
77	amb	31	fflush(stdout);
78			}
79			}
80
81	amb	33	printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d \n",segments->number,supernodes->number);
82	amb	31	fflush(stdout);
83
84	amb	33	return(supernodes);
85	amb	16	}
86	amb	31
87
88			/*++++++++++++++++++++++++++++++++++++++
89			Create the super-segments.
90
91			SegmentsMem *CreateSuperSegments Returns the set of super-segments.
92
93			Nodes *nodes The list of nodes.
94
95			Segments *segments The list of segments.
96
97			Ways *ways The list of ways.
98
99	amb	33	Nodes *supernodes The list of super-nodes.
100	amb	31	++++++++++++++++++++++++++++++++++++++*/
101
102	amb	33	SegmentsMem CreateSuperSegments(Nodes nodes,Segments segments,Ways ways,Nodes *supernodes)
103	amb	31	{
104			SegmentsMem *supersegments;
105	amb	45	int i,j;
106	amb	31
107			/* Create super-segments */
108
109			supersegments=NewSegmentList();
110
111	amb	33	for(i=0;i<supernodes->number;i++)
112	amb	31	{
113			Results *results;
114
115	amb	33	results=FindRoutes(nodes,segments,supernodes->nodes[i].id,supernodes);
116	amb	31
117	amb	45	for(j=0;j<results->number;j++)
118			if(FindNode(supernodes,results->results[j].node))
119			{
120			distance_t distance;
121			duration_t duration;
122			Segment *segment=AppendSegment(supersegments,supernodes->nodes[i].id,results->results[j].node,0);
123	amb	31
124	amb	45	distance=results->results[j].shortest.distance;
125			duration=results->results[j].quickest.duration;
126	amb	31
127	amb	45	if(distance>=INVALID_SHORT_DISTANCE)
128			{
129			fprintf(stderr,"\nSuper-Segment too long (%d->%d) = %.1f km\n",segment->node1,segment->node2,distance_to_km(distance));
130			distance=INVALID_SHORT_DISTANCE;
131			}
132	amb	31
133	amb	45	if(duration>INVALID_SHORT_DURATION)
134			{
135			fprintf(stderr,"\nSuper-Segment too long (%d->%d) = %.1f mins\n",segment->node1,segment->node2,duration_to_minutes(duration));
136			duration=INVALID_SHORT_DURATION;
137	amb	31	}
138
139	amb	45	segment->distance=distance;
140			segment->duration=duration;
141			}
142
143	amb	31	FreeResultsList(results);
144
145	amb	38	if(!((i+1)%1000))
146	amb	31	{
147	amb	38	printf("\rFinding Super-Segments: Super-Nodes=%d Super-Segments=%d",i+1,supersegments->number);
148	amb	31	fflush(stdout);
149			}
150			}
151
152	amb	33	printf("\rFound Super-Segments: Super-Nodes=%d Super-Segments=%d \n",supernodes->number,supersegments->number);
153	amb	31	fflush(stdout);
154
155			return(supersegments);
156			}