trunk/src/supersegments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.4 2009-01-11 09:42:26 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%10000))
      {
       printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i,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>(distance_short_t)~0)
               {
                fprintf(stderr,"\nSuper-Segment too long (%d->%d) = %.1f km\n",segment->node1,segment->node2,distance_to_km(distance));
                distance=(distance_short_t)~0;
               }

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

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

    FreeResultsList(results);

    if(!(i%1000))
      {
       printf("\rFinding Super-Segments: Super-Nodes=%d Super-Segments=%d",i,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	33	$Header: /home/amb/CVS/routino/src/supersegments.c,v 1.4 2009-01-11 09:42:26 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			if(!(i%10000))
75			{
76	amb	33	printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i,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			int i,j,k;
106
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			for(j=0;j<NBINS_RESULTS;j++)
118			for(k=0;k<results->number[j];k++)
119	amb	33	if(FindNode(supernodes,results->results[j][k]->node))
120	amb	31	{
121			distance_t distance;
122			duration_t duration;
123	amb	33	Segment *segment=AppendSegment(supersegments,supernodes->nodes[i].id,results->results[j][k]->node,0);
124	amb	31
125			distance=results->results[j][k]->shortest.distance;
126			duration=results->results[j][k]->quickest.duration;
127
128			if(distance>(distance_short_t)~0)
129			{
130			fprintf(stderr,"\nSuper-Segment too long (%d->%d) = %.1f km\n",segment->node1,segment->node2,distance_to_km(distance));
131			distance=(distance_short_t)~0;
132			}
133
134			if(duration>(duration_short_t)~0)
135			{
136			fprintf(stderr,"\nSuper-Segment too long (%d->%d) = %.1f mins\n",segment->node1,segment->node2,duration_to_minutes(duration));
137			duration=(duration_short_t)~0;
138			}
139
140			segment->distance=distance;
141			segment->duration=duration;
142			}
143
144			FreeResultsList(results);
145
146			if(!(i%1000))
147			{
148	amb	33	printf("\rFinding Super-Segments: Super-Nodes=%d Super-Segments=%d",i,supersegments->number);
149	amb	31	fflush(stdout);
150			}
151			}
152
153	amb	33	printf("\rFound Super-Segments: Super-Nodes=%d Super-Segments=%d \n",supernodes->number,supersegments->number);
154	amb	31	fflush(stdout);
155
156			return(supersegments);
157			}