DAG.h Source File

00001 
00052 #ifndef __DAG_H__
00053 #define __DAG_H__
00054 
00055 #include <fstream.h>
00056 #include <LEDA/d_array.h>
00057 #include <LEDA/graph_alg.h>
00058 
00059 #include "DAGNode.h"
00060 #include "String.h"
00061 
00063 //#define WANT_STREAM                  // include.h will get stream fns
00064 //#define WANT_MATH                    // include.h will get math fns
00065                                      // newmatap.h will get include.h
00066 
00067 #define _STANDARD_
00068 #define use_namespace 
00069 #include <newmatap.h>                // need matrix applications
00070 #include <newmatio.h>                // need matrix output routines
00071 
00072 #define Matrix NEWMAT::Matrix
00073 
00074 //#ifdef use_namespace
00075 //using namespace NEWMAT;              // access NEWMAT namespace
00076 //#endif
00077 //*************
00078 
00079 //using namespace LEDA;
00080 
00081 typedef leda_list<leda_edge> EdgeList;
00082 typedef leda_list<leda_node> NodeList;
00083 typedef leda_d_array<leda_node, leda_node> NodeMap;
00084 typedef leda_d_array<leda_edge, leda_node> EdgeNodeMap;
00085 typedef leda_d_array<leda_node, leda_list_item> NodeListItemMap;
00086 typedef leda_d_array<leda_node, int> NodeIndexMap;
00087 
00088 typedef leda_list<DAGNodePtr> DAGNodeList;
00089 typedef leda_d_array<DAGNodePtr, DAGNodePtr> DAGNodeMap;
00090 
00091 typedef SmartMatrix<double> SimMatrix;
00092 typedef SmartArray<int> NodeIdxArray;
00093 typedef SmartArray<NodeIdxArray> NodeIdxMatrix;
00094 
00095 typedef LEDA_GRAPH<DAGNodePtr, double> DAG_BASE_CLASS;
00096 
00097 class DistMeasurer;
00098 class MatchedNodePair;
00099 class DAG;
00100 
00102 typedef SmartPtr<DAG> DAGPtr;
00103 
00104 
00123 class DAG : public DAG_BASE_CLASS
00124 {
00125 public:
00127     enum SF {EXP_NEG_SUM, INV_NODE_DIST, INV_NODE_DIST_AND_TSV, ID_NODE_DIST};
00128         typedef double distance_type;
00129 
00130         struct MatchParams
00131         {
00132                 SF nSimFuncType;                        
00133         int nNodeDistFunc;                      
00134         double dTSVSimWeight;           
00135         double dSimilMassWeight;        
00136         double dRelMassWeight;          
00137         double dMinNodeSim;                     
00138         double dBreakSibRelPen;         
00139                 int nPreserveAncestorRel;       
00140 
00141                 //Indexing params
00142                 int nUseNewVoteWeightFunc;      
00143                 int nUseMOOVC;                          
00144 
00145                 MatchParams();
00146                 void Print(ostream& os) const;
00147         };
00148 
00149 private:
00150         String strGraphLbl;                             
00151         int nFileOffset;                                
00152         int nDAGId;                                             
00153         int nCumulativeMass;                    
00154 
00155         // Derived values
00156         int nMaxBFactor;                                
00157         double dTotalTSVSum;                    
00158         TSV eigenVals;                                  
00159         SmartMatrix<int> transClosMat;  
00160 
00161 protected:
00162         int nViewNumber;
00163         String strObjectName;
00164 
00165         DistMeasurer* pDistMeasurer;
00166 
00167         static MatchParams s_matchParams;
00168         static bool s_bDbgMode;
00169 
00170 protected:
00171         TSV& GetNodeTSV(leda_node v)                            { return operator[](v)->GetTSV(); }
00172         const TSV&      GetNodeTSV(leda_node v) const   { return inf(v)->GetTSV(); }
00173         void SetEigenVals(const Matrix& adj);
00174 
00175 public:
00176 // Virtual functions:
00177         virtual ~DAG() { }      
00178         virtual DAG& operator=(const DAG& rhs);
00179         virtual void Clear();
00180         virtual double NodeSimilarity(leda_node g1Node, const DAG& g2, leda_node g2Node) const;
00181         virtual double  EigenDistance(leda_node g1Node, const DAG& g2, leda_node g2Node) const;
00182         virtual void Print(ostream& os = cout) const;
00183         virtual istream& Read(istream& is, bool bOnlyDataForMatching = false);
00184         virtual ostream& Write(ostream& os) const;
00185         virtual void ComputeDerivedValues();
00186 
00187 // Pure virtual functions:
00188         virtual double NodeDistance(leda_node g1Node, const DAG& g2, leda_node g2Node) const = 0;
00189         virtual bool AreNodesRelated(leda_node g1Node, const DAG& g2, leda_node g2Node) const = 0;
00190         virtual DAG* CreateObject() const = 0;
00191         virtual DAGNodePtr CreateNodeObject(NODE_LABEL lbl) const = 0;
00192         virtual DAGNodePtr ReadNode(istream& is) const = 0;
00193         virtual String ClassName() const = 0;
00194         virtual int NodeType(leda_node v) const = 0;
00195 
00196 #ifdef XML_READING
00197         virtual bool ReadFromXMLFile(const char* szFileName, bool bCompEigenLbl = true) = 0;
00198 #endif //XML_READING
00199 
00200 // Inline functions:
00201         DAG ()                                                                                  { Clear(); pDistMeasurer = NULL;}
00202         leda_node   NewNode(DAGNodePtr ptr)                             { return DAG_BASE_CLASS::new_node(ptr); }
00203         leda_edge   NewEdge(leda_node u, leda_node v, double dVal = 1.0)                                
00204                                                                                                         { return DAG_BASE_CLASS::new_edge(u, v, dVal); }
00205         void            DelEdge(leda_edge e)                            { del_edge(e); }
00206         int                     GetNodeCount() const                            { return number_of_nodes(); }
00207         int                     GetEdgeCount() const                            { return number_of_edges(); }
00208         double          GetEdgeWeight(leda_edge e) const        { return inf(e); }
00209         NODE_LABEL      GetNodeLbl(leda_node v) const           { return inf(v)->GetNodeLbl(); }
00210         double          GetEigenLbl(leda_node v) const          { return inf(v)->GetEigenLbl(); }
00211 
00212         TSV             GetNodeTSV(leda_node v, int nDim) const { return inf(v)->GetTSV(nDim); }
00213         double  GetNodeTSVNorm(leda_node v) const               { return inf(v)->GetTSVNorm(); }
00214 
00215         const DAGNodePtr GetNode(leda_node v) const             { return inf(v); }
00216         DAGNodePtr&              GetNode(leda_node v)                   { return operator[](v); }
00217         leda_node GetNode(int nIndex);
00218 
00219         void SetNodeLbl(leda_node v, NODE_LABEL lbl)    { operator[](v)->SetNodeLbl(lbl); }
00220         void SetEigenLbl(leda_node v, double lbl)               { operator[](v)->SetEigenLbl(lbl); }
00221 
00222         int GetNodeIndex(leda_node v) const                             { return index(v); }
00223 
00224         String GetDAGLbl()      const                                           { return strGraphLbl; }
00225         void SetDAGLbl(const char* szLbl)                               { strGraphLbl = szLbl; }
00226 
00227         int GetDAGId() const                                                    { return nDAGId; }
00228         void SetDAGId(int nId)                                                  { nDAGId = nId; }
00229 
00230         int GetFileOffset()     const                                           { return nFileOffset; }
00231         
00232         int GetMaxTSVDimension() const                                  { return nMaxBFactor + 1; }
00233         double GetTotalTSVSum() const                                   { return dTotalTSVSum; }
00234         int GetViewNumber() const                                               { return nViewNumber; }
00235         const String& GetObjName() const                                { return strObjectName; }
00236         
00237         void SetViewNumber(int n)                                               { nViewNumber = n; }
00238         void SetObjName(char *str)                                              { strObjectName = str; }
00239 
00240         int GetNodeMass(leda_node v) const                              { return GetNode(v)->GetMass(); }
00241         int GetNodeLevel(leda_node v) const                     { return GetNode(v)->GetLevel(); }
00242         int GetNodeDFSIndex(leda_node v) const                  { return GetNode(v)->GetDFSIndex(); }
00243         bool IsNodeVisited(leda_node v) const                   { return GetNode(v)->Visited(); }
00244 
00245         leda_node GetFirstParent(leda_node v) const { return source(first_in_edge(v)); }
00246         leda_node GetSecondParent(leda_node v) const { return source(in_succ(first_in_edge(v))); }
00247 
00248         leda_node GetFirstChild(leda_node v) const { return target(first_adj_edge(v)); }
00249         leda_node GetSecondChild(leda_node v) const { return target(adj_succ(first_adj_edge(v))); }
00250 
00251         double Similarity(const DAG& model, DAGNodeMap& nodeMap, bool bRecomputeTSVs = false) const
00252         {
00253                 return DAG::Similarity(*this, model, nodeMap, bRecomputeTSVs);
00254         }
00255 
00256         void DeleteSubDAG(leda_node v);
00257 
00258         double ComputeTSVs(leda_node root);
00259         double ComputeTSVs(leda_node v, int& j, Matrix& adj, NodeIndexMap& loopyNodeMap);
00260         //double ComputeTSVs(leda_node v, Matrix& adj);
00261         int AddTreeToMatrix(leda_node r, int i, Matrix& adj);
00262 
00263 // Static functions:
00264         static void SetMatchParams(const MatchParams& matchParams)      { s_matchParams = matchParams; }
00265 
00266         static double ComputeEigenSum(const Matrix& adj, int nVals);
00267         static double ComputeLaplacian(const Matrix& adj);
00268         static void ComputeHeights(const Matrix& adj, Matrix& m);
00269 
00270         static double Match(DAG& g1, DAG& g2, SimMatrix& simMat,
00271                 DAGNodeMap& paired1, DAGNodeMap& paired2, MatchedNodePair* pMatchedPair = NULL);
00272 
00273         static leda_edge ComputeBipartiteGraph(LEDA_GRAPH<leda_node, double>& G, 
00274                 const DAG& g1, const DAG& g2, SimMatrix& simMat,
00275                 const DAGNodeMap& paired1, const DAGNodeMap& paired2, 
00276                 MatchedNodePair* pMatchedPair = NULL);
00277         
00278         static double Similarity(const DAG& image, const DAG& model, 
00279                 DAGNodeMap& nodeMap, bool bRecomputeTSVs = false);
00280 
00281         static double Distance(const DAG& image, const DAG& model, 
00282                 DAGNodeMap& nodeMap, bool bRecomputeTSVs = false);
00283 
00284 
00285 // Non-virtual const functions:
00286         void AddEdge(Matrix& adj, leda_edge e, int sourceNodeLbl, int targetNodeLbl) const;
00287         void DelEdge(Matrix& adj, int sourceNodeLbl, int targetNodeLbl) const;
00288         leda_node GetFirstRootNode() const;
00289         leda_node GetRoot() const { return GetFirstRootNode(); }
00290         void PrintTSVs(ostream& os = cout) const;
00291         double NodeTSVSimilarity(leda_node u, const DAG& from, leda_node v) const;
00292         void PrintAdjMatrix(ostream& os = cout);
00293         leda_node DFSGetNext(leda_node v, EdgeList& l, bool bVisitNode = true) const;
00294         leda_node BFSGetNext(leda_node v, EdgeList& l, bool bVisitNode = true) const;
00295 
00296         const SmartMatrix<int>& GetTransClosMat() const { return transClosMat; }
00297 
00298 // Non-virtual non-const functions:
00299         DAGPtr SplitSubGraph(leda_node v, bool bRecomputeTSVs = false);
00300         leda_node SplitSubGraph(leda_node v, DAGPtr& ptrDag);
00301         void ComputeTransiveClosure();
00302         int ComputeNodesInfo(leda_node v, int nLevel, int nDFSIndex);
00303         void ResetNodesInfo();
00304         void ComputeNodesMass();
00305 
00306         friend ostream& operator<<(ostream &os, const DAG& dag) { return dag.Write(os); }
00307         friend istream& operator>>(istream &is, DAG& dag)               { return dag.Read(is); }
00308 
00310         istream& read(istream& is) { return Read(is); }
00311 
00313         ostream& write(ostream& os) const { return Write(os); }
00314 
00315 private:
00317         leda_node new_node(DAGNodePtr ptr = (DAGNode*)NULL)                             { return NewNode(ptr); }
00318 
00320         leda_edge new_edge(leda_node u, leda_node v, double dVal = 0.0) { return NewEdge(u, v, dVal); }
00321 
00322 public:
00323         static void EnterDbgMode() { s_bDbgMode = true; }
00324         static void LeaveDbgMode() { s_bDbgMode = false; }
00325         static bool IsDbgMode() { return s_bDbgMode; }
00326         static const MatchParams& GetMatchParams() { return s_matchParams; }
00327 };
00328 
00331 class DistMeasurer
00332 {
00333 protected:
00334         virtual double CompDistance() const = 0;
00335 
00336 public:
00337         virtual ~DistMeasurer() {}
00338 
00339         virtual double GetDistance(const DAG& dag1, leda_node u, 
00340                 const DAG& dag2, leda_node v) = 0;
00341 };
00342 
00346 template <class G, class V> class DistMeasurerT : public DistMeasurer
00347 {
00348  protected:
00349          const G* pG1, *pG2;
00350          const V* pNode1, *pNode2;
00351          leda_node v1, v2;
00352          
00353  public:
00354          DistMeasurerT()
00355          {
00356                  pG1 = NULL;
00357                  pG2 = NULL;
00358                  pNode1 = NULL;
00359                  pNode2 = NULL;
00360                  v1 = nil;
00361                  v2 = nil;
00362          }
00363          
00364          double GetDistance(const DAG& dag1, leda_node u, const DAG& dag2, leda_node v)
00365          {
00366                  pG1 = dynamic_cast<const G*>(&dag1);
00367                  pG2 = dynamic_cast<const G*>(&dag2);
00368                  pNode1 = dynamic_cast<const V*>((const DAGNode*) dag1.GetNode(u));
00369                  pNode2 = dynamic_cast<const V*>((const DAGNode*) dag2.GetNode(v));
00370                  
00371                  ASSERT(pG1 && pG2 && pNode1 && pNode2);
00372                  
00373                  v1 = u;
00374                  v2 = v;
00375                  
00376                  return CompDistance();
00377          }
00378 };
00379 
00380 class MatchedNodePair
00381 {
00382         int q, m; //<! indices of query and model nodes that were just matched
00383         
00384         const SmartMatrix<int>* pQueryTCM; //<! TCM for query
00385         const SmartMatrix<int>* pModelTCM; //<! TCM for model
00386         
00387         NodeIdxMatrix qparents, mparents;       //<! Adjacency matrix for query and model
00388         const DAG* pMG;
00389 
00390 private:
00391         static bool IsAnsestor(int u, int v, const SmartMatrix<int>& tcm)
00392         {
00393                 return tcm[u][v] != 0;
00394         }
00395 
00396         static bool IsSibling(int u, int v, const SmartMatrix<int>& tcm, const NodeIdxMatrix& parents)
00397         {
00398                 const NodeIdxArray& vpar = parents[v];
00399 
00400                 for (int i = 0; i < vpar.GetSize(); i++)
00401                         if (IsAnsestor(vpar[i], u, tcm))
00402                                 return true;
00403 
00404                 return false;
00405         }
00406         
00407         static NodeIdxArray GetSiblingsVector(int v, const SmartMatrix<int>& tcm, const NodeIdxMatrix& parents);
00408 
00409 public:
00410         MatchedNodePair(const DAG& query, const DAG& model)
00411         {       
00412                 pQueryTCM = &query.GetTransClosMat();
00413                 pModelTCM = &model.GetTransClosMat();
00414                 SetParents(query, qparents);
00415                 SetParents(model, mparents);
00416                 SetEmpty();
00417                 pMG = &model;
00418         }
00419         
00420         void SetEmpty() { q = m = -1; }
00421         bool IsEmpty() const { return q == -1 && m == -1; }
00422         
00423         void SetNodes(int v1, int v2)
00424         {
00425                 q = v1;
00426                 m = v2;
00427         }
00428         
00435         void SetParents(const DAG& g, NodeIdxMatrix& parents)
00436         {
00437                 leda_node v;
00438                 leda_edge e;
00439                 int i, j;
00440                 
00441                 parents.ReSize(g.GetNodeCount());
00442                 
00443                 forall_nodes(v, g)
00444                 {
00445                         i = g.GetNodeDFSIndex(v);
00446                         ASSERT(parents[i].GetSize() == 0);
00447                         parents[i].ReSize(g.indeg(v));
00448                         
00449                         j = 0;
00450                         forall_in_edges(e, v)
00451                                 parents[i][j++] = g.GetNodeDFSIndex(g.source(e));
00452                 }
00453         }
00454         
00455         int GetQueryNode() const { return q; }
00456         int GetModelNode() const { return m; }
00457 
00458         bool AnsestorRelPreserved(int qq, int mm) const
00459         {
00460                 bool aq = IsAnsestor(qq, q, *pQueryTCM), am = IsAnsestor(mm, m, *pModelTCM);
00461                 return (aq && am) || (!aq && !am);
00462         }
00463 
00464         bool SiblingRelPreserved(int qq, int mm) const
00465         {
00466                 bool sq = IsSibling(qq, q, *pQueryTCM, qparents), sm = IsSibling(mm, m, *pModelTCM, mparents);
00467                 return  (sq && sm) || (!sq && !sm);
00468         }
00469         
00470         void UpdateSimMat(SimMatrix& simMat, const double& alpha) const;
00471 };
00472 
00473 enum METHOD {MWMC, MW};
00474 
00475 class SimilarityGraph : public LEDA_GRAPH<leda_node, double>
00476 {
00477         NodeMap g1Map, g2Map;
00478         EdgeNodeMap g1MatchedNodeMap, g2MatchedNodeMap;
00479         const DAG* pG1, *pG2;
00480 
00481 public:
00482         SimilarityGraph(const DAG& g1, const DAG& g2)
00483         {
00484                 pG1 = &g1;
00485                 pG2 = &g2;
00486         }
00487 
00488         leda_node MapNode(NodeMap& map, leda_node v)
00489         {
00490                 if (!map.defined(v))
00491                         return map[v] = new_node(v);
00492                 else
00493                         return map[v];
00494         }
00495 
00496         bool IsG1NodeMapped(leda_node v) const
00497         {
00498                 return g1Map.defined(v);
00499         }
00500 
00501         bool IsG2NodeMapped(leda_node v) const
00502         {
00503                 return g2Map.defined(v);
00504         }
00505 
00506         void Add(leda_node g1Node, leda_node g2Node, double dSimilarity, 
00507                 leda_node g1MatchedNode, leda_node g2MatchedNode);
00508 
00509         void Add(leda_node g1Node, leda_node g2Node, double dSimilarity);
00510 
00511         void MergeG2Nodes(leda_node remNode, leda_node delNode);
00512 
00513         double ComputeBestAssignment(METHOD nMethod, int* pnMatched, NodeMap* pNodeMap = NULL);
00514 };
00515 
00516 #endif //__DAG_H__
00517