GraphContainer.cc

Go to the documentation of this file.
00001 // $Id: GraphContainer.cc 243 2006-07-06 07:57:25Z bingmann $
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 //#define DBGOUTPUT
00018 
00019 // disable this for testing rtree speed
00020 #define CALCATTRVALUES
00021 
00022 namespace VGServer {
00023 
00024 const bool GraphContainer::rtreemap_descending = false;
00025 
00026 // force complete instanciation of the rtree
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     // TODO: thread synchronization here
00054     GraphData::swap(newgraph);
00055 
00056     // reconstruct new index stuff
00057     recreateRTree();
00058 }
00059 
00060 void GraphContainer::swap(class GraphContainer &newgraph)
00061 {
00062     // TODO: thread synchronization here
00063 
00064     // swap graph data arrays
00065     GraphData::swap(newgraph);
00066 
00067     // swap index structures
00068     std::swap(rtreemap, newgraph.rtreemap);
00069     
00070     // update callback pointers, because std::map swap doesnt use assignment
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         //int x1 = getVertexAttr(vi, vertexattrid_xaxis).getInteger();
00101         //int y1 = getVertexAttr(vi, vertexattrid_yaxis).getInteger();
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             //int x2 = getVertexAttr(tvi, vertexattrid_xaxis).getInteger();
00112             //int y2 = getVertexAttr(tvi, vertexattrid_yaxis).getInteger();
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                 // create new R-Tree instance
00121                 rtreei = rtreemap.insert( rtreemap_t::value_type(level, GraphRTree(&rtree_callback)) ).first;
00122                 rtreei->second.setReinsertNum(reinsertnum);
00123             }
00124             
00125             // the rectangle itself is computed on-demand by the RTreeDataCallback
00126             rtreei->second.insertRect(RTreeData(vi, tvi));
00127 
00128             // dumb and funny progress status
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     // calculate statistics
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     // first delete all modified or deleted changes from the rtrees
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() || // modification was a delete
00183                 (cl.edgeaddlist.find( e->first ) == cl.edgeaddlist.end()) // not new vertex
00184                 )
00185             {
00186                 // retrieve the level on which to find this edge
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     // afterwards add all new edges and reinsert the modified ones
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()) // modification was a delete
00210             {
00211                 // retrieve the level on which to find this edge
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                     // create new R-Tree instance
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     // check the number of rectangles
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     // first write a signature
00250     unsigned int key = 0x23232323;
00251     s.write(reinterpret_cast<char*>(&key), sizeof(key));
00252     
00253     // *** call the function to save the GraphData
00254     key = 0x00000001;
00255     s.write(reinterpret_cast<char*>(&key), sizeof(key));
00256 
00257     GraphData::saveSnapshot(s);
00258 
00259     // *** then save the r-trees
00260     key = 0x00000002;
00261     s.write(reinterpret_cast<char*>(&key), sizeof(key));
00262     
00263     // save size of map
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         // save map key
00270         key = ti->first;
00271         s.write(reinterpret_cast<char*>(&key), sizeof(key));
00272 
00273         // write the r-tree serialization
00274         ti->second.saveSnapshot(s);
00275     }
00276 
00277     // finished
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     // read signature
00287     if (!s.read(reinterpret_cast<char*>(&key), sizeof(key))) return false;
00288     if (key != 0x23232323) return false;
00289 
00290     // read vertices
00291     while( s.read(reinterpret_cast<char*>(&key), sizeof(key)) )
00292     {
00293         switch(key)
00294         {
00295         case 0: // termination
00296             return true;
00297 
00298         case 1: // graph data: call upwards.
00299         {
00300             if (!GraphData::loadSnapshot(s)) return false;
00301             break;
00302         }
00303         case 2: // r-trees
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                 // create new R-Tree instance
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     // while loop terminated by istream error
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()) { // the modification was a delVertex, so return an invalid VertexRef
00345             return VertexRef(NULL, 0);
00346         }
00347 
00348         // construct the reference including a copy of the modifications
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); // return a blank EdgeRef
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     // list of edge in global graph
00383     int startedgeidx, endedgeidx;
00384 
00385     if (vid >= vertices.size()-1) // source is outside the global graph's range
00386     {
00387         startedgeidx = endedgeidx = 0;
00388     }
00389     else
00390     {
00391         startedgeidx = vertices[vid].edgeidx;
00392         endedgeidx = vertices[vid+1].edgeidx;
00393     }
00394 
00395     // merge in the Changelist
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         // add new edges that come before the eii index.
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             // overwrite the edge object in the global graph
00413             edgelist.push_back(EdgeRef(this, vid, eci->first, *eci->second));
00414             eci++;
00415             edgeidx++; // by skipping this entry
00416         }
00417 
00418         // add edges from the global graph
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     // add rest edges that come after the last index.
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); // format v1.00
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 Output byte stream: look at docs/timo/kodierung.pdf
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); // format v1.00
00467 
00468     // *** parse selection expressions
00469     AttributeSelectorList asl_vertex, asl_edge;
00470     
00471     // vertex selection expression
00472     try {
00473         if (!vertexattrsel) vertexattrsel = "";
00474         asl_vertex.parseString(vertexattrsel, properties, VE_VERTEX);
00475     }
00476     catch (GraphException &e) // these are ParseException or ConversionException
00477     {
00478         // output string error into buffer
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     // edge selection expression
00486     try {
00487         if (!edgeattrsel) edgeattrsel = "";
00488         asl_edge.parseString(edgeattrsel, properties, VE_EDGE);
00489     }
00490     catch (GraphException &e) // these are ParseException or ConversionException
00491     {
00492         // output string error into buffer
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     // parse filter expression
00500     FilterRoot filter;
00501     
00502     try {
00503         if (!filtertext) filtertext = "";
00504         filter.parseString(filtertext, properties);
00505     }
00506     catch (GraphException &e) // these are ParseException or ConversionException
00507     {
00508         // output string error into buffer
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     // append section 1 describing the graph vertex attribute properties parsed
00516     // from the vertexattrsel
00517     s.append<unsigned char>(0x01);
00518     asl_vertex.appendBinaryFormat(s);
00519 
00520     // append section 2 describing the graph edge attribute properties parsed
00521     // from the edgeattrsel
00522     s.append<unsigned char>(0x02);
00523     asl_edge.appendBinaryFormat(s);
00524 
00525     // *** perform range query on the r-trees
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         // set to remove duplicate vertex info from result
00538         hash_set<unsigned int> vertexdup;
00539 
00540         // query limit parameter
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         // two different counters here: first one counts all "seen" objects, so
00547         // this will become == maxlimit when enough are seen, and resultnum
00548         // which is the number of picked objects.
00549 
00550         unsigned int vertexnum = 0;
00551         unsigned int edgenum = 0;
00552 
00553         unsigned int vertexresultnum = 0;
00554         unsigned int edgeresultnum = 0;
00555 
00556         // this is used as std::stack, but we also need a reverse_iterator at
00557         // the end.
00558         typedef std::deque<Visitor> levels_t;
00559         std::deque<Visitor> levels;
00560         
00561         // TODO: fix lookups into changelist.
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             // create new visitor
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             // query the rtree in the right level.
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                 // continue into next level
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         // append each of the selected levels in reverse order so that the
00618         // nodes with highest z-value (lowest priority) come at the end.
00619 
00620         if (selvertex)
00621         {
00622             // append section 3 which are the selected vertices.
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             // append section 4 which are the selected edges.
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         // append animation section 5
00660         s.append<unsigned char>(0x05);
00661 
00662         // temp save the animation data, so we can add it's size
00663         ByteBuffer abb;
00664         ByteOutBuffer abob (abb);
00665 
00666         // number of animation frames following
00667         abob.append<unsigned int>(ct.getFrameCount());
00668 
00669         // we have to keep an own Changelist of the current animation so
00670         // src.attr lookups will work right!
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                 // save the change operation made
00688                 abob.append<unsigned char>(cfe->chgid);
00689 
00690 #ifdef DBGOUTPUT
00691                 anientry++;
00692 #endif
00693                 
00694                 // apply the change to our running ChangeList and save the
00695                 // selector's result on the changed vertex/edge
00696                 switch(cfe->chgid)
00697                 {
00698                 case ChangeFrame::CHG_NONE:
00699                 default:
00700                     assert(0);
00701                     break;
00702 
00703                 // *** Vertex Operations
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                 // *** Edge Operations
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 // append the size of the animation data
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     // terminating section id
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     // check in vertex duplicate hash
00808     if (vertexdup.insert(vid).second == false)
00809     {
00810         // insertion failed -> vertex id is already in the set.
00811         return;
00812     }
00813 
00814 #ifdef CALCATTRVALUES
00815     // add vertex attributes to output buffer
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     // add edge attributes to output buffer
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     // TODO: add function to exclude edges not in range
00844     // TODO: changelist
00845 
00846     if (filtertype == 0) // null-filter
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) // vertex-filter
00864     {
00865         bool addedge = false;
00866 
00867         // check if the filter is true on the source vertex of this edge
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         // then the target vertex
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         // add the edge inbetween if either vertex was included
00886         if (asl_edge.size() != 0 && (edgenum < edgemaxlimit) && addedge)
00887         {
00888             add_edge(d.src, d.tgt);
00889         }
00890     }
00891     else if (filtertype == 2) // edge-filter
00892     {
00893         // check if the filter is true on the edge
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             // add inzident vertices if there is still room.
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     // stop the range query first when both counters exceed their maxlimit.
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); // format v1.00
00927 
00928     // *** parse selection expressions
00929     AttributeSelectorList asl_vertex, asl_edge;
00930     
00931     // vertex selection expression
00932     try {
00933         if (!vertexattrsel) vertexattrsel = "";
00934         asl_vertex.parseString(vertexattrsel, properties, VE_VERTEX);
00935     }
00936     catch (GraphException &e) // these are ParseException or ConversionException
00937     {
00938         // output string error into buffer
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     // edge selection expression
00946     try {
00947         if (!edgeattrsel) edgeattrsel = "";
00948         asl_edge.parseString(edgeattrsel, properties, VE_EDGE);
00949     }
00950     catch (GraphException &e) // these are ParseException or ConversionException
00951     {
00952         // output string error into buffer
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     // parse filter expression
00960     FilterRoot filter;
00961     
00962     try {
00963         if (!filtertext) filtertext = "";
00964         filter.parseString(filtertext, properties);
00965     }
00966     catch (GraphException &e) // these are ParseException or ConversionException
00967     {
00968         // output string error into buffer
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     // append section 1 describing the graph vertex attribute properties parsed
00976     // from the vertexattrsel
00977     s.append<unsigned char>(0x01);
00978     asl_vertex.appendBinaryFormat(s);
00979 
00980     // append section 2 describing the graph edge attribute properties parsed
00981     // from the edgeattrsel
00982     s.append<unsigned char>(0x02);
00983     asl_edge.appendBinaryFormat(s);
00984 
00985     // *** perform range query on the r-trees
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         // set to remove duplicate vertex info from result
00998         hash_set<unsigned int> vertexdup;
00999 
01000         // query limit parameters
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         // two different counters here: first one counts all "seen" objects, so
01007         // this will become == maxlimit when enough are seen, and resultnum
01008         // which is the number of picked objects.
01009 
01010         unsigned int vertexnum = 0;
01011         unsigned int edgenum = 0;
01012 
01013         unsigned int vertexresultnum = 0;
01014         unsigned int edgeresultnum = 0;
01015 
01016         // this is used as std::stack, but we also need a reverse_iterator at
01017         // the end.
01018         typedef std::deque<NNVisitor> levels_t;
01019         std::deque<NNVisitor> levels;
01020 
01022         NNResult nnr( RTree_t::Point(selx, sely) );
01023         
01024         // TODO: fix lookups into changelist.
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             // create new visitor
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             // query the rtree in the right level.
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                 // do not update nnr object.
01060                 break;
01061             }
01062             else
01063             {
01064                 // continue into next level
01065                 vertexnum += v.vertexnum;
01066                 edgenum += v.edgenum;
01067 
01068                 if (vertexresultnum + v.vertexnum <= vertexmaxlimit)
01069                 {
01070                     vertexresultnum += v.vertexnum;
01071 
01072                     // copy vertex nnr result
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                     // copy edge nnr result
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         // nearestNeighbor returns only one object each, if it was found
01095 
01096         AttributeVertexTinyBlob attrblob;
01097 
01098         if (selvertex && nnr.nn_vid != VERTEX_INVALID)
01099         {
01100             // append section 3 which are the selected vertices.
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             // append section 4 which are the selected edges.
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     // terminating section id
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     // check in vertex duplicate hash
01188     if (vertexdup.insert(vid).second == false)
01189     {
01190         // insertion failed -> vertex id is already in the set.
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     // TODO: changelist
01205 
01206     // retrieve coordinates. this could be accelerated by using the rectangle,
01207     // but we dont know how the coordinates correspond.
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) // null-filter
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) // vertex-filter
01236     {
01237         bool addedge = false;
01238 
01239         // check if the filter is true on the source vertex of this edge
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         // then the target vertex
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         // add the edge inbetween if either vertex was included
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) // edge-filter
01271     {
01272         // check if the filter is true on the edge
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             // add inzident vertices if there is still room.
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     // stop the range query first when both counters exceed their maxlimit.
01297     return (edgenum < edgemaxlimit) || (vertexnum < vertexmaxlimit);
01298 }
01299 
01300 } // namespace VGServer

Generated on Wed Sep 27 14:34:00 2006 for VGServer by  doxygen 1.4.7