trunk/src/supersegments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.5 2009-01-14 19:29:22 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,k;

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

             distance=results->results[j][k]->shortest.distance;
             duration=results->results[j][k]->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	/***************************************
2	$Header: /home/amb/CVS/routino/src/supersegments.c,v 1.5 2009-01-14 19:29:22 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 count_oneway=0,count_twoway=0;
41	node_t node=0;
42	NodesMem *supernodes;
43
44	/* Find super-nodes */
45
46	supernodes=NewNodeList();
47
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	AppendNode(supernodes,node,oldnode->latitude,oldnode->longitude);
59	}
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	if(!((i+1)%10000))
75	{
76	printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i+1,supernodes->number);
77	fflush(stdout);
78	}
79	}
80
81	printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d \n",segments->number,supernodes->number);
82	fflush(stdout);
83
84	return(supernodes);
85	}
86
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	Nodes *supernodes The list of super-nodes.
100	++++++++++++++++++++++++++++++++++++++*/
101
102	SegmentsMem CreateSuperSegments(Nodes nodes,Segments segments,Ways ways,Nodes *supernodes)
103	{
104	SegmentsMem *supersegments;
105	int i,j,k;
106
107	/* Create super-segments */
108
109	supersegments=NewSegmentList();
110
111	for(i=0;i<supernodes->number;i++)
112	{
113	Results *results;
114
115	results=FindRoutes(nodes,segments,supernodes->nodes[i].id,supernodes);
116
117	for(j=0;j<NBINS_RESULTS;j++)
118	for(k=0;k<results->number[j];k++)
119	if(FindNode(supernodes,results->results[j][k]->node))
120	{
121	distance_t distance;
122	duration_t duration;
123	Segment *segment=AppendSegment(supersegments,supernodes->nodes[i].id,results->results[j][k]->node,0);
124
125	distance=results->results[j][k]->shortest.distance;
126	duration=results->results[j][k]->quickest.duration;
127
128	if(distance>=INVALID_SHORT_DISTANCE)
129	{
130	fprintf(stderr,"\nSuper-Segment too long (%d->%d) = %.1f km\n",segment->node1,segment->node2,distance_to_km(distance));
131	distance=INVALID_SHORT_DISTANCE;
132	}
133
134	if(duration>INVALID_SHORT_DURATION)
135	{
136	fprintf(stderr,"\nSuper-Segment too long (%d->%d) = %.1f mins\n",segment->node1,segment->node2,duration_to_minutes(duration));
137	duration=INVALID_SHORT_DURATION;
138	}
139
140	segment->distance=distance;
141	segment->duration=duration;
142	}
143
144	FreeResultsList(results);
145
146	if(!((i+1)%1000))
147	{
148	printf("\rFinding Super-Segments: Super-Nodes=%d Super-Segments=%d",i+1,supersegments->number);
149	fflush(stdout);
150	}
151	}
152
153	printf("\rFound Super-Segments: Super-Nodes=%d Super-Segments=%d \n",supernodes->number,supersegments->number);
154	fflush(stdout);
155
156	return(supersegments);
157	}