#include <Tree.h>
Public Member Functions | |
| Tree () | |
| Tree (const Tree &t) | |
| bool | operator== (const Tree &t) |
| ~Tree () | |
| bool | isTree () |
| Node | getRoot () const |
| Node | getNode (int externalId) const |
| NodeWeight | getNodeInf (int externalId) const |
| void | postOrder () |
| void | postOrderRay () |
| void | postOrderComplete () |
| double | insertSubtreeCost (Node n) const |
| double | deleteSubtreeCost (Node n) const |
Static Public Member Functions | |
| static bool | areSubtreesEqual (const Tree &t1, Node n1, const Tree &t2, Node n2) |
| static double | swapSubtrees (const Tree &t1, Node n11, Node n12, const Tree &t2, Node n21, Node n22) |
| static double | distance (const Tree &t1, const Tree &t2) |
| static void | print (const Tree &t, ostream &os) |
Protected Member Functions | |
| virtual void | save_graph_info_handler (ostream *os) const |
| virtual void | save_node_info_handler (ostream *os, node n) const |
| virtual void | load_graph_info_handler (GML_pair *list_graph) |
| virtual void | load_node_info_handler (node n, GML_pair *list_node) |
Private Member Functions | |
| void | postOrder (Node n, int &counter, bool makeKeyroot) |
| void | postOrderRay (Node n, int &counter, bool makeKeyroot) |
| void | postOrderComplete (Node n, int &counter, bool makeKeyroot) |
| void | insertSubtreeCost (Node n, double &cost) const |
Private Attributes | |
| bool | tree |
Fecha de creaci髇 : 2007-03-18
Definition at line 40 of file Tree.h.
| Tree::Tree | ( | ) |
Definition at line 28 of file Tree.cpp.
References tree.
00028 : 00029 Graph<NodeWeight>() 00030 { 00031 tree = true ; 00032 }
| Tree::Tree | ( | const Tree & | t | ) |
| bool Tree::operator== | ( | const Tree & | t | ) |
Definition at line 40 of file Tree.cpp.
References areSubtreesEqual(), and getRoot().
00040 { 00041 return areSubtreesEqual( *this, this->getRoot(), t, t.getRoot() ) ; 00042 }
| bool Tree::isTree | ( | ) |
| Node Tree::getRoot | ( | ) | const |
Definition at line 53 of file Tree.cpp.
References Node.
Referenced by operator==().
00054 { 00055 Node root ; 00056 00057 // Se busca el nodo raiz 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 }
| Node Tree::getNode | ( | int | externalId | ) | const |
Busca un nodo discriminandolo por su externalId
| id |
Definition at line 72 of file Tree.cpp.
References Node.
Referenced by distance().
00073 { 00074 Node n ; 00075 00076 // Se busca el nodo de interes 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 }
| NodeWeight Tree::getNodeInf | ( | int | externalId | ) | const |
Definition at line 86 of file Tree.cpp.
References Graph< NodeWeight >::inf().
Referenced by distance().
00087 { 00088 return this->inf( this->getNode( externalId ) ) ; 00089 }
| void Tree::postOrder | ( | ) |
| void Tree::postOrderRay | ( | ) |
Definition at line 92 of file Tree.cpp.
References Node.
Referenced by HyperSurface::buildAreaTree(), and postOrderRay().
00093 { 00094 Node root ; 00095 00096 // Se busca el nodo raiz 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 }
| void Tree::postOrderComplete | ( | ) |
| double Tree::insertSubtreeCost | ( | Node | n | ) | const |
El costo de insertarun nodo es la suma de todos los pesos de los nodos generados a partir de el
| n |
Definition at line 114 of file Tree.cpp.
Referenced by deleteSubtreeCost(), distance(), and insertSubtreeCost().
00114 { 00115 double cost = 0.0 ; 00116 00117 insertSubtreeCost( n, cost ) ; 00118 00119 return cost ; 00120 }
| double Tree::deleteSubtreeCost | ( | Node | n | ) | const |
El costo de remover un nodo, corresponde a valor de su peso
| n |
Definition at line 127 of file Tree.cpp.
References insertSubtreeCost().
Referenced by distance().
00127 { 00128 00129 // return inf( n ).getWeightValue() ; 00130 double cost = 0.0 ; 00131 00132 insertSubtreeCost( n, cost ) ; 00133 00134 return cost ; 00135 00136 00137 }
| n1 | Nodo inicial perteneciente al Arbol 1 ( this ) | |
| t2 | Arbol contra el cual se comparar谩 | |
| n2 | Nodo inicial perteneciente al Arbol 2 ( t2 ) |
Definition at line 146 of file Tree.cpp.
References TarisApplication::getDebugLevel(), TarisApplication::getDoubleThresholdComparison(), Graph< NODE_TYPE, EDGE_TYPE, GRAPH_TYPE >::inf(), and TarisApplication::Instance().
Referenced by operator==(), and swapSubtrees().
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 }
| double Tree::swapSubtrees | ( | const Tree & | t1, | |
| Node | n11, | |||
| Node | n12, | |||
| const Tree & | t2, | |||
| Node | n21, | |||
| Node | n22 | |||
| ) | [static] |
Esta funci贸n calcula el costo de intercambiar dos ramas cuyos origenes son n11 y n12 para el arbol original
| n11 | ||
| n12 | ||
| n21 | ||
| n22 |
Definition at line 238 of file Tree.cpp.
References areSubtreesEqual(), Graph< NODE_TYPE, EDGE_TYPE, GRAPH_TYPE >::inf(), and TarisApplication::Instance().
Referenced by distance().
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 // ( n11.outdeg() == 1 ) es equivalente a preguntar que el nodo tiene padres ? 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 }
Definition at line 372 of file Tree.cpp.
References deleteSubtreeCost(), GAMMA, NodeWeight::getLeftmost(), getNode(), getNodeInf(), NodeWeight::getWeightValue(), insertSubtreeCost(), NodeWeight::isKeyroot(), swapSubtrees(), and Graph< NodeWeight >::x.
Referenced by Programs::TARIS_TreesDistance::main(), and Programs::TARIS_Matrices::main().
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 * Se agregan las cosas en el vector, solo con el motivo de 00424 * encontrar el minimo valor 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 // cout << "El minimo es: " << forestDistance[i][j] << endl ; 00435 //*********************************************************** 00436 00437 if( t1.getNodeInf( i ).getLeftmost() == t1.getNodeInf( x ).getLeftmost() && 00438 t2.getNodeInf( j ).getLeftmost() == t2.getNodeInf( y ).getLeftmost() ){ 00439 00440 /************************************************************ 00441 * Se agregan las cosas en el vector, solo con el motivo de 00442 * encontrar el minimo valor 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 * Se agregan las cosas en el vector, solo con el motivo de 00457 * encontrar el minimo valor 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 * Se agregan las cosas en el vector, solo con el motivo de 00477 * encontrar el minimo valor 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 }
| void Tree::print | ( | const Tree & | t, | |
| ostream & | os | |||
| ) | [static] |
Definition at line 511 of file Tree.cpp.
References Edge, Graph< NODE_TYPE, EDGE_TYPE, GRAPH_TYPE >::inf(), and Node.
Referenced by Programs::TARIS_BuildTree::main().
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 // for( map< double, vector<Node> >::iterator it = nodesValues.begin() ; it != nodesValues.end(); it++ ){ 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 }
| void Tree::save_graph_info_handler | ( | ostream * | os | ) | const [protected, virtual] |
| void Tree::save_node_info_handler | ( | ostream * | os, | |
| node | n | |||
| ) | const [protected, virtual] |
Definition at line 590 of file Tree.cpp.
References Graph< NodeWeight >::inf().
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 }
| void Tree::load_graph_info_handler | ( | GML_pair * | list_graph | ) | [protected, virtual] |
Definition at line 609 of file Tree.cpp.
References tree.
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 }
| void Tree::load_node_info_handler | ( | node | n, | |
| GML_pair * | list_node | |||
| ) | [protected, virtual] |
Definition at line 625 of file Tree.cpp.
References Graph< NodeWeight >::inf().
00626 { 00627 while ( list_node ) { 00628 00629 if( strcmp( "label", list_node->key ) == 0 ){ 00630 // En este caso no interesa, solo es para visualizaci髇 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 }
| void Tree::postOrder | ( | Node | n, | |
| int & | counter, | |||
| bool | makeKeyroot | |||
| ) | [private] |
| void Tree::postOrderRay | ( | Node | n, | |
| int & | counter, | |||
| bool | makeKeyroot | |||
| ) | [private] |
| n | ||
| counter |
Definition at line 305 of file Tree.cpp.
References Graph< NodeWeight >::assign(), Graph< NodeWeight >::inf(), postOrderRay(), NodeWeight::setExternalId(), NodeWeight::setKeyroot(), and NodeWeight::setLeftmost().
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 }
| void Tree::postOrderComplete | ( | Node | n, | |
| int & | counter, | |||
| bool | makeKeyroot | |||
| ) | [private] |
| void Tree::insertSubtreeCost | ( | Node | n, | |
| double & | cost | |||
| ) | const [private] |
Definition at line 355 of file Tree.cpp.
References Graph< NodeWeight >::inf(), insertSubtreeCost(), and Node.
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 }
bool Tree::tree [private] |
Definition at line 82 of file Tree.h.
Referenced by isTree(), load_graph_info_handler(), and Tree().
1.5.4