Claw
1.7.0
|
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-2011 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@gamned.org 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