BALL: molecularGraph.h Source File

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