Информация об изменениях

Сообщение Re: Перевод понимания из интуиции в логику от 20.11.2020 23:51

Изменено 20.11.2020 23:57 xma

Старый текст
Новый текст
Разница

Re: Перевод понимания из интуиции в логику

Здравствуйте, Khimik, Вы писали:

K>У меня возникла такая задача: определить в молекуле все циклы (точнее, ароматические циклы). Молекула – это набор атомов с декартовыми координатами и связей между ними. Например в этой молекуле два цикла по 6 атомов:

вкртаце, чтобы получить число наикратчайших замкнутых путей (циклов), (синтаксис приблизительный

)

для начала надо разработать структуру хранения данных

Скрытый текст

struct cycle_data {
   int cycle_index = -1; // ну понятно такая инициализация - не прокатит, надо переписать нормально
   int cycle_deep_length = -1; //
};

struct atom {
    int index = -1; // 
    int deep_counter = -1; // 
    std::vector <cycle_data> cycles_index;
    bool have_cycles = false;
    
    std::vector <struct atom *> neighborhoods;
};

для начала найдём все атомы — присвоим каждому индекс и поместим в массив

Скрытый текст

vector <struct atom *> atoms;

void find_atoms( struct atom * atom_ ) { // рекурсивненько

   if (NULL == atom_) return;
   
   if (atom_->index >= 0) return;
   
   atom_->index = atoms.size();
   atoms.push_back(atom_); 
   
   for (int i = 0; i<atom_->neighborhoods.size(); ++i) {
    find_atoms( atom_->neighborhoods[i] );
   }
}

далее, напишем метод нахождения первого попавшегося кратчайшего замкнутого пути из атомов (для цикла)

Скрытый текст

/* 
рекурсивненько обходим весь граф, сохраняя при каждом шаге рекурсии - глубину (количество) шагов (deep_counter) в проходимом атоме, чтобы при напарывании на атом с меньшей глубиной (расстоянием до эталона атома atom_ref) - мы текущую ветвь рекурсии отбрасывали .. и сохраняем в cycle_data в атоме - текущий номер цикла и количество атомов в нём (да, тут криво сделано - по идее лучше бы через hash_map и т.п., но мне лень и я уже спать хочу)

возвращает глубину пути (первую попавшуюся минимальную), (-1 нет пути)
*/ 
int find_least_way( struct atom * atom_, int way_deep, const struct atom * atom_ref, const int cycle_index ) {

   if (NULL == atom_ref) return -1;
   if (NULL == atom_) return -1;
   
   if (atom_ref->neighborhoods.size() <= 1) return -1;
   if (atom_->neighborhoods.size() <= 1) return -1;

   atom_->deep_counter = way_deep;
  
   int new_way_deep = INT_MAX;
   bool have_a_way = false; 
   for (int i = 0; i<atom_->neighborhoods.size(); ++i) {
   
       if (atom_ref == atom_->neighborhoods[i] ) {
            return 1;
       }

        
        if ( atom_->neighborhoods[i]->deep_counter >= 0 ) {
            if ( atom_->neighborhoods[i]->deep_counter <= way_deep) continue;
        }
        
        int temp_new_way_deep = find_least_way( atom_->neighborhoods[i], way_deep + 1, atom_ref );        
        
        if (temp_new_way_deep < 0) continue; // нудевых указателей - не должно быть
        
        if ( temp_new_way_deep < new_way_deep ) {
           new_way_deep = temp_new_way_deep;
           have_a_way = true; 
        }
   }
   
   if (false == have_a_way) return -1;
   
   atom_->cycles_index.resize( cycle_index + 1 );
   atom_->cycles_index[cycle_index].cycle_index = cycle_index;
   atom_->cycles_index[cycle_index].cycle_deep_length = way_deep + new_way_deep;
  
   return new_way_deep;
}

Скрытый текст


void clear_deep_counters() {
   for (int i=0; i<atoms.size(); ++i) {
     atoms[i]->deep_counter = -1;
   }
}

// ставит флаг (have_cycles) вхождения атома в цикл в true или false, а также - очищает следы в атомах от более длинных чем наименьший циклы (/пути)
void delete_temp_cycle_indices ( const int cycle_index ) {

   for (int k=0; k<cycle_index; ++k) {
       for ( int i=0; i<atoms.size(); ++i ) {
          if ( k >= atoms[i]->cycles_index.size() ) continue;
          
          for ( int j=0; j<atoms.size(); ++j ) {
             if ( atoms[j]->cycles_index[k].cycle_deep_length > atoms[i]->cycles_index[k].cycle_deep_length ) {
                 atoms[j]->cycles_index[k].cycle_index = -1;
                 atoms[j]->cycles_index[k].cycle_deep_length = -1;
             }
          }
       }
   }
   
   for ( int i=0; i<atoms.size(); ++i ) {
      atoms[i]->have_cycles = false;
      
      if ( atoms[i]->cycles_index.size() <= 0 ) continue;
      
      const int n = (cycle_index > atoms[i]->cycles_index.size() ) ? atoms[i]->cycles_index.size() : cycle_index;
      for (int k=0; k<n; ++k) {
          if ( (atoms[i]->cycles_index[k].cycle_index >= 0) &&(atoms[i]->cycles_index[k].cycle_deep_length >= 3)) {
             atoms[i]->have_cycles = true;
             break;
          }
      }
   }
};

/*
ну и главная функция - запихивает все атомы в массив, далее для каждого ещё не попавшегося в цикл - пытается его (цикл) найти .. 

по итогу работы функции - в массиве atoms - атомы с отметками (have_cycles) о том входят ли они в циклы (хотя бы в один) и в cycles_index в атомах - номер (индекс) цикла и количество атомов в нём .. 

возвращает количество циклов (cycle_index) в графе .. 
*/
int find_num_cycles (struct atom * first_atom) {

   find_atoms( first_atom ); // atoms;
   
   int cycle_index = 0;
   for (int i=0; i<atoms.size(); ++i) {
   
       //if ( (atoms[i]->cycles_index.size() > 0) && () ) continue;
       
       if ( atoms[i]->have_cycles ) continue;
       
       clear_deep_counters(); 
       
       if ( find_least_way( atoms[i], 0, atoms[i], cycle_index ) >= 3) {   
          ++cycle_index;
       }
   }
   
   delete_temp_cycle_indices( cycle_index );

   return cycle_index;
};

щаз понял, что если как соты фигачится будут циклы с атомами — то надо будет дополнительно сохранять массив индексов атомов каждого цикла в каждый атом, и уже по каждому атому пробегаться (по аналогии с методом выше) — и сравнивать все индексы (цикла), при их полной одинаковости — считать совпадающие атомы одним циклом ..

понятно что может можно и похэшить для оптимизации и т.д., но это уже другой вопрос .. я так понял человеку — надо для начала просто чтобы работало ..

вообщем я спать, код тот (выше) на скорую руки набацал ночью — но для понимания общей идеи думаю пойдёт ..

P.S.:

Re: Перевод понимания из интуиции в логику

)

для начала надо разработать структуру хранения данных

Скрытый текст

struct cycle_data {
   int cycle_index = -1; // ну понятно такая инициализация - не прокатит, надо переписать нормально
   int cycle_deep_length = -1; //
};

struct atom {
    int index = -1; // 
    int deep_counter = -1; // 
    std::vector <cycle_data> cycles_index;
    bool have_cycles = false;
    
    std::vector <struct atom *> neighborhoods;
};

для начала найдём все атомы — присвоим каждому индекс и поместим в массив

Скрытый текст

vector <struct atom *> atoms;

void find_atoms( struct atom * atom_ ) { // рекурсивненько

   if (NULL == atom_) return;
   
   if (atom_->index >= 0) return;
   
   atom_->index = atoms.size();
   atoms.push_back(atom_); 
   
   for (int i = 0; i<atom_->neighborhoods.size(); ++i) {
    find_atoms( atom_->neighborhoods[i] );
   }
}

далее, напишем метод нахождения первого попавшегося кратчайшего замкнутого пути из атомов (для цикла)

Скрытый текст

/* 
рекурсивненько обходим весь граф, сохраняя при каждом шаге рекурсии - глубину (количество) шагов (deep_counter) в проходимом атоме, чтобы при напарывании на атом с меньшей глубиной (расстоянием до эталона атома atom_ref) - мы текущую ветвь рекурсии отбрасывали .. и сохраняем в cycle_data в атоме - текущий номер цикла и количество атомов в нём (да, тут криво сделано - по идее лучше бы через hash_map и т.п., но мне лень и я уже спать хочу)

возвращает глубину пути (первую попавшуюся минимальную), (-1 нет пути)
*/ 
int find_least_way( struct atom * atom_, int way_deep, const struct atom * atom_ref, const int cycle_index ) {

   if (NULL == atom_ref) return -1;
   if (NULL == atom_) return -1;
   
   if (atom_ref->neighborhoods.size() <= 1) return -1;
   if (atom_->neighborhoods.size() <= 1) return -1;

   atom_->deep_counter = way_deep;
  
   int new_way_deep = INT_MAX;
   bool have_a_way = false; 
   for (int i = 0; i<atom_->neighborhoods.size(); ++i) {
   
       if (atom_ref == atom_->neighborhoods[i] ) {
            return 1;
       }

        
        if ( atom_->neighborhoods[i]->deep_counter >= 0 ) {
            if ( atom_->neighborhoods[i]->deep_counter <= way_deep) continue;
        }
        
        int temp_new_way_deep = find_least_way( atom_->neighborhoods[i], way_deep + 1, atom_ref );        
        
        if (temp_new_way_deep < 0) continue; // нудевых указателей - не должно быть
        
        if ( temp_new_way_deep < new_way_deep ) {
           new_way_deep = temp_new_way_deep;
           have_a_way = true; 
        }
   }
   
   if (false == have_a_way) return -1;
   
   atom_->cycles_index.resize( cycle_index + 1 );
   atom_->cycles_index[cycle_index].cycle_index = cycle_index;
   atom_->cycles_index[cycle_index].cycle_deep_length = way_deep + new_way_deep;
  
   return new_way_deep;
}

Скрытый текст


void clear_deep_counters() {
   for (int i=0; i<atoms.size(); ++i) {
     atoms[i]->deep_counter = -1;
   }
}

// ставит флаг (have_cycles) вхождения атома в цикл в true или false, а также - очищает следы в атомах от более длинных чем наименьший циклы (/пути)
void delete_temp_cycle_indices ( const int cycle_index ) {

   for (int k=0; k<cycle_index; ++k) {
       for ( int i=0; i<atoms.size(); ++i ) {
          if ( k >= atoms[i]->cycles_index.size() ) continue;
          
          for ( int j=0; j<atoms.size(); ++j ) {
             if ( atoms[j]->cycles_index[k].cycle_deep_length > atoms[i]->cycles_index[k].cycle_deep_length ) {
                 atoms[j]->cycles_index[k].cycle_index = -1;
                 atoms[j]->cycles_index[k].cycle_deep_length = -1;
             }
          }
       }
   }
   
   for ( int i=0; i<atoms.size(); ++i ) {
      atoms[i]->have_cycles = false;
      
      if ( atoms[i]->cycles_index.size() <= 0 ) continue;
      
      const int n = (cycle_index > atoms[i]->cycles_index.size() ) ? atoms[i]->cycles_index.size() : cycle_index;
      for (int k=0; k<n; ++k) {
          if ( (atoms[i]->cycles_index[k].cycle_index >= 0) &&(atoms[i]->cycles_index[k].cycle_deep_length >= 3)) {
             atoms[i]->have_cycles = true;
             break;
          }
      }
   }
};

/*
ну и главная функция - запихивает все атомы в массив, далее для каждого ещё не попавшегося в цикл - пытается его (цикл) найти .. 

по итогу работы функции - в массиве atoms - атомы с отметками (have_cycles) о том входят ли они в циклы (хотя бы в один) и в cycles_index в атомах - номер (индекс) цикла и количество атомов в нём .. 

возвращает количество циклов (cycle_index) в графе .. 
*/
int find_num_cycles (struct atom * first_atom) {

   find_atoms( first_atom ); // atoms;
   
   int cycle_index = 0;
   for (int i=0; i<atoms.size(); ++i) {
   
       //if ( (atoms[i]->cycles_index.size() > 0) && () ) continue;
       
       if ( atoms[i]->have_cycles ) continue;
       
       clear_deep_counters(); 
       
       if ( find_least_way( atoms[i], 0, atoms[i], cycle_index ) >= 3) {   
          ++cycle_index;
       }
   }
   
   delete_temp_cycle_indices( cycle_index );

   return cycle_index;
};

P.S.: ну и сохранять дополнительно придётся — все одинаковые минимальные длины пути (циклы), а не только первый попавшийся минимальный цикл (/путь) — для каждого атома ..