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

# DAG.h

Go to the documentation of this 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