BALL: molecularGraph.h Source File

00001 // -*- Mode: C++; tab-width: 2; -*-
00002 // vi: set ts=2:
00003 //
00004 // $Id: molecularGraph.h,v 1.12.6.1 2007/03/25 21:25:28 oliver Exp $
00005 //
00006 
00007 #ifndef BALL_STRUCTURE_MOLECULARGRAPH_H
00008 #define BALL_STRUCTURE_MOLECULARGRAPH_H
00009 
00010 #ifndef BALL_KERNEL_ATOM_H
00011 # include <BALL/KERNEL/atom.h>
00012 #endif
00013 
00014 #ifndef BALL_KERNEL_BOND_H
00015 # include <BALL/KERNEL/bond.h>
00016 #endif
00017 
00018 #ifndef BALL_STRUCTURE_MOLECULE_H
00019 # include <BALL/KERNEL/molecule.h>
00020 #endif
00021 
00022 #ifndef BALL_STRUCTURE_FRAGMENT_H
00023 # include <BALL/KERNEL/fragment.h>
00024 #endif
00025 
00026 #include <list>
00027 #include <iostream>
00028 #include <algorithm>
00029 
00030 namespace BALL
00031 {
00032   // forward declarations to resolve nasty dependencies
00033   template <typename Node, typename Edge> 
00034   class EdgeItem;
00035 
00036   template <typename Node, typename Edge> 
00037   class TMolecularGraph;
00038 
00042   template <typename Node, typename Edge>
00043   class NodeItem
00044   {
00045     public:
00049 
00050     typedef NodeItem<Node, Edge> NodeItemType;
00051 
00053     typedef EdgeItem<Node, Edge> EdgeItemType;
00054 
00056     typedef typename std::list<EdgeItem<Node, Edge>*>::iterator Iterator;
00058     typedef typename std::list<EdgeItem<Node, Edge>*>::const_iterator ConstIterator;
00060 
00061     friend class TMolecularGraph<Node, Edge>;
00062 
00063     NodeItem() ;
00064     NodeItem(const Atom& atom) ;
00065 
00066     Node& getData() ;
00067     const Node& getData() const ;
00068     void setData(const Node& data) ;
00069 
00070     const Atom* getAtom() const ;
00071     Atom* getAtom() ;
00072 
00073     Iterator begin() ;
00074     ConstIterator begin() const ;
00075     Iterator end() ;
00076     ConstIterator end() const ;
00077 
00078     Size getDegree() const ;
00079 
00080     bool operator == (const NodeItem& item) const ;
00081     bool operator != (const NodeItem& item) const ;
00082 
00083     protected:
00084 
00085     void deleteEdge_(EdgeItemType* item)
00086       ;
00087 
00088     Node  data_;
00089     Atom* atom_;
00090     std::list<EdgeItemType*> adjacent_edges_;
00091   };
00092 
00093 
00094   template <typename Node, typename Edge>
00095   class EdgeItem
00096   {
00097     public:
00098     typedef NodeItem<Node, Edge> NodeItemType;
00099     typedef EdgeItem<Node, Edge> EdgeItemType;
00100     typedef typename std::list<NodeItem<Node, Edge>*>::iterator Iterator;
00101     typedef typename std::list<NodeItem<Node, Edge>*>::const_iterator ConstIterator;
00102 
00103     EdgeItem() 
00104       : bond_(0), source_(0), target_(0)
00105     {}
00106 
00107     EdgeItem(const Bond& bond);
00108     EdgeItem(const Bond& bond, NodeItemType* source, NodeItemType* target);
00109 
00110     NodeItemType& getSource() {return *source_;}
00111     NodeItemType& getTarget() {return *target_;}
00112     const NodeItemType& getSource() const {return *source_;}
00113     const NodeItemType& getTarget() const {return *target_;}
00114     
00115     Node& getData() {return data_;}
00116     const Node& getData() const {return data_;}
00117     void setData(const Edge& data) { data_ = data; };
00118 
00119     Bond* getBond() { return bond_; }
00120     const Bond* getBond() const { return bond_; }
00121 
00122     bool operator == (const EdgeItem& item) const { return (bond_ == item.bond_); }
00123     bool operator != (const EdgeItem& item) const { return (bond_ != item.bond_); }
00124 
00125     protected:
00126     Edge  data_;
00127     Bond* bond_;
00128     NodeItemType* source_;
00129     NodeItemType* target_;
00130   };
00131 
00132   template <typename Node, typename Edge>
00133   EdgeItem<Node, Edge>::EdgeItem(const Bond& bond)
00134     : bond_(const_cast<Bond*>(&bond))
00135   {
00136   }
00137 
00138   template <typename Node, typename Edge>
00139   EdgeItem<Node, Edge>::EdgeItem(const Bond& bond, NodeItem<Node, Edge>* first, NodeItem<Node, Edge>* second)
00140     : bond_(const_cast<Bond*>(&bond)),
00141       source_(first),
00142       target_(second)
00143   {
00144   }
00145 
00146   template <typename Node, typename Edge>
00147   class TMolecularGraph
00148   {
00149     public:
00150     typedef NodeItem<Node, Edge> NodeItemType;
00151     typedef EdgeItem<Node, Edge> EdgeItemType;
00152     typedef typename std::list<NodeItemType>::iterator NodeIterator;
00153     typedef typename std::list<NodeItemType>::const_iterator NodeConstIterator;
00154     typedef typename std::list<EdgeItemType>::iterator EdgeIterator;
00155     typedef typename std::list<EdgeItemType>::const_iterator EdgeConstIterator;
00156 
00157     TMolecularGraph() ;
00158     TMolecularGraph(const Molecule& molecule) ;
00159 
00160     bool newNode(const Atom& atom) ;
00161     bool newEdge(const Bond& bond) ;
00162 
00163     bool deleteNode(NodeItemType& node);
00164     bool deleteEdge(EdgeItemType& edge);
00165         
00166     bool deleteNode(const Atom& atom);
00167     bool deleteEdge(const Bond& bond);
00168         
00169     NodeIterator beginNode() { return nodes_.begin(); }
00170     NodeConstIterator beginNode() const { return nodes_.begin(); }
00171     EdgeIterator beginEdge() { return edges_.begin(); }
00172     EdgeConstIterator beginEdge() const { return edges_.begin(); }
00173     NodeIterator endNode() { return nodes_.end(); }
00174     NodeConstIterator endNode() const { return nodes_.end(); }
00175     EdgeIterator endEdge() { return edges_.end(); }
00176     EdgeConstIterator endEdge() const { return edges_.end(); }
00177     
00178     bool has(const Atom& atom) const { return atom_to_node_.has(const_cast<Atom*>(&atom)); }
00179     bool has(const Bond& bond) const { return bond_to_edge_.has(const_cast<Bond*>(&bond)); }
00180 
00181     NodeItemType& getNode(Position index) { return nodes_[index]; };
00182     const NodeItemType& getNode(Position index) const { return nodes_[index]; };
00183     EdgeItemType& getEdge(Position index) { return edges_[index]; };
00184     const EdgeItemType& getEdge(Position index) const { return edges_[index]; };
00185 
00188     Size getNumberOfNodes() const ;
00189 
00192     Size getNumberOfEdges() const ;
00193 
00194     protected:
00195     std::list<NodeItemType> nodes_;
00196     std::list<EdgeItemType> edges_;
00197     HashMap<Atom*, NodeItemType*> atom_to_node_;
00198     HashMap<Bond*, EdgeItemType*> bond_to_edge_;
00199   };
00200 
00204   typedef TMolecularGraph<Index, Index> MolecularGraph;
00205 
00206   template <typename Node, typename Edge>
00207   TMolecularGraph<Node, Edge>::TMolecularGraph()
00208       
00209     : nodes_(),
00210       edges_(),
00211       atom_to_node_(),
00212       bond_to_edge_()
00213   {
00214   }
00215 
00216   template <typename Node, typename Edge>
00217   TMolecularGraph<Node, Edge>::TMolecularGraph(const Molecule& molecule)
00218       
00219     : nodes_(),
00220       edges_(),
00221       atom_to_node_(),
00222       bond_to_edge_()
00223   {
00224     AtomConstIterator ai = molecule.beginAtom();
00225     Atom::BondConstIterator bi;
00226     for (; +ai; ++ai)
00227     {
00228       newNode(*ai);
00229     }
00230     for (ai = molecule.beginAtom(); +ai; ++ai)
00231     {
00232       for (bi = ai->beginBond(); +bi; ++bi)
00233       {
00234         if (bi->getFirstAtom() == &*ai)
00235         {
00236           newEdge(*bi);
00237         }
00238       }
00239     }
00240   }
00241 
00242   template <typename Node, typename Edge>
00243   bool TMolecularGraph<Node, Edge>::newNode(const Atom& atom)
00244     
00245   {
00246     Atom* atom_ptr = const_cast<Atom*>(&atom);
00247 
00248     if (atom_to_node_.has(atom_ptr))
00249     {
00250       return false;
00251     }
00252 
00253     nodes_.push_back(NodeItemType(atom));
00254     atom_to_node_.insert(std::pair<Atom*, NodeItemType*>(atom_ptr, &(nodes_.back())));
00255 
00256     return true;
00257   }
00258 
00259   template <typename Node, typename Edge>
00260   bool TMolecularGraph<Node, Edge>::newEdge(const Bond& bond)
00261     
00262   {
00263     // Create convenience aliases for atoms.
00264     Atom* first = const_cast<Atom*>(bond.getFirstAtom());
00265     Atom* second = const_cast<Atom*>(bond.getSecondAtom()); 
00266 
00267     // Make sure we have atoms/nodes for this bond/edge.
00268     if (!atom_to_node_.has(first) || !atom_to_node_.has(second))
00269     {
00270       return false;
00271     }
00272 
00273     // Make sure not to create the same edge twice.
00274     if (bond_to_edge_.has(const_cast<Bond*>(&bond)))
00275     {
00276       return true;
00277     }
00278     
00279     // Create the new edge und add it to the hash map relating
00280     // the bond to the edge.
00281     NodeItemType* first_item = atom_to_node_[first];
00282     NodeItemType* second_item = atom_to_node_[second];
00283     edges_.push_back(EdgeItemType(bond, first_item, second_item));
00284     bond_to_edge_.insert(std::pair<Bond*, EdgeItemType*>(const_cast<Bond*>(&bond), &edges_.back()));
00285     first_item->adjacent_edges_.push_back(&edges_.back());
00286     second_item->adjacent_edges_.push_back(&edges_.back());
00287 
00288     return true;
00289   }
00290 
00291   template <typename Node, typename Edge>
00292   std::ostream& operator << (std::ostream& os, const TMolecularGraph<Node, Edge>& G)
00293   {   
00294     os << "Nodes:" << std::endl;
00295 
00296     typename TMolecularGraph<Node, Edge>::NodeConstIterator node = G.beginNode();
00297     Size count = 0;
00298     for (; node != G.endNode(); ++node)
00299     {
00300       os << count++ << ": " << node->getAtom()->getFullName() << " [" << node->getDegree() << "] '" << node->getAtom() << "'" << std::endl;     
00301     }
00302 
00303     os << "Edges:" << std::endl;  
00304 
00305     typename TMolecularGraph<Node, Edge>::EdgeConstIterator edge = G.beginEdge();
00306     count = 0;
00307     for (; edge != G.endEdge(); ++edge)
00308     {
00309       os << count++ << ": " << edge->getSource().getAtom() << "-" << edge->getTarget().getAtom() << " '" << edge->getBond() << "'" << std::endl;
00310     }
00311 
00312     return os;
00313   }
00314 
00315   template <typename Node, typename Edge>
00316   bool TMolecularGraph<Node, Edge>::deleteNode(const Atom& atom)
00317   {
00318     if (!atom_to_node_.has(const_cast<Atom*>(&atom)))
00319     {
00320       return false;
00321     }
00322     
00323     return deleteNode(*atom_to_node_[const_cast<Atom*>(&atom)]);
00324   }
00325 
00326   template <typename Node, typename Edge>
00327   bool TMolecularGraph<Node, Edge>::deleteEdge(const Bond& bond)
00328   {
00329     if (!bond_to_edge_.has(const_cast<Bond*>(&bond)))
00330     {
00331       return false;
00332     }
00333     
00334     return deleteEdge(*bond_to_edge_[const_cast<Bond*>(&bond)]);
00335   }
00336 
00337   template <typename Node, typename Edge>
00338   bool TMolecularGraph<Node, Edge>::deleteNode(typename TMolecularGraph<Node, Edge>::NodeItemType& node)
00339   {
00340     NodeIterator node_it = std::find(nodes_.begin(), nodes_.end(), node);
00341     if (node_it == nodes_.end())
00342     {
00343       return false;
00344     }
00345 
00346     bool remove = true;
00347     while (remove)
00348     {
00349       remove = false;
00350       typename NodeItemType::Iterator edge(node.begin());
00351       for (; edge != node.end(); ++edge)
00352       {
00353         deleteEdge(**edge);
00354         break;
00355       }
00356     }
00357 
00358     atom_to_node_.erase(node_it->getAtom());
00359     nodes_.erase(node_it);
00360   
00361     return true;
00362   }
00363 
00364   template <typename Node, typename Edge>
00365   bool TMolecularGraph<Node, Edge>::deleteEdge(typename TMolecularGraph<Node, Edge>::EdgeItemType& edge)
00366   {
00367     typename std::list<EdgeItemType>::iterator edge_it = std::find(edges_.begin(), edges_.end(), edge);
00368     if (edge_it == edges_.end())
00369     {
00370       return false;
00371     }
00372     edge.getSource().deleteEdge_(&edge);
00373     edge.getTarget().deleteEdge_(&edge);
00374     bond_to_edge_.erase(edge_it->getBond());
00375     edges_.erase(edge_it);
00376     
00377     return true;
00378   }
00379 
00380 
00381   template <typename Node, typename Edge>
00382   NodeItem<Node, Edge>::NodeItem()
00383     
00384     : atom_(0)
00385   {
00386   }
00387 
00388   template <typename Node, typename Edge>
00389   NodeItem<Node, Edge>::NodeItem(const Atom& atom)
00390     
00391     : atom_(const_cast<Atom*>(&atom))
00392   {
00393   }
00394 
00395   template <typename Node, typename Edge>
00396   Node& NodeItem<Node, Edge>::getData()
00397     
00398   {
00399     return data_;
00400   }
00401 
00402   template <typename Node, typename Edge>
00403   const Node& NodeItem<Node, Edge>::getData() const 
00404     
00405   { 
00406     return data_;
00407   }
00408 
00409 
00410   template <typename Node, typename Edge>
00411   void NodeItem<Node, Edge>::setData(const Node& data) 
00412     
00413   { 
00414     data_ = data; 
00415   }
00416 
00417   
00418   template <typename Node, typename Edge>
00419   const Atom* NodeItem<Node, Edge>::getAtom() const 
00420     
00421   { 
00422     return atom_;
00423   }
00424 
00425   template <typename Node, typename Edge>
00426   Atom* NodeItem<Node, Edge>::getAtom() 
00427     
00428   { 
00429     return atom_;
00430   }
00431 
00432   template <typename Node, typename Edge>
00433   typename NodeItem<Node, Edge>::Iterator NodeItem<Node, Edge>::begin() 
00434     
00435   { 
00436     return adjacent_edges_.begin(); 
00437   }
00438   
00439   template <typename Node, typename Edge>
00440   typename NodeItem<Node, Edge>::ConstIterator NodeItem<Node, Edge>::begin() const 
00441     
00442   { 
00443     return adjacent_edges_.begin(); 
00444   }
00445 
00446   template <typename Node, typename Edge>
00447   typename NodeItem<Node, Edge>::Iterator NodeItem<Node, Edge>::end() 
00448     
00449   { 
00450     return adjacent_edges_.end(); 
00451   }
00452 
00453   template <typename Node, typename Edge>
00454   typename NodeItem<Node, Edge>::ConstIterator NodeItem<Node, Edge>::end() const    
00455     
00456   { 
00457     return adjacent_edges_.end(); 
00458   }
00459 
00460   template <typename Node, typename Edge>
00461   Size NodeItem<Node, Edge>::getDegree() const 
00462     
00463   { 
00464     return (Size)adjacent_edges_.size(); 
00465   }
00466 
00467   template <typename Node, typename Edge>
00468   bool NodeItem<Node, Edge>::operator == (const NodeItem& item) const 
00469     
00470   { 
00471     return (atom_ == item.atom_); 
00472   }
00473 
00474   template <typename Node, typename Edge>
00475   bool NodeItem<Node, Edge>::operator != (const NodeItem& item) const 
00476     
00477   { 
00478     return (atom_ != item.atom_); 
00479   }
00480 
00481   template <typename Node, typename Edge>
00482   void NodeItem<Node, Edge>::deleteEdge_(EdgeItemType* item)
00483     
00484   {
00485     Iterator it(std::find(adjacent_edges_.begin(), adjacent_edges_.end(), item));
00486     if (it != adjacent_edges_.end())
00487     {
00488       adjacent_edges_.erase(it);
00489     }
00490   }
00491 
00492   template <typename Node, typename Edge>
00493   BALL_INLINE
00494   Size TMolecularGraph<Node, Edge>::getNumberOfNodes() const
00495     
00496   {
00497     return nodes_.size();
00498   }
00499 
00500   template <typename Node, typename Edge>
00501   BALL_INLINE
00502   Size TMolecularGraph<Node, Edge>::getNumberOfEdges() const
00503     
00504   {
00505     return edges_.size();
00506   }
00507 
00508   
00509 } // namespace BALL
00510 
00511 #endif // BALL_STRUCTURE_MOLECULARGRAPH_H