Vaucanson 1.4
isomorph.hxx
00001 // isomorph.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 The Vaucanson Group.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
00016 //
00017 #ifndef VCSN_ALGORITHMS_ISOMORPH_HXX
00018 # define VCSN_ALGORITHMS_ISOMORPH_HXX
00019 
00020 # include <vaucanson/algorithms/isomorph.hh>
00021 # include <vaucanson/algorithms/determinize.hh>
00022 
00023 # include <vaucanson/automata/concept/automata_base.hh>
00024 # include <vaucanson/misc/usual_macros.hh>
00025 
00026 # include <vaucanson/algorithms/internal/skeleton.hh>
00027 
00028 # include <queue>
00029 # include <set>
00030 # include <list>
00031 # include <utility>
00032 
00033 namespace vcsn
00034 {
00035 
00036   /*--------------------------------------.
00037   | Helper for are_isomorphic algorithm.  |
00038   `--------------------------------------*/
00039 
00040   class Trie
00041   {
00042     public:
00043       Trie();
00045       Trie(const Trie& t);
00046 
00047       Trie* insert(std::vector<int>&);
00048 
00049     public:
00050       std::list<int> A, B;
00051 
00052       // Node in list C pointing to this node
00053       std::list<Trie*>::iterator L;
00054 
00055     private:
00057       bool L_is_valid;
00058       Trie* insert_suffix(std::vector<int>&, unsigned int);
00059       std::map<int, Trie> children;
00060   };
00061 
00062   inline
00063   Trie::Trie ()
00064     : A(), B(), L(), L_is_valid(false), children()
00065   {
00066   }
00067 
00068   inline
00069   Trie::Trie (const Trie& t)
00070     : A(t.A), B(t.B),
00071       L(), L_is_valid(t.L_is_valid), children(t.children)
00072   {
00073     if (L_is_valid)
00074       L = t.L;
00075   }
00076 
00077 
00078   // Find node associated to the insertion of a vector of integers.
00079   inline Trie* Trie::insert(std::vector<int>& S)
00080   {
00081     return insert_suffix(S, 0);
00082   }
00083 
00084   inline Trie* Trie::insert_suffix(std::vector<int>& S, unsigned int p)
00085   {
00086     if (p == S.capacity() - 1)
00087       return this;
00088 
00089     return children[S[p]].insert_suffix(S, p + 1);
00090   }
00091 
00092 
00093 
00094   /*--------------------------------------.
00095   | Functor for are_isomorphic algorithm. |
00096   `--------------------------------------*/
00097 
00098   template<typename A, typename T>
00099   class Isomorpher
00100   {
00101     public:
00102 
00103       typedef Element<A, T> auto_t;
00104       AUTOMATON_TYPES(auto_t);
00105 
00106       typedef std::vector<int> trans_t;
00107       typedef std::list<int> state_list_t;
00108       typedef std::vector<state_list_t> delta_t;
00109 
00110       struct automaton_vars
00111       {
00112           // We have to build the vector T_L using a valid iterator (i.e., not a
00113           // singular one).  We use a temp int list to this end.
00114           automaton_vars(const automaton_t& aut)
00115             : s(aut),
00116               aut(aut),
00117               perm(aut.states().size(), -1),
00118               T_L(aut.states().size(), state_list_t().end()),
00119               delta_det_in(aut.states().size()),
00120               delta_det_out(aut.states().size()),
00121               class_state(aut.states().size())
00122           {
00123           }
00124 
00125           void
00126           shrink_unused()
00127           {
00128             T_L.clear();
00129             delta_det_in.clear();
00130             delta_det_out.clear();
00131             class_state.clear();
00132             class_state.clear();
00133           }
00134 
00135 
00136           Skeleton<A, T> s;
00137           const automaton_t aut;
00138 
00139           // perm[i] = state of another automaton corresponding to state i in
00140           // the isomorphism, or -1 when the association
00141           // is yet undefined.
00142           trans_t perm;
00143 
00144           // Vector indexed by states that points to the corresponding node
00145           // of the list of states of each class of states stored in the
00146           // Tries.
00147           std::vector<state_list_t::iterator> T_L;
00148 
00149           // Lists of deterministic ingoing and outgoing transitions
00150           // for each state (delta_det_in[i] = list of deterministic ingoing
00151           // transitions for state i, idem for delta_det_out[i])
00152           delta_t delta_det_in;
00153           delta_t delta_det_out;
00154 
00155           // class_state_A[i] = class (node of a Trie) of state i for automaton A
00156           std::vector<Trie*> class_state;
00157       };
00158 
00159       Isomorpher(const automaton_t& a, const automaton_t& b)
00160         : a_(a), b_(b)
00161       {
00162       }
00163 
00164       bool
00165       operator()()
00166       {
00167         if (fails_on_quick_tests())
00168           return false;
00169 
00170         list_in_out_det_trans(a_);
00171         list_in_out_det_trans(b_);
00172 
00173         if (!construct_tries())
00174           return false;
00175 
00176         // Analyzes co-deterministic ingoing and outgoing transitions
00177         //(obs: if the automata are deterministic, the isomorphism test
00178         // ends here)
00179         if (!analyse_det_trans())
00180           return false;
00181 
00182         a_.shrink_unused();
00183         b_.shrink_unused();
00184 
00185         return backtracking();
00186       }
00187 
00188     private:
00194       bool
00195       fails_on_quick_tests()
00196       {
00197         return a_.aut.states().size() != b_.aut.states().size()
00198           || a_.aut.transitions().size() != b_.aut.transitions().size()
00199           || a_.aut.initial().size() != b_.aut.initial().size()
00200           || a_.aut.final().size() != b_.aut.final().size();
00201       }
00202 
00203 
00209       void
00210       list_in_out_det_trans(automaton_vars& av)
00211       {
00212         for (int i = 0; i < static_cast<int>(av.aut.states().size()); i++)
00213         {
00214           if (av.s.delta_in[i].size() > 0)
00215             list_det_trans(av, av.delta_det_in, av.s.delta_in, i);
00216 
00217           if (av.s.delta_out[i].size() > 0)
00218             list_det_trans(av, av.delta_det_out, av.s.delta_out, i);
00219         }
00220       }
00221 
00222 
00230       bool
00231       construct_tries()
00232       {
00233         // Constructs Tries for Automaton A.
00234         for (int i = 0; i < static_cast<int>(a_.aut.states().size()); i++)
00235         {
00236           Trie *T_aux = add_all_transitions_to_trie(a_, i);
00237 
00238           // New class?
00239           if (T_aux->A.size() == 0)
00240           {
00241             // Inserts in list C of classes (nodes of Tries)
00242             C_.push_front(T_aux);
00243 
00244             // Each Trie node points to its node in list C
00245             T_aux->L = C_.begin();
00246           }
00247 
00248           // Inserts the state in the list A of its corresponding class
00249           T_aux->A.push_front(i);
00250           // Defines class of state i
00251           a_.class_state[i] = T_aux;
00252           // T_L_A[i] = node of the list of states of class of state i
00253           a_.T_L[i] = T_aux->A.begin();
00254         }
00255 
00256 
00257         // Constructs Tries for automaton B.
00258         for (int i = 0; i < static_cast<int>(b_.aut.states().size()); i++)
00259         {
00260           Trie *T_aux = add_all_transitions_to_trie(b_, i);
00261 
00262           // Does the class of state i have more states for automaton B
00263           // than those for automaton A ?
00264           if (T_aux->A.size() == T_aux->B.size())
00265             return false;
00266 
00267           // Inserts the state in the list B of its corresponding class
00268           T_aux->B.push_front(i);
00269           // Defines class of state i
00270           b_.class_state[i] = T_aux;
00271           // T_L_B[i] = node of the list of states of class of state i
00272           b_.T_L[i] = T_aux->B.begin();
00273         }
00274 
00275         return true;
00276       }
00277 
00278 
00289       bool
00290       construct_list_of_classes_with_one_state(std::list<int>& U)
00291       {
00292         std::list<Trie*>::iterator itr_C = C_.begin();
00293 
00294         while (itr_C != C_.end())
00295         {
00296           // Do automata A and B have the same number of states in the
00297           // current class?
00298           if ((*itr_C)->A.size() != (*itr_C)->B.size())
00299             return false;
00300 
00301           // Class *itr_C contains only one state of each automata?
00302           if ((*itr_C)->A.size() == 1)
00303           {
00304             // States *((*itr_C).A.begin()) and
00305             // *((*itr_C).B.begin()) have to be identified.
00306             int k = *((*itr_C)->A.begin());
00307             U.push_front(k);
00308             int l = *((*itr_C)->B.begin());
00309             a_.perm[k] = l;
00310             b_.perm[l] = k;
00311 
00312             // Just for coherence, lists A and B of class *itr_C are voided
00313             ((*itr_C)->A).erase((*itr_C)->A.begin());
00314             ((*itr_C)->B).erase((*itr_C)->B.begin());
00315             // Deletes current node and points to the next.
00316             itr_C = C_.erase(itr_C);
00317           }
00318           else
00319             itr_C++;
00320         }
00321         return true;
00322       }
00323 
00333       void
00334       list_det_trans(automaton_vars& av,
00335                      delta_t& delta_det,
00336                      const delta_t& delta_in_or_out,
00337                      int i)
00338       {
00339         state_list_t::const_iterator it = delta_in_or_out[i].begin();
00340         // Number of transitions with the same label
00341         int j = 1;
00342 
00343         for (it++; it != delta_in_or_out[i].end(); it++)
00344         {
00345           // It seems there is no iterator arithmetics in C++:
00346           // *(it_int - 1) doesn't compile.
00347           int k = *(--it);
00348           it++;
00349           // New label?
00350           if (av.s.transitions_labels[*it] != av.s.transitions_labels[k])
00351             // The last transition is deterministic?
00352             if (j == 1)
00353               delta_det[i].push_back(k);
00354           // Several transitions with the same label?
00355             else
00356               // Does nothing. A series of transitions with a new label begins.
00357               j = 1;
00358           // Same label?
00359           else
00360             j++;
00361         }
00362         // The last label visited is deterministic?
00363         if (j == 1)
00364         {
00365           delta_det[i].push_back(*(--it));
00366           it++;
00367         }
00368       }
00369 
00377       Trie *
00378       add_all_transitions_to_trie(const automaton_vars& av,
00379                                   int i)
00380       {
00381         // Vector all_transitions_lex contains the sequence of labels of
00382         // ingoing and outgoing transitions of state i in lex. order,
00383         // separated by a mark (-1)
00384         trans_t all_transitions_lex(av.s.delta_in[i].size() +
00385                                     av.s.delta_out[i].size() + 1);
00386 
00387         // First stores the sequence of ingoing transitions
00388         for (state_list_t::const_iterator it = av.s.delta_in[i].begin();
00389              it != av.s.delta_in[i].end(); ++it)
00390           all_transitions_lex.push_back(av.s.transitions_labels[*it]);
00391 
00392         all_transitions_lex.push_back(-1);
00393 
00394         // Next, outgoing transitions
00395         for (state_list_t::const_iterator it = av.s.delta_out[i].begin();
00396              it != av.s.delta_out[i].end(); ++it)
00397           all_transitions_lex.push_back(av.s.transitions_labels[*it]);
00398 
00399         // Gets the node of the correct Trie (Trie of initial, final or normal
00400         // states) for the sequence of transitions of state i
00401         if (av.aut.is_initial(av.s.states[i]))
00402           return T_I_.insert(all_transitions_lex);
00403         if (av.aut.is_final(av.s.states[i]))
00404           return T_T_.insert(all_transitions_lex);
00405 
00406         return T_Q_IT_.insert(all_transitions_lex);
00407       }
00408 
00419       bool
00420       analyse_det_trans()
00421       {
00422         state_list_t U;
00423 
00424         if (!construct_list_of_classes_with_one_state(U))
00425           return false;
00426 
00427         for (; !U.empty(); U.pop_front())
00428           if (!do_analyse_det_trans(U,
00429                                     a_.delta_det_in,
00430                                     b_.delta_det_in,
00431                                     a_.s.src_transitions,
00432                                     b_.s.src_transitions)
00433               || !do_analyse_det_trans(U,
00434                                        a_.delta_det_out,
00435                                        b_.delta_det_out,
00436                                        a_.s.dst_transitions,
00437                                        b_.s.dst_transitions))
00438             return false;
00439 
00440         return true;
00441       }
00442 
00443 
00444       bool
00445       do_analyse_det_trans(std::list<int>& U,
00446                            const delta_t& delta_det_A,
00447                            const delta_t& delta_det_B,
00448                            const trans_t& transitions_A,
00449                            const trans_t& transitions_B)
00450       {
00451         // Each state in U has already an image (perm_A and perm_B are
00452         // defined for this state)
00453 
00454         // i = current state in automaton A, j = its image in automaton B
00455         int i = U.front();
00456         int j = a_.perm[i];
00457 
00458         // As states i and j are already associated, they belong to
00459         // the same class, then have the same sequence of
00460         // deterministic transitions.
00461         state_list_t::const_iterator it = delta_det_A[i].begin();
00462         state_list_t::const_iterator it_aux = delta_det_B[j].begin();
00463         for (; it != delta_det_A[i].end(); ++it, ++it_aux)
00464         {
00465 
00466           // The states being considered are the sources of current
00467           // co-deterministic transitions (k for automaton A, l for B)
00468           int k = transitions_A[*it];
00469           int l = transitions_B[*it_aux];
00470 
00471           // Has state k already been visited?
00472           if (a_.perm[k] >= 0)
00473           {
00474             // If it has already been visited, does the current image
00475             // matches state l?
00476             if (a_.perm[k] != l)
00477               return false;
00478           }
00479           else
00480           {
00481             // State k has not already been visited. The same must be
00482             // true for state l.
00483             if (b_.perm[l] != -1)
00484               return false;
00485             // Tries to associate states k and l
00486 
00487             // Does k and l belongs to different classes?
00488             if (a_.class_state[k] != b_.class_state[l])
00489               return false;
00490             // The states k and l belong to the same class and can be
00491             // associated.
00492             a_.perm[b_.perm[l] = k] = l;
00493             // Removes k and l from theirs lists of states in theirs
00494             // classes (O(1))
00495             a_.class_state[k]->A.erase(a_.T_L[k]);
00496             b_.class_state[l]->B.erase(b_.T_L[l]);
00497             U.push_front(k);
00498             if (a_.class_state[k]->A.size() == 1)
00499             {
00500               // If it remains only one state of each
00501               // automaton in the class of the current states,
00502               // they must be associated. Then they are
00503               // putted in list U, and the class are removed
00504               // from C.
00505               // From now on k and l represent these states.
00506               Trie* T_aux = a_.class_state[k];
00507               k = T_aux->A.front();
00508               l = T_aux->B.front();
00509               a_.perm[b_.perm[l] = k] = l;
00510 
00511               U.push_front(k);
00512 
00513               // Removes class T_aux from C
00514               C_.erase(T_aux->L);
00515             }
00516           }
00517         }
00518         return true;
00519       }
00520 
00521 
00526       bool
00527       backtracking()
00528       {
00529         // Stores in l the number of non-fixed states
00530         int l = 0;
00531         for (std::list<Trie*>::iterator it = C_.begin();
00532              it != C_.end(); ++it)
00533           l += (*it)->A.size();
00534 
00535         // Vectors of classes of remaining states.      States in the same
00536         // class are stored contiguously, and in the case of vector for
00537         // automaton B, classes are separated by two enTries: one with -1,
00538         // denoting the end of the class, and the following with the
00539         // position where the class begins in this vector.
00540         trans_t C_A(l);
00541         trans_t C_B(l + 2 * C_.size());
00542         // current[i] = position in C_B of image of state C_A[i] during
00543         // backtracking.
00544         trans_t current(l);
00545 
00546 
00547         // Vector for test of correspondence of transitions of states already
00548         // attributed
00549         trans_t correspondence_transitions(a_.aut.states().size(), 0);
00550 
00551         list_remaining(C_A, C_B, current);
00552 
00553         // Tries to associate states of C_A and C_B
00554 
00555         int i = 0;
00556         bool rvalue = true;
00557 
00558         // Backtracking loop. Each iteration Tries to associate state
00559         // C_A[i]. If i = C_A.size(), the automata are isomorphic.
00560         while (i < static_cast<int>(C_A.size()))
00561         {
00562           int j;
00563           // Searches for the first free state in the class of C_A[i]
00564           for (j = current[i]; C_B[j] != -1 && b_.perm[C_B[j]] >= 0; j++)
00565             continue;
00566 
00567           // There is no possibility for state C_A[i]
00568           if (C_B[j] == -1)
00569           {
00570             // If there is no possibility for C_A[0], the automata are not
00571             // isomorphic
00572             if (i == 0)
00573               return false;
00574             else
00575             {
00576               // Prepares for backtracking in next iteration.
00577               // Image of C_A[i] is set to first state of its class
00578               current[i] = C_B[j + 1];
00579               // Next iteration will try to associate state i - 1
00580               // to next possible position
00581               i--;
00582               b_.perm[a_.perm[C_A[i]]] = -1;
00583               a_.perm[C_A[i]] = -1;
00584               current[i]++;
00585             }
00586           }
00587           // Tries to associate state C_A[i] to state C_B[j]
00588           else
00589           {
00590             current[i] = j;
00591             a_.perm[C_A[i]] = C_B[j];
00592             b_.perm[C_B[j]] = C_A[i];
00593 
00594             rvalue = (test_correspondence(a_.s.delta_in, b_.s.delta_in,
00595                                           a_.s.src_transitions,
00596                                           b_.s.src_transitions,
00597                                           C_A, C_B, i, j,
00598                                           correspondence_transitions)
00599                       && test_correspondence(a_.s.delta_out, b_.s.delta_out,
00600                                              a_.s.dst_transitions,
00601                                              b_.s.dst_transitions,
00602                                              C_A, C_B, i, j,
00603                                              correspondence_transitions));
00604 
00605             // States C_A[i] and C_B[j] can be associated.
00606             if (rvalue)
00607               // Tries to associate state in C_A[i + 1] in next iteration
00608               i++;
00609             // Impossible to associate C_A[i] to C_B[j]
00610             else
00611             {
00612               // Tries C_A[i] to C_B[j + 1] in next iteration
00613               b_.perm[a_.perm[C_A[i]]] = -1;
00614               a_.perm[C_A[i]] = -1;
00615               current[i]++;
00616             }
00617           }
00618         }
00619         return rvalue;
00620       }
00621 
00627       void
00628       list_remaining(trans_t& C_A,
00629                      trans_t& C_B,
00630                      trans_t& current)
00631       {
00632         int i = 0, j = 0;
00633         for (std::list<Trie*>::iterator it = C_.begin(); it != C_.end();
00634              it++)
00635         {
00636           state_list_t::iterator it_A = (*it)->A.begin();
00637           state_list_t::iterator it_B = (*it)->B.begin();
00638           C_A[i] = *it_A;
00639           C_B[j] = *it_B;
00640           current[i++] = j++;
00641           for (it_A++, it_B++; it_A != (*it)->A.end();
00642                it_A++, it_B++)
00643           {
00644             C_A[i] = *it_A;
00645             C_B[j++] = *it_B;
00646             current[i] = current[i - 1];
00647             i++;
00648           }
00649           // End of class
00650           C_B[j++] = -1;
00651           // Position where the class begins
00652           C_B[j++] = current[i - 1];
00653         }
00654       }
00655 
00660       bool
00661       test_correspondence(const delta_t& delta_A,
00662                           const delta_t& delta_B,
00663                           const trans_t& transitions_A,
00664                           const trans_t& transitions_B,
00665                           trans_t& C_A,
00666                           trans_t& C_B,
00667                           int i,
00668                           int j,
00669                           trans_t& correspondence_transitions)
00670       {
00671         state_list_t::const_iterator it_A = delta_A[C_A[i]].begin();
00672         state_list_t::const_iterator it_B = delta_B[C_B[j]].begin();
00673 
00674         // Each iteration considers a sequence of ingoing labels
00675         // with the same label. The sequence begins at it_int
00676         while (it_A != delta_A[C_A[i]].end())
00677         {
00678           // Searches for sources of ingoing transitions for current
00679           // label that have already been associated. For each state
00680           // visited, its position in correspondence_transitions is
00681           // incremented.
00682           int k = 0;
00683           state_list_t::const_iterator it_aux;
00684           for (it_aux = it_A;
00685                (it_aux != delta_A[C_A[i]].end()) &&
00686                  (a_.s.transitions_labels[*it_aux] ==
00687                   a_.s.transitions_labels[*it_A]);
00688                it_aux++, k++)
00689             // Is the source of current transition associated?
00690             if (a_.perm[transitions_A[*it_aux]] >= 0)
00691               correspondence_transitions[transitions_A[*it_aux]]++;
00692 
00693           // Here, k = number of ingoing transitions for current label
00694 
00695           // Idem for ingoing transitions of state C_B[j], but positions in
00696           // correspondence_transitions are decremented.
00697           for (; (k > 0); it_B++, k--)
00698             // Has the source of current transition already been visited?
00699             if (b_.perm[transitions_B[*it_B]] >= 0)
00700               {
00701               // Trying to decrement a position with 0 means that the
00702               // corresponding state in A is not correct.
00703                 if (correspondence_transitions[b_.perm[transitions_B[*it_B]]]
00704                     == 0)
00705                   // The association of C_A[i] and C_B[j] is impossible
00706                   return false;
00707                 else
00708                   correspondence_transitions[b_.perm[transitions_B[*it_B]]]--;
00709               }
00710 
00711           // Verifies correspondence_transitions. The correspondence for
00712           // current label is correct iff correspondence_transitions[l] = 0
00713           // for all src l of ingoing transitions of C_A[i] labelled by
00714           // the current label.
00715           // For this, int_itr visits all transitions until int_itr_aux.
00716 
00717           for (; it_A != it_aux; it_A++)
00718           {
00719             if (a_.perm[transitions_A[*it_A]] >= 0)
00720               if (correspondence_transitions[transitions_A[*it_A]] != 0)
00721                 return false;
00722             // All positions must be 0 for next iteration
00723             correspondence_transitions[transitions_A[*it_A]] = 0;
00724           }
00725 
00726         }
00727         return true;
00728       }
00729 
00730 
00731 
00732       //Private Attributes
00733       automaton_vars a_;
00734       automaton_vars b_;
00735       std::list<Trie*> C_;
00736       // Tries of classes of normal, initial and final states.
00737       Trie T_Q_IT_;
00738       Trie T_I_;
00739       Trie T_T_;
00740   };
00741 
00742 
00743   /*---------------.
00744   | are_isomorphic |
00745   `---------------*/
00746 
00747   template<typename A, typename T>
00748   bool
00749   are_isomorphic(const Element<A, T>& a, const Element<A, T>& b)
00750   {
00751     BENCH_TASK_SCOPED("are_isomorphic");
00752 
00753     Isomorpher<A, T> isomorpher(a, b);
00754 
00755     return isomorpher();
00756   }
00757 
00758 } // vcsn
00759 
00760 #endif // ! VCSN_ALGORITHMS_ISOMORPH_HXX