00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #ifndef TREE_H
00021 #define TREE_H
00022
00023 #include <GTL/graph.h>
00024
00025 #include <Graph.h>
00026 #include <NodeWeight.h>
00027
00028 #define MAX(X,Y) (X) > (Y) ? : (X) : (Y)
00029 #define MIN(X,Y) (X) < (Y) ? : (X) : (Y)
00030 #define GAMMA(p, q) fabs(p-q)
00031 #define GAMMA1(p, q) (fabs(p-q))>(1e-6) ? 1.0 : 0.0
00032
00040 class Tree : public Graph<NodeWeight>
00041 {
00042 public:
00043 Tree() ;
00044 Tree( const Tree& t ) ;
00045 bool operator == ( const Tree& t ) ;
00046 ~Tree() ;
00047
00048 bool isTree() ;
00049
00050 Node getRoot() const ;
00051 Node getNode( int externalId ) const ;
00052 NodeWeight getNodeInf( int externalId ) const ;
00053
00054 void postOrder() ;
00055 void postOrderRay() ;
00056 void postOrderComplete() ;
00057
00058 double insertSubtreeCost( Node n ) const ;
00059 double deleteSubtreeCost( Node n ) const ;
00060
00062 static bool areSubtreesEqual( const Tree& t1, Node n1, const Tree& t2, Node n2 ) ;
00063 static double swapSubtrees( const Tree& t1, Node n11, Node n12, const Tree& t2, Node n21, Node n22 ) ;
00064 static double distance( const Tree& t1, const Tree& t2 ) ;
00065 static void print( const Tree& t, ostream& os ) ;
00066
00067 protected:
00068 virtual void save_graph_info_handler( ostream* os ) const ;
00069 virtual void save_node_info_handler( ostream* os, node n ) const ;
00070
00071 virtual void load_graph_info_handler( GML_pair* list_graph ) ;
00072 virtual void load_node_info_handler( node n, GML_pair* list_node ) ;
00073
00074 private:
00075 void postOrder( Node n, int& counter, bool makeKeyroot ) ;
00076 void postOrderRay( Node n, int& counter, bool makeKeyroot ) ;
00077 void postOrderComplete( Node n, int& counter, bool makeKeyroot ) ;
00078 void insertSubtreeCost( Node n, double& cost ) const ;
00079
00080
00081 private:
00082 bool tree ;
00083 };
00084
00085 #endif