buildable_atom_algorithms.h

Go to the documentation of this file.

// -*- mode: c++; -*-
//
//The Biomolecule Toolkit (BTK) is a C++ library for use in the
//modeling, analysis, and design of biological macromolecules.
//Copyright (C) 2004, Christopher Saunders <ctsa@users.sourceforge.net>
//
//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 2.1 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, write to the Free Software Foundation, 
//Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.


#ifndef BUILDABLE_ATOM_ALGORITHMS_H
#define BUILDABLE_ATOM_ALGORITHMS_H


#include "atom_algorithms.h"
#include "buildable_atom.h"
#include "linear_algebra.h"

#include <boost/concept_check.hpp>

#include <iterator>
#include <queue>
#include <set>


namespace BTK {



  template <typename AtomType>
  void 
  add_bond(AtomType& first,
           AtomType& last);

  template <typename AtomType>
  unsigned
  bond_distance_4(AtomType& a1, 
                  AtomType& a2);

  template <typename AtomIterator>
  void
  build(AtomIterator first,
        AtomIterator last);

  // implementation: runs bredth-first search to find the closest
  // buildable atom to build off of, and tries to rebuild atoms back
  // toward the target atom, until target atom becomes buildable
  //
  template <typename AtomType>
  void
  build_atom(AtomType& a);

#if 0
  template <typename AtomIterator>
  void
  conservative_build(AtomIterator first,
                     AtomIterator last);
#endif

  template <typename AtomType>
  void 
  restricted_rotate(AtomType& start,
                    AtomType& boundary,
                    double delta_angle);

  template <typename AtomType, typename UnaryFunction>
  UnaryFunction
  for_each_buildable_atom(AtomType& start, 
                          AtomType& boundary, 
                          UnaryFunction func);

  
} // namespace BTK  






// implementation
//

namespace BTK{
  namespace Internal{
    template <typename AtomType, typename UnaryFunction>
    void
    for_each_buildable_atom_iter(AtomType& a, 
                                 std::set<AtomType*>& visited, 
                                 UnaryFunction func);

    template <typename AtomType>
    void
    cache_bond_distance_4(AtomType& a);

    template <typename AtomType>
    void
    cache_bond_distance_4_iter(AtomType& start,
                               AtomType& boundary,
                               AtomType& a1,
                               unsigned dist);

    template <typename AtomType>
    bool
    build_atom_iter(std::set<AtomType*>& visited,
                    std::queue<AtomType*>& bfs_queue,
                    std::map<AtomType*,AtomType*>& traceback);

    template <typename AtomType>
    void
    build_atom_traceback(AtomType& a,
                         std::map<AtomType*,AtomType*>& traceback);
  }
}



template <typename AtomType>
void 
BTK::
add_bond(AtomType& first,
         AtomType& last)
{
  first.add_adjacent(last);
  last.add_adjacent(first);

}


template <typename AtomType>
unsigned
BTK::
bond_distance_4(AtomType& a1, 
                AtomType& a2)
{
  // requires BuildableAtom
  boost::function_requires<boost::ConvertibleConcept<AtomType,BuildableAtom> >();

  AtomType* ap1 = &a1;
  AtomType* ap2 = &a2;
  if(ap1 == ap2) return 0;
  else if(ap1 > ap2) std::swap(ap1,ap2);

  if(! ap1->is_bond_distance_cached()) {
    Internal::cache_bond_distance_4(*ap1);
    ap1->set_is_bond_distance_cached(true);
  }

  return ap1->bond_distance_4(*ap2);
}

template <typename AtomIterator>
void
BTK::
build(AtomIterator first,
      AtomIterator last)
{
  for(;first!=last;++first){
    build_atom(*first);
  }
}

// run bfs search for built atoms to build atom a from
template <typename AtomType>
void
BTK::
build_atom(AtomType& a)
{
  // bfs search for closest built atom
  if(a.build()) return;

  std::set<AtomType*> visited;
  std::queue<AtomType*> bfs_queue;
  std::map<AtomType*,AtomType*> traceback;

  visited.insert(&a);
  bfs_queue.push(&a);
  traceback[&a] = 0;

  bool result = Internal::build_atom_iter(visited,bfs_queue,traceback);

  // if nothing found to build off of, then bootstrap
  if(!result) a.boot_build();
}


template <typename AtomType>
void 
BTK::
restricted_rotate(AtomType& start,
                  AtomType& boundary,
                  double delta_angle)
{
  boost::function_requires<boost::ConvertibleConcept<AtomType,BuildableAtom> >();

  BTKMatrix rot_matrix( create_rotation_matrix(start.position()-boundary.position(),delta_angle) );
  BTKVector rot_offset( prec_prod(rot_matrix,-boundary.position())+boundary.position() ); 
  
  for_each_buildable_atom(start,boundary,atom_rotator<AtomType>(rot_matrix,rot_offset));
}


template <typename AtomType, typename UnaryFunction>
UnaryFunction
BTK::
for_each_buildable_atom(AtomType& start, 
                        AtomType& boundary, 
                        UnaryFunction func)
{
  boost::function_requires<boost::ConvertibleConcept<AtomType,BuildableAtom> >();

  std::set<AtomType*> visited;
  
  visited.insert(&start);
  visited.insert(&boundary);
  Internal::for_each_buildable_atom_iter(start,visited,func);
  return func;
}





// private implementation
//
template <typename AtomType, typename UnaryFunction>
void
BTK::Internal::
for_each_buildable_atom_iter(AtomType& a,
                             std::set<AtomType*>& visited,
                             UnaryFunction func)
{
  typename BuildableAtom::adjacent_iterator ai=a.adjacent_begin(), ai_end=a.adjacent_end();

  for (;ai!=ai_end;ai++){
    if( visited.find(static_cast<AtomType*>(*ai)) == visited.end() ){
      visited.insert(static_cast<AtomType*>(*ai));
      func(*static_cast<AtomType*>(*ai));
      for_each_buildable_atom_iter(*static_cast<AtomType*>(*ai),visited,func);
    }
  }
}

template <typename AtomType>
void
BTK::Internal::
cache_bond_distance_4(AtomType& a)
{
  //
  //  std::cerr << "cached_bond_dist atom: " << a.position() << " " << ELEMENT::name(a.element()) << std::endl;
  cache_bond_distance_4_iter(a,a,a,0);
}


template <typename AtomType>
void
BTK::Internal::
cache_bond_distance_4_iter(AtomType& start,
                           AtomType& boundary,
                           AtomType& a1,
                           unsigned dist)
{
  dist += 1;

  BuildableAtom::const_adjacent_iterator ai=start.adjacent_begin(),ai_end=start.adjacent_end();
  for (;ai!=ai_end;++ai){
    AtomType& a2 = *static_cast<AtomType*>(*ai);
    if(&a2 == &boundary) continue;

    AtomType* ap1 = &a1;
    AtomType* ap2 = &a2;
    if( ap1 > ap2 ) std::swap(ap1,ap2);
    if( dist < ap1->bond_distance_4(*ap2) ){
      ap1->set_bond_distance_4(*ap2,dist);
    }
    if( dist < 4 ) cache_bond_distance_4_iter(a2,start,a1,dist);
  }
}


template <typename AtomType>
bool
BTK::Internal::
build_atom_iter(std::set<AtomType*>& visited,
                std::queue<AtomType*>& bfs_queue,
                std::map<AtomType*,AtomType*>& traceback)
{
  AtomType& a = *(bfs_queue.front());
  bfs_queue.pop();
  bool are_any_built = false;

  BuildableAtom::adjacent_iterator ai=a.adjacent_begin(),ai_end=a.adjacent_end();
  for(;ai!=ai_end;++ai){
    AtomType& a2 = *static_cast<AtomType*>(*ai);

    if(visited.find(&a2) != visited.end()) continue;

    if(!a2.is_built()) {
      if(a2.build()) {
        // succesful new build, now use traceback to build back
        // towards original goal, starting a new bfs build search on
        // any atoms that cause trouble along the way
        //
        build_atom_traceback(a,traceback);
        return true;
      }
    } else {
      are_any_built = true;
    }
 
    traceback[&a2] = &a;
    visited.insert(&a2);
    bfs_queue.push(&a2);
  }

  while(! bfs_queue.empty() ){
    bool result = build_atom_iter(visited,bfs_queue,traceback);
    if(result) are_any_built = true;
  }
  return are_any_built;
}


template <typename AtomType>
void
BTK::Internal::
build_atom_traceback(AtomType& a,
                     std::map<AtomType*,AtomType*>& traceback)
{
  if(!a.build()){
    // start a totally fresh bfs on a
    build_atom(a);
    if(!a.is_built()) return;
  }
  AtomType* a2 = traceback[&a];
  if(!a2) return;
  build_atom_traceback(*a2,traceback);
}



#endif

---