Claw  1.7.3
graph.tpp
1 /*
2  CLAW - a C++ Library Absolutely Wonderful
3 
4  CLAW is a free library without any particular aim but being useful to
5  anyone.
6 
7  Copyright (C) 2005-2011 Julien Jorge
8 
9  This library is free software; you can redistribute it and/or
10  modify it under the terms of the GNU Lesser General Public
11  License as published by the Free Software Foundation; either
12  version 2.1 of the License, or (at your option) any later version.
13 
14  This library is distributed in the hope that it will be useful,
15  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  Lesser General Public License for more details.
18 
19  You should have received a copy of the GNU Lesser General Public
20  License along with this library; if not, write to the Free Software
21  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 
23  contact: julien.jorge@gamned.org
24 */
25 /**
26  * \file graph.tpp
27  * \brief Implementation of the claw::graph class.
28  * \author Julien Jorge
29  */
30 #include <cassert>
31 #include <algorithm>
32 
33 #include <claw/functional.hpp>
34 
35 /*---------------------------------------------------------------------------*/
36 /**
37  * \brief Default constructor.
38  */
39 claw::graph_exception::graph_exception() throw()
40  : m_msg("No message")
41 {
42 
43 } // graph_exception()
44 
45 /*---------------------------------------------------------------------------*/
46 /**
47  * \brief Constructor.
48  * \param s An explanation of the problem.
49  */
50 claw::graph_exception::graph_exception( const std::string& s) throw()
51  : m_msg(s)
52 {
53 
54 } // graph_exception()
55 
56 /*---------------------------------------------------------------------------*/
57 /**
58  * \brief Destructor.
59  */
60 claw::graph_exception::~graph_exception() throw()
61 {
62 
63 } // ~graph_exception()
64 
65 /*---------------------------------------------------------------------------*/
66 /**
67  * \brief Get an explanation of the problem.
68  */
69 const char* claw::graph_exception::what() const throw()
70 {
71  return m_msg.c_str();
72 } // what()
73 
74 
75 
76 
77 /*---------------------------------------------------------------------------*/
78 /**
79  * \brief Constructor of the graph_vertex_iterator class.
80  */
81 template <class S, class A, class Comp>
82 claw::graph<S, A, Comp>::graph_vertex_iterator::graph_vertex_iterator()
83 {
84 
85 } // graph_vertex_iterator() [constructor]
86 
87 /*---------------------------------------------------------------------------*/
88 /**
89  * \brief Preincrement.
90  * \pre Iterator is not at the end of the container.
91  */
92 template <class S, class A, class Comp>
93 typename claw::graph<S, A, Comp>::graph_vertex_iterator&
94 claw::graph<S, A, Comp>::graph_vertex_iterator::operator++()
95 {
96  ++m_iterator;
97  return *this;
98 } // operator++() [preincrement]
99 
100 /*---------------------------------------------------------------------------*/
101 /**
102  * \brief Postincrement.
103  * \pre Iterator is not at the end of the container.
104  */
105 template <class S, class A, class Comp>
106 typename claw::graph<S, A, Comp>::graph_vertex_iterator
107 claw::graph<S, A, Comp>::graph_vertex_iterator::operator++(int)
108 {
109  graph_vertex_iterator it_tmp(*this);
110  m_iterator++;
111  return *this;
112 } // operator++() [postincrement]
113 
114 /*---------------------------------------------------------------------------*/
115 /**
116  * \brief Predecrement.
117  * \pre Iterator is not at the begining of the container.
118  */
119 template <class S, class A, class Comp>
120 typename claw::graph<S, A, Comp>::graph_vertex_iterator&
121 claw::graph<S, A, Comp>::graph_vertex_iterator::operator--()
122 {
123  --m_iterator;
124  return *this;
125 } // operator--() [predecrement]
126 
127 /*---------------------------------------------------------------------------*/
128 /**
129  * \brief Postdecrement.
130  * \pre Iterator is not at the begining of the container.
131  */
132 template <class S, class A, class Comp>
133 typename claw::graph<S, A, Comp>::graph_vertex_iterator
134 claw::graph<S, A, Comp>::graph_vertex_iterator::operator--(int)
135 {
136  graph_vertex_iterator it_tmp(*this);
137  m_iterator--;
138  return it_tmp;
139 } // operator--() [postdecrement]
140 
141 /*---------------------------------------------------------------------------*/
142 /**
143  * \brief Dereference.
144  * \pre Iterator is not at the end of the container.
145  */
146 template <class S, class A, class Comp>
147 typename claw::graph<S, A, Comp>::graph_vertex_iterator::reference
148 claw::graph<S, A, Comp>::graph_vertex_iterator::operator*() const
149 {
150  return m_iterator->first;
151 } // operator*()
152 
153 /*---------------------------------------------------------------------------*/
154 /**
155  * \brief Reference.
156  * \pre Iterator is not at the end of the container.
157  */
158 template <class S, class A, class Comp>
159 typename claw::graph<S, A, Comp>::graph_vertex_iterator::pointer
160 claw::graph<S, A, Comp>::graph_vertex_iterator::operator->() const
161 {
162  return &(m_iterator->first);
163 } // operator->()
164 
165 /*---------------------------------------------------------------------------*/
166 /**
167  * \brief Equality.
168  * \param it Iterator to compare to.
169  * \pre Iterator and it are not at the end of their respective containers.
170  */
171 template <class S, class A, class Comp>
172 bool claw::graph<S, A, Comp>::graph_vertex_iterator::operator==
173 (const graph_vertex_iterator& it) const
174 {
175  return m_iterator == it.m_iterator;
176 } // operator==()
177 
178 /*---------------------------------------------------------------------------*/
179 /**
180  * \brief Difference.
181  * \param it Iterator to compare to.
182  * \pre Iterator and it are not at the end of their respective containers.
183  */
184 template <class S, class A, class Comp>
185 bool claw::graph<S, A, Comp>::graph_vertex_iterator::operator!=
186 (const graph_vertex_iterator& it) const
187 {
188  return m_iterator != it.m_iterator;
189 } // operator!=()
190 
191 /*---------------------------------------------------------------------------*/
192 /**
193  * \brief Constructor with an iterator on graph class data.
194  * \param it Iterator where scan starts.
195  */
196 template <class S, class A, class Comp>
197 claw::graph<S, A, Comp>::graph_vertex_iterator::graph_vertex_iterator
198 (typename graph_content::const_iterator it)
199  : m_iterator(it)
200 {
201 
202 } // graph_vertex_iterator() [constructor on an iterator]
203 
204 
205 
206 
207 /*---------------------------------------------------------------------------*/
208 /**
209  * \brief Constructor.
210  */
211 template <class S, class A, class Comp>
212 claw::graph<S, A, Comp>::graph_edge_iterator::edge::edge()
213  : m_label(NULL), m_source(NULL), m_target(NULL)
214 {
215 
216 } // edge::edge [constructor]
217 
218 /*---------------------------------------------------------------------------*/
219 /**
220  * \brief Gets edge's label.
221  */
222 template <class S, class A, class Comp>
223 const typename claw::graph<S, A, Comp>::edge_type&
224 claw::graph<S, A, Comp>::graph_edge_iterator::edge::label() const
225 {
226  assert(m_label != NULL);
227  return *m_label;
228 } // edge::label()
229 
230 /*---------------------------------------------------------------------------*/
231 /**
232  * \brief Gets edge's source.
233  */
234 template <class S, class A, class Comp>
235 const typename claw::graph<S, A, Comp>::vertex_type&
236 claw::graph<S, A, Comp>::graph_edge_iterator::edge::source() const
237 {
238  assert(m_source != NULL);
239  return *m_source;
240 } // edge::source()
241 
242 /*---------------------------------------------------------------------------*/
243 /**
244  * \brief Gets edge's target.
245  */
246 template <class S, class A, class Comp>
247 const typename claw::graph<S, A, Comp>::vertex_type&
248 claw::graph<S, A, Comp>::graph_edge_iterator::edge::target() const
249 {
250  assert(m_target != NULL);
251  return *m_target;
252 } // edge::target()
253 
254 /*---------------------------------------------------------------------------*/
255 /**
256  * \brief Sets label, source and taget.
257  */
258 template <class S, class A, class Comp>
259 void claw::graph<S, A, Comp>::graph_edge_iterator::edge::
260 set( const edge_type& l, const vertex_type& s, const vertex_type& t )
261 {
262  m_label = &l;
263  m_source = &s;
264  m_target = &t;
265 } // edge::set()
266 
267 
268 
269 
270 /*---------------------------------------------------------------------------*/
271 /**
272  * \brief Constructor of the graph_edge_iterator class.
273  */
274 template <class S, class A, class Comp>
275 claw::graph<S, A, Comp>::graph_edge_iterator::graph_edge_iterator()
276 {
277 
278 } // graph_edge_iterator() [constructor]
279 
280 /*---------------------------------------------------------------------------*/
281 /**
282  * \brief Preincrement.
283  * \pre Iterator is not at the end of the container.
284  */
285 template <class S, class A, class Comp>
286 typename claw::graph<S, A, Comp>::graph_edge_iterator&
287 claw::graph<S, A, Comp>::graph_edge_iterator::operator++()
288 {
289  bool ok = true;
290  ++m_neighbours_iterator;
291 
292  // end of a neighbourhood
293  if ( m_neighbours_iterator == m_vertex_iterator->second.end() )
294  {
295  // find next edge or end.
296  ok = false;
297  ++m_vertex_iterator;
298 
299  while ( (m_vertex_iterator != m_vertex_end) && !ok )
300  if ( !m_vertex_iterator->second.empty() )
301  {
302  ok = true;
303  m_neighbours_iterator = m_vertex_iterator->second.begin();
304  }
305  else
306  ++m_vertex_iterator;
307  }
308 
309  if (ok)
310  m_edge.set( m_neighbours_iterator->second, m_vertex_iterator->first,
311  m_neighbours_iterator->first );
312 
313  return *this;
314 } // operator++() [preincrement]
315 
316 /*---------------------------------------------------------------------------*/
317 /**
318  * \brief Postincrement.
319  * \pre Iterator is not at the end of the container.
320  */
321 template <class S, class A, class Comp>
322 typename claw::graph<S, A, Comp>::graph_edge_iterator
323 claw::graph<S, A, Comp>::graph_edge_iterator::operator++(int)
324 {
325  graph_edge_iterator it_tmp(*this);
326  ++(*this);
327  return it_tmp;
328 } // operator++() [postincrement]
329 
330 /*---------------------------------------------------------------------------*/
331 /**
332  * \brief Predecrement.
333  * \pre Iterator is not at the begining of the container.
334  */
335 template <class S, class A, class Comp>
336 typename claw::graph<S, A, Comp>::graph_edge_iterator&
337 claw::graph<S, A, Comp>::graph_edge_iterator::operator--()
338 {
339  bool ok = true;
340 
341  if (m_vertex_iterator == m_vertex_end)
342  {
343  --m_vertex_iterator;
344  m_neighbours_iterator = m_vertex_iterator->second.end();
345  }
346 
347  // begining of a neighbourhood
348  if ( m_neighbours_iterator == m_vertex_iterator->second.begin() )
349  {
350  ok = false;
351  // find previous edge or begining.
352  while ( (m_vertex_iterator != m_vertex_begin) && !ok )
353  {
354  --m_vertex_iterator;
355  if ( !m_vertex_iterator->second.empty() )
356  {
357  ok = true;
358  m_neighbours_iterator = --m_vertex_iterator->second.end();
359  }
360  }
361  }
362  else
363  --m_neighbours_iterator;
364 
365  if (!ok)
366  m_vertex_iterator == m_vertex_end;
367  else
368  m_edge.set( m_neighbours_iterator->second, m_vertex_iterator->first,
369  m_neighbours_iterator->first );
370 
371  return *this;
372 } // operator--() [predecrement]
373 
374 /*---------------------------------------------------------------------------*/
375 /**
376  * \brief postdecrement.
377  * \pre Iterator is not at the begining of the container.
378  */
379 template <class S, class A, class Comp>
380 typename claw::graph<S, A, Comp>::graph_edge_iterator
381 claw::graph<S, A, Comp>::graph_edge_iterator::operator--(int)
382 {
383  graph_edge_iterator it_tmp(*this);
384  --(*this);
385  return it_tmp;
386 } // operator--() [postdecrement]
387 
388 /*---------------------------------------------------------------------------*/
389 /**
390  * \brief Reference.
391  * \pre Iterator is not at the end of the container.
392  */
393 template <class S, class A, class Comp>
394 typename claw::graph<S, A, Comp>::graph_edge_iterator::reference
395 claw::graph<S, A, Comp>::graph_edge_iterator::operator*() const
396 {
397  return m_edge;
398 } // operator*()
399 
400 /*---------------------------------------------------------------------------*/
401 /**
402  * \brief Pointer.
403  * \pre Iterator is not at the end of the container.
404  */
405 template <class S, class A, class Comp>
406 typename claw::graph<S, A, Comp>::graph_edge_iterator::pointer
407 claw::graph<S, A, Comp>::graph_edge_iterator::operator->() const
408 {
409  return &m_edge;
410 } // operator->()
411 
412 /*---------------------------------------------------------------------------*/
413 /**
414  * \brief Equality.
415  * \param it Iterator to compare to.
416  * \pre Iterator and it are not at the end of their respective containers.
417  */
418 template <class S, class A, class Comp>
419 bool claw::graph<S, A, Comp>::graph_edge_iterator::operator==
420 (const graph_edge_iterator& it) const
421 {
422  // both are empty
423  if ( m_vertex_begin == m_vertex_end )
424  return (it.m_vertex_begin == it.m_vertex_end)
425  && (m_vertex_begin == it.m_vertex_begin);
426  else
427  if ( it.m_vertex_begin == it.m_vertex_end ) // -it- is empty
428  return false;
429  else
430  // none is empty, perheaps at the end ?
431  if (m_vertex_iterator == m_vertex_end)
432  return (it.m_vertex_iterator == it.m_vertex_end)
433  && (m_vertex_begin == it.m_vertex_begin);
434  else
435  if (it.m_vertex_iterator == it.m_vertex_end)
436  return false;
437  else
438  return m_neighbours_iterator == it.m_neighbours_iterator;
439 } // operator==()
440 
441 /*---------------------------------------------------------------------------*/
442 /**
443  * \brief Difference.
444  * \param it Iterator to compare to.
445  * \pre Iterator and it are not at the end of their respective containers.
446  */
447 template <class S, class A, class Comp>
448 bool claw::graph<S, A, Comp>::graph_edge_iterator::operator!=
449 (const graph_edge_iterator& it) const
450 {
451  return !(*this == it);
452 } // operator!=()
453 
454 /*---------------------------------------------------------------------------*/
455 /**
456  * \brief Constructor with an iterator on graph class data.
457  * \param it_begin Iterator on the first node.
458  * \param it_end Iterator on the last node.
459  * \param it_s Iterator on current edge's source.
460  * \param it_d Iterator where scan starts.
461  */
462 template <class S, class A, class Comp>
463 claw::graph<S, A, Comp>::graph_edge_iterator::graph_edge_iterator
464 ( typename graph_content::const_iterator it_begin,
465  typename graph_content::const_iterator it_end,
466  typename graph_content::const_iterator it_s,
467  typename neighbours_list::const_iterator it_d)
468  : m_vertex_begin(it_begin), m_vertex_end(it_end),
469  m_vertex_iterator(it_s), m_neighbours_iterator(it_d)
470 {
471  if (m_vertex_begin != m_vertex_end)
472  m_edge.set( m_neighbours_iterator->second, m_vertex_iterator->first,
473  m_neighbours_iterator->first );
474 } // graph_edge_iterator() [constructor on an iterator]
475 
476 
477 
478 
479 /*---------------------------------------------------------------------------*/
480 /**
481  * \brief Constructor.
482  */
483 template <class S, class A, class Comp>
484 claw::graph<S, A, Comp>::graph()
485  : m_edges_count(0)
486 {
487 
488 } // graph::graph() [constructor]
489 
490 /*---------------------------------------------------------------------------*/
491 /**
492  * \brief Add an edge in the graph.
493  * \param s1 Tail of the edge.
494  * \param s2 Head of the edgre.
495  * \param e The label on the edge.
496  */
497 template <class S, class A, class Comp>
498 void claw::graph<S, A, Comp>::add_edge
499 ( const vertex_type& s1, const vertex_type& s2, const edge_type& e )
500 {
501  if ( !edge_exists(s1, s2) )
502  {
503  // s2 is not a neighbor of s1
504  ++m_edges_count;
505 
506  add_vertex(s1);
507  add_vertex(s2);
508 
509  // in all cases, s2 as one more inner edge
510  ++m_inner_degrees[s2];
511  }
512 
513  m_edges[s1][s2] = e;
514 } // graph::add_edge()
515 
516 /*---------------------------------------------------------------------------*/
517 /**
518  * \brief Add a vertex.
519  * \param s The vertex to add.
520  */
521 template <class S, class A, class Comp>
522 void claw::graph<S, A, Comp>::add_vertex( const vertex_type& s )
523 {
524  std::pair<S, neighbours_list> p;
525 
526  if (m_edges.find(s) == m_edges.end())
527  {
528  // Add the vertex in the adjacency list.
529  p.first = s;
530  m_edges.insert(p);
531  m_inner_degrees[s] = 0;
532  }
533 } // graph::add_vertex()
534 
535 /*---------------------------------------------------------------------------*/
536 /**
537  * \brief Check if there is an edge linking to vertices.
538  * \param s Vertex at the tail of the edge.
539  * \param r Vertex at the head of the edge.
540  */
541 template <class S, class A, class Comp>
542 bool claw::graph<S, A, Comp>::edge_exists
543 ( const vertex_type& s, const vertex_type& r ) const
544 {
545  typename graph_content::const_iterator it = m_edges.find(s);
546 
547  if ( it == m_edges.end() )
548  return false;
549  else
550  return it->second.find(r) != it->second.end();
551 } // graph::edge_exists()
552 
553 /*---------------------------------------------------------------------------*/
554 /**
555  * \brief Get the neighbors of a vertex.
556  * \param s The vertex.
557  * \param v (out) The neighbors.
558  */
559 template <class S, class A, class Comp>
560 void claw::graph<S, A, Comp>::neighbours
561 (const vertex_type& s, std::vector<vertex_type>& v) const
562 {
563  typename graph_content::const_iterator it_s = m_edges.find(s);
564  v.clear();
565 
566  if ( it_s != m_edges.end() )
567  {
568  v.resize( it_s->second.size() );
569  std::transform( it_s->second.begin(), it_s->second.end(), v.begin(),
570  const_first<S,A>() );
571  }
572 } // graph::neighbours()
573 
574 /*---------------------------------------------------------------------------*/
575 /**
576  * \brief Get all the vertices.
577  * \param v (out) The vertices.
578  */
579 template <class S, class A, class Comp>
580 void claw::graph<S, A, Comp>::vertices(std::vector<vertex_type>& v) const
581 {
582  v.clear();
583  v.resize(m_edges.size());
584 
585  std::transform( m_edges.begin(), m_edges.end(), v.begin(),
586  const_first<S,neighbours_list>() );
587 } // graph::vertices()
588 
589 /*---------------------------------------------------------------------------*/
590 /**
591  * \brief Get a node iterator on the first node.
592  * \remark Returns vertex_end() if graph is empty.
593  */
594 template <class S, class A, class Comp>
595 typename claw::graph<S, A, Comp>::vertex_iterator
596 claw::graph<S, A, Comp>::vertex_begin() const
597 {
598  return vertex_iterator( m_edges.begin() );
599 } // graph::vertex_begin()
600 
601 /*---------------------------------------------------------------------------*/
602 /**
603  * \brief Get a node iterator past the last node.
604  */
605 template <class S, class A, class Comp>
606 typename claw::graph<S, A, Comp>::vertex_iterator
607 claw::graph<S, A, Comp>::vertex_end() const
608 {
609  return vertex_iterator( m_edges.end() );
610 } // graph::vertex_end()
611 
612 /*---------------------------------------------------------------------------*/
613 /**
614  * \brief Get a node iterator on a particular node.
615  * \remark Returns vertex_end() if S is not found.
616  */
617 template <class S, class A, class Comp>
618 typename claw::graph<S, A, Comp>::vertex_iterator
619 claw::graph<S, A, Comp>::vertex_begin( const vertex_type& s ) const
620 {
621  return vertex_iterator( m_edges.find(s) );
622 } // graph::vertex_begin()
623 
624 /*---------------------------------------------------------------------------*/
625 /**
626  * \brief Get a reverse node iterator on the first node.
627  * \remark Returns vertex_rend() if graph is empty.
628  */
629 template <class S, class A, class Comp>
630 typename claw::graph<S, A, Comp>::reverse_vertex_iterator
631 claw::graph<S, A, Comp>::vertex_rbegin() const
632 {
633  return reverse_vertex_iterator( vertex_end() );
634 } // graph::vertex_rbegin()
635 
636 /*---------------------------------------------------------------------------*/
637 /**
638  * \brief Get a reverse node iterator past the last node.
639  */
640 template <class S, class A, class Comp>
641 typename claw::graph<S, A, Comp>::reverse_vertex_iterator
642 claw::graph<S, A, Comp>::vertex_rend() const
643 {
644  return reverse_vertex_iterator( vertex_begin() );
645 } // graph::vertex_rend()
646 
647 /*---------------------------------------------------------------------------*/
648 /**
649  * \brief Get a reverse node iterator just after a particular node.
650  * \remark Returns vertex_rend() if s is not found.
651  */
652 template <class S, class A, class Comp>
653 typename claw::graph<S, A, Comp>::reverse_vertex_iterator
654 claw::graph<S, A, Comp>::vertex_rbegin( const vertex_type& s ) const
655 {
656  vertex_iterator it = vertex_begin(s);
657 
658  if (it != vertex_end())
659  ++it;
660 
661  return reverse_vertex_iterator( it );
662 } // graph::vertex_rbegin()
663 
664 /*---------------------------------------------------------------------------*/
665 /**
666  * \brief Get an edge iterator on the first edge.
667  * \remark Returns edge_end() if there's no edge in the graph.
668  */
669 template <class S, class A, class Comp>
670 typename claw::graph<S, A, Comp>::edge_iterator
671 claw::graph<S, A, Comp>::edge_begin() const
672 {
673  bool ok = false;
674  typename graph_content::const_iterator it_s;
675  it_s = m_edges.begin();
676 
677  while ( (it_s != m_edges.end()) && !ok )
678  if ( it_s->second.empty() )
679  ++it_s;
680  else
681  ok = true;
682 
683  if (ok)
684  return edge_iterator( m_edges.begin(), m_edges.end(), it_s,
685  it_s->second.begin() );
686  else
687  return edge_end();
688 
689 } // graph::edge_begin()
690 
691 /*---------------------------------------------------------------------------*/
692 /**
693  * \brief Get an edge iterator after the last edge.
694  */
695 template <class S, class A, class Comp>
696 typename claw::graph<S, A, Comp>::edge_iterator
697 claw::graph<S, A, Comp>::edge_end() const
698 {
699  return edge_iterator( m_edges.begin(), m_edges.end(), m_edges.end(),
700  typename neighbours_list::const_iterator() );
701 } // graph::edge_end()
702 
703 /*---------------------------------------------------------------------------*/
704 /**
705  * \brief Get en iterator on a particular edge .
706  * \remark Returns edge_end() if edge (s1,s2) is not found.
707  */
708 template <class S, class A, class Comp>
709 typename claw::graph<S, A, Comp>::edge_iterator
710 claw::graph<S, A, Comp>::edge_begin
711 ( const vertex_type& s1, const vertex_type& s2 ) const
712 {
713  if ( edge_exists(s1, s2) )
714  {
715  typename graph_content::const_iterator it_s1;
716 
717  it_s1 = m_edges.find(s1);
718  return edge_iterator( m_edges.begin(), m_edges.end(), it_s1,
719  it_s1->second.find(s2) );
720  }
721  else
722  return edge_end();
723 } // graph::edge_()
724 
725 /*---------------------------------------------------------------------------*/
726 /**
727  * \brief Get a reverse edge iterator on the first edge.
728  * \remark Returns redge_end() if there's no edge in the graph.
729  */
730 template <class S, class A, class Comp>
731 typename claw::graph<S, A, Comp>::reverse_edge_iterator
732 claw::graph<S, A, Comp>::edge_rbegin() const
733 {
734  return reverse_edge_iterator( edge_end() );
735 } // graph::edge_rbegin()
736 
737 /*---------------------------------------------------------------------------*/
738 /**
739  * \brief Get a reverse edge iterator after the last edge.
740  */
741 template <class S, class A, class Comp>
742 typename claw::graph<S, A, Comp>::reverse_edge_iterator
743 claw::graph<S, A, Comp>::edge_rend() const
744 {
745  return reverse_edge_iterator( edge_begin() );
746 } // graph::edge_rend()
747 
748 /*---------------------------------------------------------------------------*/
749 /**
750  * \brief Get a reverse edge iterator on a particular edge.
751  * \remark Returns redge_end() if edge (s1,s2) is not found.
752  */
753 template <class S, class A, class Comp>
754 typename claw::graph<S, A, Comp>::reverse_edge_iterator
755 claw::graph<S, A, Comp>::edge_rbegin
756 ( const vertex_type& s1, const vertex_type& s2 ) const
757 {
758  reverse_edge_iterator it = edge_begin(s1, s2);
759 
760  if ( it != edge_end() )
761  ++it;
762 
763  return reverse_edge_iterator( it );
764 } // graph::edge_rbegin()
765 
766 /*---------------------------------------------------------------------------*/
767 /**
768  * \brief Get the label of an edge.
769  * \param s The vertex at the tail of the edge.
770  * \param r The vertex at the head of the edge.
771  */
772 template <class S, class A, class Comp>
773 const typename claw::graph<S, A, Comp>::edge_type&
774 claw::graph<S, A, Comp>::label
775 ( const vertex_type& s, const vertex_type& r ) const
776 {
777  typename graph_content::const_iterator it_s = m_edges.find(s);
778 
779  if ( it_s == m_edges.end() )
780  throw graph_exception
781  ("claw::graph::label(): unkonwn source vertex.");
782  else
783  {
784  typename neighbours_list::const_iterator it_r = it_s->second.find(r);
785 
786  if ( it_r == it_s->second.end() )
787  throw graph_exception
788  ("claw::graph::label(): destination is not a neighbor.");
789  else
790  return it_r->second;
791  }
792 } // graph::label()
793 
794 /*---------------------------------------------------------------------------*/
795 /**
796  * \brief Get the outter degree of a vertex.
797  * \param s The vertex.
798  */
799 template <class S, class A, class Comp>
800 std::size_t claw::graph<S, A, Comp>::outer_degree( const vertex_type& s ) const
801 {
802  typename graph_content::const_iterator it = m_edges.find(s);
803 
804  if (it == m_edges.end())
805  throw graph_exception("claw::graph::outer_degree(): unknown vertex.");
806  else
807  return it->second.size();
808 } // graph::outer_degree()
809 
810 /*---------------------------------------------------------------------------*/
811 /**
812  * \brief Get the inner degree of a vertex.
813  * \param s The vertex
814  */
815 template <class S, class A, class Comp>
816 std::size_t claw::graph<S, A, Comp>::inner_degree( const vertex_type& s ) const
817 {
818  typename std::map<S, std::size_t, Comp>::const_iterator it;
819  it = m_inner_degrees.find(s);
820 
821  if (it == m_inner_degrees.end())
822  throw graph_exception
823  ("claw::graph::inner_degree(): unkown vertex.");
824  else
825  return it->second;
826 } // graph::inner_degree()
827 
828 /*---------------------------------------------------------------------------*/
829 /**
830  * \brief Get the number of vertices.
831  */
832 template <class S, class A, class Comp>
833 std::size_t claw::graph<S, A, Comp>::vertices_count() const
834 {
835  return m_edges.size();
836 } // graph::vertices_count()
837 
838 /*---------------------------------------------------------------------------*/
839 /**
840  * \brief Get the number of edges.
841  */
842 template <class S, class A, class Comp>
843 std::size_t claw::graph<S, A, Comp>::edges_count() const
844 {
845  return m_edges_count;
846 } // graph::edges_count()
847