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 <stack>
00031 #include <cassert>
00032 #include <algorithm>
00033
00034 #include <claw/functional.hpp>
00035
00036
00037
00038
00042 claw::graph_exception::graph_exception() throw()
00043 : m_msg("No message")
00044 {
00045
00046 }
00047
00048
00053 claw::graph_exception::graph_exception( const std::string& s) throw()
00054 : m_msg(s)
00055 {
00056
00057 }
00058
00059
00063 claw::graph_exception::~graph_exception() throw()
00064 {
00065
00066 }
00067
00068
00072 const char* claw::graph_exception::what() const throw()
00073 {
00074 return m_msg.c_str();
00075 }
00076
00077
00078
00079
00080
00081
00082
00083
00087 template <class S, class A, class Comp>
00088 claw::graph<S, A, Comp>::graph_vertex_iterator::graph_vertex_iterator()
00089 {
00090
00091 }
00092
00093
00098 template <class S, class A, class Comp>
00099 typename claw::graph<S, A, Comp>::graph_vertex_iterator&
00100 claw::graph<S, A, Comp>::graph_vertex_iterator::operator++()
00101 {
00102 ++m_iterator;
00103 return *this;
00104 }
00105
00106
00111 template <class S, class A, class Comp>
00112 typename claw::graph<S, A, Comp>::graph_vertex_iterator
00113 claw::graph<S, A, Comp>::graph_vertex_iterator::operator++(int)
00114 {
00115 graph_vertex_iterator it_tmp(*this);
00116 m_iterator++;
00117 return *this;
00118 }
00119
00120
00125 template <class S, class A, class Comp>
00126 typename claw::graph<S, A, Comp>::graph_vertex_iterator&
00127 claw::graph<S, A, Comp>::graph_vertex_iterator::operator--()
00128 {
00129 --m_iterator;
00130 return *this;
00131 }
00132
00133
00138 template <class S, class A, class Comp>
00139 typename claw::graph<S, A, Comp>::graph_vertex_iterator
00140 claw::graph<S, A, Comp>::graph_vertex_iterator::operator--(int)
00141 {
00142 graph_vertex_iterator it_tmp(*this);
00143 m_iterator--;
00144 return it_tmp;
00145 }
00146
00147
00152 template <class S, class A, class Comp>
00153 typename claw::graph<S, A, Comp>::graph_vertex_iterator::reference
00154 claw::graph<S, A, Comp>::graph_vertex_iterator::operator*() const
00155 {
00156 return m_iterator->first;
00157 }
00158
00159
00164 template <class S, class A, class Comp>
00165 typename claw::graph<S, A, Comp>::graph_vertex_iterator::pointer
00166 claw::graph<S, A, Comp>::graph_vertex_iterator::operator->() const
00167 {
00168 return &(m_iterator->first);
00169 }
00170
00171
00177 template <class S, class A, class Comp>
00178 bool claw::graph<S, A, Comp>::graph_vertex_iterator::operator==
00179 (const graph_vertex_iterator& it) const
00180 {
00181 return m_iterator == it.m_iterator;
00182 }
00183
00184
00190 template <class S, class A, class Comp>
00191 bool claw::graph<S, A, Comp>::graph_vertex_iterator::operator!=
00192 (const graph_vertex_iterator& it) const
00193 {
00194 return m_iterator != it.m_iterator;
00195 }
00196
00197
00198
00199
00200
00201
00202
00207 template <class S, class A, class Comp>
00208 claw::graph<S, A, Comp>::graph_vertex_iterator::graph_vertex_iterator
00209 (typename graph_content::const_iterator it)
00210 : m_iterator(it)
00211 {
00212
00213 }
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00227 template <class S, class A, class Comp>
00228 claw::graph<S, A, Comp>::graph_edge_iterator::edge::edge()
00229 : m_label(NULL), m_source(NULL), m_target(NULL)
00230 {
00231
00232 }
00233
00234
00238 template <class S, class A, class Comp>
00239 const typename claw::graph<S, A, Comp>::edge_type&
00240 claw::graph<S, A, Comp>::graph_edge_iterator::edge::label() const
00241 {
00242 assert(m_label != NULL);
00243 return *m_label;
00244 }
00245
00246
00250 template <class S, class A, class Comp>
00251 const typename claw::graph<S, A, Comp>::vertex_type&
00252 claw::graph<S, A, Comp>::graph_edge_iterator::edge::source() const
00253 {
00254 assert(m_source != NULL);
00255 return *m_source;
00256 }
00257
00258
00262 template <class S, class A, class Comp>
00263 const typename claw::graph<S, A, Comp>::vertex_type&
00264 claw::graph<S, A, Comp>::graph_edge_iterator::edge::target() const
00265 {
00266 assert(m_target != NULL);
00267 return *m_target;
00268 }
00269
00270
00274 template <class S, class A, class Comp>
00275 void claw::graph<S, A, Comp>::graph_edge_iterator::edge::
00276 set( const edge_type& l, const vertex_type& s, const vertex_type& t )
00277 {
00278 m_label = &l;
00279 m_source = &s;
00280 m_target = &t;
00281 }
00282
00283
00284
00285
00286
00287
00288
00289
00290
00294 template <class S, class A, class Comp>
00295 claw::graph<S, A, Comp>::graph_edge_iterator::graph_edge_iterator()
00296 {
00297
00298 }
00299
00300
00305 template <class S, class A, class Comp>
00306 typename claw::graph<S, A, Comp>::graph_edge_iterator&
00307 claw::graph<S, A, Comp>::graph_edge_iterator::operator++()
00308 {
00309 bool ok = true;
00310 ++m_neighbours_iterator;
00311
00312
00313 if ( m_neighbours_iterator == m_vertex_iterator->second.end() )
00314 {
00315
00316 ok = false;
00317 ++m_vertex_iterator;
00318
00319 while ( (m_vertex_iterator != m_vertex_end) && !ok )
00320 if ( !m_vertex_iterator->second.empty() )
00321 {
00322 ok = true;
00323 m_neighbours_iterator = m_vertex_iterator->second.begin();
00324 }
00325 else
00326 ++m_vertex_iterator;
00327 }
00328
00329 if (ok)
00330 m_edge.set( m_neighbours_iterator->second, m_vertex_iterator->first,
00331 m_neighbours_iterator->first );
00332
00333 return *this;
00334 }
00335
00336
00341 template <class S, class A, class Comp>
00342 typename claw::graph<S, A, Comp>::graph_edge_iterator
00343 claw::graph<S, A, Comp>::graph_edge_iterator::operator++(int)
00344 {
00345 graph_edge_iterator it_tmp(*this);
00346 ++(*this);
00347 return it_tmp;
00348 }
00349
00350
00355 template <class S, class A, class Comp>
00356 typename claw::graph<S, A, Comp>::graph_edge_iterator&
00357 claw::graph<S, A, Comp>::graph_edge_iterator::operator--()
00358 {
00359 bool ok = true;
00360
00361 if (m_vertex_iterator == m_vertex_end)
00362 {
00363 --m_vertex_iterator;
00364 m_neighbours_iterator = m_vertex_iterator->second.end();
00365 }
00366
00367
00368 if ( m_neighbours_iterator == m_vertex_iterator->second.begin() )
00369 {
00370 ok = false;
00371
00372 while ( (m_vertex_iterator != m_vertex_begin) && !ok )
00373 {
00374 --m_vertex_iterator;
00375 if ( !m_vertex_iterator->second.empty() )
00376 {
00377 ok = true;
00378 m_neighbours_iterator = --m_vertex_iterator->second.end();
00379 }
00380 }
00381 }
00382 else
00383 --m_neighbours_iterator;
00384
00385 if (!ok)
00386 m_vertex_iterator == m_vertex_end;
00387 else
00388 m_edge.set( m_neighbours_iterator->second, m_vertex_iterator->first,
00389 m_neighbours_iterator->first );
00390
00391 return *this;
00392 }
00393
00394
00399 template <class S, class A, class Comp>
00400 typename claw::graph<S, A, Comp>::graph_edge_iterator
00401 claw::graph<S, A, Comp>::graph_edge_iterator::operator--(int)
00402 {
00403 graph_edge_iterator it_tmp(*this);
00404 --(*this);
00405 return it_tmp;
00406 }
00407
00408
00413 template <class S, class A, class Comp>
00414 typename claw::graph<S, A, Comp>::graph_edge_iterator::reference
00415 claw::graph<S, A, Comp>::graph_edge_iterator::operator*() const
00416 {
00417 return m_edge;
00418 }
00419
00420
00425 template <class S, class A, class Comp>
00426 typename claw::graph<S, A, Comp>::graph_edge_iterator::pointer
00427 claw::graph<S, A, Comp>::graph_edge_iterator::operator->() const
00428 {
00429 return &m_edge;
00430 }
00431
00432
00438 template <class S, class A, class Comp>
00439 bool claw::graph<S, A, Comp>::graph_edge_iterator::operator==
00440 (const graph_edge_iterator& it) const
00441 {
00442
00443 if ( m_vertex_begin == m_vertex_end )
00444 return (it.m_vertex_begin == it.m_vertex_end)
00445 && (m_vertex_begin == it.m_vertex_begin);
00446 else
00447 if ( it.m_vertex_begin == it.m_vertex_end )
00448 return false;
00449 else
00450
00451 if (m_vertex_iterator == m_vertex_end)
00452 return (it.m_vertex_iterator == it.m_vertex_end)
00453 && (m_vertex_begin == it.m_vertex_begin);
00454 else
00455 if (it.m_vertex_iterator == it.m_vertex_end)
00456 return false;
00457 else
00458 return m_neighbours_iterator == it.m_neighbours_iterator;
00459 }
00460
00461
00467 template <class S, class A, class Comp>
00468 bool claw::graph<S, A, Comp>::graph_edge_iterator::operator!=
00469 (const graph_edge_iterator& it) const
00470 {
00471 return !(*this == it);
00472 }
00473
00474
00475
00476
00477
00478
00479
00480
00488 template <class S, class A, class Comp>
00489 claw::graph<S, A, Comp>::graph_edge_iterator::graph_edge_iterator
00490 ( typename graph_content::const_iterator it_begin,
00491 typename graph_content::const_iterator it_end,
00492 typename graph_content::const_iterator it_s,
00493 typename neighbours_list::const_iterator it_d)
00494 : m_vertex_begin(it_begin), m_vertex_end(it_end),
00495 m_vertex_iterator(it_s), m_neighbours_iterator(it_d)
00496 {
00497 if (m_vertex_begin != m_vertex_end)
00498 m_edge.set( m_neighbours_iterator->second, m_vertex_iterator->first,
00499 m_neighbours_iterator->first );
00500 }
00501
00502
00503
00504
00505
00506
00507
00508
00509
00510
00514 template <class S, class A, class Comp>
00515 claw::graph<S, A, Comp>::graph()
00516 : m_edges_count(0)
00517 {
00518
00519 }
00520
00521
00528 template <class S, class A, class Comp>
00529 void claw::graph<S, A, Comp>::add_edge( const vertex_type& s1,
00530 const vertex_type& s2,
00531 const edge_type& e )
00532 {
00533 if ( !edge_exists(s1, s2) )
00534 {
00535
00536 ++m_edges_count;
00537
00538 add_vertex(s1);
00539 add_vertex(s2);
00540
00541
00542 ++m_inner_degrees[s2];
00543 }
00544
00545 m_edges[s1][s2] = e;
00546 }
00547
00548
00553 template <class S, class A, class Comp>
00554 void claw::graph<S, A, Comp>::add_vertex( const vertex_type& s )
00555 {
00556 std::pair<S, neighbours_list> p;
00557
00558 if (m_edges.find(s) == m_edges.end())
00559 {
00560
00561 p.first = s;
00562 m_edges.insert(p);
00563 m_inner_degrees[s] = 0;
00564 }
00565 }
00566
00567
00573 template <class S, class A, class Comp>
00574 bool claw::graph<S, A, Comp>::edge_exists( const vertex_type& s,
00575 const vertex_type& r ) const
00576 {
00577 typename graph_content::const_iterator it = m_edges.find(s);
00578
00579 if ( it == m_edges.end() )
00580 return false;
00581 else
00582 return it->second.find(r) != it->second.end();
00583 }
00584
00585
00591 template <class S, class A, class Comp>
00592 void claw::graph<S, A, Comp>::neighbours(const vertex_type& s,
00593 std::vector<vertex_type>& v) const
00594 {
00595 typename graph_content::const_iterator it_s = m_edges.find(s);
00596 v.clear();
00597
00598 if ( it_s != m_edges.end() )
00599 {
00600 v.resize( it_s->second.size() );
00601 std::transform( it_s->second.begin(), it_s->second.end(), v.begin(),
00602 const_first<S,A>() );
00603 }
00604 }
00605
00606
00611 template <class S, class A, class Comp>
00612 void claw::graph<S, A, Comp>::vertices(std::vector<vertex_type>& v) const
00613 {
00614 v.clear();
00615 v.resize(m_edges.size());
00616
00617 std::transform( m_edges.begin(), m_edges.end(), v.begin(),
00618 const_first<S,neighbours_list>() );
00619 }
00620
00621
00626 template <class S, class A, class Comp>
00627 typename claw::graph<S, A, Comp>::vertex_iterator
00628 claw::graph<S, A, Comp>::vertex_begin() const
00629 {
00630 return vertex_iterator( m_edges.begin() );
00631 }
00632
00633
00637 template <class S, class A, class Comp>
00638 typename claw::graph<S, A, Comp>::vertex_iterator
00639 claw::graph<S, A, Comp>::vertex_end() const
00640 {
00641 return vertex_iterator( m_edges.end() );
00642 }
00643
00644
00649 template <class S, class A, class Comp>
00650 typename claw::graph<S, A, Comp>::vertex_iterator
00651 claw::graph<S, A, Comp>::vertex_begin( const vertex_type& s ) const
00652 {
00653 return vertex_iterator( m_edges.find(s) );
00654 }
00655
00656
00661 template <class S, class A, class Comp>
00662 typename claw::graph<S, A, Comp>::reverse_vertex_iterator
00663 claw::graph<S, A, Comp>::vertex_rbegin() const
00664 {
00665 return reverse_vertex_iterator( vertex_end() );
00666 }
00667
00668
00672 template <class S, class A, class Comp>
00673 typename claw::graph<S, A, Comp>::reverse_vertex_iterator
00674 claw::graph<S, A, Comp>::vertex_rend() const
00675 {
00676 return reverse_vertex_iterator( vertex_begin() );
00677 }
00678
00679
00684 template <class S, class A, class Comp>
00685 typename claw::graph<S, A, Comp>::reverse_vertex_iterator
00686 claw::graph<S, A, Comp>::vertex_rbegin( const vertex_type& s ) const
00687 {
00688 vertex_iterator it = vertex_begin(s);
00689
00690 if (it != vertex_end())
00691 ++it;
00692
00693 return reverse_vertex_iterator( it );
00694 }
00695
00696
00701 template <class S, class A, class Comp>
00702 typename claw::graph<S, A, Comp>::edge_iterator
00703 claw::graph<S, A, Comp>::edge_begin() const
00704 {
00705 bool ok = false;
00706 typename graph_content::const_iterator it_s;
00707 it_s = m_edges.begin();
00708
00709 while ( (it_s != m_edges.end()) && !ok )
00710 if ( it_s->second.empty() )
00711 ++it_s;
00712 else
00713 ok = true;
00714
00715 if (ok)
00716 return edge_iterator( m_edges.begin(), m_edges.end(), it_s,
00717 it_s->second.begin() );
00718 else
00719 return edge_end();
00720
00721 }
00722
00723
00727 template <class S, class A, class Comp>
00728 typename claw::graph<S, A, Comp>::edge_iterator
00729 claw::graph<S, A, Comp>::edge_end() const
00730 {
00731 return edge_iterator( m_edges.begin(), m_edges.end(), m_edges.end(),
00732 typename neighbours_list::const_iterator() );
00733 }
00734
00735
00740 template <class S, class A, class Comp>
00741 typename claw::graph<S, A, Comp>::edge_iterator
00742 claw::graph<S, A, Comp>::edge_begin( const vertex_type& s1,
00743 const vertex_type& s2 ) const
00744 {
00745 if ( edge_exists(s1, s2) )
00746 {
00747 typename graph_content::const_iterator it_s1;
00748
00749 it_s1 = m_edges.find(s1);
00750 return edge_iterator( m_edges.begin(), m_edges.end(), it_s1,
00751 it_s1->second.find(s2) );
00752 }
00753 else
00754 return edge_end();
00755 }
00756
00757
00762 template <class S, class A, class Comp>
00763 typename claw::graph<S, A, Comp>::reverse_edge_iterator
00764 claw::graph<S, A, Comp>::edge_rbegin() const
00765 {
00766 return reverse_edge_iterator( edge_end() );
00767 }
00768
00769
00773 template <class S, class A, class Comp>
00774 typename claw::graph<S, A, Comp>::reverse_edge_iterator
00775 claw::graph<S, A, Comp>::edge_rend() const
00776 {
00777 return reverse_edge_iterator( edge_begin() );
00778 }
00779
00780
00785 template <class S, class A, class Comp>
00786 typename claw::graph<S, A, Comp>::reverse_edge_iterator
00787 claw::graph<S, A, Comp>::edge_rbegin
00788 ( const vertex_type& s1, const vertex_type& s2 ) const
00789 {
00790 reverse_edge_iterator it = edge_begin(s1, s2);
00791
00792 if ( it != edge_end() )
00793 ++it;
00794
00795 return reverse_edge_iterator( it );
00796 }
00797
00798
00804 template <class S, class A, class Comp>
00805 const typename claw::graph<S, A, Comp>::edge_type&
00806 claw::graph<S, A, Comp>::label( const vertex_type& s,
00807 const vertex_type& r ) const
00808 {
00809 typename graph_content::const_iterator it_s = m_edges.find(s);
00810
00811 if ( it_s == m_edges.end() )
00812 throw graph_exception
00813 ("claw::graph::label(): unkonwn source vertex.");
00814 else
00815 {
00816 typename neighbours_list::const_iterator it_r = it_s->second.find(r);
00817
00818 if ( it_r == it_s->second.end() )
00819 throw graph_exception
00820 ("claw::graph::label(): destination is not a neighbor.");
00821 else
00822 return it_r->second;
00823 }
00824 }
00825
00826
00831 template <class S, class A, class Comp>
00832 unsigned int
00833 claw::graph<S, A, Comp>::outer_degree( const vertex_type& s ) const
00834 {
00835 typename graph_content::const_iterator it = m_edges.find(s);
00836
00837 if (it == m_edges.end())
00838 throw graph_exception("claw::graph::outer_degree(): unknown vertex.");
00839 else
00840 return it->second.size();
00841 }
00842
00843
00848 template <class S, class A, class Comp>
00849 unsigned int
00850 claw::graph<S, A, Comp>::inner_degree( const vertex_type& s ) const
00851 {
00852 typename std::map<S, unsigned int, Comp>::const_iterator it;
00853 it = m_inner_degrees.find(s);
00854
00855 if (it == m_inner_degrees.end())
00856 throw graph_exception
00857 ("claw::graph::inner_degree(): unkown vertex.");
00858 else
00859 return it->second;
00860 }
00861
00862
00866 template <class S, class A, class Comp>
00867 unsigned int claw::graph<S, A, Comp>::vertices_count() const
00868 {
00869 return m_edges.size();
00870 }
00871
00872
00876 template <class S, class A, class Comp>
00877 unsigned int claw::graph<S, A, Comp>::edges_count() const
00878 {
00879 return m_edges_count;
00880 }
00881