00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
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 }
00044
00045
00050 claw::graph_exception::graph_exception( const std::string& s) throw()
00051 : m_msg(s)
00052 {
00053
00054 }
00055
00056
00060 claw::graph_exception::~graph_exception() throw()
00061 {
00062
00063 }
00064
00065
00069 const char* claw::graph_exception::what() const throw()
00070 {
00071 return m_msg.c_str();
00072 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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
00293 if ( m_neighbours_iterator == m_vertex_iterator->second.end() )
00294 {
00295
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 }
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 }
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
00348 if ( m_neighbours_iterator == m_vertex_iterator->second.begin() )
00349 {
00350 ok = false;
00351
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 }
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 }
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 }
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 }
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
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 )
00428 return false;
00429 else
00430
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 }
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 }
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 }
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 }
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
00504 ++m_edges_count;
00505
00506 add_vertex(s1);
00507 add_vertex(s2);
00508
00509
00510 ++m_inner_degrees[s2];
00511 }
00512
00513 m_edges[s1][s2] = e;
00514 }
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
00529 p.first = s;
00530 m_edges.insert(p);
00531 m_inner_degrees[s] = 0;
00532 }
00533 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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 }
00847