<div dir="ltr"><div><i>The C code will execute a query to select all the edges that have at least one end in that partition:<br></i><br></div>do we need to retrieve all the edges that are lying totally or partially in that partition or even if we retrieve only those edges that are directly  connected to the source node that is load only those edges that have one of its node as source node.  <br>
</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Jul 5, 2013 at 7:49 PM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Mukul asks:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
can you help me coming up with basic class skeletons for retrieving<br>
partitions using an index key  and for keeping a track of loaded<br>
partitions as well .<br>
</blockquote>
<br>
The problem:<br>
<br>
* we have an incomplete graph to solve<br>
* we need to find a node in the graph but it is not in the graph<br>
  * we call a method graph::LoadPartition(<u></u>partition_id) to load the partition with that node<br>
  * if this fails then the route fails and we clean up, and throw an error<br>
* otherwise we continue solving the graph until we need to load another partition<br>
<br>
This assumes it is cheap to find a node or to find that it is missing.<br>
But the question is how do we define "missing".<br>
<br>
A node has two pieces of information, the node_id and the partition_id. We can can make some assumptions here that if both ends of an edge are in the same partition then we will never find it in the graph unless the partition has been loaded. So edges that cross partition boundaries are the ones that concern us because the adjacent partition may or may not have been loaded.<br>

<br>
So we might define an edge like:<br>
<br>
eid   -- edge id<br>
sid   -- source node id<br>
spid  -- source partition id<br>
tid   -- target node id<br>
tpid  -- target partition id<br>
cost<br>
rcost<br>
...<br>
<br>
We could set both spid and tpid to zero if the edge is not a boundary edge. So a simple check if either of these is zero then we know both are loaded. If they are not zero then we need to check if the partition is loaded and if not call graph::LoadPartiton(partition_<u></u>id).<br>

<br>
I would recommend maintaining a bit array where the partition_id >0 is the index into the bit array.<br>
<br>
How does graph::LoadPartiton(partition_<u></u>id) work?<br>
<br>
After we partition the data we have a tables like:<br>
<br>
CREATE TABLE grid_vertices<br>
(<br>
  id integer NOT NULL,   -- node id<br>
  pid integer,           -- partition id<br>
  the_geom geometry,<br>
  quadkey text,<br>
  CONSTRAINT grid_vertices_pkey PRIMARY KEY (id)<br>
);<br>
<br>
The following is the edge table and it can have other columns as need or it can be a view with the source, target, sgid, and tgid columns joined from another table.<br>
<br>
CREATE TABLE grid<br>
(<br>
  gid serial NOT NULL,<br>
  source integer,         -- source node_id<br>
  target integer,         -- target node_id<br>
  cost double precision,<br>
  sgid integer,           -- source grid_id (partition_id)<br>
  tgid integer,           -- target grid_id (partition_id)<br>
  CONSTRAINT grid_pkey PRIMARY KEY (gid)<br>
);<br>
<br>
So the LoadPartition() method will call a C function that will run a query using the postgresql SPI functions, build a struct array and return the array pointer to the method that will load the array into the graph and update the bit array that tracks the loaded partitions. Then free the struct array and return ok or fail.<br>

<br>
The C code will execute a query to select all the edges that have at least one end in that partition:<br>
<br>
   select * from grid where sgid=<pid><br>
   union<br>
   select * from grid where tgid=<pid><br>
<br>
both sgid and tgid columns should be indexed on the table.<br>
<br>
The struct will be something like:<br>
<br>
typedef struct partition_t {<br>
  integer gid;<br>
  integer source;<br>
  integer spart;<br>
  integer target;<br>
  integer tpart<br>
  double precision cost;<br>
  double precision rcost;<br>
  ...<br>
}<br>
<br>
You will need to return the edge count for the partition_t[] array or add a dummy record with gid = -1 to signal the end of the array.<br>
<br>
When the method loads the edges, if will zero the partition_ids if both are the same. It will need to check if they are different, and check if the other partition is already load if that edge as already been loaded into the graph to avoid duplication of the edges for these boundary edges.<br>

<br>
Does this cover everything?<br>
Do you need some help with the C code? and processing the SQL query?<br>
<br>
-Steve<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</blockquote></div><br></div>