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

# VoteCounter.cpp

    00001
    00002 #include "VoteCounter.h"
    00003 #include <LEDA/node_array.h>
    00004 #include <LEDA/mwb_matching.h>
    00005 #include <LEDA/graph_alg.h>
    00006
    00007 #include "ShockGraph.h" // needed for ShowGraph()
    00008 #include "VisualDAG.h"  // needed for ShowGraph()
    00009
    00010 #define MAX_MODEL_NODE_COUNT 1024
    00011
    00012 using namespace MOOVC;
    00013
    00014 SmartArray<leda_node> PartitionBins::modelNodeMap(MAX_MODEL_NODE_COUNT);
    00015
    00020 bool QueryRange::DoPtsOverlap(const TSV pt1, const TSV pt2) const
    00021 {
    00022         ASSERT(GetSize() == pt1.GetSize());
    00023         ASSERT(GetSize() == pt2.GetSize());
    00024
    00025         double min1, max1, min2, max2;
    00026
    00027         for (int i = 0; i < GetSize(); i++)
    00028         {
    00029                 GetDimBounds(pt1[i], i, min1, max1);
    00030                 GetDimBounds(pt2[i], i, min2, max2);
    00031
    00032                 if (max1 < min2 || min1 > max2)
    00033                         return false;
    00034         }
    00035
    00036         return true;
    00037 }
    00038
    00039 void PartitionBins::CreateVoteGraph(LEDA_GRAPH<int, double>& g) const
    00040 {
    00041         leda_node q;
    00042         int queryNode, modelNode;
    00043         double weight;
    00044         leda_pq_item it;
    00045
    00046         ASSERT(g.empty());
    00047
    00048         // Init the map of model nodes
    00049         modelNodeMap.Set(nil);
    00050
    00051         // Add the model nodes and the edge weights to the graph of node votes
    00052         for (queryNode = 0; queryNode < GetNodeCount(); queryNode++)
    00053         {
    00054                 if (!bins[queryNode].empty())
    00055                 {
    00056                         // Add the query node to the graph of node votes
    00057                         q = g.new_node(queryNode);
    00058
    00059                         forall_items(it, bins[queryNode])
    00060                         {
    00061                                 modelNode = bins[queryNode].inf(it);
    00062                                 weight = bins[queryNode].prio(it);
    00063
    00064                                 if (modelNodeMap[modelNode] == nil)
    00065                                         modelNodeMap[modelNode] = g.new_node(modelNode);
    00066
    00067                                 g.new_edge(q, modelNodeMap[modelNode], weight);
    00068                         }
    00069                 }
    00070         }
    00071 }
    00072
    00073 double PartitionBins::CompPartitionVote() const
    00074 {
    00075         LEDA_GRAPH<int, double> g;
    00076         leda_edge e;
    00077         leda_list_item it;
    00078
    00079         // Quick test
    00080         if (GetCumulativeVote() == 0.0)
    00081                 return 0;
    00082
    00083         // Since there have been some votes, we must do work now...
    00084         CreateVoteGraph(g);
    00085
    00086         leda_edge_array<double> edgeCosts(g);
    00087
    00088         // Gather the weigths in an array and let the weights in the graph be equal to 1.
    00089         forall_edges(e, g)
    00090         {
    00091                 edgeCosts[e] = g.inf(e);
    00092                 g[e] = 1.0;
    00093         }
    00094
    00095         MWA_SCALE_WEIGHTS(g, edgeCosts);
    00096         leda_list<leda_edge> voteMapping = MAX_WEIGHT_BIPARTITE_MATCHING(g, edgeCosts);
    00097
    00098         double partitionVote = 0.0;
    00099
    00100         // Sum up the votes in the mapping
    00101         forall_items(it, voteMapping)
    00102         {
    00103                 partitionVote += edgeCosts[voteMapping[it]];
    00104                 //cerr << g.inf(source(voteMapping[it])) << "=>" << g.inf(target(voteMapping[it])) << endl;
    00105         }
    00106
    00107         ASSERT(partitionVote >= 0.0 && partitionVote <= 1.0);
    00108
    00109         return partitionVote;
    00110 }
    00111
    00112 void ModelBins::AddPartitionVotes(Partition& part, const DAGPtr ptrQueryDag, DAGDatabase& modelDB,
    00113         const QueryRange& range, double dQueryNodeRelMass)
    00114 {
    00115         VoteBalance balance(modelDB.GetMaxTSVDimension(), dQueryNodeRelMass);
    00116         SmartArray<DAGSearchRecordEx> closestModelNodes;
    00117         int idxNode, idxModel, i;
    00118         VOTE vote;
    00119         //QueryRange rangeCheck(range.GetDimDelta(), modelDB.GetMaxTSVDimension());
    00120
    00121         // Set size (and, implicitly, bounds) for each partition bin
    00122         for (idxModel = 0; idxModel < modelDB.GetDAGCount(); idxModel++)
    00123                 partBins[idxModel].SetPartitionSize(part.NodeCount());
    00124
    00125         // Do NN-search for each node in the partition
    00126         for (idxNode = 0; idxNode < part.NodeCount(); idxNode++)
    00127         {
    00128                 vote.queryNode = part[idxNode];
    00129                 balance.SetQueryNode(ptrQueryDag, vote.queryNode);
    00130
    00131                 closestModelNodes = modelDB.GetIndexDB().GetClosest(*ptrQueryDag, vote.queryNode, range.GetDimDelta());
    00132
    00133                 // Add each node's vote to the partition bin
    00134                 // of the corresponding model
    00135                 for (i = 0; i < closestModelNodes.GetSize(); i++)
    00136                 {
    00137                         const DAGSearchRecordEx& modelNodeInfo = closestModelNodes[i];
    00138                         //ASSERT(rangeCheck.DoPtsOverlap(balance.GetQueryNodeTSV(), modelNodeInfo.nodeTSV));
    00139
    00140                         if (vote.dWeight = balance.Weight(modelNodeInfo))
    00141                         {
    00142                         vote.nModelGraph = modelNodeInfo.id;
    00143                         vote.nModelNode = modelNodeInfo.node;
    00144
    00145                         partBins[vote.nModelGraph].AddVote(idxNode, vote);
    00146                    }
    00147                 }
    00148         }
    00149
    00150         // Add up the total vote for each model's partition
    00151         for (idxModel = 0; idxModel < modelDB.GetDAGCount(); idxModel++)
    00152                 AddVote(idxModel, partBins[idxModel].CompPartitionVote());
    00153 }
    00154
    00155 SmartArray<VOTE> ModelBins::GetRankedVotes() const
    00156 {
    00157         SmartArray<VOTE> sortedVotes(nModelsAboveMinVote);
    00158
    00159         for (int i = 0, j = 0; i < modelVotes.GetSize(); i++)
    00160         {
    00161                 if (modelVotes[i] >= dMinTotalModelVote)
    00162                 {
    00163                         VOTE& vote = sortedVotes[j++];
    00164
    00165                         vote.dWeight = modelVotes[i];
    00166                         vote.nModelGraph = i;
    00167                 }
    00168         }
    00169
    00170         sortedVotes.Sort(VOTE::Compare);
    00171
    00172         return sortedVotes;
    00173 }
    00174
    00184 DAGPtr MOOVC::ComputeOverlappingNodeGraph(const DAGPtr ptrQueryDag, const QueryRange& r)
    00185 {
    00186         leda_node u, v;
    00187
    00188         DAGPtr ptrDag = ptrQueryDag->CreateObject();
    00189
    00190         // Copy the graph info but not its nodes or edges. Simply do:
    00191         *ptrDag = *ptrQueryDag;
    00192         ptrDag->del_all_nodes(); //this will later re-index the nodes
    00193
    00194         // Create a graph with the nodes in the query graph. Note that
    00195         // leaf nodes don't vote, so we must not include them in the new graph
    00196         forall_nodes(u, *ptrQueryDag)
    00197                 if (ptrQueryDag->GetNodeMass(u) > 1)
    00198                         ptrDag->NewNode(ptrQueryDag->GetNode(u));
    00199
    00200         // We can speed up things a bit by computing all the TSVs with the right
    00201         // dimension only once.
    00202         SmartArray<TSV> tsvs(ptrDag->GetNodeCount());
    00203         int tsvdim = r.GetSize(), idxU, idxV;
    00204         TSV pt1, pt2;
    00205
    00206         forall_nodes(u, *ptrDag)
    00207                 tsvs[ptrDag->GetNodeIndex(u)] = ptrDag->GetNodeTSV(u, tsvdim);
    00208
    00209         // Find the edges of the overlap graph. Since the overlapping relation is symmetric,
    00210         // we only need to do N! comparisons.
    00211         for (u = ptrDag->first_node(); u != nil; u = ptrDag->succ_node(u))
    00212         {
    00213                 pt1 = tsvs[ptrDag->GetNodeIndex(u)];
    00214
    00215                 for (v = ptrDag->succ_node(u); v != nil; v = ptrDag->succ_node(v))
    00216                 {
    00217                         pt2 = tsvs[ptrDag->GetNodeIndex(v)];
    00218
    00219                         if (r.DoPtsOverlap(pt1, pt2))
    00220                                 ptrDag->NewEdge(u, v);
    00221                 }
    00222         }
    00223
    00224         //ShowGraph(*ptrDag);
    00225
    00226         return ptrDag;
    00227 }
    00228
    00229 PartitionArray MOOVC::FindPartitions(const DAGPtr ptrOverlapDag)
    00230 {
    00231         leda_node v;
    00232
    00233         // Solve the connected components problem
    00234         leda_node_array<int> compnum(*ptrOverlapDag);
    00235         int c = COMPONENTS(*ptrOverlapDag, compnum);
    00236
    00237         // Create the partitions
    00238         PartitionArray parts(ptrOverlapDag);
    00239         parts.SetSize(c);
    00240
    00241         forall_nodes(v, *ptrOverlapDag)
    00242                 parts.AddElement(compnum[v], v);
    00243
    00244         return parts;
    00245 }
    00246
    00247 NNVoteArray ComputeVotesForModelGraphs(const DAGPtr ptrQueryDag, DAGDatabase& modelDB,
    00248         const QueryRange& range, double dQueryNodeRelMass, double dMinSimilarity)
    00249 {
    00250           ModelBins modelBins(modelDB.GetDAGCount(), dMinSimilarity);
    00251           DAGPtr ptrOverlapGraph = ComputeOverlappingNodeGraph(ptrQueryDag, range);
    00252           PartitionArray partitions = FindPartitions(ptrOverlapGraph);
    00253
    00254           for (int i = 0; i < partitions.GetSize(); i++)
    00255                   modelBins.AddPartitionVotes(partitions[i], ptrOverlapGraph, modelDB, range, dQueryNodeRelMass);
    00256
    00257           return modelBins.GetRankedVotes();
    00258 }
    00259