src/lib-gmapkernel/g-map-vertex/gmv-isomorphisme.cc

Go to the documentation of this file.

/*
 * lib-gmapkernel : Un noyau de 3-G-cartes et des opérations.
 * Copyright (C) 2004, Moka Team, Université de Poitiers, Laboratoire SIC
 *               http://www.sic.sp2mi.univ-poitiers.fr/
 * Copyright (C) 2009, Guillaume Damiand, CNRS, LIRIS,
 *               guillaume.damiand@liris.cnrs.fr, http://liris.cnrs.fr/
 *
 * This file is part of lib-gmapkernel
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

//******************************************************************************
#include "g-map-vertex.hh"
#include "chrono.hh"
#include <iostream>
using namespace std;
using namespace GMap3d;
//******************************************************************************
int CGMapVertex::findMotif( CGMapVertex* AMap )
{
   int index = getNewDirectInfo();

   int markTreated  = getNewMark();
   int markTreated2 = AMap->getNewMark();
   bool matchOne = false;
   bool matchAll = true;

   CChrono c;
   c.start();
   
   CDynamicCoverageAll it1(this);
   CDynamicCoverageAll it2(AMap);
   
   for ( ; it1.cont(); ++it1 )
     setDirectInfo(*it1, index, NULL);
   
   for ( it1.reinit(); matchAll && it1.cont(); ++it1 )
     {
       if ( getDirectInfo(*it1,index)==NULL )
         {
           matchOne = false;
           for ( it2.reinit(); !matchOne && it2.cont(); ++it2 )
             {
               matchOne=findMotifFrom(*it1, markTreated, index,
                                      AMap, *it2, markTreated2);

               unmarkMotifMark(*it1,markTreated,(matchOne?-1:index),
                               AMap,*it2,(matchOne?-1:markTreated2));

               // assert( isWholeMapUnmarked(markTreated) );
             }

           if ( !matchOne ) matchAll = false;
         }
     }

   freeMark(markTreated);

   AMap->unmarkAll(markTreated2);
   AMap->freeMark(markTreated2);

   c.stop();
   c.display("Temps de recherche du motif");
   
   if ( !matchAll )
     {
       freeDirectInfo(index);
       return -1;
     }

   return index;
}
//******************************************************************************
unsigned int CGMapVertex::countNumberOfMotifs( CGMapVertex* AMap )
{
  unsigned int res = 0;
  int index = getNewDirectInfo();
  
  int markTreated  = getNewMark();
  int markTreated2 = AMap->getNewMark();
  bool match = false;


  CChrono c; c.start();
  
  CDynamicCoverageAll it1(this);
  CDynamicCoverageAll it2(AMap);
  
  for ( ; it1.cont(); ++it1 )
    setDirectInfo(*it1, index, NULL);
  it1.reinit();
  
  for ( it2.reinit(); it2.cont(); ++it2 )
    {
      match=findMotifFrom(*it1, markTreated, index,
                          AMap, *it2, markTreated2);

      unmarkMotifMark(*it1,markTreated,index,
                      AMap,*it2,markTreated2);

      if ( match ) ++res;
      // assert( isWholeMapUnmarked(markTreated) );
    }

   freeMark(markTreated);
   AMap->freeMark(markTreated2);

   c.stop();
   c.display("Temps de recherche de tout les motifs");
   
   freeDirectInfo(index);

   return res;
}
//******************************************************************************
void CGMapVertex::unmarkMotifMark(CDart* ADart, int AMark, int AIndex,
                                  CGMapVertex* AMap, CDart* ADart2, int AMark2)
{
  if ( !isMarked(ADart, AMark) ) return;
  
  stack<CDart*> toTreat;
  stack<CDart*> toTreat2;

   toTreat.push(ADart);
   toTreat2.push(ADart2);
   
   CDart* current;
   CDart* other;
   int i;
   
   while (!toTreat.empty())
   {
      current = toTreat.top(); toTreat.pop();
      other = toTreat2.top(); toTreat2.pop();

      if ( isMarked(current, AMark) )
      {         
        for ( i=0; i<=3; ++i )
          if ( isMarked(alpha(current,i), AMark) )
            {
              toTreat.push(alpha(current,i));   
              toTreat2.push(AMap->alpha(other,i));      
            }
        
        unsetMark(current, AMark);
        if ( AMark2!=-1 ) AMap->unsetMark(other, AMark2);
        if ( AIndex!=-1 ) setDirectInfo(current, AIndex, NULL);
      }
   }
}
//******************************************************************************
bool CGMapVertex::findMotifFrom( CDart* AFromDart, unsigned int AMarkTreated,
                                 unsigned int AIndex,
                                 CGMapVertex* AMap, CDart* ADestDart,
                                 unsigned int AMarkTreated2 )
{
   bool match = true;
   int i = 0;

   // Les 2 piles pour parcourir les 2 cartes en parallèle.
   stack<CDart*> toTreat;
   stack<CDart*> toTreat2;

   toTreat.push(AFromDart);
   toTreat2.push(ADestDart);

   // Le parcours, tant que la pile n'est pas vide.
   CDart* current;
   CDart* other;

   while (match && !toTreat.empty())
   {
      // Le prochain brin.
      current = toTreat.top();  toTreat.pop();
      other   = toTreat2.top(); toTreat2.pop();

      if ( !isMarked(current, AMarkTreated) )
        {
          if ( AMap->isMarked(other, AMarkTreated2) )
            match = false;
          else
            {         
              // On fixe l'injection.
              setDirectInfo(current, AIndex, other);
              
              setMark(current, AMarkTreated);
              AMap->setMark(other, AMarkTreated2);
              
              // On teste si l'injection est valide avec les voisins.
              // On sort dès qu'il y a un problème.
              for ( i=0; match && i<=3; ++i )
                {
                  if ( !isFree(current,i) )
                    {
                      if (isMarked(alpha(current,i), AMarkTreated) )
                        {
                          if ( getDirectInfoAsDart(alpha(current,i), AIndex)!=
                               AMap->alpha(other,i) )
                            match = false;
                        }
                      else
                        {
                          if ( AMap->isMarked(AMap->alpha(other,i),AMarkTreated2) )
                            match = false;
                          else
                            {
                              toTreat.push(alpha(current,i));
                              toTreat2.push(AMap->alpha(other,i));
                            }
                        }
                    }
                  else
                    {
                      if (!AMap->isFree(other,i) &&
                          AMap->isMarked(AMap->alpha(other,i),AMarkTreated2) )
                        match = false;
                    }
                }
            }     
        }
   }
   
   return match;
}
//******************************************************************************

---