graph.tpp

Go to the documentation of this file.
00001 /*
00002   CLAW - a C++ Library Absolutely Wonderful
00003 
00004   CLAW is a free library without any particular aim but being useful to 
00005   anyone.
00006 
00007   Copyright (C) 2005-2008 Julien Jorge
00008 
00009   This library is free software; you can redistribute it and/or
00010   modify it under the terms of the GNU Lesser General Public
00011   License as published by the Free Software Foundation; either
00012   version 2.1 of the License, or (at your option) any later version.
00013 
00014   This library is distributed in the hope that it will be useful,
00015   but WITHOUT ANY WARRANTY; without even the implied warranty of
00016   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00017   Lesser General Public License for more details.
00018 
00019   You should have received a copy of the GNU Lesser General Public
00020   License along with this library; if not, write to the Free Software
00021   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00022 
00023   contact: julien_jorge@yahoo.fr
00024 */
00030 #include <cassert>
00031 #include <algorithm>
00032 
00033 #include <claw/functional.hpp>
00034 
00035 /*---------------------------------------------------------------------------*/
00039 claw::graph_exception::graph_exception() throw()
00040   : m_msg("No message") 
00041 {
00042 
00043 } // graph_exception()
00044 
00045 /*---------------------------------------------------------------------------*/
00050 claw::graph_exception::graph_exception( const std::string& s) throw()
00051   : m_msg(s) 
00052 {
00053 
00054 } // graph_exception()
00055 
00056 /*---------------------------------------------------------------------------*/
00060 claw::graph_exception::~graph_exception() throw()
00061 {
00062 
00063 } // ~graph_exception()
00064 
00065 /*---------------------------------------------------------------------------*/
00069 const char* claw::graph_exception::what() const throw()
00070 {
00071   return m_msg.c_str(); 
00072 } // what()
00073 
00074 
00075 
00076 
00077 /*---------------------------------------------------------------------------*/
00081 template <class S, class A, class Comp>
00082 claw::graph<S, A, Comp>::graph_vertex_iterator::graph_vertex_iterator()
00083 {
00084 
00085 } // graph_vertex_iterator() [constructor]
00086 
00087 /*---------------------------------------------------------------------------*/
00092 template <class S, class A, class Comp>
00093 typename claw::graph<S, A, Comp>::graph_vertex_iterator&
00094 claw::graph<S, A, Comp>::graph_vertex_iterator::operator++()
00095 {
00096   ++m_iterator;
00097   return *this;
00098 } // operator++() [preincrement]
00099 
00100 /*---------------------------------------------------------------------------*/
00105 template <class S, class A, class Comp>
00106 typename claw::graph<S, A, Comp>::graph_vertex_iterator
00107 claw::graph<S, A, Comp>::graph_vertex_iterator::operator++(int)
00108 {
00109   graph_vertex_iterator it_tmp(*this);
00110   m_iterator++;
00111   return *this;
00112 } // operator++() [postincrement]
00113 
00114 /*---------------------------------------------------------------------------*/
00119 template <class S, class A, class Comp>
00120 typename claw::graph<S, A, Comp>::graph_vertex_iterator&
00121 claw::graph<S, A, Comp>::graph_vertex_iterator::operator--()
00122 {
00123   --m_iterator;
00124   return *this;
00125 } // operator--() [predecrement]
00126 
00127 /*---------------------------------------------------------------------------*/
00132 template <class S, class A, class Comp>
00133 typename claw::graph<S, A, Comp>::graph_vertex_iterator 
00134 claw::graph<S, A, Comp>::graph_vertex_iterator::operator--(int)
00135 {
00136   graph_vertex_iterator it_tmp(*this);
00137   m_iterator--;
00138   return it_tmp;
00139 } // operator--() [postdecrement]
00140 
00141 /*---------------------------------------------------------------------------*/
00146 template <class S, class A, class Comp>
00147 typename claw::graph<S, A, Comp>::graph_vertex_iterator::reference
00148 claw::graph<S, A, Comp>::graph_vertex_iterator::operator*() const
00149 {
00150   return m_iterator->first;
00151 } // operator*()
00152 
00153 /*---------------------------------------------------------------------------*/
00158 template <class S, class A, class Comp>
00159 typename claw::graph<S, A, Comp>::graph_vertex_iterator::pointer
00160 claw::graph<S, A, Comp>::graph_vertex_iterator::operator->() const
00161 {
00162   return &(m_iterator->first);
00163 } // operator->()
00164 
00165 /*---------------------------------------------------------------------------*/
00171 template <class S, class A, class Comp>
00172 bool claw::graph<S, A, Comp>::graph_vertex_iterator::operator==
00173 (const graph_vertex_iterator& it) const
00174 {
00175   return m_iterator == it.m_iterator;
00176 } // operator==()
00177 
00178 /*---------------------------------------------------------------------------*/
00184 template <class S, class A, class Comp>
00185 bool claw::graph<S, A, Comp>::graph_vertex_iterator::operator!=
00186 (const graph_vertex_iterator& it) const
00187 {
00188   return m_iterator != it.m_iterator;
00189 } // operator!=()
00190 
00191 /*---------------------------------------------------------------------------*/
00196 template <class S, class A, class Comp>
00197 claw::graph<S, A, Comp>::graph_vertex_iterator::graph_vertex_iterator
00198 (typename graph_content::const_iterator it)
00199   : m_iterator(it)
00200 {
00201   
00202 } // graph_vertex_iterator() [constructor on an iterator]
00203 
00204 
00205 
00206 
00207 /*---------------------------------------------------------------------------*/
00211 template <class S, class A, class Comp>
00212 claw::graph<S, A, Comp>::graph_edge_iterator::edge::edge()
00213   : m_label(NULL), m_source(NULL), m_target(NULL)
00214 {
00215 
00216 } // edge::edge [constructor]
00217 
00218 /*---------------------------------------------------------------------------*/
00222 template <class S, class A, class Comp>
00223 const typename claw::graph<S, A, Comp>::edge_type& 
00224 claw::graph<S, A, Comp>::graph_edge_iterator::edge::label() const
00225 {
00226   assert(m_label != NULL);
00227   return *m_label;
00228 } // edge::label()
00229 
00230 /*---------------------------------------------------------------------------*/
00234 template <class S, class A, class Comp>
00235 const typename claw::graph<S, A, Comp>::vertex_type& 
00236 claw::graph<S, A, Comp>::graph_edge_iterator::edge::source() const
00237 {
00238   assert(m_source != NULL);
00239   return *m_source;
00240 } // edge::source()
00241 
00242 /*---------------------------------------------------------------------------*/
00246 template <class S, class A, class Comp>
00247 const typename claw::graph<S, A, Comp>::vertex_type&
00248 claw::graph<S, A, Comp>::graph_edge_iterator::edge::target() const
00249 {
00250   assert(m_target != NULL);
00251   return *m_target;
00252 } // edge::target()
00253 
00254 /*---------------------------------------------------------------------------*/
00258 template <class S, class A, class Comp>
00259 void claw::graph<S, A, Comp>::graph_edge_iterator::edge::
00260 set( const edge_type& l, const vertex_type& s, const vertex_type& t )
00261 {
00262   m_label = &l;
00263   m_source = &s;
00264   m_target = &t;
00265 } // edge::set()
00266 
00267 
00268 
00269 
00270 /*---------------------------------------------------------------------------*/
00274 template <class S, class A, class Comp>
00275 claw::graph<S, A, Comp>::graph_edge_iterator::graph_edge_iterator()
00276 {
00277 
00278 } // graph_edge_iterator() [constructor]
00279 
00280 /*---------------------------------------------------------------------------*/
00285 template <class S, class A, class Comp>
00286 typename claw::graph<S, A, Comp>::graph_edge_iterator&
00287 claw::graph<S, A, Comp>::graph_edge_iterator::operator++()
00288 {
00289   bool ok = true;
00290   ++m_neighbours_iterator;
00291 
00292   // end of a neighbourhood
00293   if ( m_neighbours_iterator == m_vertex_iterator->second.end() )
00294     {
00295       // find next edge or end.
00296       ok = false;
00297       ++m_vertex_iterator;
00298 
00299       while ( (m_vertex_iterator != m_vertex_end) && !ok )
00300         if ( !m_vertex_iterator->second.empty() )
00301           {
00302             ok = true;
00303             m_neighbours_iterator = m_vertex_iterator->second.begin();
00304           }
00305         else
00306           ++m_vertex_iterator;
00307     }
00308 
00309   if (ok)
00310     m_edge.set( m_neighbours_iterator->second, m_vertex_iterator->first,
00311                 m_neighbours_iterator->first );
00312 
00313   return *this;
00314 } // operator++() [preincrement]
00315 
00316 /*---------------------------------------------------------------------------*/
00321 template <class S, class A, class Comp>
00322 typename claw::graph<S, A, Comp>::graph_edge_iterator
00323 claw::graph<S, A, Comp>::graph_edge_iterator::operator++(int)
00324 {
00325   graph_edge_iterator it_tmp(*this);
00326   ++(*this);
00327   return it_tmp;
00328 } // operator++() [postincrement]
00329 
00330 /*---------------------------------------------------------------------------*/
00335 template <class S, class A, class Comp>
00336 typename claw::graph<S, A, Comp>::graph_edge_iterator&
00337 claw::graph<S, A, Comp>::graph_edge_iterator::operator--()
00338 {
00339   bool ok = true;
00340 
00341   if (m_vertex_iterator == m_vertex_end)
00342     {
00343       --m_vertex_iterator;
00344       m_neighbours_iterator = m_vertex_iterator->second.end();
00345     }
00346 
00347   // begining of a neighbourhood
00348   if ( m_neighbours_iterator == m_vertex_iterator->second.begin() )
00349     {
00350       ok = false;
00351       // find previous edge or begining.
00352       while ( (m_vertex_iterator != m_vertex_begin) && !ok )
00353         {
00354           --m_vertex_iterator;
00355           if ( !m_vertex_iterator->second.empty() )
00356             {
00357               ok = true;
00358               m_neighbours_iterator = --m_vertex_iterator->second.end();
00359             }
00360         }
00361     }
00362   else
00363     --m_neighbours_iterator;
00364 
00365   if (!ok)
00366     m_vertex_iterator == m_vertex_end;
00367   else
00368     m_edge.set( m_neighbours_iterator->second, m_vertex_iterator->first,
00369                 m_neighbours_iterator->first );
00370 
00371   return *this;
00372 } // operator--() [predecrement]
00373 
00374 /*---------------------------------------------------------------------------*/
00379 template <class S, class A, class Comp>
00380 typename claw::graph<S, A, Comp>::graph_edge_iterator 
00381 claw::graph<S, A, Comp>::graph_edge_iterator::operator--(int)
00382 {
00383   graph_edge_iterator it_tmp(*this);
00384   --(*this);
00385   return it_tmp;
00386 } // operator--() [postdecrement]
00387 
00388 /*---------------------------------------------------------------------------*/
00393 template <class S, class A, class Comp>
00394 typename claw::graph<S, A, Comp>::graph_edge_iterator::reference
00395 claw::graph<S, A, Comp>::graph_edge_iterator::operator*() const
00396 {
00397   return m_edge;
00398 } // operator*()
00399 
00400 /*---------------------------------------------------------------------------*/
00405 template <class S, class A, class Comp>
00406 typename claw::graph<S, A, Comp>::graph_edge_iterator::pointer
00407 claw::graph<S, A, Comp>::graph_edge_iterator::operator->() const
00408 {
00409   return &m_edge;
00410 } // operator->()
00411 
00412 /*---------------------------------------------------------------------------*/
00418 template <class S, class A, class Comp>
00419 bool claw::graph<S, A, Comp>::graph_edge_iterator::operator==
00420 (const graph_edge_iterator& it) const
00421 {
00422   // both are empty
00423   if ( m_vertex_begin == m_vertex_end )
00424     return (it.m_vertex_begin == it.m_vertex_end) 
00425       && (m_vertex_begin == it.m_vertex_begin);
00426   else
00427     if ( it.m_vertex_begin == it.m_vertex_end ) // -it- is empty
00428       return false;
00429     else
00430       // none is empty, perheaps at the end ?
00431       if (m_vertex_iterator == m_vertex_end)
00432         return (it.m_vertex_iterator == it.m_vertex_end)
00433           && (m_vertex_begin == it.m_vertex_begin);
00434       else
00435         if (it.m_vertex_iterator == it.m_vertex_end)
00436           return false;
00437         else
00438           return m_neighbours_iterator == it.m_neighbours_iterator;
00439 } // operator==()
00440 
00441 /*---------------------------------------------------------------------------*/
00447 template <class S, class A, class Comp>
00448 bool claw::graph<S, A, Comp>::graph_edge_iterator::operator!=
00449 (const graph_edge_iterator& it) const
00450 {
00451   return !(*this == it);
00452 } // operator!=()
00453 
00454 /*---------------------------------------------------------------------------*/
00462 template <class S, class A, class Comp>
00463 claw::graph<S, A, Comp>::graph_edge_iterator::graph_edge_iterator
00464 ( typename graph_content::const_iterator it_begin,
00465   typename graph_content::const_iterator it_end,
00466   typename graph_content::const_iterator it_s,
00467   typename neighbours_list::const_iterator it_d)
00468   : m_vertex_begin(it_begin), m_vertex_end(it_end), 
00469     m_vertex_iterator(it_s), m_neighbours_iterator(it_d)
00470 {
00471   if (m_vertex_begin != m_vertex_end)
00472     m_edge.set( m_neighbours_iterator->second, m_vertex_iterator->first,
00473                 m_neighbours_iterator->first );
00474 } // graph_edge_iterator() [constructor on an iterator]
00475 
00476 
00477 
00478 
00479 /*---------------------------------------------------------------------------*/
00483 template <class S, class A, class Comp>
00484 claw::graph<S, A, Comp>::graph()
00485   : m_edges_count(0)
00486 {
00487 
00488 } // graph::graph() [constructor]
00489 
00490 /*---------------------------------------------------------------------------*/
00497 template <class S, class A, class Comp>
00498 void claw::graph<S, A, Comp>::add_edge
00499 ( const vertex_type& s1, const vertex_type& s2, const edge_type& e )
00500 {
00501   if ( !edge_exists(s1, s2) )
00502     {
00503       // s2 is not a neighbor of s1
00504       ++m_edges_count;
00505 
00506       add_vertex(s1);
00507       add_vertex(s2); 
00508 
00509       // in all cases, s2 as one more inner edge
00510       ++m_inner_degrees[s2]; 
00511     }
00512 
00513   m_edges[s1][s2] = e;
00514 } // graph::add_edge()
00515 
00516 /*---------------------------------------------------------------------------*/
00521 template <class S, class A, class Comp>
00522 void claw::graph<S, A, Comp>::add_vertex( const vertex_type& s )
00523 {
00524   std::pair<S, neighbours_list> p;
00525 
00526   if (m_edges.find(s) == m_edges.end())
00527     {
00528       // Add the vertex in the adjacency list.
00529       p.first = s;
00530       m_edges.insert(p);
00531       m_inner_degrees[s] = 0;
00532     }
00533 } // graph::add_vertex()
00534 
00535 /*---------------------------------------------------------------------------*/
00541 template <class S, class A, class Comp>
00542 bool claw::graph<S, A, Comp>::edge_exists
00543 ( const vertex_type& s, const vertex_type& r ) const 
00544 { 
00545   typename graph_content::const_iterator it = m_edges.find(s);
00546 
00547   if ( it == m_edges.end() )
00548     return false;
00549   else
00550     return it->second.find(r) != it->second.end(); 
00551 } // graph::edge_exists()
00552 
00553 /*---------------------------------------------------------------------------*/
00559 template <class S, class A, class Comp>
00560 void claw::graph<S, A, Comp>::neighbours
00561 (const vertex_type& s, std::vector<vertex_type>& v) const 
00562 { 
00563   typename graph_content::const_iterator it_s = m_edges.find(s);
00564   v.clear();
00565 
00566   if ( it_s != m_edges.end() )
00567     {
00568       v.resize( it_s->second.size() );
00569       std::transform( it_s->second.begin(), it_s->second.end(), v.begin(),
00570                       const_first<S,A>() );
00571     }
00572 } // graph::neighbours()
00573 
00574 /*---------------------------------------------------------------------------*/
00579 template <class S, class A, class Comp>
00580 void claw::graph<S, A, Comp>::vertices(std::vector<vertex_type>& v) const 
00581 { 
00582   v.clear();
00583   v.resize(m_edges.size());
00584 
00585   std::transform( m_edges.begin(), m_edges.end(), v.begin(), 
00586                   const_first<S,neighbours_list>() );
00587 } // graph::vertices()
00588 
00589 /*---------------------------------------------------------------------------*/
00594 template <class S, class A, class Comp>
00595 typename claw::graph<S, A, Comp>::vertex_iterator
00596 claw::graph<S, A, Comp>::vertex_begin() const
00597 {
00598   return vertex_iterator( m_edges.begin() );
00599 } // graph::vertex_begin()
00600 
00601 /*---------------------------------------------------------------------------*/
00605 template <class S, class A, class Comp>
00606 typename claw::graph<S, A, Comp>::vertex_iterator 
00607 claw::graph<S, A, Comp>::vertex_end() const
00608 {
00609   return vertex_iterator( m_edges.end() );
00610 } // graph::vertex_end()
00611 
00612 /*---------------------------------------------------------------------------*/
00617 template <class S, class A, class Comp>
00618 typename claw::graph<S, A, Comp>::vertex_iterator 
00619 claw::graph<S, A, Comp>::vertex_begin( const vertex_type& s ) const
00620 {
00621   return vertex_iterator( m_edges.find(s) );
00622 } // graph::vertex_begin()
00623 
00624 /*---------------------------------------------------------------------------*/
00629 template <class S, class A, class Comp>
00630 typename claw::graph<S, A, Comp>::reverse_vertex_iterator
00631 claw::graph<S, A, Comp>::vertex_rbegin() const
00632 {
00633   return reverse_vertex_iterator( vertex_end() );
00634 } // graph::vertex_rbegin()
00635 
00636 /*---------------------------------------------------------------------------*/
00640 template <class S, class A, class Comp>
00641 typename claw::graph<S, A, Comp>::reverse_vertex_iterator 
00642 claw::graph<S, A, Comp>::vertex_rend() const
00643 {
00644   return reverse_vertex_iterator( vertex_begin() );
00645 } // graph::vertex_rend()
00646 
00647 /*---------------------------------------------------------------------------*/
00652 template <class S, class A, class Comp>
00653 typename claw::graph<S, A, Comp>::reverse_vertex_iterator 
00654 claw::graph<S, A, Comp>::vertex_rbegin( const vertex_type& s ) const
00655 {
00656   vertex_iterator it = vertex_begin(s);
00657 
00658   if (it != vertex_end())
00659     ++it;
00660 
00661   return reverse_vertex_iterator( it );
00662 } // graph::vertex_rbegin()
00663 
00664 /*---------------------------------------------------------------------------*/
00669 template <class S, class A, class Comp>
00670 typename claw::graph<S, A, Comp>::edge_iterator
00671 claw::graph<S, A, Comp>::edge_begin() const
00672 {
00673   bool ok = false;
00674   typename graph_content::const_iterator it_s;
00675   it_s = m_edges.begin();
00676 
00677   while ( (it_s != m_edges.end()) && !ok )
00678     if ( it_s->second.empty() )
00679       ++it_s;
00680     else
00681       ok = true;
00682 
00683   if (ok)
00684     return edge_iterator( m_edges.begin(), m_edges.end(), it_s, 
00685                           it_s->second.begin() );
00686   else
00687     return edge_end();
00688                                                  
00689 } // graph::edge_begin()
00690 
00691 /*---------------------------------------------------------------------------*/
00695 template <class S, class A, class Comp>
00696 typename claw::graph<S, A, Comp>::edge_iterator
00697 claw::graph<S, A, Comp>::edge_end() const
00698 {
00699   return edge_iterator( m_edges.begin(), m_edges.end(), m_edges.end(),
00700                         typename neighbours_list::const_iterator() );
00701 } // graph::edge_end()
00702 
00703 /*---------------------------------------------------------------------------*/
00708 template <class S, class A, class Comp>
00709 typename claw::graph<S, A, Comp>::edge_iterator
00710 claw::graph<S, A, Comp>::edge_begin
00711 ( const vertex_type& s1, const vertex_type& s2 ) const
00712 {
00713   if ( edge_exists(s1, s2) )
00714     {
00715       typename graph_content::const_iterator it_s1;
00716 
00717       it_s1 = m_edges.find(s1);
00718       return edge_iterator( m_edges.begin(), m_edges.end(), it_s1, 
00719                             it_s1->second.find(s2) );
00720     }
00721   else
00722     return edge_end();
00723 } // graph::edge_()
00724 
00725 /*---------------------------------------------------------------------------*/
00730 template <class S, class A, class Comp>
00731 typename claw::graph<S, A, Comp>::reverse_edge_iterator
00732 claw::graph<S, A, Comp>::edge_rbegin() const
00733 {
00734   return reverse_edge_iterator( edge_end() );
00735 } // graph::edge_rbegin()
00736 
00737 /*---------------------------------------------------------------------------*/
00741 template <class S, class A, class Comp>
00742 typename claw::graph<S, A, Comp>::reverse_edge_iterator 
00743 claw::graph<S, A, Comp>::edge_rend() const
00744 {
00745   return reverse_edge_iterator( edge_begin() );
00746 } // graph::edge_rend()
00747 
00748 /*---------------------------------------------------------------------------*/
00753 template <class S, class A, class Comp>
00754 typename claw::graph<S, A, Comp>::reverse_edge_iterator 
00755 claw::graph<S, A, Comp>::edge_rbegin
00756 ( const vertex_type& s1, const vertex_type& s2 ) const
00757 {
00758   reverse_edge_iterator it = edge_begin(s1, s2);
00759 
00760   if ( it != edge_end() )
00761     ++it;
00762 
00763   return reverse_edge_iterator( it );
00764 } // graph::edge_rbegin()
00765 
00766 /*---------------------------------------------------------------------------*/
00772 template <class S, class A, class Comp>
00773 const typename claw::graph<S, A, Comp>::edge_type& 
00774 claw::graph<S, A, Comp>::label
00775 ( const vertex_type& s, const vertex_type& r ) const 
00776 { 
00777   typename graph_content::const_iterator it_s = m_edges.find(s);
00778 
00779   if ( it_s == m_edges.end() )
00780     throw graph_exception
00781       ("claw::graph::label(): unkonwn source vertex.");
00782   else 
00783     {
00784       typename neighbours_list::const_iterator it_r = it_s->second.find(r);
00785 
00786       if ( it_r == it_s->second.end() )
00787         throw graph_exception
00788           ("claw::graph::label(): destination is not a neighbor.");
00789       else
00790         return it_r->second; 
00791     }
00792 } // graph::label()
00793 
00794 /*---------------------------------------------------------------------------*/
00799 template <class S, class A, class Comp>
00800 std::size_t claw::graph<S, A, Comp>::outer_degree( const vertex_type& s ) const 
00801 { 
00802   typename graph_content::const_iterator it = m_edges.find(s);
00803   
00804   if (it == m_edges.end())
00805     throw graph_exception("claw::graph::outer_degree(): unknown vertex.");
00806   else
00807     return it->second.size(); 
00808 } // graph::outer_degree()
00809 
00810 /*---------------------------------------------------------------------------*/
00815 template <class S, class A, class Comp>
00816 std::size_t claw::graph<S, A, Comp>::inner_degree( const vertex_type& s ) const 
00817 { 
00818   typename std::map<S, std::size_t, Comp>::const_iterator it;
00819   it = m_inner_degrees.find(s);
00820   
00821   if (it == m_inner_degrees.end())
00822     throw graph_exception
00823       ("claw::graph::inner_degree(): unkown vertex.");
00824   else
00825     return it->second; 
00826 } // graph::inner_degree()
00827 
00828 /*---------------------------------------------------------------------------*/
00832 template <class S, class A, class Comp>
00833 std::size_t claw::graph<S, A, Comp>::vertices_count() const 
00834 {
00835   return m_edges.size(); 
00836 } // graph::vertices_count()
00837 
00838 /*---------------------------------------------------------------------------*/
00842 template <class S, class A, class Comp>
00843 std::size_t claw::graph<S, A, Comp>::edges_count() const 
00844 {
00845   return m_edges_count; 
00846 } // graph::edges_count()
00847 

Generated on 9 Nov 2009 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.6.1