00001
00002
00003 #include "GraphContainer.h"
00004 #include "GraphData.h"
00005 #include "Changelist.h"
00006 #include "ChangeTimeline.h"
00007 #include "ByteOutBuffer.h"
00008 #include "AttributeParser.h"
00009
00010 #include "AttributeBlob_impl.h"
00011 #include "RTree.h"
00012
00013 #include <iostream>
00014 #include <deque>
00015 #include <sys/time.h>
00016
00017
00018
00019
00020 #define CALCATTRVALUES
00021
00022 namespace VGServer {
00023
00024 const bool GraphContainer::rtreemap_descending = false;
00025
00026
00027 template class RTree::Tree<struct GraphContainer::RTreeData, struct GraphContainer::RTreeDataCallback>;
00028
00029 inline double timestamp()
00030 {
00031 struct timeval tp;
00032 gettimeofday(&tp, NULL);
00033 return double(tp.tv_sec) + tp.tv_usec / 1000000.;
00034 }
00035
00036 GraphContainer::GraphContainer(const class GraphProperties &properties)
00037 : GraphData(properties), rtreemap(rtreemap_compare(rtreemap_descending)),
00038 rtree_callback(*this)
00039 {
00040 vertexattrid_xaxis = 0;
00041 vertexattrid_yaxis = 1;
00042 edgeattrid_zaxis = 2;
00043
00044 reinsertnum = 9;
00045 }
00046
00047 GraphContainer::~GraphContainer()
00048 {
00049 }
00050
00051 void GraphContainer::applyGraphData(class GraphData &newgraph)
00052 {
00053
00054 GraphData::swap(newgraph);
00055
00056
00057 recreateRTree();
00058 }
00059
00060 void GraphContainer::swap(class GraphContainer &newgraph)
00061 {
00062
00063
00064
00065 GraphData::swap(newgraph);
00066
00067
00068 std::swap(rtreemap, newgraph.rtreemap);
00069
00070
00071 for(rtreemap_t::iterator ti = rtreemap.begin(); ti != rtreemap.end(); ++ti)
00072 {
00073 ti->second.setCallback(&rtree_callback);
00074 }
00075
00076 std::swap(vertexattrid_xaxis, newgraph.vertexattrid_xaxis);
00077 std::swap(vertexattrid_yaxis, newgraph.vertexattrid_yaxis);
00078
00079 std::swap(edgeattrid_zaxis, newgraph.edgeattrid_zaxis);
00080 }
00081
00082 void GraphContainer::recreateRTree()
00083 {
00084 std::cerr << "Rebuilding R-Tree: 0%";
00085 std::cerr.flush();
00086
00087 double ts1 = timestamp();
00088
00089 rtreemap.clear();
00090
00091 unsigned int dotstepmax = (edges.size()-1) / 60;
00092 unsigned int dotstep = 0;
00093 unsigned int percentstepmax = 6;
00094 unsigned int percentstep = 0;
00095
00096 for(vertexid_t vi = 0; vi < vertices.size()-1; vi++)
00097 {
00098 if (not existVertex(vi)) continue;
00099
00100
00101
00102
00103 unsigned int endedgeidx = vertices[vi+1].edgeidx;
00104
00105 for(unsigned int ei = vertices[vi].edgeidx; ei < endedgeidx; ei++)
00106 {
00107 vertexid_t tvi = edges[ei].target;
00108 if (tvi == VERTEX_INVALID) break;
00109 if (not existVertex(tvi)) continue;
00110
00111
00112
00113
00114 unsigned int level = edges[ei].getAttr(edgeattrid_zaxis, *this).getInteger();
00115
00116 rtreemap_t::iterator rtreei = rtreemap.find(level);
00117
00118 if (rtreei == rtreemap.end())
00119 {
00120
00121 rtreei = rtreemap.insert( rtreemap_t::value_type(level, GraphRTree(&rtree_callback)) ).first;
00122 rtreei->second.setReinsertNum(reinsertnum);
00123 }
00124
00125
00126 rtreei->second.insertRect(RTreeData(vi, tvi));
00127
00128
00129 if (++dotstep >= dotstepmax) {
00130 std::cerr << ".";
00131 dotstep = 0;
00132
00133 if (++percentstep > percentstepmax)
00134 {
00135 std::cerr << int(double(ei) / double(edges.size()-1) * 100.0) << "%";
00136 percentstep = 0;
00137 }
00138
00139 std::cerr.flush();
00140 }
00141 }
00142 }
00143
00144 std::cerr << "100% done\n";
00145 double ts2 = timestamp();
00146
00147 std::cerr << "Time: " << (ts2-ts1) << "\n";
00148
00149
00150 RTree_t::Stats st;
00151
00152 getRTreeStats(st);
00153
00154 RTree_t::LevelStats lst;
00155
00156 std::cerr << "RTree Stats: levels = " << st.level.size() << "\n";
00157
00158 for(int li = st.level.size()-1; li >= 0; li--)
00159 {
00160 std::cerr << "l " << li << " " << st.level[li] << "\n";
00161 lst += st.level[li];
00162 }
00163
00164 std::cerr << "total: " << lst << "\n";
00165 }
00166
00167 void GraphContainer::getRTreeStats(RTreeStats_t &st) const
00168 {
00169 for(rtreemap_t::const_iterator ti = rtreemap.begin(); ti != rtreemap.end(); ++ti)
00170 {
00171 ti->second.calcStats(st);
00172 }
00173 }
00174
00175 void GraphContainer::applyChangelist(const class Changelist &cl)
00176 {
00177
00178 {
00179 Changelist::edgechglist_t::const_iterator e;
00180 for(e = cl.edgechglist.begin(); e != cl.edgechglist.end(); e++)
00181 {
00182 if (e->second.empty() ||
00183 (cl.edgeaddlist.find( e->first ) == cl.edgeaddlist.end())
00184 )
00185 {
00186
00187 unsigned int level = GraphData::getEdgeAttr(e->first.first, e->first.second,
00188 edgeattrid_zaxis).getInteger();
00189
00190 rtreemap_t::iterator rtreei = rtreemap.find(level);
00191
00192 if (rtreei == rtreemap.end()) {
00193 std::cerr << "applyChangelist: could not find rtree level to delete from\n";
00194 }
00195 else if (!rtreei->second.deleteRect( RTreeData(e->first.first, e->first.second) )) {
00196 std::cerr << "Could not find rect in rtree\n";
00197 }
00198 }
00199 }
00200 }
00201
00202 GraphData::applyChangelist(cl);
00203
00204
00205 {
00206 Changelist::edgechglist_t::const_iterator e;
00207 for(e = cl.edgechglist.begin(); e != cl.edgechglist.end(); e++)
00208 {
00209 if (!e->second.empty())
00210 {
00211
00212 unsigned int level = GraphData::getEdgeAttr(e->first.first, e->first.second,
00213 edgeattrid_zaxis).getInteger();
00214
00215 rtreemap_t::iterator rtreei = rtreemap.find(level);
00216
00217 if (rtreei == rtreemap.end()) {
00218
00219 rtreei = rtreemap.insert( rtreemap_t::value_type(level, GraphRTree(&rtree_callback)) ).first;
00220 rtreei->second.setReinsertNum(reinsertnum);
00221 }
00222
00223 rtreei->second.insertRect( RTreeData(e->first.first, e->first.second) );
00224 }
00225 }
00226 }
00227
00228
00229 #ifndef NDEBUG
00230 {
00231 unsigned int rectcount = 0;
00232
00233 for(rtreemap_t::const_iterator ti = rtreemap.begin(); ti != rtreemap.end(); ++ti)
00234 {
00235 rectcount += ti->second.size();
00236 }
00237 assert(rectcount == getEdgeCount());
00238 }
00239 #endif
00240 }
00241
00242 void GraphContainer::applyChangeTimeline(const class ChangeTimeline &ct)
00243 {
00244 applyChangelist(ct.getChangelistEnd());
00245 }
00246
00247 void GraphContainer::saveSnapshot(std::ostream &s) const
00248 {
00249
00250 unsigned int key = 0x23232323;
00251 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00252
00253
00254 key = 0x00000001;
00255 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00256
00257 GraphData::saveSnapshot(s);
00258
00259
00260 key = 0x00000002;
00261 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00262
00263
00264 key = static_cast<unsigned int>(rtreemap.size());
00265 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00266
00267 for(rtreemap_t::const_iterator ti = rtreemap.begin(); ti != rtreemap.end(); ++ti)
00268 {
00269
00270 key = ti->first;
00271 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00272
00273
00274 ti->second.saveSnapshot(s);
00275 }
00276
00277
00278 key = 0x00000000;
00279 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00280 }
00281
00282 bool GraphContainer::loadSnapshot(std::istream &s)
00283 {
00284 unsigned int key;
00285
00286
00287 if (!s.read(reinterpret_cast<char*>(&key), sizeof(key))) return false;
00288 if (key != 0x23232323) return false;
00289
00290
00291 while( s.read(reinterpret_cast<char*>(&key), sizeof(key)) )
00292 {
00293 switch(key)
00294 {
00295 case 0:
00296 return true;
00297
00298 case 1:
00299 {
00300 if (!GraphData::loadSnapshot(s)) return false;
00301 break;
00302 }
00303 case 2:
00304 {
00305 unsigned int len;
00306 if (!s.read(reinterpret_cast<char*>(&len), sizeof(len))) return false;
00307
00308 std::cerr << "Loading " << len << " R-Trees." << std::endl;
00309
00310 rtreemap.clear();
00311
00312 for(unsigned int l = 0; l < len; l++)
00313 {
00314 if (!s.read(reinterpret_cast<char*>(&key), sizeof(key))) return false;
00315
00316 rtreemap_t::iterator ti = rtreemap.find(key);
00317
00318 if (ti != rtreemap.end())
00319 return false;
00320
00321
00322 ti = rtreemap.insert( rtreemap_t::value_type(key, GraphRTree(&rtree_callback)) ).first;
00323
00324 if (!ti->second.loadSnapshot(s)) return false;
00325 }
00326
00327 break;
00328 }
00329 default:
00330 return false;
00331 }
00332 }
00333
00334
00335 return false;
00336 }
00337
00338 class VertexRef GraphContainer::getVertex(vertexid_t vid, const class Changelist &cl) const
00339 {
00340 if (cl.isVertexChanged(vid))
00341 {
00342 const AttributeVertexTinyBlob& vc = cl.getVertexChange(vid);
00343
00344 if (vc.empty()) {
00345 return VertexRef(NULL, 0);
00346 }
00347
00348
00349 return VertexRef(this, vid, vc);
00350 }
00351
00352 if (not GraphData::existVertex(vid))
00353 return VertexRef(NULL, 0);
00354
00355 return VertexRef(this, vid);
00356 }
00357
00358 class EdgeRef GraphContainer::getEdge(vertexid_t src, vertexid_t tgt, const class Changelist &cl) const
00359 {
00360 if (cl.isEdgeChanged(src, tgt))
00361 {
00362 const AttributeEdgeTinyBlob &ec = cl.getEdgeChange(src, tgt);
00363
00364 if (ec.empty())
00365 return EdgeRef(NULL, 0, 0);
00366
00367 return EdgeRef(this, src, tgt, ec);
00368 }
00369
00370 unsigned int eidx = getEdgeIdx(src, tgt);
00371
00372 if (eidx >= edges.size()-1)
00373 return EdgeRef(NULL, 0, 0);
00374
00375 return EdgeRef(this, src, eidx);
00376 }
00377
00378 std::vector<class EdgeRef> GraphContainer::getEdgeList(vertexid_t vid, const class Changelist &cl) const
00379 {
00380 std::vector<class EdgeRef> edgelist;
00381
00382
00383 int startedgeidx, endedgeidx;
00384
00385 if (vid >= vertices.size()-1)
00386 {
00387 startedgeidx = endedgeidx = 0;
00388 }
00389 else
00390 {
00391 startedgeidx = vertices[vid].edgeidx;
00392 endedgeidx = vertices[vid+1].edgeidx;
00393 }
00394
00395
00396 Changelist::edgelist_t ecl = cl.getEdgeListChange(vid);
00397
00398 std::vector<unsigned int>::iterator eii;
00399 Changelist::edgelist_t::iterator eci = ecl.begin();
00400
00401 for(int edgeidx = startedgeidx; edgeidx < endedgeidx; )
00402 {
00403
00404 while (eci != ecl.end() and eci->first < edges[edgeidx].target)
00405 {
00406 edgelist.push_back(EdgeRef(this, vid, eci->first, *eci->second));
00407 eci++;
00408 }
00409
00410 if (eci != ecl.end() and eci->first == edges[edgeidx].target)
00411 {
00412
00413 edgelist.push_back(EdgeRef(this, vid, eci->first, *eci->second));
00414 eci++;
00415 edgeidx++;
00416 }
00417
00418
00419 while (edgeidx != endedgeidx and (eci == ecl.end() or eci->first > edges[edgeidx].target))
00420 {
00421 edgelist.push_back(EdgeRef(this, vid, edgeidx));
00422 edgeidx++;
00423 }
00424 }
00425
00426
00427 while (eci != ecl.end())
00428 {
00429 edgelist.push_back(EdgeRef(this, vid, eci->first, *eci->second));
00430 eci++;
00431 }
00432
00433 assert(eci == ecl.end());
00434
00435 return edgelist;
00436 }
00437
00438 void GraphContainer::getGraphProperties(class ByteBuffer &bb) const
00439 {
00440 ByteOutBuffer s (bb);
00441
00442 s.append<unsigned int>(0x00010000);
00443
00444 properties.appendBinaryFormat(s);
00445 }
00446
00447 static inline bool isInRectangle(coord_t x, coord_t y, coord_t px, coord_t py, coord_t qx, coord_t qy)
00448 {
00449 return (px <= x and x <= qx) and (py <= y and y <= qy);
00450 }
00451
00452
00453
00454
00455
00456 void GraphContainer::getArea(coord_t x1, coord_t y1, coord_t x2, coord_t y2,
00457 const QueryLimits *ql,
00458 const char* filtertext, const char* vertexattrsel, const char* edgeattrsel,
00459 const class ChangeTimeline &ct, class ByteBuffer &dest) const
00460 {
00461 #ifdef DBGOUTPUT
00462 double ts1 = timestamp();
00463 #endif
00464
00465 ByteOutBuffer s (dest);
00466 s.append<unsigned int>(0x00010000);
00467
00468
00469 AttributeSelectorList asl_vertex, asl_edge;
00470
00471
00472 try {
00473 if (!vertexattrsel) vertexattrsel = "";
00474 asl_vertex.parseString(vertexattrsel, properties, VE_VERTEX);
00475 }
00476 catch (GraphException &e)
00477 {
00478
00479 s.append<unsigned char>(0xFF);
00480 s.append<unsigned char>(static_cast<unsigned char>(e.what_str().size()));
00481 s.appendString(e.what_str());
00482 return;
00483 }
00484
00485
00486 try {
00487 if (!edgeattrsel) edgeattrsel = "";
00488 asl_edge.parseString(edgeattrsel, properties, VE_EDGE);
00489 }
00490 catch (GraphException &e)
00491 {
00492
00493 s.append<unsigned char>(0xFF);
00494 s.append<unsigned char>(static_cast<unsigned char>(e.what_str().size()));
00495 s.appendString(e.what_str());
00496 return;
00497 }
00498
00499
00500 FilterRoot filter;
00501
00502 try {
00503 if (!filtertext) filtertext = "";
00504 filter.parseString(filtertext, properties);
00505 }
00506 catch (GraphException &e)
00507 {
00508
00509 s.append<unsigned char>(0xFF);
00510 s.append<unsigned char>(static_cast<unsigned char>(e.what_str().size()));
00511 s.appendString(e.what_str());
00512 return;
00513 }
00514
00515
00516
00517 s.append<unsigned char>(0x01);
00518 asl_vertex.appendBinaryFormat(s);
00519
00520
00521
00522 s.append<unsigned char>(0x02);
00523 asl_edge.appendBinaryFormat(s);
00524
00525
00526
00527 bool selvertex = asl_vertex.size() != 0;
00528 bool seledge = asl_edge.size() != 0;
00529
00530 if (selvertex or seledge)
00531 {
00532 RTree_t::Rect queryrect(std::min(x1,x2), std::min(y1,y2),
00533 std::max(x1,x2), std::max(y1,y2));
00534
00535 rtreemap_t::const_iterator rtreelevel = rtreemap.begin();
00536
00537
00538 hash_set<unsigned int> vertexdup;
00539
00540
00541 unsigned int vertexmaxlimit = ql ? ql->vertexmaxlimit : 400000;
00542 unsigned int vertexminlimit = ql ? ql->vertexminlimit : 100000;
00543 unsigned int edgemaxlimit = ql ? ql->edgemaxlimit : 400000;
00544 unsigned int edgeminlimit = ql ? ql->edgeminlimit : 100000;
00545
00546
00547
00548
00549
00550 unsigned int vertexnum = 0;
00551 unsigned int edgenum = 0;
00552
00553 unsigned int vertexresultnum = 0;
00554 unsigned int edgeresultnum = 0;
00555
00556
00557
00558 typedef std::deque<Visitor> levels_t;
00559 std::deque<Visitor> levels;
00560
00561
00562
00563 while(rtreelevel != rtreemap.end() &&
00564 ( (selvertex && vertexnum < vertexminlimit) ||
00565 (seledge && edgenum < edgeminlimit) )
00566 )
00567 {
00568 #ifdef DBGOUTPUT
00569 std::cerr << "Query on level " << rtreelevel->first << " with vmax "
00570 << (vertexmaxlimit - vertexnum) << " and emax "
00571 << (edgemaxlimit - edgenum) << ".\n";
00572 #endif
00573
00574
00575 levels.push_back( Visitor(*this, asl_vertex, asl_edge, filter, ct.getChangelistStart(),
00576 vertexmaxlimit - vertexnum,
00577 edgemaxlimit - edgenum,
00578 vertexdup) );
00579
00580 Visitor &v = levels.back();
00581
00582 rtreelevel->second.queryRange(queryrect, v);
00583
00584 #ifdef DBGOUTPUT
00585 std::cerr << "Level " << rtreelevel->first << " yielded "
00586 << v.vertexnum << " vertices and " << v.edgenum << " edges\n";
00587 #endif
00588
00589 if ((!selvertex || vertexnum + v.vertexnum >= vertexmaxlimit) &&
00590 (!seledge || edgenum + v.edgenum >= edgemaxlimit))
00591 {
00592 #ifdef DBGOUTPUT
00593 std::cerr << "Overflow. Removing last level.\n";
00594 #endif
00595 levels.pop_back();
00596 break;
00597 }
00598 else
00599 {
00600
00601 vertexnum += v.vertexnum;
00602 edgenum += v.edgenum;
00603
00604 if (vertexresultnum + v.vertexnum <= vertexmaxlimit)
00605 vertexresultnum += v.vertexnum;
00606
00607 if (edgeresultnum + v.edgenum <= edgemaxlimit)
00608 edgeresultnum += v.edgenum;
00609
00610 rtreelevel++;
00611 }
00612 }
00613
00614 assert(vertexresultnum <= vertexmaxlimit);
00615 assert(edgeresultnum <= edgemaxlimit);
00616
00617
00618
00619
00620 if (selvertex)
00621 {
00622
00623 s.append<unsigned char>(0x03);
00624
00625 s.append<unsigned int>(vertexresultnum);
00626
00627 unsigned int vertexcount = 0;
00628 for(levels_t::reverse_iterator li = levels.rbegin(); li != levels.rend(); ++li)
00629 {
00630 s.appendByteBuffer(li->vertexout);
00631
00632 vertexcount += li->vertexnum;
00633 }
00634 assert(vertexcount == vertexresultnum);
00635 }
00636
00637 if (seledge)
00638 {
00639
00640 s.append<unsigned char>(0x04);
00641
00642 s.append<unsigned int>(edgeresultnum);
00643
00644 unsigned int edgecount = 0;
00645
00646 for(levels_t::reverse_iterator li = levels.rbegin(); li != levels.rend(); ++li)
00647 {
00648 s.appendByteBuffer(li->edgeout);
00649 edgecount += li->edgenum;
00650 }
00651
00652 assert(edgecount == edgeresultnum);
00653 }
00654 lastqueryedgenum = edgeresultnum;
00655 }
00656
00657 if ((selvertex or seledge) and ct.getFrameCount() > 0)
00658 {
00659
00660 s.append<unsigned char>(0x05);
00661
00662
00663 ByteBuffer abb;
00664 ByteOutBuffer abob (abb);
00665
00666
00667 abob.append<unsigned int>(ct.getFrameCount());
00668
00669
00670
00671 Changelist anichg(*this);
00672
00673 unsigned int p;
00674 AttributeVertexTinyBlob attrblob;
00675
00676 #ifdef DBGOUTPUT
00677 unsigned int anientry = 0;
00678 double ats1 = timestamp();
00679 #endif
00680
00681 for(ChangeTimeline::changeframelist_t::const_iterator cf = ct.frames.begin(); cf != ct.frames.end(); ++cf)
00682 {
00683 abob.append<unsigned int>(cf->chgoplist.size());
00684
00685 for(ChangeFrame::chgoplist_t::const_iterator cfe = cf->chgoplist.begin(); cfe != cf->chgoplist.end(); ++cfe)
00686 {
00687
00688 abob.append<unsigned char>(cfe->chgid);
00689
00690 #ifdef DBGOUTPUT
00691 anientry++;
00692 #endif
00693
00694
00695
00696 switch(cfe->chgid)
00697 {
00698 case ChangeFrame::CHG_NONE:
00699 default:
00700 assert(0);
00701 break;
00702
00703
00704
00705 case ChangeFrame::CHG_ADDVERTEX:
00706 anichg.addVertex(cfe->vid1, cfe->blob);
00707
00708 p = asl_vertex.processVertexAttributeBlob(attrblob, *this, anichg, cfe->vid1);
00709 abob.appendBytes(attrblob.data(), p);
00710
00711 break;
00712
00713 case ChangeFrame::CHG_SETVERTEX:
00714
00715 p = asl_vertex.processVertexAttributeBlob(attrblob, *this, anichg, cfe->vid1);
00716 abob.appendBytes(attrblob.data(), p);
00717
00718 anichg.setVertexAttr(cfe->vid1, cfe->blob);
00719
00720 p = asl_vertex.processVertexAttributeBlob(attrblob, *this, anichg, cfe->vid1);
00721 abob.appendBytes(attrblob.data(), p);
00722
00723 break;
00724
00725 case ChangeFrame::CHG_DELVERTEX:
00726
00727 p = asl_vertex.processVertexAttributeBlob(attrblob, *this, anichg, cfe->vid1);
00728 abob.appendBytes(attrblob.data(), p);
00729
00730 anichg.delVertex(cfe->vid1);
00731 break;
00732
00733
00734
00735 case ChangeFrame::CHG_ADDEDGE:
00736 anichg.addEdge(cfe->vid1, cfe->vid2, AttributeEdgeTinyBlob(cfe->blob.data(), cfe->blob.size()));
00737
00738 p = asl_edge.processEdgeAttributeBlob(attrblob, *this, anichg, cfe->vid1, cfe->vid2);
00739 abob.appendBytes(attrblob.data(), p);
00740
00741 break;
00742
00743 case ChangeFrame::CHG_SETEDGE:
00744 p = asl_edge.processEdgeAttributeBlob(attrblob, *this, anichg, cfe->vid1, cfe->vid2);
00745 abob.appendBytes(attrblob.data(), p);
00746
00747 anichg.setEdgeAttr(cfe->vid1, cfe->vid2, reinterpret_cast<const AttributeEdgeTinyBlob&>(cfe->blob));
00748
00749 p = asl_edge.processEdgeAttributeBlob(attrblob, *this, anichg, cfe->vid1, cfe->vid2);
00750 abob.appendBytes(attrblob.data(), p);
00751
00752 break;
00753
00754 case ChangeFrame::CHG_DELEDGE:
00755
00756 p = asl_edge.processEdgeAttributeBlob(attrblob, *this, anichg, cfe->vid1, cfe->vid2);
00757 abob.appendBytes(attrblob.data(), p);
00758
00759 anichg.delEdge(cfe->vid1, cfe->vid2);
00760 break;
00761 }
00762 }
00763 }
00764
00765
00766 #ifdef DBGOUTPUT
00767 double ats2 = timestamp();
00768
00769 std::cerr << "Animation size: " << abb.size() << " - " << anientry << " entries\n";
00770 std::cerr << "animation time: " << (ats2 - ats1) << "\n";
00771 #endif
00772
00773 s.append<unsigned int>(abb.size());
00774 s.appendByteBuffer(abb);
00775 }
00776
00777
00778 s.append<unsigned char>(0x00);
00779
00780 #ifdef DBGOUTPUT
00781 double ts2 = timestamp();
00782
00783 std::cerr << "getArea Querytime: " << (ts2 - ts1) << "sec. Result size " << dest.size() << "\n";
00784 #endif
00785 }
00786
00787 inline GraphContainer::Visitor::Visitor(const GraphContainer &_gc,
00788 const class AttributeSelectorList &_asl_vertex, const class AttributeSelectorList &_asl_edge,
00789 const class FilterRoot &_filter,
00790 const class Changelist &_cl, unsigned int _vertexmaxlimit, unsigned int _edgemaxlimit,
00791 hash_set<unsigned int> &_vertexdup)
00792 : gc(_gc),
00793 asl_vertex(_asl_vertex), asl_edge(_asl_edge),
00794 filter(_filter),
00795 cl(_cl),
00796 vertexmaxlimit(_vertexmaxlimit), edgemaxlimit(_edgemaxlimit),
00797 vertexdup(_vertexdup),
00798 vertexnum(0), edgenum(0)
00799 {
00800 if (filter.isEmpty()) filtertype = 0;
00801 else if (filter.getType() == VE_VERTEX) filtertype = 1;
00802 else filtertype = 2;
00803 }
00804
00805 inline void GraphContainer::Visitor::add_vertex(unsigned int vid)
00806 {
00807
00808 if (vertexdup.insert(vid).second == false)
00809 {
00810
00811 return;
00812 }
00813
00814 #ifdef CALCATTRVALUES
00815
00816 unsigned int p = asl_vertex.processVertexAttributeBlob(attrblob, gc, cl, vid);
00817
00818 ByteOutBuffer vertexoutwr (vertexout);
00819
00820 vertexoutwr.appendBytes(attrblob.data(), p);
00821
00822 #else
00823 #warning "Attribute calculation is disabled!"
00824 #endif
00825 vertexnum++;
00826 }
00827
00828 inline void GraphContainer::Visitor::add_edge(unsigned int src, unsigned int tgt)
00829 {
00830 #ifdef CALCATTRVALUES
00831
00832 unsigned int p = asl_edge.processEdgeAttributeBlob(attrblob, gc, cl, src, tgt);
00833
00834 ByteOutBuffer edgeoutwr (edgeout);
00835
00836 edgeoutwr.appendBytes(attrblob.data(), p);
00837 #endif
00838 edgenum++;
00839 }
00840
00841 bool GraphContainer::Visitor::operator()(const RTree_t::Rect &, const RTreeData &d)
00842 {
00843
00844
00845
00846 if (filtertype == 0)
00847 {
00848 if (asl_edge.size() != 0 && (edgenum < edgemaxlimit))
00849 {
00850 add_edge(d.src, d.tgt);
00851 }
00852
00853 if (asl_vertex.size() != 0 && (vertexnum < vertexmaxlimit))
00854 {
00855 add_vertex(d.src);
00856 }
00857
00858 if (asl_vertex.size() != 0 && (vertexnum < vertexmaxlimit))
00859 {
00860 add_vertex(d.tgt);
00861 }
00862 }
00863 else if (filtertype == 1)
00864 {
00865 bool addedge = false;
00866
00867
00868 if (filter.eval_vertex(gc, cl, d.src))
00869 {
00870 if (asl_vertex.size() != 0 && (vertexnum < vertexmaxlimit))
00871 add_vertex(d.src);
00872
00873 addedge = true;
00874 }
00875
00876
00877 if (filter.eval_vertex(gc, cl, d.tgt))
00878 {
00879 if (asl_vertex.size() != 0 && (vertexnum < vertexmaxlimit))
00880 add_vertex(d.tgt);
00881
00882 addedge = true;
00883 }
00884
00885
00886 if (asl_edge.size() != 0 && (edgenum < edgemaxlimit) && addedge)
00887 {
00888 add_edge(d.src, d.tgt);
00889 }
00890 }
00891 else if (filtertype == 2)
00892 {
00893
00894 if (filter.eval_edge(gc, cl, d.src, d.tgt))
00895 {
00896 if (asl_edge.size() != 0 && (edgenum < edgemaxlimit))
00897 add_edge(d.src, d.tgt);
00898
00899
00900 if (asl_vertex.size() != 0 && (vertexnum < vertexmaxlimit))
00901 {
00902 add_vertex(d.src);
00903 }
00904
00905 if (asl_vertex.size() != 0 && (vertexnum < vertexmaxlimit))
00906 {
00907 add_vertex(d.tgt);
00908 }
00909 }
00910 }
00911
00912
00913 return (edgenum < edgemaxlimit) || (vertexnum < vertexmaxlimit);
00914 }
00915
00916 void GraphContainer::getNearestNeighbor(coord_t x1, coord_t y1, coord_t x2, coord_t y2,
00917 coord_t selx, coord_t sely, const QueryLimits *ql,
00918 const char* filtertext, const char* vertexattrsel, const char* edgeattrsel,
00919 const class Changelist &cl, class ByteBuffer &dest) const
00920 {
00921 #ifdef DBGOUTPUT
00922 double ts1 = timestamp();
00923 #endif
00924
00925 ByteOutBuffer s (dest);
00926 s.append<unsigned int>(0x00010000);
00927
00928
00929 AttributeSelectorList asl_vertex, asl_edge;
00930
00931
00932 try {
00933 if (!vertexattrsel) vertexattrsel = "";
00934 asl_vertex.parseString(vertexattrsel, properties, VE_VERTEX);
00935 }
00936 catch (GraphException &e)
00937 {
00938
00939 s.append<unsigned char>(0xFF);
00940 s.append<unsigned char>(static_cast<unsigned char>(e.what_str().size()));
00941 s.appendString(e.what_str());
00942 return;
00943 }
00944
00945
00946 try {
00947 if (!edgeattrsel) edgeattrsel = "";
00948 asl_edge.parseString(edgeattrsel, properties, VE_EDGE);
00949 }
00950 catch (GraphException &e)
00951 {
00952
00953 s.append<unsigned char>(0xFF);
00954 s.append<unsigned char>(static_cast<unsigned char>(e.what_str().size()));
00955 s.appendString(e.what_str());
00956 return;
00957 }
00958
00959
00960 FilterRoot filter;
00961
00962 try {
00963 if (!filtertext) filtertext = "";
00964 filter.parseString(filtertext, properties);
00965 }
00966 catch (GraphException &e)
00967 {
00968
00969 s.append<unsigned char>(0xFF);
00970 s.append<unsigned char>(static_cast<unsigned char>(e.what_str().size()));
00971 s.appendString(e.what_str());
00972 return;
00973 }
00974
00975
00976
00977 s.append<unsigned char>(0x01);
00978 asl_vertex.appendBinaryFormat(s);
00979
00980
00981
00982 s.append<unsigned char>(0x02);
00983 asl_edge.appendBinaryFormat(s);
00984
00985
00986
00987 bool selvertex = asl_vertex.size() != 0;
00988 bool seledge = asl_edge.size() != 0;
00989
00990 if (selvertex or seledge)
00991 {
00992 RTree_t::Rect queryrect(std::min(x1,x2), std::min(y1,y2),
00993 std::max(x1,x2), std::max(y1,y2));
00994
00995 rtreemap_t::const_iterator rtreelevel = rtreemap.begin();
00996
00997
00998 hash_set<unsigned int> vertexdup;
00999
01000
01001 unsigned int vertexmaxlimit = ql ? ql->vertexmaxlimit : 400000;
01002 unsigned int vertexminlimit = ql ? ql->vertexminlimit : 100000;
01003 unsigned int edgemaxlimit = ql ? ql->edgemaxlimit : 400000;
01004 unsigned int edgeminlimit = ql ? ql->edgeminlimit : 100000;
01005
01006
01007
01008
01009
01010 unsigned int vertexnum = 0;
01011 unsigned int edgenum = 0;
01012
01013 unsigned int vertexresultnum = 0;
01014 unsigned int edgeresultnum = 0;
01015
01016
01017
01018 typedef std::deque<NNVisitor> levels_t;
01019 std::deque<NNVisitor> levels;
01020
01022 NNResult nnr( RTree_t::Point(selx, sely) );
01023
01024
01025
01026 while(rtreelevel != rtreemap.end() &&
01027 ( (selvertex && vertexnum < vertexminlimit) ||
01028 (seledge && edgenum < edgeminlimit) )
01029 )
01030 {
01031 #ifdef DBGOUTPUT
01032 std::cerr << "Query on level " << rtreelevel->first << " with vmax "
01033 << (vertexmaxlimit - vertexnum) << " and emax "
01034 << (edgemaxlimit - edgenum) << ".\n";
01035 #endif
01036
01037
01038 levels.push_back( NNVisitor(*this, nnr, asl_vertex, asl_edge, filter, cl,
01039 vertexmaxlimit - vertexnum,
01040 edgemaxlimit - edgenum,
01041 vertexdup) );
01042
01043 NNVisitor &v = levels.back();
01044
01045 rtreelevel->second.queryRange(queryrect, v);
01046
01047 #ifdef DBGOUTPUT
01048 std::cerr << "Level " << rtreelevel->first << " yielded "
01049 << v.vertexnum << " vertices and " << v.edgenum << " edges\n";
01050 #endif
01051
01052 if ((!selvertex || vertexnum + v.vertexnum >= vertexmaxlimit) &&
01053 (!seledge || edgenum + v.edgenum >= edgemaxlimit))
01054 {
01055 #ifdef DBGOUTPUT
01056 std::cerr << "Overflow. Removing last level.\n";
01057 #endif
01058 levels.pop_back();
01059
01060 break;
01061 }
01062 else
01063 {
01064
01065 vertexnum += v.vertexnum;
01066 edgenum += v.edgenum;
01067
01068 if (vertexresultnum + v.vertexnum <= vertexmaxlimit)
01069 {
01070 vertexresultnum += v.vertexnum;
01071
01072
01073 nnr.nn_vid = v.nnr.nn_vid;
01074 nnr.dist_nn_vid = v.nnr.dist_nn_vid;
01075 }
01076
01077 if (edgeresultnum + v.edgenum <= edgemaxlimit)
01078 {
01079 edgeresultnum += v.edgenum;
01080
01081
01082 nnr.nn_esrc = v.nnr.nn_esrc;
01083 nnr.nn_etgt = v.nnr.nn_etgt;
01084 nnr.dist_nn_edge = v.nnr.dist_nn_edge;
01085 }
01086
01087 rtreelevel++;
01088 }
01089 }
01090
01091 assert(vertexresultnum <= vertexmaxlimit);
01092 assert(edgeresultnum <= edgemaxlimit);
01093
01094
01095
01096 AttributeVertexTinyBlob attrblob;
01097
01098 if (selvertex && nnr.nn_vid != VERTEX_INVALID)
01099 {
01100
01101 s.append<unsigned char>(0x03);
01102
01103 s.append<unsigned int>(1);
01104
01105 unsigned int p = asl_vertex.processVertexAttributeBlob(attrblob, *this, cl, nnr.nn_vid);
01106 s.appendBytes(attrblob.data(), p);
01107 }
01108
01109 if (seledge && nnr.nn_esrc != VERTEX_INVALID)
01110 {
01111
01112 s.append<unsigned char>(0x04);
01113
01114 s.append<unsigned int>(1);
01115
01116 unsigned int p = asl_edge.processEdgeAttributeBlob(attrblob, *this, cl, nnr.nn_esrc, nnr.nn_etgt);
01117 s.appendBytes(attrblob.data(), p);
01118 }
01119 }
01120
01121
01122 s.append<unsigned char>(0x00);
01123
01124 #ifdef DBGOUTPUT
01125 double ts2 = timestamp();
01126
01127 std::cerr << "getNearestNeighbor Querytime: " << (ts2 - ts1) << "sec. Result size " << dest.size() << "\n";
01128 #endif
01129 }
01130
01131 inline GraphContainer::NNVisitor::NNVisitor(const GraphContainer &_gc, const class NNResult &_nnr,
01132 const class AttributeSelectorList &_asl_vertex, const class AttributeSelectorList &_asl_edge,
01133 const class FilterRoot &_filter,
01134 const class Changelist &_cl, unsigned int _vertexmaxlimit, unsigned int _edgemaxlimit,
01135 hash_set<unsigned int> &_vertexdup)
01136 : gc(_gc),
01137 use_asl_vertex(_asl_vertex.size() != 0), use_asl_edge(_asl_edge.size() != 0),
01138 filter(_filter),
01139 cl(_cl),
01140 vertexmaxlimit(_vertexmaxlimit), edgemaxlimit(_edgemaxlimit),
01141 vertexdup(_vertexdup),
01142 vertexnum(0), edgenum(0),
01143 nnr(_nnr)
01144 {
01145 if (filter.isEmpty()) filtertype = 0;
01146 else if (filter.getType() == VE_VERTEX) filtertype = 1;
01147 else filtertype = 2;
01148 }
01149
01151 inline GraphContainer::NNResult::NNResult(const RTree_t::Point &p)
01152 {
01153 point = p;
01154
01155 nn_vid = VERTEX_INVALID;
01156 nn_esrc = nn_etgt = VERTEX_INVALID;
01157
01158 dist_nn_vid = std::numeric_limits<RTree_t::AreaType>::max();
01159 dist_nn_edge = std::numeric_limits<RTree_t::AreaType>::max();
01160 }
01161
01162 inline void GraphContainer::NNResult::checkVertex(coord_t x, coord_t y, unsigned int vid)
01163 {
01164 RTree_t::AreaType d = point.getDistanceSquare(x, y);
01165
01166 if (d < dist_nn_vid)
01167 {
01168 nn_vid = vid;
01169 dist_nn_vid = d;
01170 }
01171 }
01172
01173 inline void GraphContainer::NNResult::checkEdge(coord_t x1, coord_t y1, coord_t x2, coord_t y2, unsigned int vsrc, unsigned int vtgt)
01174 {
01175 RTree_t::AreaType d = point.getDistanceLineSquare(x1, y1, x2, y2);
01176
01177 if (d < dist_nn_edge)
01178 {
01179 nn_esrc = vsrc;
01180 nn_etgt = vtgt;
01181 dist_nn_edge = d;
01182 }
01183 }
01184
01185 inline void GraphContainer::NNVisitor::add_vertex(unsigned int vid)
01186 {
01187
01188 if (vertexdup.insert(vid).second == false)
01189 {
01190
01191 return;
01192 }
01193
01194 vertexnum++;
01195 }
01196
01197 inline void GraphContainer::NNVisitor::add_edge(unsigned int , unsigned int )
01198 {
01199 edgenum++;
01200 }
01201
01202 bool GraphContainer::NNVisitor::operator()(const RTree_t::Rect &, const RTreeData &d)
01203 {
01204
01205
01206
01207
01208 coord_t x1 = gc.getVertexAttr(d.src, gc.vertexattrid_xaxis).getInteger();
01209 coord_t y1 = gc.getVertexAttr(d.src, gc.vertexattrid_yaxis).getInteger();
01210
01211 coord_t x2 = gc.getVertexAttr(d.tgt, gc.vertexattrid_xaxis).getInteger();
01212 coord_t y2 = gc.getVertexAttr(d.tgt, gc.vertexattrid_yaxis).getInteger();
01213
01214
01215 if (filtertype == 0)
01216 {
01217 if (use_asl_edge && (edgenum < edgemaxlimit))
01218 {
01219 add_edge(d.src, d.tgt);
01220 nnr.checkEdge(x1, y1, x2, y2, d.src, d.tgt);
01221 }
01222
01223 if (use_asl_vertex && (vertexnum < vertexmaxlimit))
01224 {
01225 add_vertex(d.src);
01226 nnr.checkVertex(x1, y1, d.src);
01227 }
01228
01229 if (use_asl_vertex && (vertexnum < vertexmaxlimit))
01230 {
01231 add_vertex(d.tgt);
01232 nnr.checkVertex(x2, y2, d.tgt);
01233 }
01234 }
01235 else if (filtertype == 1)
01236 {
01237 bool addedge = false;
01238
01239
01240 if (filter.eval_vertex(gc, cl, d.src))
01241 {
01242 if (use_asl_vertex && (vertexnum < vertexmaxlimit))
01243 {
01244 add_vertex(d.src);
01245 nnr.checkVertex(x1, y1, d.src);
01246 }
01247
01248 addedge = true;
01249 }
01250
01251
01252 if (filter.eval_vertex(gc, cl, d.tgt))
01253 {
01254 if (use_asl_vertex && (vertexnum < vertexmaxlimit))
01255 {
01256 add_vertex(d.tgt);
01257 nnr.checkVertex(x1, y1, d.tgt);
01258 }
01259
01260 addedge = true;
01261 }
01262
01263
01264 if (use_asl_edge && (edgenum < edgemaxlimit) && addedge)
01265 {
01266 add_edge(d.src, d.tgt);
01267 nnr.checkEdge(x1, y1, x2, y2, d.src, d.tgt);
01268 }
01269 }
01270 else if (filtertype == 2)
01271 {
01272
01273 if (filter.eval_edge(gc, cl, d.src, d.tgt))
01274 {
01275 if (use_asl_edge && (edgenum < edgemaxlimit))
01276 {
01277 add_edge(d.src, d.tgt);
01278 nnr.checkEdge(x1, y1, x2, y2, d.src, d.tgt);
01279 }
01280
01281
01282 if (use_asl_vertex && (vertexnum < vertexmaxlimit))
01283 {
01284 add_vertex(d.src);
01285 nnr.checkVertex(x1, y1, d.src);
01286 }
01287
01288 if (use_asl_vertex && (vertexnum < vertexmaxlimit))
01289 {
01290 add_vertex(d.tgt);
01291 nnr.checkVertex(x1, y1, d.tgt);
01292 }
01293 }
01294 }
01295
01296
01297 return (edgenum < edgemaxlimit) || (vertexnum < vertexmaxlimit);
01298 }
01299
01300 }