trunk/src/supersegments.c

/***************************************
 $Header: /home/amb/CVS/routino/src/supersegments.c,v 1.21 2009-01-28 18:46:55 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 *nodesmem The nodes.

  SegmentsMem *segmentsmem The segments.

  WaysMem *waysmem The ways.

  int iteration The current super-node / super-segment iteration number.
  ++++++++++++++++++++++++++++++++++++++*/

void ChooseSuperNodes(NodesMem *nodesmem,SegmentsMem *segmentsmem,WaysMem *waysmem,int iteration)
{
 int i;
 int        segcount=0,difference=0,nnodes=0;
 node_t     node=0;
 speed_t    limit=0;
 waytype_t  type=0;
 wayallow_t allow=0;

 /* Find super-nodes */

 node=segmentsmem->xdata[0].node1;

 for(i=0;i<segmentsmem->number;i++)
   {
    SegmentEx *segmentex=LookupSegmentEx(segmentsmem,i);
    WayEx *wayex=LookupWayEx(waysmem,segmentex->segment.wayindex);

    if(segmentex->super==iteration)
      {
       if(segmentex->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)
            {
             NodeEx *nodeex=FindNode(nodesmem,node);

             nodeex->super++;

             nnodes++;
            }

          segcount=1;
          difference=0;

          node=segmentex->node1;
          type=wayex->way.type;
          limit=wayex->way.limit;
          allow=wayex->way.allow;
         }
       else                        /* Same starting node */
         {
          if(wayex->way.type!=type)
             difference=1;

          if(wayex->way.limit!=limit)
             difference=1;

          if(wayex->way.allow!=allow)
             difference=1;

          segcount+=1;
         }
      }

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

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


/*++++++++++++++++++++++++++++++++++++++
  Create the super-segments.

  NodesMem *nodesmem The nodes.

  SegmentsMem *segmentsmem The segments.

  WaysMem *waysmem The ways.

  int iteration The current super-node / super-segment iteration number.
  ++++++++++++++++++++++++++++++++++++++*/

void CreateSuperSegments(NodesMem *nodesmem,SegmentsMem *segmentsmem,WaysMem *waysmem,int iteration)
{
 int i;
 SegmentsMem *supersegmentsmem;

 supersegmentsmem=NewSegmentList();

 /* Create super-segments for each super-node. */

 for(i=0;i<nodesmem->number;i++)
   {
    if(nodesmem->xdata[i].super>iteration)
      {
       SegmentEx *segmentex,*first;

       segmentex=first=FindFirstSegment(segmentsmem,nodesmem->xdata[i].id);

       while(segmentex)
         {
          WayEx *wayex=LookupWayEx(waysmem,segmentex->segment.wayindex);

          /* Check that this type of way hasn't already been routed */

          if(segmentex!=first)
            {
             SegmentEx *othersegmentex=first;

             while(othersegmentex && othersegmentex!=segmentex)
               {
                WayEx *otherwayex=LookupWayEx(waysmem,othersegmentex->segment.wayindex);

                if(otherwayex->way.type ==wayex->way.type  &&
                   otherwayex->way.allow==wayex->way.allow &&
                   otherwayex->way.limit==wayex->way.limit)
                  {
                   wayex=NULL;
                   break;
                  }

                othersegmentex=FindNextSegment(segmentsmem,othersegmentex);
               }
            }

          /* Route the way and store the super-segments. */

          if(wayex)
            {
             Results *results=FindRoutesWay(nodesmem,segmentsmem,waysmem,nodesmem->xdata[i].id,wayex,iteration);
             Result *result=FirstResult(results);

             while(result)
               {
                NodeEx *nodeex=FindNode(nodesmem,result->node);

                if(result->node!=nodesmem->xdata[i].id && nodeex->super>iteration)
                  {
                   SegmentEx *supersegmentex=AppendSegment(supersegmentsmem,nodesmem->xdata[i].id,result->node,IndexWayEx(waysmem,wayex));

                   supersegmentex->segment.distance=result->shortest.distance;

                   if(wayex->way.type&Way_OneWay)
                     {
                      supersegmentex=AppendSegment(supersegmentsmem,result->node,nodesmem->xdata[i].id,IndexWayEx(waysmem,wayex));

                      supersegmentex->segment.distance=ONEWAY_OPPOSITE|result->shortest.distance;
                     }
                  }

                result=NextResult(results,result);
               }

             FreeResultsList(results);
            }

          segmentex=FindNextSegment(segmentsmem,segmentex);
         }
      }

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

 printf("\rCreated Super-Segments: Nodes=%d Super-Segments=%d \n",nodesmem->number,supersegmentsmem->number);
 fflush(stdout);

 /* Append the new supersegments onto the segments. */

 for(i=0;i<supersegmentsmem->number;i++)
   {
    SegmentEx *segmentex=AppendSegment(segmentsmem,0,0,0);

    *segmentex=supersegmentsmem->xdata[i];
    segmentex->super=iteration+1;
   }
}
1	amb	16	/***************************************
2	amb	89	$Header: /home/amb/CVS/routino/src/supersegments.c,v 1.21 2009-01-28 18:46:55 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	amb	89
25	amb	16	/*++++++++++++++++++++++++++++++++++++++
26			Select the super-segments from the list of segments.
27
28	amb	89	NodesMem *nodesmem The nodes.
29	amb	16
30	amb	89	SegmentsMem *segmentsmem The segments.
31	amb	16
32	amb	89	WaysMem *waysmem The ways.
33	amb	16
34	amb	89	int iteration The current super-node / super-segment iteration number.
35	amb	16	++++++++++++++++++++++++++++++++++++++*/
36
37	amb	89	void ChooseSuperNodes(NodesMem nodesmem,SegmentsMem segmentsmem,WaysMem *waysmem,int iteration)
38	amb	16	{
39	amb	31	int i;
40	amb	89	int segcount=0,difference=0,nnodes=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	16
46	amb	54	/* Find super-nodes */
47
48	amb	89	node=segmentsmem->xdata[0].node1;
49	amb	52
50	amb	89	for(i=0;i<segmentsmem->number;i++)
51	amb	31	{
52	amb	89	SegmentEx *segmentex=LookupSegmentEx(segmentsmem,i);
53			WayEx *wayex=LookupWayEx(waysmem,segmentex->segment.wayindex);
54	amb	31
55	amb	89	if(segmentex->super==iteration)
56	amb	31	{
57	amb	89	if(segmentex->node1!=node)
58	amb	31	{
59	amb	89	/* Store the node if there is a difference in the ways that could affect routing.
60			Store the node if it is not a dead-end and if it isn't just the middle of a way. */
61	amb	31
62	amb	89	if(difference \|\| segcount>2)
63			{
64			NodeEx *nodeex=FindNode(nodesmem,node);
65	amb	31
66	amb	89	nodeex->super++;
67	amb	52
68	amb	89	nnodes++;
69			}
70	amb	31
71	amb	89	segcount=1;
72			difference=0;
73	amb	31
74	amb	89	node=segmentex->node1;
75			type=wayex->way.type;
76			limit=wayex->way.limit;
77			allow=wayex->way.allow;
78			}
79			else /* Same starting node */
80			{
81			if(wayex->way.type!=type)
82			difference=1;
83	amb	31
84	amb	89	if(wayex->way.limit!=limit)
85			difference=1;
86
87			if(wayex->way.allow!=allow)
88			difference=1;
89
90			segcount+=1;
91			}
92	amb	52	}
93	amb	31
94	amb	38	if(!((i+1)%10000))
95	amb	31	{
96	amb	89	printf("\rFinding Super-Nodes: Segments=%d Super-Nodes=%d",i+1,nnodes);
97	amb	31	fflush(stdout);
98			}
99			}
100
101	amb	89	printf("\rFound Super-Nodes: Segments=%d Super-Nodes=%d \n",segmentsmem->number,nnodes);
102	amb	31	fflush(stdout);
103	amb	16	}
104	amb	31
105
106			/*++++++++++++++++++++++++++++++++++++++
107			Create the super-segments.
108
109	amb	89	NodesMem *nodesmem The nodes.
110	amb	31
111	amb	89	SegmentsMem *segmentsmem The segments.
112	amb	31
113	amb	89	WaysMem *waysmem The ways.
114	amb	31
115	amb	89	int iteration The current super-node / super-segment iteration number.
116	amb	31	++++++++++++++++++++++++++++++++++++++*/
117
118	amb	89	void CreateSuperSegments(NodesMem nodesmem,SegmentsMem segmentsmem,WaysMem *waysmem,int iteration)
119	amb	31	{
120	amb	79	int i;
121	amb	89	SegmentsMem *supersegmentsmem;
122	amb	31
123	amb	89	supersegmentsmem=NewSegmentList();
124	amb	31
125	amb	54	/* Create super-segments for each super-node. */
126
127	amb	89	for(i=0;i<nodesmem->number;i++)
128	amb	31	{
129	amb	89	if(nodesmem->xdata[i].super>iteration)
130	amb	54	{
131	amb	89	SegmentEx segmentex,first;
132	amb	54
133	amb	89	segmentex=first=FindFirstSegment(segmentsmem,nodesmem->xdata[i].id);
134	amb	54
135	amb	89	while(segmentex)
136	amb	56	{
137	amb	89	WayEx *wayex=LookupWayEx(waysmem,segmentex->segment.wayindex);
138	amb	56
139	amb	89	/* Check that this type of way hasn't already been routed */
140
141			if(segmentex!=first)
142	amb	56	{
143	amb	89	SegmentEx *othersegmentex=first;
144	amb	56
145	amb	89	while(othersegmentex && othersegmentex!=segmentex)
146	amb	56	{
147	amb	89	WayEx *otherwayex=LookupWayEx(waysmem,othersegmentex->segment.wayindex);
148
149			if(otherwayex->way.type ==wayex->way.type &&
150			otherwayex->way.allow==wayex->way.allow &&
151			otherwayex->way.limit==wayex->way.limit)
152			{
153			wayex=NULL;
154			break;
155			}
156
157			othersegmentex=FindNextSegment(segmentsmem,othersegmentex);
158	amb	56	}
159			}
160
161	amb	89	/* Route the way and store the super-segments. */
162	amb	54
163	amb	89	if(wayex)
164			{
165			Results *results=FindRoutesWay(nodesmem,segmentsmem,waysmem,nodesmem->xdata[i].id,wayex,iteration);
166			Result *result=FirstResult(results);
167	amb	31
168	amb	89	while(result)
169	amb	54	{
170	amb	89	NodeEx *nodeex=FindNode(nodesmem,result->node);
171	amb	31
172	amb	89	if(result->node!=nodesmem->xdata[i].id && nodeex->super>iteration)
173	amb	62	{
174	amb	89	SegmentEx *supersegmentex=AppendSegment(supersegmentsmem,nodesmem->xdata[i].id,result->node,IndexWayEx(waysmem,wayex));
175	amb	62
176	amb	89	supersegmentex->segment.distance=result->shortest.distance;
177
178			if(wayex->way.type&Way_OneWay)
179			{
180			supersegmentex=AppendSegment(supersegmentsmem,result->node,nodesmem->xdata[i].id,IndexWayEx(waysmem,wayex));
181
182			supersegmentex->segment.distance=ONEWAY_OPPOSITE\|result->shortest.distance;
183			}
184	amb	62	}
185	amb	89
186			result=NextResult(results,result);
187	amb	54	}
188
189	amb	89	FreeResultsList(results);
190	amb	79	}
191
192	amb	89	segmentex=FindNextSegment(segmentsmem,segmentex);
193	amb	45	}
194	amb	54	}
195	amb	31
196	amb	38	if(!((i+1)%1000))
197	amb	31	{
198	amb	89	printf("\rCreating Super-Segments: Nodes=%d Super-Segments=%d",i+1,supersegmentsmem->number);
199	amb	31	fflush(stdout);
200			}
201			}
202
203	amb	89	printf("\rCreated Super-Segments: Nodes=%d Super-Segments=%d \n",nodesmem->number,supersegmentsmem->number);
204	amb	31	fflush(stdout);
205
206	amb	89	/* Append the new supersegments onto the segments. */
207	amb	54
208	amb	89	for(i=0;i<supersegmentsmem->number;i++)
209	amb	54	{
210	amb	89	SegmentEx *segmentex=AppendSegment(segmentsmem,0,0,0);
211	amb	54
212	amb	89	*segmentex=supersegmentsmem->xdata[i];
213			segmentex->super=iteration+1;
214	amb	54	}
215			}