Main Page Namespace List Class Hierarchy Compound List File List Namespace Members Compound Members File Members Related Pages

# VoteCounter.h

    00001 #ifndef VOTECOUNTER_H
    00002 #define VOTECOUNTER_H
    00003
    00004 #include "DAGDatabase.h"
    00005 #include <LEDA/p_queue.h>
    00006
    00007 typedef SmartArray<double> RealVector;
    00008
    00009 class QueryRange : public RealVector
    00010 {
    00011         double commonDelta;
    00012
    00013 public:
    00014         QueryRange(double delta, int dim) : RealVector(dim)
    00015         {
    00016                 Set(delta);
    00017                 commonDelta = delta;
    00018         }
    00019
    00020         QueryRange(const RealVector& rangeVector) : RealVector(rangeVector)
    00021         {
    00022                 commonDelta = 0;
    00023         }
    00024
    00025         QueryRange(const QueryRange& range) : RealVector(range)
    00026         {
    00027                 commonDelta = range.commonDelta;
    00028         }
    00029
    00030         void operator=(const QueryRange& range)
    00031         {
    00032             RealVector::operator=(range);
    00033             commonDelta = range.commonDelta;
    00034         }
    00035
    00036         bool IsInBounds(const double& x, const double& min, const double& max) const
    00037         {
    00038                 return (x >= min && x <= max);
    00039         }
    00040
    00041         void GetDimBounds(const double& x, int dim, double& min, double& max) const
    00042         {
    00043                 double delta = x * (*this)[dim];
    00044                 min = x - delta;
    00045                 max = x + delta;
    00046         }
    00047
    00048         double GetDimDelta() const
    00049         {
    00050                 return commonDelta;
    00051         }
    00052
    00053         bool DoPtsOverlap(const TSV pt1, const TSV pt2) const;
    00054 };
    00055
    00057 // Helper classes for the MOOVC algorithm
    00058
    00064 namespace MOOVC {
    00065
    00066 struct VOTE
    00067 {
    00068         leda_node queryNode;   //<! query node that may vote for multiple model nodes
    00069         int nQueryGraph;           //<! ID of the query graph
    00070
    00071         int nModelNode;   //<! model node that recives a vote from a given query node
    00072         int nModelGraph;  //<! ID of the model graph
    00073
    00074         double dWeight;   //<! the vote weight that sasfies 0 <= weight <= 1
    00075
    00076         VOTE()
    00077         {
    00078                 dWeight = 0.0;
    00079         }
    00080
    00081         void operator+=(const double& w)
    00082         {
    00083                 dWeight += w;
    00084         }
    00085
    00086         static int Compare(const void* elem1, const void* elem2)
    00087         {
    00088                 double a = ((const VOTE*)elem1)->dWeight, b = ((const VOTE*)elem2)->dWeight;
    00089                 return a > b ? -1:(a < b ? 1:0);
    00090         }
    00091 };
    00092
    00093 class VoteBalance
    00094 {
    00095         TSV queryNodeTSV;       //<! TSV of the the subgraph rooted at the query node
    00096         int nQueryNodeLbl;      //<! Label of the node
    00097         double dQueryNodeRelMass; //<! Relative mass of the subgraph rooted at the query node
    00098         int nTSVDim;    //<! Max dimension off all TSV in the database
    00099         double dAlpha;  //<! Convexity parameter for the query rel mass vs. model node rel mass
    00100
    00101 public:
    00102
    00103         VoteBalance(int nTSVDimension, double dConvexityParam = 0.5)
    00104         {
    00105                 nTSVDim = nTSVDimension;
    00106                 dAlpha = dConvexityParam;
    00107         }
    00108
    00109         void SetQueryNode(const DAGPtr ptrDag, leda_node v)
    00110         {
    00111                 queryNodeTSV = ptrDag->GetNodeTSV(v, nTSVDim);
    00112                 nQueryNodeLbl = ptrDag->NodeType(v);
    00113                 dQueryNodeRelMass = (1 - dAlpha) * ptrDag->GetNodeTSVNorm(v) / ptrDag->GetTotalTSVSum();
    00114         }
    00115
    00116         const TSV& GetQueryNodeTSV() const
    00117         {
    00118                 return queryNodeTSV;
    00119         }
    00120
    00121         double Weight(const DAGSearchRecordEx& modelNodeInfo)
    00122         {
    00123                 if (modelNodeInfo.nodeLbl != nQueryNodeLbl)
    00124                         return 0;
    00125
    00126                 double dModelNodeRelMass = dAlpha * modelNodeInfo.nodeTSV.Norm2() / modelNodeInfo.totalVote;
    00127                 double dNormDiff = Norm2(queryNodeTSV - modelNodeInfo.nodeTSV);
    00128
    00129                 return (dQueryNodeRelMass + dModelNodeRelMass) / (1 + dNormDiff);
    00130         }
    00131 };
    00132
    00137 class BoundedBin : public leda_p_queue<double, int>
    00138 {
    00139         int nMaxSize;
    00140 public:
    00141         BoundedBin(int sz = 0) { SetMaxSize(sz); }
    00142         void SetMaxSize(int sz) { nMaxSize = sz; }
    00143         int GetMaxSize() const { return nMaxSize; }
    00144
    00145         void AddVote(VOTE v)
    00146         {
    00147                 ASSERT(size() <= nMaxSize);
    00148
    00149                 // Keep the size <= nMaxSize
    00150                 if (size() == nMaxSize)
    00151                 {
    00152                         pq_item min = find_min(); //O(1)
    00153
    00154                         if (prio(min) < v.dWeight)
    00155                                 del_item(min); //O(log nMaxSize)
    00156                         else
    00157                                 return; // nothing to insert
    00158
    00159                 }
    00160
    00161                 insert(v.dWeight, v.nModelNode); //O(log nMaxSize)
    00162         }
    00163
    00164         void Clear()
    00165         {
    00166                 clear();
    00167         }
    00168 };
    00169
    00170 class PartitionBins
    00171 {
    00172           SmartArray<BoundedBin> bins;
    00173           double dCumulativeVote;
    00174
    00175           // Ideally, the number of nodes in the model would be know.
    00176           // This should be save in the NN info. Temporarely we use a fixed-size map.
    00177           static SmartArray<leda_node> modelNodeMap;
    00178
    00179 public:
    00180           void AddVote(int idxElem, VOTE v)
    00181           {
    00182                   bins[idxElem].AddVote(v);
    00183                   dCumulativeVote += v.dWeight;
    00184           }
    00185
    00186           int GetNodeCount() const { return bins.GetSize(); }
    00187           int GetBinBound(int idxBin) const { return bins[idxBin].GetMaxSize(); }
    00188           double GetCumulativeVote() const { return dCumulativeVote; }
    00189
    00190           void SetPartitionSize(int nNodeCount)
    00191           {
    00192                   bins.ReSize(nNodeCount, false);
    00193                   dCumulativeVote = 0;
    00194
    00195                   for (int i = 0; i < nNodeCount; i++)
    00196                   {
    00197                           bins[i].Clear();
    00198                           bins[i].SetMaxSize(nNodeCount);
    00199                   }
    00200           }
    00201
    00202           void CreateVoteGraph(LEDA_GRAPH<int, double>& g) const;
    00203           double CompPartitionVote() const;
    00204 };
    00205
    00206 class Partition : public SmartArray<leda_node>
    00207 {
    00208 public:
    00209         int NodeCount() const { return GetSize(); }
    00210         void AddElement(leda_node v) { AddTail(v); }
    00211 };
    00212
    00213 class PartitionArray : public SmartArray<Partition>
    00214 {
    00215         const DAG* pDag;
    00216
    00217 public:
    00218         PartitionArray(const DAG* pOverlapGraph)
    00219         {
    00220                 pDag = pOverlapGraph;
    00221         }
    00222
    00223         void SetSize(int sz)
    00224         {
    00225                 ReSize(sz, false);
    00226         }
    00227
    00228         void AddElement(int idxPart, leda_node v)
    00229         {
    00230                 (*this)[idxPart].AddElement(v);
    00231         }
    00232 };
    00233
    00234 class ModelBins
    00235 {
    00236         SmartArray<double> modelVotes;
    00237         SmartArray<PartitionBins> partBins;
    00238         double dMinTotalModelVote;
    00239         int nModelsAboveMinVote;
    00240
    00241 public:
    00242         ModelBins(int nNumModels, double dMinModelVote)
    00243         {
    00244                 modelVotes.ReSize(nNumModels, true); //init to zero!
    00245                 partBins.ReSize(nNumModels, false);
    00246                 dMinTotalModelVote = dMinModelVote;
    00247                 nModelsAboveMinVote = 0;
    00248         }
    00249
    00250         void AddVote(int idxModel, const double& vote)
    00251         {
    00252                 double& currModelWeight = modelVotes[idxModel];
    00253                 bool flag = currModelWeight < dMinTotalModelVote;
    00254
    00255                 ASSERT(currModelWeight >= 0.0);
    00256
    00257                 currModelWeight += vote;
    00258
    00259                 if (flag && currModelWeight >= dMinTotalModelVote)
    00260                         nModelsAboveMinVote++;
    00261
    00262                 ASSERT(currModelWeight <= 1.0);
    00263         }
    00264
    00265         void AddPartitionVotes(Partition& part, const DAGPtr ptrQueryDag, DAGDatabase& modelDB,
    00266                 const QueryRange& range, double dQueryNodeRelMass);
    00267
    00268         SmartArray<VOTE> GetRankedVotes() const;
    00269
    00270         ModelBins& operator=(const ModelBins& rhs)
    00271         {
    00272                 modelVotes = rhs.modelVotes;
    00273                 partBins = rhs.partBins;
    00274
    00275                 return *this;
    00276         }
    00277 };
    00278
    00284 DAGPtr ComputeOverlappingNodeGraph(const DAGPtr ptrQueryDag, const QueryRange& r);
    00285
    00289 PartitionArray FindPartitions(const DAGPtr ptrOverlapDag);
    00290
    00291 } // end namespace MOOVC
    00292
    00293 typedef SmartArray<MOOVC::VOTE> NNVoteArray;
    00294
    00298 NNVoteArray ComputeVotesForModelGraphs(const DAGPtr ptrQueryDag,
    00299         DAGDatabase& modelDB, const QueryRange& r, double dQueryNodeRelMass, double dMinSimilarity);
    00300
    00301 #endif