Tree.h

Go to the documentation of this file.
00001 /***************************************************************************
00002  *   Copyright (C) 2007 by Universidad Nacional de Colombia                *
00003  *   http://www.unal.edu.co                                                *
00004  *                                                                         *
00005  *   This program is free software; you can redistribute it and/or modify  *
00006  *   it under the terms of the GNU General Public License as published by  *
00007  *   the Free Software Foundation; either version 2 of the License, or     *
00008  *   (at your option) any later version.                                   *
00009  *                                                                         *
00010  *   This program is distributed in the hope that it will be useful,       *
00011  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
00012  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
00013  *   GNU General Public License for more details.                          *
00014  *                                                                         *
00015  *   You should have received a copy of the GNU General Public License     *
00016  *   along with this program; if not, write to the                         *
00017  *   Free Software Foundation, Inc.,                                       *
00018  *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
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 //              friend ostream& operator << ( ostream& os, const Tree& e ) ;
00080                 
00081         private:
00082                 bool tree ;
00083 };
00084 
00085 #endif

Generated on Mon May 26 20:29:46 2008 for TARIS by  doxygen 1.5.4