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 */
39claw::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 */
50claw::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 */
60claw::graph_exception::~graph_exception() throw()
61{
62
63} // ~graph_exception()
64
65/*---------------------------------------------------------------------------*/
66/**
67 * \brief Get an explanation of the problem.
68 */
69const 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 */
81template <class S, class A, class Comp>
82claw::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 */
92template <class S, class A, class Comp>
93typename claw::graph<S, A, Comp>::graph_vertex_iterator&
94claw::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 */
105template <class S, class A, class Comp>
106typename claw::graph<S, A, Comp>::graph_vertex_iterator
107claw::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 */
119template <class S, class A, class Comp>
120typename claw::graph<S, A, Comp>::graph_vertex_iterator&
121claw::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 */
132template <class S, class A, class Comp>
133typename claw::graph<S, A, Comp>::graph_vertex_iterator
134claw::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 */
146template <class S, class A, class Comp>
147typename claw::graph<S, A, Comp>::graph_vertex_iterator::reference
148claw::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 */
158template <class S, class A, class Comp>
159typename claw::graph<S, A, Comp>::graph_vertex_iterator::pointer
160claw::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 */
171template <class S, class A, class Comp>
172bool 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 */
184template <class S, class A, class Comp>
185bool 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 */
196template <class S, class A, class Comp>
197claw::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 */
211template <class S, class A, class Comp>
212claw::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 */
222template <class S, class A, class Comp>
223const typename claw::graph<S, A, Comp>::edge_type&
224claw::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 */
234template <class S, class A, class Comp>
235const typename claw::graph<S, A, Comp>::vertex_type&
236claw::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 */
246template <class S, class A, class Comp>
247const typename claw::graph<S, A, Comp>::vertex_type&
248claw::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 */
258template <class S, class A, class Comp>
259void claw::graph<S, A, Comp>::graph_edge_iterator::edge::
260set( 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 */
274template <class S, class A, class Comp>
275claw::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 */
285template <class S, class A, class Comp>
286typename claw::graph<S, A, Comp>::graph_edge_iterator&
287claw::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 */
321template <class S, class A, class Comp>
322typename claw::graph<S, A, Comp>::graph_edge_iterator
323claw::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 */
335template <class S, class A, class Comp>
336typename claw::graph<S, A, Comp>::graph_edge_iterator&
337claw::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 */
379template <class S, class A, class Comp>
380typename claw::graph<S, A, Comp>::graph_edge_iterator
381claw::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 */
393template <class S, class A, class Comp>
394typename claw::graph<S, A, Comp>::graph_edge_iterator::reference
395claw::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 */
405template <class S, class A, class Comp>
406typename claw::graph<S, A, Comp>::graph_edge_iterator::pointer
407claw::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 */
418template <class S, class A, class Comp>
419bool 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 */
447template <class S, class A, class Comp>
448bool 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 */
462template <class S, class A, class Comp>
463claw::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 */
483template <class S, class A, class Comp>
484claw::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 */
497template <class S, class A, class Comp>
498void 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 */
521template <class S, class A, class Comp>
522void 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 */
541template <class S, class A, class Comp>
542bool 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 */
559template <class S, class A, class Comp>
560void 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 */
579template <class S, class A, class Comp>
580void 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 */
594template <class S, class A, class Comp>
595typename claw::graph<S, A, Comp>::vertex_iterator
596claw::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 */
605template <class S, class A, class Comp>
606typename claw::graph<S, A, Comp>::vertex_iterator
607claw::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 */
617template <class S, class A, class Comp>
618typename claw::graph<S, A, Comp>::vertex_iterator
619claw::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 */
629template <class S, class A, class Comp>
630typename claw::graph<S, A, Comp>::reverse_vertex_iterator
631claw::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 */
640template <class S, class A, class Comp>
641typename claw::graph<S, A, Comp>::reverse_vertex_iterator
642claw::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 */
652template <class S, class A, class Comp>
653typename claw::graph<S, A, Comp>::reverse_vertex_iterator
654claw::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 */
669template <class S, class A, class Comp>
670typename claw::graph<S, A, Comp>::edge_iterator
671claw::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 */
695template <class S, class A, class Comp>
696typename claw::graph<S, A, Comp>::edge_iterator
697claw::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 */
708template <class S, class A, class Comp>
709typename claw::graph<S, A, Comp>::edge_iterator
710claw::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 */
730template <class S, class A, class Comp>
731typename claw::graph<S, A, Comp>::reverse_edge_iterator
732claw::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 */
741template <class S, class A, class Comp>
742typename claw::graph<S, A, Comp>::reverse_edge_iterator
743claw::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 */
753template <class S, class A, class Comp>
754typename claw::graph<S, A, Comp>::reverse_edge_iterator
755claw::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 */
772template <class S, class A, class Comp>
773const typename claw::graph<S, A, Comp>::edge_type&
774claw::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 */
799template <class S, class A, class Comp>
800std::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 */
815template <class S, class A, class Comp>
816std::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 */
832template <class S, class A, class Comp>
833std::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 */
842template <class S, class A, class Comp>
843std::size_t claw::graph<S, A, Comp>::edges_count() const
844{
845 return m_edges_count;
846} // graph::edges_count()
847