GraphContainer.h

Go to the documentation of this file.

// $Id: GraphContainer.h 231 2006-06-25 20:00:02Z bingmann $

#ifndef VGS_GraphContainer_H
#define VGS_GraphContainer_H

#include "GraphTypes.h"
#include "GraphData.h"
#include "ByteBuffer.h"
#include "RTree.h"

#include <map>

#if defined(__GNUC__)
#include <ext/hash_set>
#else
#include <hash_set>
#endif

namespace VGServer {

#if defined(__GNUC__)
using __gnu_cxx::hash_set;
#else
using stdext::hash_set;
#endif

class GraphContainer : public GraphData
{
public:
    //typedef class RTree<coord_t, long long> RTree_t;
    typedef class RTree RTree_t;

    struct RTreeData
    {
        // vertex id's
        unsigned int src, tgt;

        RTreeData()
        { }

        RTreeData(unsigned int _src, unsigned int _tgt)
            : src(_src), tgt(_tgt)
        { }

        inline bool operator==(const RTreeData &o) const
        { return (src == o.src) && (tgt == o.tgt); }
    };

    struct RTreeDataCallback
    {
        GraphContainer &gc;

        RTreeDataCallback(GraphContainer &_gc)
            : gc(_gc)
        { }
        
        inline const class RTree_t::Rect getMBR(const RTreeData &d) const
        {
            int x1 = gc.getVertexAttr(d.src, gc.vertexattrid_xaxis).getInteger();
            int y1 = gc.getVertexAttr(d.src, gc.vertexattrid_yaxis).getInteger();

            int x2 = gc.getVertexAttr(d.tgt, gc.vertexattrid_xaxis).getInteger();
            int y2 = gc.getVertexAttr(d.tgt, gc.vertexattrid_yaxis).getInteger();

            return RTree_t::Rect(std::min(x1,x2), std::min(y1,y2),
                                 std::max(x1,x2), std::max(y1,y2));
        }
    };

    typedef RTree_t::Tree<struct RTreeData, struct RTreeDataCallback> GraphRTree;

private:
    static const bool rtreemap_descending;

    struct rtreemap_compare
    {
        bool descending;

        rtreemap_compare(bool _desc) : descending(_desc) { }

        inline bool operator()(unsigned int a, unsigned int b) const {
            return descending ? (a > b) : (a < b);
        }
    };

    typedef std::map<unsigned int, GraphRTree, rtreemap_compare> rtreemap_t;
    rtreemap_t          rtreemap;

    void        recreateRTree();

    RTreeDataCallback   rtree_callback;

    unsigned int vertexattrid_xaxis, vertexattrid_yaxis;

    unsigned int edgeattrid_zaxis;

    mutable unsigned int lastqueryedgenum;

public:
    // *** Instead of returning pointers into the vertex or edge arrays, the
    // *** functions of GraphContainer will return objects holding references
    // *** to the various places allowing them to return further information.
    // *** These Ref objects (VertexRef and EdgeRef) are declared below.

    unsigned int reinsertnum;
public:
    explicit GraphContainer(const class GraphProperties &properties);

    ~GraphContainer();

    void        applyGraphData(class GraphData &newgraph);

    void        swap(class GraphContainer &other);

    //*** essentially just pass-thru functions

    void        applyChangelist(const class Changelist &cl);

    void        applyChangeTimeline(const class ChangeTimeline &ct);

    void        saveSnapshot(std::ostream &s) const;

    bool        loadSnapshot(std::istream &s);

    //*** these functions unify the information in the global graph and that in
    //*** the parameter Changelists

    class VertexRef getVertex(vertexid_t id, const class Changelist &cl) const;

    class EdgeRef getEdge(vertexid_t src, vertexid_t tgt, const class Changelist &cl) const;

    std::vector<class EdgeRef> getEdgeList(vertexid_t id, const class Changelist &cl) const;

    //*** provided by search data structures
    //*** (or for the beginning by linear algorithms)

    void getGraphProperties(class ByteBuffer &dest) const;
    
    void        getArea(coord_t x1, coord_t y1, coord_t x2, coord_t y2, const QueryLimits *ql,
                        const char* filter, const char* vertexattrsel, const char* edgeattrsel,
                        const class ChangeTimeline &ct, class ByteBuffer &dest) const;

    void        getNearestNeighbor(coord_t x1, coord_t y1, coord_t x2, coord_t y2,
                                   coord_t selx, coord_t sely, const QueryLimits *ql,
                                   const char* filter, const char* vertexattrsel, const char* edgeattrsel,
                                   const class Changelist &cl, class ByteBuffer &dest) const;

    inline unsigned int getLastQueryEdgenum() const
    { return lastqueryedgenum; }

    inline unsigned int getRTreeNum() const
    { return rtreemap.size(); }

    typedef RTree_t::Stats RTreeStats_t;
    typedef RTree_t::LevelStats RTreeLevelStats_t;

    void getRTreeStats(RTreeStats_t &st) const;

private:
    class Visitor
    {
    private:
        // *** References to parent objects
        const class GraphContainer &gc;
        const class AttributeSelectorList &asl_vertex, &asl_edge;
        const class FilterRoot &filter;
        const class Changelist &cl;

        AttributeVertexTinyBlob attrblob;
        
        unsigned int vertexmaxlimit, edgemaxlimit;

        int     filtertype;

        hash_set<unsigned int>  &vertexdup;

    public:
        ByteBuffer vertexout, edgeout;

        unsigned int vertexnum, edgenum;

        Visitor(const GraphContainer &_gc,
                const class AttributeSelectorList &_asl_vertex, const class AttributeSelectorList &_asl_edge,
                const class FilterRoot &_filter,
                const class Changelist &_cl, unsigned int _vertexmaxlimit, unsigned int _edgemaxlimit,
                hash_set<unsigned int> &vertexdup);

        bool operator()(const RTree_t::Rect &, const RTreeData &d);

        void    add_vertex(unsigned int vid);

        void    add_edge(unsigned int src, unsigned int tgt);
    };

    class NNResult
    {
    public:
        class RTree_t::Point point;

        unsigned int    nn_vid;

        unsigned int    nn_esrc, nn_etgt;

        RTree_t::AreaType       dist_nn_vid;

        RTree_t::AreaType       dist_nn_edge;

        inline NNResult(const RTree_t::Point &p);

        inline void     checkVertex(coord_t x, coord_t y, unsigned int vid);

        inline void     checkEdge(coord_t x1, coord_t y1, coord_t x2, coord_t y2, unsigned int vsrc, unsigned int vtgt);
    };

    class NNVisitor
    {
    private:
        // *** References to parent objects
        const class GraphContainer &gc;
        const bool use_asl_vertex, use_asl_edge;
        const class FilterRoot &filter;
        const class Changelist &cl;

        unsigned int vertexmaxlimit, edgemaxlimit;

        int     filtertype;

        hash_set<unsigned int>  &vertexdup;

    public:
        unsigned int vertexnum, edgenum;

        class NNResult nnr;

        NNVisitor(const GraphContainer &_gc, const class NNResult &nnr,
                  const class AttributeSelectorList &_asl_vertex, const class AttributeSelectorList &_asl_edge,
                  const class FilterRoot &_filter,
                  const class Changelist &_cl, unsigned int _vertexmaxlimit, unsigned int _edgemaxlimit,
                  hash_set<unsigned int> &vertexdup);

        bool operator()(const RTree_t::Rect &, const RTreeData &d);

        void    add_vertex(unsigned int vid);

        void    add_edge(unsigned int src, unsigned int tgt);
    };
};

class VertexRef
{
private:
    const class GraphData* graphdata;

    unsigned int vertexid;

    const AttributeVertexTinyBlob* attrmodified;

protected:
    inline VertexRef(const class GraphData* gd, unsigned int vid)
        : graphdata(gd), vertexid(vid), attrmodified(NULL)
    {
    }

    inline VertexRef(const class GraphData* gd, unsigned int vid, const AttributeVertexTinyBlob& am)
        : graphdata(gd), vertexid(vid), attrmodified(new AttributeVertexTinyBlob(am))
    {
    }

    friend class GraphContainer;

public:
    inline VertexRef(const VertexRef &orig)
        : graphdata(orig.graphdata), vertexid(orig.vertexid)
    {
        attrmodified = orig.attrmodified ? new AttributeVertexTinyBlob(*orig.attrmodified) : NULL;
    }

    inline VertexRef& operator=(const VertexRef &orig)
    {
        if (attrmodified) delete attrmodified;
        graphdata = orig.graphdata;
        vertexid = orig.vertexid;
        attrmodified = orig.attrmodified ? new AttributeVertexTinyBlob(*orig.attrmodified) : NULL;
        return *this;
    }

    inline ~VertexRef()
    {
        if (attrmodified) delete attrmodified;
    }

    inline bool valid() const
    { return graphdata != NULL; }

    inline vertexid_t getId() const
    { return vertexid; }

    inline AnyType getAttr(unsigned int attrid) const
    {
        assert(graphdata);      // programs should call valid() first

        if (attrmodified)
            return attrmodified->getAttrChainValue(0, attrid, graphdata->getProperties().vertexattr);

        return graphdata->vertices[vertexid].getAttr(attrid, *graphdata);
    }
};

class EdgeRef
{
private:
    const class GraphData* graphdata;

    vertexid_t srcvid;

    unsigned int edgeidx;

    const AttributeEdgeTinyBlob* attrmodified;

protected:
    inline EdgeRef(const class GraphData* gd, unsigned int _srcvid, unsigned int _edgeidx)
        : graphdata(gd), srcvid(_srcvid), edgeidx(_edgeidx), attrmodified(NULL)
    {
    }

    inline EdgeRef(const class GraphData* gd, unsigned int _srcvid, unsigned int _edgeidx, const AttributeEdgeTinyBlob& am)
        : graphdata(gd), srcvid(_srcvid), edgeidx(_edgeidx), attrmodified(new AttributeEdgeTinyBlob(am))
    {
    }

    friend class GraphContainer;

public:
    inline EdgeRef(const EdgeRef &orig)
        : graphdata(orig.graphdata), srcvid(orig.srcvid), edgeidx(orig.edgeidx)
    {
        attrmodified = orig.attrmodified ? new AttributeEdgeTinyBlob(*orig.attrmodified) : NULL;
    }

    inline EdgeRef& operator=(const EdgeRef &orig)
    {
        if (attrmodified) delete attrmodified;
        graphdata = orig.graphdata;
        srcvid = orig.srcvid;
        edgeidx = orig.edgeidx;
        attrmodified = orig.attrmodified ? new AttributeEdgeTinyBlob(*orig.attrmodified) : NULL;
        return *this;
    }

    inline ~EdgeRef()
    {
        if (attrmodified) delete attrmodified;
    }

    inline bool valid() const
    { return graphdata != NULL; }

    inline vertexid_t getSource() const
    { return srcvid; }

    inline vertexid_t getTarget() const
    {
        if (attrmodified) return edgeidx;
        assert(graphdata);
        return graphdata->edges[edgeidx].target;
    }

    inline AnyType getAttr(unsigned int attrid) const
    {
        assert(graphdata);      // programs should call valid() first

        if (attrmodified)
            return attrmodified->getAttrChainValue(0, attrid, graphdata->getProperties().edgeattr);

        return graphdata->edges[edgeidx].getAttr(attrid, *graphdata);
    }

};

} // namespace VGServer

#endif // VGS_GraphContainer_H

---