Сравнение двух деревьев

/////////////////////////////////////////////////////////////////////////////////////////
// Программа определяет, эквивалентны ли два дерева, заданные списком ребер.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <list>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_str;
typedef T_str        T_vertex;    
/////////////////////////////////////////////////////////////////////////////////////////
class  T_tree
{  
    typedef std::map     <T_vertex,  int>                    T_vertices_weights;
    typedef std::set     <T_vertex>                          T_vertices;
    typedef T_vertices::const_iterator                       T_vert_const_it;
    typedef std::pair    <T_vert_const_it, T_vert_const_it>  T_edge;
    typedef std::list    <T_edge>                            T_edges;    
    typedef std::vector  <int>                               T_tree_key;    
    //-----------------------------------------------------------------------------------
    T_edges                     edges_;
    T_vertices                  vertices_;
    mutable T_vertices_weights  vertices_weights_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    bool  operator== (const T_tree&  tree) const
    {
        return  get_key() == tree.get_key();
    }
    //-----------------------------------------------------------------------------------
    bool  add_edge
        (
            const T_vertex&  vertex_1, 
            const T_vertex&  vertex_2
        )
    {
        //Ребро принимается, если множество ребер пусто, или если одна из вершин ребра 
        //принадлежит дереву, а другая нет.        
        bool  bool_res = false;
        if( vertices_.empty() )
        {
            bool_res = vertex_1 != vertex_2;
        }
        else
        {
            bool_res =   vertices_.count(vertex_1) 
                       + vertices_.count(vertex_2) == 1;
        }
                         
        if(bool_res)
        {
            vertices_.insert(vertex_1);
            vertices_weights_[vertex_1] = 1;
 
            vertices_.insert(vertex_2);
            vertices_weights_[vertex_2] = 1;
 
            edges_.push_back
                (
                    std::make_pair
                        (
                            vertices_.find(vertex_1),
                            vertices_.find(vertex_2)
                        )
                );
        }        
        return  bool_res;
    }
    //-----------------------------------------------------------------------------------
    int  edges_count() const
    {
        return  edges_.size();
    }
    //-----------------------------------------------------------------------------------
    const T_vertices&  get_vertices() const
    {
        return  vertices_;
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------    
    static T_vertices  get_vertices_with_degree_greater_1(const T_edges&  edges)
    {
        typedef std::map<T_vertex, int>  T_vert_degree;
 
        T_vert_degree                    vert_degree;
        T_vertices                       res_vertices;
 
        for(T_edges::const_iterator  edge_it = edges.begin(); edge_it != edges.end(); ++edge_it)
        {
            const T_vertex  v1 = *edge_it->first;
            const T_vertex  v2 = *edge_it->second;            
            
            if(++vert_degree[v1] > 1)
            {
                res_vertices.insert(v1);
            }
 
            if(++vert_degree[v2] > 1)
            {
                res_vertices.insert(v2);
            }
        }
        return  res_vertices;        
    }
    //-----------------------------------------------------------------------------------    
    T_tree_key  get_root_tree_key
        (
            const T_vertex&  root, 
            T_vertices       vertices           
        ) const 
    {
        T_tree_key  res_tree_key;        
        res_tree_key.push_back(vertices_weights_.find(root)->second);
        vertices.erase(root);
 
        T_vertices  root_children;
        //Пробегаемся по всем ребрам дерева и из каждого ребра, содержащего корень, 
        //заносим в root_children его сына, если он принадлежит vertices.
        for(T_edges::const_iterator  edge_it = edges_.begin(); edge_it != edges_.end(); 
            ++edge_it)
        {            
            T_vertex  v1 = *edge_it->first;
            T_vertex  v2 = *edge_it->second;
            
            if(   root                == v1
               && vertices.count(v2)  != 0 )
            {
                root_children.insert(v2);
            }
            else if(   root == v2
                    && vertices.count(v1) != 0 )
            {
                root_children.insert(v1);
            }
        }
        
        typedef std::set<T_tree_key>  T_tree_keys;
        T_tree_keys                   children_tree_keys;
        //Пробегаемся по root_children, находим tree_key для каждого поддерева с корнем 
        //в этой вершине и заносим их в children_tree_keys.        
        for(T_vertices::const_iterator  child_it = root_children.begin();
            child_it != root_children.end(); ++child_it)
        {
            children_tree_keys.insert
                (
                    get_root_tree_key
                        (
                            *child_it,
                            vertices
                        )
                );
        }        
 
        //Пробегаемся по children_tree_keys и добавляем все ключи в хвост ключу res_tree_key.
        for(T_tree_keys::const_iterator  child_key_it = children_tree_keys.begin();
            child_key_it != children_tree_keys.end(); ++child_key_it)
        {
            res_tree_key.insert
                (
                    res_tree_key.end(),
                    child_key_it->begin(),
                    child_key_it->end()
                );
        }
        return  res_tree_key;
    }
    //-----------------------------------------------------------------------------------
    T_tree_key  get_key() const
    {       
        T_edges     edges_for_get_key     = edges_;      
        T_vertices  vertices_for_get_key  = vertices_;
 
        while(vertices_for_get_key.size() > 2)
        {
            vertices_for_get_key 
                = get_vertices_with_degree_greater_1(edges_for_get_key);            
 
            //Пробегаемся по edges_for_get_key и если одна из вершин ребра не принадлежит
            //vertices_for_get_key, то для другой вершины этого ребра увеличиваем вес на 1 
            //и удаляем это ребро.            
            for(T_edges::const_iterator  edge_it = edges_for_get_key.begin();
                edge_it != edges_for_get_key.end(); )
            {                
                const T_vertex&  v1 = *edge_it->first;
                const T_vertex&  v2 = *edge_it->second;
                
                bool  v1_is_leaf_in_edges_for_get_key  = vertices_for_get_key.count(v1) == 0;
                bool  v2_is_leaf_in_edges_for_get_key  = vertices_for_get_key.count(v2) == 0;
 
                if(   v1_is_leaf_in_edges_for_get_key
                   || v2_is_leaf_in_edges_for_get_key )
                {                   
                    ++vertices_weights_.find(v1_is_leaf_in_edges_for_get_key ? v2 : v1)->second;
                    
                    T_edges::const_iterator  edge_it_for_erase = edge_it;
                    ++edge_it;
                    edges_for_get_key.erase(edge_it_for_erase);               
                }
                else
                {
                    ++edge_it;
                }
            }//for        
        }//while
        //Утверждение. Каждая вершина дерева имеет вес, равный числу вершин
        //в дереве, корнем которого она является, а vertices_for_get_key
        //содержит одну или две вершины, которые и назначаем корнями дерева.
 
        T_vertex  A_root = *vertices_for_get_key.begin   ();
        T_vertex  B_root = *vertices_for_get_key.rbegin  ();        
 
        T_tree_key  A_tree_key = 
            get_root_tree_key
                (
                    A_root,
                    vertices_
                );
 
        if(B_root != A_root)
        {
            T_tree_key  B_tree_key = 
                get_root_tree_key
                    (
                        B_root,
                        vertices_
                    );
            return  std::min(A_tree_key, B_tree_key);
        }
        return  A_tree_key;
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
void  input_tree_edges
    (
        int      tree_edges_total,
        T_tree&  tree
    )
{    
    do
    {
        std::cout << '\t'
                  << "ребро #"
                  << tree.edges_count() + 1
                  << ":"
                  << std::endl;
 
        T_vertex  vertex_1;
        do
        {
            std::cout << '\t'
                      << '\t'
                      << "вершина 1";
 
            if( tree.edges_count() )
            {
                std::cout <<" (из списка: ";            
 
                std::copy
                    (
                        tree.get_vertices().begin(),
                        tree.get_vertices().end(),
                        std::ostream_iterator<T_vertex>(std::cout, " ")
                    );
                std::cout  <<")";
            }
            else
            {
                std::cout <<" (корень дерева)";
            }
                      
            std::cout <<": ";
 
            std::cin >> vertex_1;
        }while(   tree.edges_count() != 0
               && tree.get_vertices().find(vertex_1) == tree.get_vertices().end() );        
 
        T_vertex  vertex_2;
        do
        {
            std::cout << '\t'
                      << '\t' 
                      << "вершина 2: ";
 
            std::cin >> vertex_2;
        }while( !tree.add_edge(vertex_1, vertex_2) ); 
 
        std::cout << std::endl;
    }while(tree.edges_count() < tree_edges_total); 
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
 
    int  tree_A_edges_total = 0;
    do
    {
        std::cout << "Введите количество ребер первого дерева: ";
        std::cin >> tree_A_edges_total;
    }while(tree_A_edges_total <= 0);
    
    std::cout << "Введите "
              << tree_A_edges_total
              << " ребер первого дерева:"
              << std::endl;
    T_tree  tree_A;
    input_tree_edges(tree_A_edges_total, tree_A);
 
 
    int  tree_B_edges_total = 0;
    do
    {
        std::cout << std::endl
                  << std::endl
                  << "Введите количество ребер второго дерева: ";
        std::cin >> tree_B_edges_total;
    }while(tree_B_edges_total <= 0);
    
    std::cout << "Введите "
              << tree_B_edges_total
              << " ребер второго дерева:"
              << std::endl;
    T_tree  tree_B;
    input_tree_edges(tree_B_edges_total, tree_B);
 
    
    std::cout << "Деревья "
              << (tree_A == tree_B ? "" : "НЕ ")
              << "эквивалентны."
              << std::endl;
}

/////////////////////////////////////////////////////////////////////////////////////////
// Программа определяет, эквивалентны ли два дерева, заданные списком ребер.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <list>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_str;
typedef T_str        T_vertex;    
/////////////////////////////////////////////////////////////////////////////////////////
class  T_tree
{  
    typedef std::map       <T_vertex,        int>              T_vertices_distances;
    typedef std::set       <T_vertex>                          T_vertices;
    typedef T_vertices::const_iterator                         T_vert_const_it;
    typedef std::pair      <T_vert_const_it, T_vert_const_it>  T_edge;
    typedef std::list      <T_edge>                            T_edges;    
    typedef std::multiset  <int>                               T_tree_key;    
    //-----------------------------------------------------------------------------------
    T_edges                       edges_;
    T_vertices                    vertices_;
    mutable T_vertices_distances  vertices_distances_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    bool  operator== (const T_tree&  tree) const
    {
        return  get_key() == tree.get_key();
    }
    //-----------------------------------------------------------------------------------
    bool  add_edge
        (
            const T_vertex&  vertex_1, 
            const T_vertex&  vertex_2
        )
    {
        //Ребро принимается, если множество ребер пусто, или если одна из вершин ребра 
        //принадлежит дереву, а другая нет.        
        bool  bool_res = false;
        if( vertices_.empty() )
        {
            bool_res = vertex_1 != vertex_2;
        }
        else
        {
            bool_res =   vertices_.count(vertex_1) 
                       + vertices_.count(vertex_2) == 1;
        }
                         
        if(bool_res)
        {
            vertices_.insert(vertex_1);           
            vertices_.insert(vertex_2);            
 
            edges_.push_back
                (
                    std::make_pair
                        (
                            vertices_.find(vertex_1),
                            vertices_.find(vertex_2)
                        )
                );
        }        
        return  bool_res;
    }
    //-----------------------------------------------------------------------------------
    int  edges_count() const
    {
        return  edges_.size();
    }
    //-----------------------------------------------------------------------------------
    const T_vertices&  get_vertices() const
    {
        return  vertices_;
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------    
    T_vertices  get_leafs() const
    {
        typedef std::map<T_vertex, int>  T_vert_degree;
 
        T_vert_degree                    vert_degree;
        T_vertices                       res_vertices = vertices_;
 
        for(T_edges::const_iterator  edge_it = edges_.begin(); edge_it != edges_.end(); ++edge_it)
        {
            const T_vertex  v1 = *edge_it->first;
            const T_vertex  v2 = *edge_it->second;            
            
            if(++vert_degree[v1] > 1)
            {
                res_vertices.erase(v1);
            }
 
            if(++vert_degree[v2] > 1)
            {
                res_vertices.erase(v2);
            }
        }
        return  res_vertices;       
    }
    //-----------------------------------------------------------------------------------    
    T_tree_key  get_key() const
    {
        T_tree_key  res_tree_key;
        //Находим множество вершин-листьев дерева.
        T_vertices  leafs = get_leafs();
        
        //Пробегаемся по всем листьям, и для каждого находим расстояние до всех
        //остальных листьев.
        for(T_vertices::const_iterator  leaf_it = leafs.begin(); 
            leaf_it != leafs.end(); ++leaf_it)
        {
            //Обнуляем расстояния для вершины *leaf_it.
            vertices_distances_[*leaf_it] = 0;
            //Создаем множество для измерения расстояний из вершины *leaf_it.
            T_vertices  tree_from_cur_leaf;
            tree_from_cur_leaf.insert(*leaf_it);
            while( tree_from_cur_leaf.size() < vertices_.size() )
            {
                //Перебираем ребра дерева, и если находим ребро, одна вершина 
                //которого принадлежит tree_from_cur_leaf, а другая нет, то 
                //включаем ее в tree_from_cur_leaf и присваиваем ей расстояние
                //на единицу большее, чем у другой вершины этого ребра.
                for(T_edges::const_iterator  edge_it = edges_.begin();
                    edge_it != edges_.end(); ++edge_it)
                {
                    T_vertex  v1 = *edge_it->first;
                    T_vertex  v2 = *edge_it->second;
 
                    if(  tree_from_cur_leaf.count(v1)
                       + tree_from_cur_leaf.count(v2) != 1 )
                    {
                        continue;
                    }
 
                    T_vertex  new_vert = v1;
                    T_vertex  old_vert = v2;
 
                    if( tree_from_cur_leaf.count(v1) )
                    {
                        std::swap(new_vert, old_vert);
                    }                    
 
                    tree_from_cur_leaf.insert(new_vert);
                    vertices_distances_[new_vert] 
                        = vertices_distances_[old_vert] + 1;
                    //Если это лист, то записываем это расстояние в ключ.
                        if( leafs.count(new_vert) == 1 )
                    {
                        res_tree_key.insert(vertices_distances_[new_vert]);
                    }                       
                }//for
            }//while        
        }//for
        return  res_tree_key;
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
void  input_tree_edges
    (
        int      tree_edges_total,
        T_tree&  tree
    )
{    
    do
    {
        std::cout << '\t'
                  << "ребро #"
                  << tree.edges_count() + 1
                  << ":"
                  << std::endl;
 
        T_vertex  vertex_1;
        do
        {
            std::cout << '\t'
                      << '\t'
                      << "вершина 1";
 
            if( tree.edges_count() )
            {
                std::cout <<" (из списка: ";            
 
                std::copy
                    (
                        tree.get_vertices().begin(),
                        tree.get_vertices().end(),
                        std::ostream_iterator<T_vertex>(std::cout, " ")
                    );
                std::cout  <<")";
            }
            else
            {
                std::cout <<" (корень дерева)";
            }
                      
            std::cout <<": ";
 
            std::cin >> vertex_1;
        }while(   tree.edges_count() != 0
               && tree.get_vertices().find(vertex_1) == tree.get_vertices().end() );        
 
        T_vertex  vertex_2;
        do
        {
            std::cout << '\t'
                      << '\t' 
                      << "вершина 2: ";
 
            std::cin >> vertex_2;
        }while( !tree.add_edge(vertex_1, vertex_2) ); 
 
        std::cout << std::endl;
    }while(tree.edges_count() < tree_edges_total); 
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
 
    int  tree_A_edges_total = 0;
    do
    {
        std::cout << "Введите количество ребер первого дерева: ";
        std::cin >> tree_A_edges_total;
    }while(tree_A_edges_total <= 0);
    
    std::cout << "Введите "
              << tree_A_edges_total
              << " ребер первого дерева:"
              << std::endl;
    T_tree  tree_A;
    input_tree_edges(tree_A_edges_total, tree_A);
 
 
    int  tree_B_edges_total = 0;
    do
    {
        std::cout << std::endl
                  << std::endl
                  << "Введите количество ребер второго дерева: ";
        std::cin >> tree_B_edges_total;
    }while(tree_B_edges_total <= 0);
    
    std::cout << "Введите "
              << tree_B_edges_total
              << " ребер второго дерева:"
              << std::endl;
    T_tree  tree_B;
    input_tree_edges(tree_B_edges_total, tree_B);
 
    
    std::cout << "Деревья "
              << (tree_A == tree_B ? "" : "НЕ ")
              << "эквивалентны."
              << std::endl;
}