00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #include "Tree.h"
00021
00022 #include <TarisApplication.h>
00023
00024 #include <algorithm>
00025 #include <iomanip>
00026 using namespace std ;
00027
00028 Tree::Tree():
00029 Graph<NodeWeight>()
00030 {
00031 tree = true ;
00032 }
00033
00034 Tree::Tree( const Tree& t )
00035 {
00036 this->tree = true ;
00037 this->copy( t ) ;
00038 }
00039
00040 bool Tree::operator == ( const Tree& t ){
00041 return areSubtreesEqual( *this, this->getRoot(), t, t.getRoot() ) ;
00042 }
00043
00044 Tree::~Tree()
00045 {
00046 }
00047
00048 bool Tree::isTree()
00049 {
00050 return tree ;
00051 }
00052
00053 Node Tree::getRoot() const
00054 {
00055 Node root ;
00056
00057
00058 for( Tree::node_iterator it = this->nodes_begin(); it != this->nodes_end(); it++ ){
00059 if( this->inf(*it).isRoot() ){
00060 root = *it ;
00061 }
00062 }
00063
00064 return root ;
00065 }
00066
00072 Node Tree::getNode( int externalId ) const
00073 {
00074 Node n ;
00075
00076
00077 for( Tree::node_iterator it = this->nodes_begin(); it != this->nodes_end(); it++ ){
00078 if( this->inf(*it).getExternalId() == externalId ){
00079 n = *it ;
00080 }
00081 }
00082
00083 return n ;
00084 }
00085
00086 NodeWeight Tree::getNodeInf( int externalId ) const
00087 {
00088 return this->inf( this->getNode( externalId ) ) ;
00089 }
00090
00091
00092 void Tree::postOrderRay()
00093 {
00094 Node root ;
00095
00096
00097 for( Tree::node_iterator it = this->nodes_begin(); it != this->nodes_end(); it++ ){
00098 if( this->inf(*it).isRoot() ){
00099 root = *it ;
00100 }
00101 }
00102
00103 int counter = 1 ;
00104 postOrderRay( root, counter, true ) ;
00105 }
00106
00107
00114 double Tree::insertSubtreeCost( Node n ) const {
00115 double cost = 0.0 ;
00116
00117 insertSubtreeCost( n, cost ) ;
00118
00119 return cost ;
00120 }
00121
00127 double Tree::deleteSubtreeCost( Node n ) const {
00128
00129
00130 double cost = 0.0 ;
00131
00132 insertSubtreeCost( n, cost ) ;
00133
00134 return cost ;
00135
00136
00137 }
00138
00146 bool Tree::areSubtreesEqual( const Tree& t1, Node n1, const Tree& t2, Node n2 )
00147 {
00148 if( n1 == node() ){
00149
00150 if( TarisApplication::Instance()->getDebugLevel() >= 2 ){
00152 cerr << "Warning from: bool Tree::equalTrees( Node n1, const Tree& t2, Node n2 )" << endl ;
00153 cerr << "\tNodo " ;
00154 cerr << "[" << t1.inf( n1 ).getExternalId() << "] ";
00155 cerr << "del arbol 1 invalido" << endl ;
00156 }
00157
00158 return false ;
00159
00160 }else if( n2 == node() ){
00161
00162 if( TarisApplication::Instance()->getDebugLevel() >= 2 ){
00163 cerr << "Warning from: bool Tree::equalTrees( Node n1, const Tree& t2, Node n2 )" << endl ;
00164 cerr << "\tNodo " ;
00165 cerr << "[" << t2.inf( n2 ).getExternalId() << "] ";
00166 cerr << "del arbol 2 invalido" << endl ;
00167 }
00168
00169 return false ;
00170
00171 }else if( fabs( t1.inf( n1 ).getWeightValue() - t2.inf( n2 ).getWeightValue() ) > TarisApplication::Instance()->getDoubleThresholdComparison() ){
00172
00173 if( TarisApplication::Instance()->getDebugLevel() >= 2 ){
00174 cerr << "Warning from: bool Tree::equalTrees( Node n1, const Tree& t2, Node n2 )" << endl ;
00175 cerr << "\tDistintos valores de pesos para los nodos: " ;
00176 cerr << "[" << t1.inf( n1 ).getExternalId() << "]";
00177 cerr << ", " ;
00178 cerr << "[" << t2.inf( n2 ).getExternalId() << "]" << endl ;
00179 cerr << "Valor de la diferencia = " << fabs( t1.inf( n1 ).getWeightValue() - t2.inf( n2 ).getWeightValue() ) << endl ;
00180 }
00181
00182 return false ;
00183
00184 }else if( n1.indeg() != n2.indeg() ){
00185
00186 if( TarisApplication::Instance()->getDebugLevel() >= 2 ){
00187 cerr << "Warning from: bool Tree::equalTrees( Node n1, const Tree& t2, Node n2 )" << endl ;
00188 cerr << "\tDistinto numero de hijos para los nodos: " ;
00189 cerr << "[" << t1.inf( n1 ).getExternalId() << "]";
00190 cerr << ", " ;
00191 cerr << "[" << t2.inf( n2 ).getExternalId() << "]" << endl ;
00192 }
00193
00194 return false ;
00195
00196 }else{
00197 map<int, Node> children1 ;
00198 map<int, Node> children2 ;
00199
00200 for( node::in_edges_iterator it1 = n1.in_edges_begin(); it1 != n1.in_edges_end() ; it1++ ){
00201 children1[ t1.inf( it1->opposite( n1 ) ).getExternalId() ] = it1->opposite( n1 ) ;
00202 }
00203
00204 for( node::in_edges_iterator it2 = n2.in_edges_begin(); it2 != n2.in_edges_end() ; it2++ ){
00205 children2[ t2.inf( it2->opposite( n2 ) ).getExternalId() ] = it2->opposite( n2 ) ;
00206 }
00207
00208 map<int, Node>::iterator it1 = children1.begin() ;
00209 map<int, Node>::iterator it2 = children2.begin() ;
00210
00211 if( children1.size() > 0 && children2.size() > 0 ){
00212
00213 for( ; it1 != children1.end() || it2 != children2.end() ; it1++, it2++ ){
00214
00215 if( !areSubtreesEqual( t1, children1[ it1->first ], t2, children2[ it2->first ] ) ){
00216
00217 return false ;
00218
00219 }
00220
00221 }
00222
00223 }
00224
00225 return true ;
00226
00227 }
00228 }
00229
00238 double Tree::swapSubtrees( const Tree& t1, Node n11, Node n12, const Tree& t2, Node n21, Node n22 )
00239 {
00241 if( n11 == node() ){
00242
00243 if( TarisApplication::Instance()->getDebugLevel() >= 2 ){
00244 cerr << "Warning from: double Tree::swapSubtrees( const Tree& t1, Node n11, Node n12, const Tree& t2, Node n21, Node n22 )" << endl ;
00245 cerr << "\tNodo " ;
00246 cerr << "[" << t1.inf( n11 ).getExternalId() << "] ";
00247 cerr << "del arbol 1 invalido" << endl ;
00248 }
00249
00250 return INFINITY ;
00251
00252 }else if( n12 == node() ){
00253
00254 if( TarisApplication::Instance()->getDebugLevel() >= 2 ){
00255 cerr << "Warning from: double Tree::swapSubtrees( const Tree& t1, Node n11, Node n12, const Tree& t2, Node n21, Node n22 )" << endl ;
00256 cerr << "\tNodo " ;
00257 cerr << "[" << t1.inf( n12 ).getExternalId() << "] ";
00258 cerr << "del arbol 1 invalido" << endl ;
00259 }
00260
00261 return INFINITY ;
00262
00263 }else if( n21 == node() ){
00264
00265 if( TarisApplication::Instance()->getDebugLevel() >= 2 ){
00266 cerr << "Warning from: double Tree::swapSubtrees( const Tree& t1, Node n11, Node n12, const Tree& t2, Node n21, Node n22 )" << endl ;
00267 cerr << "\tNodo " ;
00268 cerr << "[" << t2.inf( n21 ).getExternalId() << "] ";
00269 cerr << "del arbol 2 invalido" << endl ;
00270 }
00271
00272 return INFINITY ;
00273
00274 }else if( n22 == node() ){
00275
00276 if( TarisApplication::Instance()->getDebugLevel() >= 2 ){
00277 cerr << "Warning from: double Tree::swapSubtrees( const Tree& t1, Node n11, Node n12, const Tree& t2, Node n21, Node n22 )" << endl ;
00278 cerr << "\tNodo " ;
00279 cerr << "[" << t2.inf( n22 ).getExternalId() << "] ";
00280 cerr << "del arbol 2 invalido" << endl ;
00281 }
00282
00283 return INFINITY ;
00284
00285
00286 }else if( ( n11.outdeg() == 1 ) && ( n21.outdeg() == 1 ) && areSubtreesEqual( t1, n11, t2, n22 ) && areSubtreesEqual( t1, n12, t2, n21 ) ){
00287
00288 return 0.0 ;
00289
00290 }else{
00291
00292 return INFINITY ;
00293
00294 }
00295 }
00296
00305 void Tree::postOrderRay( Node n, int& counter, bool makeKeyroot )
00306 {
00307
00308 vector<double> childrenOrder ;
00309 map<double, Node> children ;
00310
00311 NodeWeight weight = this->inf( n ) ;
00312 weight.setLeftmost( counter ) ;
00313 weight.setKeyroot( makeKeyroot ) ;
00314
00315
00316 for( Node::in_edges_iterator it1 = n.in_edges_begin(); it1 != n.in_edges_end(); it1++ ){
00317
00318
00319 double order = -(this->inf( it1->opposite( n ) ).getDeepestNoNodes() + 1 ) ;
00320 int i = 1 ;
00321
00322 if(childrenOrder.size() != 0){
00323
00324 for( vector<double>::iterator it2 = childrenOrder.begin(); it2 != childrenOrder.end(); it2++){
00325 if( *it2 == order ){
00326 order = order + i*1e-6 ;
00327 i++ ;
00328 }
00329
00330 }
00331 }
00332
00333 childrenOrder.push_back( order) ;
00334 children[ order ] = it1->opposite( n ) ;
00335
00336 }
00337
00338 if( childrenOrder.size() != 0 ){
00339
00340 sort( childrenOrder.begin(), childrenOrder.end() ) ;
00341
00342 for( vector<double>::iterator it = childrenOrder.begin(); it != childrenOrder.end(); it++ ){
00343 postOrderRay( children[*it], counter, ( it != childrenOrder.begin() ) ) ;
00344
00345 }
00346 }
00347
00348 weight.setExternalId( counter ) ;
00349
00350 this->assign( n, weight ) ;
00351 counter++ ;
00352 }
00353
00354
00355 void Tree::insertSubtreeCost( Node n, double& cost ) const
00356 {
00357 map<double, Node> children ;
00358
00359 double weight = this->inf( n ).getWeightValue() ;
00360
00361 cost += weight ;
00362
00363 for( Node::in_edges_iterator it = n.in_edges_begin(); it != n.in_edges_end(); it++ ){
00364
00365 Node child = it->opposite( n ) ;
00366
00367 insertSubtreeCost( child, cost ) ;
00368
00369 }
00370 }
00371
00372 double Tree::distance( const Tree& t1, const Tree& t2 )
00373 {
00374 double** forestDistance = new double*[ t1.number_of_nodes() + 1 ];
00375 for (int i = 0; i <= t1.number_of_nodes(); i++){
00376 forestDistance[i] = new double[ t2.number_of_nodes() + 1 ] ;
00377 }
00378
00379 double** distance = new double*[ t1.number_of_nodes() ];
00380 for (int i = 0; i< t1.number_of_nodes(); i++){
00381 distance[i] = new double[ t2.number_of_nodes() ] ;
00382 }
00383
00384 for (int i = 0; i <= t1.number_of_nodes(); i++){
00385 for (int j = 0; j <= t2.number_of_nodes(); j++){
00386 forestDistance[i][j] = INFINITY ;
00387 }
00388 }
00389
00390 distance[ t1.number_of_nodes() - 1 ][ t2.number_of_nodes() - 1 ] = 0.0 ;
00391
00392 for (int x = 1; x <= t1.number_of_nodes(); x++){
00393
00394 if( t1.getNodeInf( x ).isKeyroot() ){
00395
00396 for (int y = 1; y <= t2.number_of_nodes(); y++){
00397
00398 if( t2.getNodeInf( y ).isKeyroot() ){
00399
00400 forestDistance[ t1.getNodeInf(x).getLeftmost() - 1 ][ t2.getNodeInf(y).getLeftmost() - 1 ] = 0.0 ;
00401
00402 for( int i = t1.getNodeInf(x).getLeftmost(); i <= x; i++ ){
00403
00404 forestDistance[ i ][ t2.getNodeInf(y).getLeftmost() - 1 ] =
00405 forestDistance[ t1.getNodeInf(i).getLeftmost() - 1 ][ t2.getNodeInf(y).getLeftmost() - 1 ] +
00406 t1.deleteSubtreeCost( t1.getNode( i ) ) ;
00407
00408 }
00409
00410 for( int j = t2.getNodeInf(y).getLeftmost(); j <= y; j++ ){
00411
00412 forestDistance[ t1.getNodeInf(x).getLeftmost() - 1 ][ j ] =
00413 forestDistance[ t1.getNodeInf(x).getLeftmost() - 1 ][ t2.getNodeInf(j).getLeftmost() - 1 ] +
00414 t2.insertSubtreeCost( t2.getNode( j ) ) ;
00415
00416 }
00417
00418 for( int i = t1.getNodeInf(x).getLeftmost(); i <= x; i++ ){
00419
00420 for( int j = t2.getNodeInf(y).getLeftmost(); j <= y; j++ ){
00421
00422
00423
00424
00425
00426 vector<double> vec ;
00427
00428 vec.push_back( forestDistance[i-1][j] + GAMMA( t1.getNodeInf(i).getWeightValue(), 0.0 ) ) ;
00429 vec.push_back( forestDistance[i][j-1] + GAMMA( 0.0, t2.getNodeInf(j).getWeightValue() ) ) ;
00430 vec.push_back( forestDistance[ t1.getNodeInf(i).getLeftmost() - 1 ][j] + t1.deleteSubtreeCost( t1.getNode(i) ) ) ;
00431 vec.push_back( forestDistance[i][ t2.getNodeInf(j).getLeftmost() - 1 ] + t2.insertSubtreeCost( t2.getNode(j) ) ) ;
00432
00433 forestDistance[i][j] = *min_element( vec.begin(), vec.end() ) ;
00434
00435
00436
00437 if( t1.getNodeInf( i ).getLeftmost() == t1.getNodeInf( x ).getLeftmost() &&
00438 t2.getNodeInf( j ).getLeftmost() == t2.getNodeInf( y ).getLeftmost() ){
00439
00440
00441
00442
00443
00444 vector<double> vec2 ;
00445
00446 vec2.push_back( forestDistance[i][j] ) ;
00447 vec2.push_back( forestDistance[i-1][j-1] + GAMMA( t1.getNodeInf(i).getWeightValue(), t2.getNodeInf(j).getWeightValue() ) ) ;
00448
00449 forestDistance[i][j] = *min_element( vec2.begin(), vec2.end() ) ;
00450 distance[i-1][j-1] = forestDistance[i][j] ;
00451
00452
00453 }else{
00454
00455
00456
00457
00458
00459 vector<double> vec2 ;
00460
00461 vec2.push_back( forestDistance[i][j] ) ;
00462 vec2.push_back( forestDistance[t1.getNodeInf( i ).getLeftmost()-1][t2.getNodeInf( j ).getLeftmost()-1] +
00463 distance[i-1][j-1] ) ;
00464
00465 forestDistance[i][j] = *min_element( vec2.begin(), vec2.end() ) ;
00466
00467
00468 if(
00469 t1.getNodeInf( i ).isKeyroot() &&
00470 ( t1.getNode( i ).outdeg() != 0 ) &&
00471 t2.getNodeInf( j ).isKeyroot() &&
00472 ( t2.getNode( j ).outdeg() != 0 )
00473 ){
00474
00475
00476
00477
00478
00479 vector<double> vec3 ;
00480
00481
00482 vec3.push_back( forestDistance[i][j] ) ;
00483 vec3.push_back( forestDistance[t1.getNodeInf( t1.getNodeInf( i ).getLeftmost()-1 ).getLeftmost() - 1]
00484 [t2.getNodeInf(t2.getNodeInf( j ).getLeftmost()-1 ).getLeftmost() - 1] +
00485 swapSubtrees( t1, t1.getNode( i ),
00486 t1.getNode(t1.getNodeInf( i ).getLeftmost()-1 ),
00487 t2, t2.getNode( j ),
00488 t2.getNode(t2.getNodeInf(j).getLeftmost()-1)) ) ;
00489
00490 forestDistance[i][j] = *min_element( vec3.begin(), vec3.end() ) ;
00491
00492
00493 }
00494
00495 }
00496
00497 }
00498
00499 }
00500
00501 }
00502 }
00503
00504 }
00505
00506 }
00507
00508 return distance[ t1.number_of_nodes() - 1 ][ t2.number_of_nodes() - 1 ] ;
00509 }
00510
00511 void Tree::print( const Tree& t, ostream& os )
00512 {
00513 map< double, vector<Node> > nodesValues ;
00514 vector<Node> nodes ;
00515
00516 for( Tree::node_iterator it = t.nodes_begin(); it != t.nodes_end(); it++ ){
00517
00518 nodes.clear() ;
00519
00520 nodes.push_back( *it ) ;
00521
00522 for( Tree::node_iterator it2 = t.nodes_begin(); it2 != t.nodes_end(); it2++ ){
00523
00524 if( ( fabs( t.inf(*it).getPotentialValue() - t.inf(*it2).getPotentialValue() ) < 1e-6 ) && ( it2 != it ) ){
00525
00526 nodes.push_back( *it2 ) ;
00527
00528 }
00529
00530 }
00531
00532 nodesValues[ t.inf(*it).getPotentialValue() ] = nodes ;
00533
00534 }
00535
00536 os << "---------------" << endl ;
00537 os << " Levels" << endl ;
00538 os << "---------------" << endl ;
00539 os << endl ;
00540 os << " <Potential> <Nodes>" << endl ;
00541 os << endl ;
00542
00543 for( map< double, vector<Node> >::reverse_iterator it = nodesValues.rbegin() ; it != nodesValues.rend(); it++ ){
00544
00545 os.setf(ios::fixed) ;
00546 os.precision(5) ;
00547 os << setw(10) << it->first << ": " ;
00548
00549 for( vector<Node>::iterator it2 = it->second.begin(); it2 != it->second.end(); it2++ ){
00550 os << "[" << t.inf(*it2).getExternalId() << "] " ;
00551 }
00552
00553 os << endl ;
00554 }
00555
00556 os << endl ;
00557
00558 os << "---------------" << endl ;
00559 os << " Connections" << endl ;
00560 os << "---------------" << endl ;
00561 os << endl ;
00562
00563 Node n;
00564 Edge out;
00565 string conn;
00566
00567 if (t.is_directed())
00568 conn = "-->";
00569 else
00570 conn = "<-->";
00571
00572 for( Tree::node_iterator itn = t.nodes_begin(); itn != t.nodes_end(); itn++ ){
00573 os << "[" << t.inf(*itn).getExternalId() << "]" << ":: ";
00574
00575 for( Node::adj_edges_iterator ite = itn->adj_edges_begin(); ite != itn->adj_edges_end(); ite++ ){
00576 os << conn << "[" << t.inf( itn->opposite(*ite) ).getExternalId() << "]" ;
00577 }
00578
00579 os << endl;
00580 }
00581
00582 os << endl ;
00583 }
00584
00585 void Tree::save_graph_info_handler( ostream* os ) const
00586 {
00587 (*os) << "tree " << 1 << endl ;
00588 }
00589
00590 void Tree::save_node_info_handler(ostream* os, node n ) const
00591 {
00592 (*os) << "label \"" << inf( n ).getExternalId() << "\"" << endl ;
00593
00594 (*os) << "weight [" << endl ;
00595 (*os) << "keyroot " << ( inf( n ).isKeyroot() ? 1 : 0 ) << endl ;
00596 (*os) << "root " << ( inf( n ).isRoot() ? 1 : 0 ) << endl ;
00597 (*os) << "externalId " << inf( n ).getExternalId() << endl ;
00598
00599 if( inf( n ).getPotentialValue() != INFINITY )
00600 (*os) << "potentialValue " << inf( n ).getPotentialValue() << endl ;
00601
00602 if( inf( n ).getWeightValue() != INFINITY )
00603 (*os) << "weightValue " << inf( n ).getWeightValue() << endl ;
00604 (*os) << "leftmost " << inf( n ).getLeftmost() << endl ;
00605 (*os) << "deepestNoNodes " << inf( n ).getDeepestNoNodes() << endl ;
00606 (*os) << "]" << endl ;
00607 }
00608
00609 void Tree::load_graph_info_handler( GML_pair* list_graph )
00610 {
00611 while ( list_graph ) {
00612 if ( strcmp( "tree", list_graph->key ) == 0 ) {
00613 tree = ( ( list_graph->value.integer == 1 ) ? true : false ) ;
00614
00615 if( !tree ){
00616 cerr << "### Error ### : This graph is not a TARIS::Tree" << endl ;
00617 exit(-1) ;
00618 }
00619 }
00620
00621 list_graph = list_graph->next;
00622 }
00623 }
00624
00625 void Tree::load_node_info_handler( node n, GML_pair* list_node )
00626 {
00627 while ( list_node ) {
00628
00629 if( strcmp( "label", list_node->key ) == 0 ){
00630
00631 }
00632
00633 if( strcmp( "weight", list_node->key ) == 0 ){
00634
00635 GML_pair* list_weight = list_node->value.list;
00636
00637 while ( list_weight ) {
00638
00639 if ( strcmp( "keyroot", list_weight->key ) == 0 ) {
00640 inf( n ).setKeyroot( ( ( list_weight->value.integer == 1 ) ? true : false ) ) ;
00641 }
00642
00643 if ( strcmp( "root", list_weight->key ) == 0 ) {
00644 inf( n ).setRoot( ( ( list_weight->value.integer == 1 ) ? true : false ) ) ;
00645 }
00646
00647 if ( strcmp( "externalId", list_weight->key ) == 0 ) {
00648 inf( n ).setExternalId( list_weight->value.integer ) ;
00649 }
00650
00651 if ( strcmp( "potentialValue", list_weight->key ) == 0 ) {
00652 inf( n ).setPotentialValue( list_weight->value.floating ) ;
00653 }
00654
00655 if ( strcmp( "weightValue", list_weight->key ) == 0 ) {
00656 inf( n ).setWeightValue( list_weight->value.floating ) ;
00657 }
00658
00659 if ( strcmp( "leftmost", list_weight->key ) == 0 ) {
00660 inf( n ).setLeftmost( list_weight->value.integer ) ;
00661 }
00662
00663 if ( strcmp( "deepestNoNodes", list_weight->key ) == 0 ) {
00664 inf( n ).setDeepestNoNodes( list_weight->value.integer ) ;
00665 }
00666
00667 list_weight = list_weight->next;
00668
00669 }
00670
00671 delete list_weight ;
00672
00673 }
00674
00675 list_node = list_node->next;
00676 }
00677 }
