00001
00002
00003 #include <map>
00004 #include <assert.h>
00005 #include <iostream>
00006
00007 #include "GraphData.h"
00008 #include "Changelist.h"
00009 #include "ByteOutBuffer.h"
00010
00011 #include "AttributeBlob_impl.h"
00012
00013 namespace VGServer {
00014
00015 GraphData::GraphData(const class GraphProperties &_properties)
00016 : properties(_properties)
00017 {
00018
00019 Vertex &v = vertices.new_back();
00020 v.attridx = v.edgeidx = 0;
00021
00022 vertexcount = 0;
00023
00024 edges.new_back();
00025
00026
00027 properties.calcAttributeLookups();
00028 }
00029
00030 void GraphData::swap(class GraphData &other)
00031 {
00032 std::swap(properties, other.properties);
00033
00034 vertices.swap(other.vertices);
00035 edges.swap(other.edges);
00036
00037 vertexattr.swap(other.vertexattr);
00038 edgeattr.swap(other.edgeattr);
00039
00040 std::swap(vertexcount, other.vertexcount);
00041 }
00042
00043
00044
00045 void GraphData::applyChangelist(const class Changelist &cl)
00046 {
00047 assert( checkReferences() );
00048
00049
00050
00051
00052 TpArray<Edge> newedges;
00053
00054 AttributeBigBlob newvertexattr;
00055 AttributeBigBlob newedgeattr;
00056
00057
00058
00059 typedef std::map<vertexid_t, const AttributeVertexTinyBlob*> vertexchglist_sorted_t;
00060 vertexchglist_sorted_t vertexchg;
00061
00062 for(Changelist::vertexchglist_t::const_iterator vci = cl.vertexchglist.begin(); vci != cl.vertexchglist.end(); ++vci)
00063 {
00064 vertexchg[vci->first] = &vci->second;
00065 }
00066
00067
00068 typedef std::map<Changelist::vertexidpair_t, const AttributeEdgeTinyBlob*> edgechglist_sorted_t;
00069 edgechglist_sorted_t edgechg;
00070
00071 for(Changelist::edgechglist_t::const_iterator eci = cl.edgechglist.begin(); eci != cl.edgechglist.end(); ++eci)
00072 {
00073 edgechg[eci->first] = &eci->second;
00074 }
00075
00076 #ifdef DBG_APPLYCHGLIST
00077
00078
00079 std::cout << "Vertex Changes:\n";
00080 for(vertexchglist_sorted_t::const_iterator vci = vertexchg.begin(); vci != vertexchg.end(); ++vci)
00081 {
00082 std::cout << "v: " << vci->first << "\n";
00083 }
00084
00085 std::cout << "Edge Changes:\n";
00086 for(edgechglist_sorted_t::const_iterator eci = edgechg.begin(); eci != edgechg.end(); ++eci)
00087 {
00088 std::cout << "e: " << eci->first.first << "," << eci->first.second << "\n";
00089 }
00090 #endif
00091
00092
00093
00094
00095 vertexid_t oldmaxvnum = vertices.size()-1;
00096 vertexid_t newmaxvnum = vertexchg.empty() ? oldmaxvnum : vertexchg.rbegin()->first+1;
00097
00098 if (oldmaxvnum < newmaxvnum)
00099 {
00100 vertices.reserve(newmaxvnum + 1);
00101
00102 assert(oldmaxvnum < vertices.size());
00103 unsigned int attrendidx = vertices[oldmaxvnum].attridx;
00104
00105
00106
00107
00108 for(vertexid_t vi = oldmaxvnum+1; vi < newmaxvnum+1; vi++)
00109 {
00110 Vertex &v = vertices.new_back();
00111 v.edgeidx = edges.size()-1;
00112 v.attridx = attrendidx;
00113 }
00114
00115 assert(vertices.size() == newmaxvnum+1);
00116 }
00117
00118
00119 newedges.reserve(edges.size() + edgechg.size());
00120
00121
00122 vertexchglist_sorted_t::const_iterator vertexchgiter = vertexchg.begin();
00123 edgechglist_sorted_t::const_iterator edgechgiter = edgechg.begin();
00124
00125 unsigned int vertexiter = 0;
00126 unsigned int oldedgeiter = 0;
00127 unsigned int newedgeiter = 0;
00128
00129 unsigned int newvertexattrpos = 0;
00130 unsigned int newedgeattrpos = 0;
00131
00132 unsigned int newvertexcount = 0;
00133
00134 while( vertexiter < vertices.size()-1 )
00135 {
00136
00137
00138 if (vertexchgiter != vertexchg.end() and vertexiter == vertexchgiter->first)
00139 {
00140
00141
00142
00143 const AttributeVertexTinyBlob* ap = vertexchgiter->second;
00144
00145 unsigned int attrlen = ap->getAttrChainLength(0, properties.vertexattr);
00146
00147 newvertexattr.copy(newvertexattrpos, ap->data(), attrlen);
00148
00149 vertices[vertexiter].attridx = newvertexattrpos;
00150
00151 newvertexattrpos += attrlen;
00152
00153 if (attrlen > 0) newvertexcount++;
00154
00155 vertexchgiter++;
00156 }
00157 else
00158 {
00159
00160
00161 unsigned int attrlen = vertices[vertexiter+1].attridx - vertices[vertexiter].attridx;
00162
00163 if (attrlen > 0)
00164 newvertexattr.copy(newvertexattrpos, vertexattr.data(vertices[vertexiter].attridx), attrlen);
00165
00166 vertices[vertexiter].attridx = newvertexattrpos;
00167
00168 newvertexattrpos += attrlen;
00169
00170 if (attrlen > 0) newvertexcount++;
00171 }
00172
00173 vertices[vertexiter].edgeidx = newedgeiter;
00174 assert(newedgeiter == newedges.size());
00175
00176
00177
00178 if (vertices[vertexiter].attridx != newvertexattrpos)
00179 {
00180
00181 unsigned int endedgeidx = vertices[vertexiter+1].edgeidx;
00182
00183 while(edgechgiter != edgechg.end() and edgechgiter->first.first < vertexiter) {
00184
00185
00186
00187 edgechgiter++;
00188 }
00189
00190 if (edgechgiter == edgechg.end() or edgechgiter->first.first != vertexiter)
00191 {
00192
00193
00194 while(oldedgeiter < endedgeidx)
00195 {
00196 assert( oldedgeiter < edges.size() );
00197
00198 Edge &e = newedges.new_back();
00199 e.target = edges[oldedgeiter].target;
00200
00201 #ifdef DBG_APPLYCHGLIST
00202 std::cout << "Flushing " << vertexiter << "," << e.target << "\n";
00203 #endif
00204
00205
00206 unsigned int attrlen = edges[oldedgeiter+1].attridx - edges[oldedgeiter].attridx;
00207
00208 if (attrlen > 0)
00209 newedgeattr.copy(newedgeattrpos, edgeattr.data(edges[oldedgeiter].attridx), attrlen);
00210
00211 e.attridx = newedgeattrpos;
00212
00213 newedgeattrpos += attrlen;
00214
00215
00216 oldedgeiter++;
00217 newedgeiter++;
00218 }
00219 }
00220 else
00221 {
00222
00223 while(oldedgeiter < endedgeidx or (edgechgiter != edgechg.end() and edgechgiter->first.first == vertexiter))
00224 {
00225 if (oldedgeiter >= endedgeidx
00226 or (edgechgiter != edgechg.end()
00227 and edgechgiter->first.first == vertexiter
00228 and edgechgiter->first.second < edges[oldedgeiter].target)
00229 )
00230 {
00231
00232
00233 if (not edgechgiter->second->empty())
00234 {
00235 Edge &e = newedges.new_back();
00236 e.target = edgechgiter->first.second;
00237
00238 #ifdef DBG_APPLYCHGLIST
00239 std::cout << "InsertingNew " << vertexiter << "," << e.target << "\n";
00240 #endif
00241
00242
00243 const AttributeEdgeTinyBlob* ap = edgechgiter->second;
00244
00245 unsigned int attrlen = ap->getAttrChainLength(0, properties.edgeattr);
00246
00247 newedgeattr.copy(newedgeattrpos, ap->data(), attrlen);
00248
00249 e.attridx = newedgeattrpos;
00250
00251 newedgeattrpos += attrlen;
00252 newedgeiter++;
00253 }
00254
00255
00256 edgechgiter++;
00257 }
00258 else if (edgechgiter == edgechg.end()
00259 or edgechgiter->first.first != vertexiter
00260 or edgechgiter->first.second > edges[oldedgeiter].target)
00261 {
00262
00263
00264
00265 assert( oldedgeiter < edges.size() );
00266
00267 Edge &e = newedges.new_back();
00268 e.target = edges[oldedgeiter].target;
00269
00270 #ifdef DBG_APPLYCHGLIST
00271 std::cout << "OldCopy " << vertexiter << "," << e.target << "\n";
00272 #endif
00273
00274
00275 unsigned int attrlen = edges[oldedgeiter+1].attridx - edges[oldedgeiter].attridx;
00276
00277 if (attrlen > 0)
00278 newedgeattr.copy(newedgeattrpos, edgeattr.data(edges[oldedgeiter].attridx), attrlen);
00279
00280 e.attridx = newedgeattrpos;
00281
00282 newedgeattrpos += attrlen;
00283
00284 oldedgeiter++;
00285 newedgeiter++;
00286 }
00287 else
00288 {
00289 assert( edgechgiter->first.first == vertexiter );
00290
00291 if (not edgechgiter->second->empty())
00292 {
00293 Edge &e = newedges.new_back();
00294 e.target = edgechgiter->first.second;
00295
00296 #ifdef DBG_APPLYCHGLIST
00297 std::cout << "Modify " << vertexiter << "," << e.target << "\n";
00298 #endif
00299
00300
00301 const AttributeEdgeTinyBlob* ap = edgechgiter->second;
00302
00303 unsigned int attrlen = ap->getAttrChainLength(0, properties.edgeattr);
00304
00305 newedgeattr.copy(newedgeattrpos, ap->data(), attrlen);
00306
00307 e.attridx = newedgeattrpos;
00308
00309 newedgeattrpos += attrlen;
00310 newedgeiter++;
00311 }
00312
00313
00314
00315 oldedgeiter++;
00316 edgechgiter++;
00317 }
00318 }
00319 }
00320 }
00321
00322 vertexiter++;
00323 }
00324
00325
00326 vertices[vertices.size()-1].edgeidx = newedgeiter;
00327 vertices[vertices.size()-1].attridx = newvertexattrpos;
00328
00329
00330 Edge &eend = newedges.new_back();
00331 eend.target = VERTEX_INVALID;
00332 eend.attridx = newedgeattrpos;
00333
00334 assert( vertexchgiter == vertexchg.end() );
00335
00336
00337
00338
00339
00340 edges.swap( newedges );
00341 vertexattr.swap( newvertexattr );
00342 edgeattr.swap( newedgeattr );
00343
00344 vertexcount = newvertexcount;
00345
00346 assert( checkReferences() );
00347 }
00348
00349 void GraphData::writeFig(bool writefigheader, std::ostream &o, unsigned int attrX, unsigned int attrY) const
00350 {
00351 if (writefigheader)
00352 o << "#FIG 3.2\nLandscape\nCenter\nInches\nLetter\n100.00\nSingle\n-2\n1200 2\n";
00353
00354 for(vertexid_t vi = 0; vi < vertices.size()-1; vi++)
00355 {
00356 if (not existVertex(vi)) continue;
00357
00358 o << "1 4 0 1 0 7 50 -1 -1 0.000 1 0.0000 "
00359 << getVertexAttr(vi, attrX).getString() << " "
00360 << getVertexAttr(vi, attrY).getString() << " 32 32 0 0 0 0\n";
00361
00362 unsigned int endedgeidx = vertices[vi+1].edgeidx;
00363
00364 for(unsigned int ei = vertices[vi].edgeidx; ei < endedgeidx; ei++)
00365 {
00366 vertexid_t tvi = edges[ei].target;
00367 if (tvi == VERTEX_INVALID) break;
00368 if (not existVertex(tvi)) continue;
00369
00370 o << "2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2\n";
00371 o << "\t\t"
00372 << getVertexAttr(vi, attrX).getString() << " " << getVertexAttr(vi, attrY).getString() << " "
00373 << getVertexAttr(tvi, attrX).getString() << " " << getVertexAttr(tvi, attrY).getString() << "\n";
00374 }
00375 }
00376 }
00377
00378 #define funcassert(x) do { if (!(x)) { fprintf(stderr, "assertion %s failed ", #x); return false; } } while(0)
00379
00380 bool GraphData::checkReferences() const
00381 {
00382 for(vertexid_t vi = 0; vi < vertices.size()-1; vi++)
00383 {
00384 funcassert(vertices[vi].edgeidx <= vertices[vi+1].edgeidx);
00385
00386 funcassert(vertices[vi].edgeidx <= edges.size());
00387 funcassert(vertices[vi+1].edgeidx <= edges.size());
00388
00389
00390 for(unsigned int ei = vertices[vi].edgeidx; ei + 1 < vertices[vi+1].edgeidx; ei++)
00391 {
00392 funcassert(edges[ei].target < edges[ei+1].target);
00393 }
00394
00395 funcassert(vertices[vi].attridx <= vertices[vi+1].attridx);
00396
00397 funcassert(vertices[vi].attridx <= vertexattr.size());
00398 funcassert(vertices[vi+1].attridx <= vertexattr.size());
00399 }
00400
00401 for(unsigned int ei = 0; ei < edges.size()-1; ei++)
00402 {
00403 funcassert(edges[ei].attridx <= edges[ei+1].attridx);
00404
00405 funcassert(edges[ei].attridx <= edgeattr.size());
00406 funcassert(edges[ei+1].attridx <= edgeattr.size());
00407 }
00408
00409 funcassert(vertices[vertices.size()-1].edgeidx == edges.size()-1);
00410
00411 return true;
00412 }
00413
00414 const GraphData::Vertex* GraphData::getVertex(vertexid_t id) const
00415 {
00416 if (id >= vertices.size()-1) id = vertices.size()-1;
00417
00418 return &vertices[id];
00419 }
00420
00421 bool GraphData::existVertex(vertexid_t id) const
00422 {
00423 if (id >= vertices.size()-1) return false;
00424
00425 return (vertices[id].attridx < vertices[id+1].attridx);
00426 }
00427
00428 class AnyType GraphData::getVertexAttr(vertexid_t id, unsigned int attr) const
00429 {
00430 const Vertex *v = getVertex(id);
00431 return v->getAttr(attr, *this);
00432 }
00433
00434 AttributeVertexTinyBlob GraphData::getVertexAttrBlob(vertexid_t id) const
00435 {
00436 if (id >= vertices.size()-1) return AttributeVertexTinyBlob();
00437
00438
00439 return AttributeVertexTinyBlob(vertexattr.data(vertices[id].attridx),
00440 vertices[id+1].attridx - vertices[id].attridx);
00441 }
00442
00443 unsigned int GraphData::getEdgeIdx(vertexid_t src, vertexid_t tgt) const
00444 {
00445 if (src >= vertices.size()-1) return edges.size()-1;
00446 if (tgt >= vertices.size()-1) return edges.size()-1;
00447
00448 int startidx = vertices[src].edgeidx;
00449 int endidx = vertices[src+1].edgeidx;
00450
00451 for(int ei = startidx; ei < endidx; ei++)
00452 {
00453 if (edges[ei].target == tgt) {
00454 return ei;
00455 }
00456 }
00457 return edges.size()-1;
00458 }
00459
00460
00461 const GraphData::Edge* GraphData::getEdge(vertexid_t src, vertexid_t tgt) const
00462 {
00463 if (src >= vertices.size()-1) return NULL;
00464 if (tgt >= vertices.size()-1) return NULL;
00465
00466 int startidx = vertices[src].edgeidx;
00467 int endidx = vertices[src+1].edgeidx;
00468
00469 for(int ei = startidx; ei < endidx; ei++)
00470 {
00471 if (edges[ei].target == tgt) {
00472 return &edges[ei];
00473 }
00474 }
00475 return NULL;
00476 }
00477
00478 bool GraphData::existEdge(vertexid_t src, vertexid_t tgt) const
00479 {
00480 return getEdgeIdx(src,tgt) < (edges.size()-1);
00481 }
00482
00483 class AnyType GraphData::getEdgeAttr(vertexid_t src, vertexid_t tgt, unsigned int attr) const
00484 {
00485 const Edge *e = getEdge(src,tgt);
00486 if (e == NULL) return AnyType(ATTRTYPE_INVALID);
00487 return e->getAttr(attr, *this);
00488 }
00489
00490 AttributeEdgeTinyBlob GraphData::getEdgeAttrBlob(vertexid_t src, vertexid_t tgt) const
00491 {
00492 if (src >= vertices.size()-1) return AttributeEdgeTinyBlob();
00493 if (tgt >= vertices.size()-1) return AttributeEdgeTinyBlob();
00494
00495 int startidx = vertices[src].edgeidx;
00496 int endidx = vertices[src+1].edgeidx;
00497
00498 for(int ei = startidx; ei < endidx; ei++)
00499 {
00500 if (edges[ei].target == tgt)
00501 {
00502
00503 return AttributeEdgeTinyBlob(edgeattr.data(edges[ei].attridx),
00504 edges[ei+1].attridx - edges[ei].attridx);
00505 }
00506 }
00507 return AttributeEdgeTinyBlob();
00508 }
00509
00510 std::vector<const GraphData::Edge*> GraphData::getEdgeList(vertexid_t id) const
00511 {
00512 std::vector<const Edge*> outedges;
00513
00514 if (id >= vertices.size()-1) return outedges;
00515
00516 int startidx = vertices[id].edgeidx;
00517 int endidx = vertices[id+1].edgeidx;
00518
00519 outedges.resize(endidx - startidx);
00520 for(int ei = startidx; ei < endidx; ei++)
00521 outedges[ei - startidx] = &edges[ei];
00522
00523 return outedges;
00524 }
00525
00526 std::vector<unsigned int> GraphData::getEdgeIdxList(vertexid_t id) const
00527 {
00528 std::vector<unsigned int> outedges;
00529
00530 if (id >= vertices.size()-1) return outedges;
00531
00532 int startidx = vertices[id].edgeidx;
00533 int endidx = vertices[id+1].edgeidx;
00534
00535 for(int ei = startidx; ei < endidx; ei++)
00536 outedges.push_back(ei);
00537
00538 return outedges;
00539 }
00540
00541 std::vector<unsigned int> GraphData::getEdgeTargetList(vertexid_t id) const
00542 {
00543 std::vector<unsigned int> outedges;
00544
00545 if (id >= vertices.size()-1) return outedges;
00546
00547 int startidx = vertices[id].edgeidx;
00548 int endidx = vertices[id+1].edgeidx;
00549
00550 for(int ei = startidx; ei < endidx; ei++)
00551 outedges.push_back(edges[ei].target);
00552
00553 return outedges;
00554 }
00555
00556 void GraphData::saveSnapshot(std::ostream &s) const
00557 {
00558
00559 unsigned int key = 0x12121212;
00560 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00561
00562
00563 key = 0x00000001;
00564 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00565
00566 ByteBuffer bb;
00567 ByteOutBuffer bob(bb);
00568
00569 properties.appendBinaryFormat(bob);
00570
00571 key = static_cast<unsigned int>(bb.size());
00572 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00573
00574 s.write(bb.data(), static_cast<std::streamsize>(bb.size()));
00575
00576
00577 key = 0x00000002;
00578 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00579
00580 key = vertices.size();
00581 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00582
00583 s.write(reinterpret_cast<const char*>(vertices.begin()), vertices.size() * sizeof(Vertex));
00584
00585
00586 key = 0x00000003;
00587 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00588
00589 key = edges.size();
00590 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00591
00592 s.write(reinterpret_cast<const char*>(edges.begin()), edges.size() * sizeof(Edge));
00593
00594
00595 key = 0x00000004;
00596 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00597
00598
00599 key = vertices.last().attridx;
00600 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00601
00602 s.write(reinterpret_cast<const char*>(vertexattr.data()), key);
00603
00604
00605 key = 0x00000005;
00606 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00607
00608 key = edges.last().attridx;
00609 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00610
00611 s.write(reinterpret_cast<const char*>(edgeattr.data()), key);
00612
00613
00614 key = 0x00000000;
00615 s.write(reinterpret_cast<char*>(&key), sizeof(key));
00616 }
00617
00618 bool GraphData::loadSnapshot(std::istream &s)
00619 {
00620 unsigned int key, len;
00621
00622
00623 if (!s.read(reinterpret_cast<char*>(&key), sizeof(key))) return false;
00624 if (key != 0x12121212) return false;
00625
00626
00627 while( s.read(reinterpret_cast<char*>(&key), sizeof(key)) )
00628 {
00629 switch(key)
00630 {
00631 case 0:
00632 return true;
00633
00634 case 1:
00635 {
00636 if (!s.read(reinterpret_cast<char*>(&len), sizeof(len))) return false;
00637
00638 ByteBuffer bb1;
00639 ByteOutBuffer bob1 (bb1);
00640 properties.appendBinaryFormat(bob1);
00641
00642
00643 if (bb1.size() != len) return false;
00644
00645 ByteBuffer bb2(len);
00646 ByteOutBuffer bob2 (bb2);
00647
00648 if (!s.read(reinterpret_cast<char*>(bb2.data()), len)) return false;
00649
00650
00651 if (memcmp(bb1.data(), bb2.data(), len) != 0) return false;
00652
00653 break;
00654 }
00655 case 2:
00656 {
00657 if (!s.read(reinterpret_cast<char*>(&len), sizeof(len))) return false;
00658
00659 std::cerr << "Loading " << len-1 << " vertices." << std::endl;
00660
00661 vertices.reserve(len);
00662 if (!s.read(reinterpret_cast<char*>(vertices.begin()), len * sizeof(Vertex))) return false;
00663
00664 vertices.set_size(len);
00665 vertexcount = len;
00666 break;
00667 }
00668 case 3:
00669 {
00670 if (!s.read(reinterpret_cast<char*>(&len), sizeof(len))) return false;
00671
00672 std::cerr << "Loading " << len-1 << " edges." << std::endl;
00673
00674 edges.reserve(len);
00675 if (!s.read(reinterpret_cast<char*>(edges.begin()), len * sizeof(Edge))) return false;
00676
00677 edges.set_size(len);
00678 break;
00679 }
00680 case 4:
00681 {
00682 if (!s.read(reinterpret_cast<char*>(&len), sizeof(len))) return false;
00683
00684 std::cerr << "Loading " << len << " bytes of vertex attributes." << std::endl;
00685
00686 vertexattr.alloc(len);
00687 if (!s.read(reinterpret_cast<char*>(vertexattr.data()), len)) return false;
00688
00689 assert(vertices.last().attridx == len);
00690 break;
00691 }
00692 case 5:
00693 {
00694 if (!s.read(reinterpret_cast<char*>(&len), sizeof(len))) return false;
00695
00696 std::cerr << "Loading " << len << " bytes of edge attributes." << std::endl;
00697
00698 edgeattr.alloc(len);
00699 if (!s.read(reinterpret_cast<char*>(edgeattr.data()), len)) return false;
00700
00701 assert(edges.last().attridx == len);
00702 break;
00703 }
00704 default:
00705 return false;
00706 }
00707 }
00708
00709
00710 return false;
00711 }
00712
00713 }