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

# DAG Class Reference

This class represents the DAG ADT. More...

`#include <DAG.h>`

Inheritance diagram for DAG:

List of all members.

## Public Types
enum | SF
| Possible similarity functions.
## Public Methods
virtual | ~DAG ()
| Necessary virtual destructor.
virtual DAG & | operator= (const DAG &rhs)
| Assignment operator for the DAG class. Must be overwritten in the derived classes.
virtual void | Clear ()
| It sets to zero all the DAG's member variables.
virtual double | NodeSimilarity (leda_node g1Node, const DAG &g2, leda_node g2Node) const
| Similarity function for two nodes.
virtual double | EigenDistance (leda_node g1Node, const DAG &g2, leda_node g2Node) const
| Eigen-value based distance function for two nodes.
virtual void | Print (ostream &os=cout) const
virtual istream & | Read (istream &is, bool bOnlyDataForMatching=false)
| Reads a DAG from the specified stream.
virtual ostream & | Write (ostream &os) const
| Writes the DAG to the specified stream.
virtual void | ComputeDerivedValues ()
| Compute all the derived values in the graph.
void | DeleteSubDAG (leda_node v)
| Deletes the subtree rooted at <v>.
double | ComputeTSVs (leda_node root)
double | ComputeTSVs (leda_node v, int &j, Matrix &adj, NodeIndexMap &loopyNodeMap)
void | AddEdge (Matrix &adj, leda_edge e, int sourceNodeLbl, int targetNodeLbl) const
| Create an edge between vertices and <j> of weight <dist>.
void | DelEdge (Matrix &adj, int sourceNodeLbl, int targetNodeLbl) const
| Delete and edge between vertices and <j>.
leda_node | GetFirstRootNode () const
| Returns the first root found in the DAG. i.e. the first node v that has indeg(v) = 0.
void | PrintTSVs (ostream &os=cout) const
| Prints the set of all TSVs in the graph.
double | NodeTSVSimilarity (leda_node u, const DAG &from, leda_node v) const
| Computes the TSV similarity between two nodes.
void | PrintAdjMatrix (ostream &os=cout)
| Prints the DAG's adjacency matrix.
DAGPtr | SplitSubGraph (leda_node v, bool bRecomputeTSVs=false)
leda_node | SplitSubGraph (leda_node v, DAGPtr &ptrDag)
int | ComputeNodesInfo (leda_node v, int nLevel, int nDFSIndex)
| Visits all the node in DFS order and computes they derived values from the info in the graph.
istream & | read (istream &is)
| Lower case version of Read().
ostream & | write (ostream &os) const
| Lower case version of Write().
## Static Public Methods
double | ComputeEigenSum (const Matrix &adj, int nVals)
| Computes eigen-sum over a given adjacency matrix.
double | Match (DAG &g1, DAG &g2, SimMatrix &simMat, DAGNodeMap &paired1, DAGNodeMap &paired2, MatchedNodePair *pMatchedPair=NULL)
| The main matching algorithm for various DAG's.
leda_edge | ComputeBipartiteGraph (LEDA_GRAPH< leda_node, double > &G, const DAG &g1, const DAG &g2, SimMatrix &simMat, const DAGNodeMap &paired1, const DAGNodeMap &paired2, MatchedNodePair *pMatchedPair=NULL)
| Static helper function for DAG::Match().
double | Similarity (const DAG &image, const DAG &model, DAGNodeMap &nodeMap, bool bRecomputeTSVs=false)
| Returns the similarity between two dags.
double | Distance (const DAG &image, const DAG &model, DAGNodeMap &nodeMap, bool bRecomputeTSVs=false)
| Returns the match distance between the two dags.

## Detailed Description

This class represents the DAG ADT.

DAG is an abstract class derived from the parameterized LEDA graph. This class can only be used by deriving a new class from it and overwriting its abstract functions.

The information contained in each node is a pointer to a DAGNode, which in turn is another abstract class. In order to handle the destruction of the objects referenced by these pointers, the class DAGNodePtr was created to keep track of the references to DAGNode's and delete them when no pointer points to them anymore.

The information in each edge is a 'double' that represents its weigth.

/see DAGNode and DAGNodePtr.

Definition at line 123 of file DAG.h.

## Member Function Documentation

leda_edge DAG::ComputeBipartiteGraph | ( | LEDA_GRAPH< leda_node, double > & | G,
|  | const DAG & | g1,
|  | const DAG & | g2,
|  | SimMatrix & | simMat,
|  | const DAGNodeMap & | paired1,
|  | const DAGNodeMap & | paired2,
|  | MatchedNodePair * | pMatchedPair = NULL
| ) | `[static]`

| Static helper function for DAG::Match(). It creates a bipartite graph between g1 and g2's nodes, as long as they weren't previously matched, in which edges are directed from a smaller to a larger set. It the solution to the max weight max card bipartite matching and returns the largest weight edge from the matching. Returns: largest weight edge from the MWMCB matching. Definition at line 463 of file DAG.cpp. References GetNode(), GetNodeDFSIndex(), GetNodeLbl(), GetNodeMass(), and nCumulativeMass. Referenced by Match().

void DAG::ComputeDerivedValues | ( |  | ) | `[virtual]`

| Compute all the derived values in the graph. The derived values are those which depend on other values and don't need to be saved. These values are in fact actually read and saved but only in order to improve computation performance. Reimplemented in ShockGraph. Definition at line 154 of file DAG.cpp. References ComputeNodesInfo(), ComputeTSVs(), and GetFirstRootNode(). Referenced by ShockGraph::ComputeDerivedValues().

double DAG::ComputeEigenSum | ( | const Matrix & | adj,
|  | int | nVals
| ) | `[static]`

| Computes eigen-sum over a given adjacency matrix. We are supposed to compute the $\delta(T_i) - 1$ largest absolute eigenvalues, where $\delta(T_i)$ is the degree of the root node of the tree $T_i$. The justification for summing the $\delta(T_i) - 1$ largest absolute eigenvalues follows: a) the largest absolute eigenvalues are the most informative of the subgraph structure. b) by summing $\delta(T_i) - 1$ elements we normalize the sum according to the local complexity of the subgraph root. According to the Overton and Womersley's Theorem, for the sum of the first k eigenvalues of a symmetric matrix A, the following semidefinite programming characterization holds: \[\lambda_1(A) + \hdots + \lamda_k(A) = max A \dot U s.t. trace(U) = k for 0 \le U \le I.\] However, for our particular case, we can't use this theorem because A is antisymmetric. Therefore, for this implementation, we compute the SVD to obtain the eigenvalues and then all the values are summed up, instead of only the $\delta(T_i) - 1$ largest ones. Todo: Find out the impact of summing all the eigenvalues instead of the $k$ largest ones.5s3l1 Definition at line 273 of file DAG.cpp. Referenced by ComputeTSVs().

int DAG::ComputeNodesInfo | ( | leda_node | v,
|  | int | nLevel,
|  | int | nDFSIndex
| ) |

| Visits all the node in DFS order and computes they derived values from the info in the graph. Returns: the last DFS index + 1. i.e. The corresponding next DFS index. Definition at line 80 of file DAG.cpp. Referenced by ComputeDerivedValues().

double DAG::ComputeTSVs | ( | leda_node | v,
|  | int & | j,
|  | Matrix & | adj,
|  | NodeIndexMap & | loopyNodeMap
| ) |

| step 1: for all adjacent nodes w of the given root node, if w has in-degree grater that 1 (multiple parents) and has already been visited, bHasLoopyChild is set to true so that a new adj matrix will be computed, in which v is the root and use it to compute v's TSV. Note that if j is the root of the matrix (i = j = 1), we don't care whether v has loopy children or not. Otherwise we would enter in an endless loop. step 2: add the edges to the adj matrix. Edges immediately below a loopy node must be added to the adj matrix, but those below them do not because they have already been added. step 3: compute v's eigen sum if necessary. Definition at line 361 of file DAG.cpp. References SmartArray< double >::Add(), AddEdge(), ComputeEigenSum(), ComputeTSVs(), SmartArray< double >::ReSize(), and TSV::Sort().

double DAG::ComputeTSVs | ( | leda_node | root | ) |

| Computes all the nodes' TSV's. Definition at line 335 of file DAG.cpp. Referenced by ComputeDerivedValues(), ComputeTSVs(), PrintAdjMatrix(), and SplitSubGraph().

void DAG::DeleteSubDAG | ( | leda_node | v | ) |

| Deletes the subtree rooted at <v>. Todo: This function does not support some kinds of DAGs. More specifically, DAGs with loops are not allowed. This must be fixed in the future. Definition at line 1149 of file DAG.cpp.

double DAG::Distance | ( | const DAG & | image,
|  | const DAG & | model,
|  | DAGNodeMap & | nodeMap,
|  | bool | bRecomputeTSVs = false
| ) | `[static]`

| Returns the match distance between the two dags. This function is simply the inverse of the Similarity function See also: Similarity Definition at line 837 of file DAG.cpp. References Similarity().

double DAG::Match | ( | DAG & | g1,
|  | DAG & | g2,
|  | SimMatrix & | simMat,
|  | DAGNodeMap & | paired1,
|  | DAGNodeMap & | paired2,
|  | MatchedNodePair * | pMatchedPair = NULL
| ) | `[static]`

| The main matching algorithm for various DAG's. It is a static function that receives two DAG's as input and computes a value representing their similarity, as well as a list of corresponding nodes in the two DAG's. Uses two node functions, <node_similarity> and <nodes_are_related>. See also: NodeSimilarity AreNodesRelated ComputeBipartiteGraph Definition at line 662 of file DAG.cpp. References ComputeBipartiteGraph(), GetNode(), GetNodeCount(), GetNodeDFSIndex(), DAGNode::SetSimilarity(), and SplitSubGraph(). Referenced by Similarity().

double DAG::NodeTSVSimilarity | ( | leda_node | u,
|  | const DAG & | from,
|  | leda_node | v
| ) | const

| Computes the TSV similarity between two nodes. The formula used is: \[ \fraq{|tsv_1 - tsv_2|}{\mbox{max} (|tsv_1|, (|tsv_2|)} \] If both terms are zero, the similarity returned is 1. If the numerator is grater than or equal to the numerator, the TSV similarity is 0. Definition at line 1117 of file DAG.cpp. References GetNodeTSV(), GetNodeTSVNorm(), and TSV::Norm2(). Referenced by NodeSimilarity().

void DAG::Print | ( | ostream & | os = cout | ) | const`[virtual]`

| Print out vertices, their labels and eigenlabels, and the adjacency structure of the graph. Reimplemented in GestureGraph, and ShockGraph. Definition at line 957 of file DAG.cpp. Referenced by ShockGraph::Print(), and GestureGraph::Print().

double DAG::Similarity | ( | const DAG & | query,
|  | const DAG & | model,
|  | DAGNodeMap & | nodeMap,
|  | bool | bRecomputeTSVs = false
| ) | `[static]`

| Returns the similarity between two dags. The similarity is computed by matching image's and model's nodes and then normalizing the number of matched nodes according to the order of the model graph. /see NodeSimilarity AreNodesRelated ComputeBipartiteGraph Match Definition at line 752 of file DAG.cpp. References CreateObject(), GetDAGLbl(), GetNodeCount(), GetNodeDFSIndex(), Match(), NodeSimilarity(), and SmartArray< SmartArray< T > >::Print(). Referenced by Distance().

leda_node DAG::SplitSubGraph | ( | leda_node | v,
|  | DAGPtr & | ptrDag
| ) |

| Recursive function called by SplitSubGraph(leda_node, bool). It recursively adds a subgraph to the graph pointed by <ptrDag> and then it deletes the subgraph from the original graph. Todo: The algorithm doesn't work well with DAG because it looses the multiple parents info of nodes in with more than one of their parents belong the the splitted subgraph. Since the TSVs of the subgraph are never recomputed, the missing edges won't affect the matching algorithm as it's currently implemented. Definition at line 218 of file DAG.cpp. References SplitSubGraph().

DAGPtr DAG::SplitSubGraph | ( | leda_node | v,
|  | bool | bRecomputeTSVs = false
| ) |

  | This function separates a subtree rooted at <v> and returs it in the <subg> parameter. The transitive clusere matrix and the cumulative mass of the entire graph is retained in both subgraphs. Parameters:
  v | root of the subtree.
  bRecomputeTSVs | controls whether the TSVs that remains in the original graph should be recomputed.
Definition at line 192 of file DAG.cpp. References ComputeTSVs(), and GetFirstRootNode(). Referenced by Match(), and SplitSubGraph().

The documentation for this class was generated from the following files:

- DAG.h
- DAG.cpp