2 CLAW - a C++ Library Absolutely Wonderful
4 CLAW is a free library without any particular aim but being useful to
7 Copyright (C) 2005-2011 Julien Jorge
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.
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.
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
23 contact: julien.jorge@gamned.org
27 * \brief Implementation of the claw::graph class.
28 * \author Julien Jorge
33 #include <claw/functional.hpp>
35 /*---------------------------------------------------------------------------*/
37 * \brief Default constructor.
39 claw::graph_exception::graph_exception() throw()
43 } // graph_exception()
45 /*---------------------------------------------------------------------------*/
48 * \param s An explanation of the problem.
50 claw::graph_exception::graph_exception( const std::string& s) throw()
54 } // graph_exception()
56 /*---------------------------------------------------------------------------*/
60 claw::graph_exception::~graph_exception() throw()
63 } // ~graph_exception()
65 /*---------------------------------------------------------------------------*/
67 * \brief Get an explanation of the problem.
69 const char* claw::graph_exception::what() const throw()
77 /*---------------------------------------------------------------------------*/
79 * \brief Constructor of the graph_vertex_iterator class.
81 template <class S, class A, class Comp>
82 claw::graph<S, A, Comp>::graph_vertex_iterator::graph_vertex_iterator()
85 } // graph_vertex_iterator() [constructor]
87 /*---------------------------------------------------------------------------*/
89 * \brief Preincrement.
90 * \pre Iterator is not at the end of the container.
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++()
98 } // operator++() [preincrement]
100 /*---------------------------------------------------------------------------*/
102 * \brief Postincrement.
103 * \pre Iterator is not at the end of the container.
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)
109 graph_vertex_iterator it_tmp(*this);
112 } // operator++() [postincrement]
114 /*---------------------------------------------------------------------------*/
116 * \brief Predecrement.
117 * \pre Iterator is not at the begining of the container.
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--()
125 } // operator--() [predecrement]
127 /*---------------------------------------------------------------------------*/
129 * \brief Postdecrement.
130 * \pre Iterator is not at the begining of the container.
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)
136 graph_vertex_iterator it_tmp(*this);
139 } // operator--() [postdecrement]
141 /*---------------------------------------------------------------------------*/
143 * \brief Dereference.
144 * \pre Iterator is not at the end of the container.
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
150 return m_iterator->first;
153 /*---------------------------------------------------------------------------*/
156 * \pre Iterator is not at the end of the container.
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
162 return &(m_iterator->first);
165 /*---------------------------------------------------------------------------*/
168 * \param it Iterator to compare to.
169 * \pre Iterator and it are not at the end of their respective containers.
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
175 return m_iterator == it.m_iterator;
178 /*---------------------------------------------------------------------------*/
181 * \param it Iterator to compare to.
182 * \pre Iterator and it are not at the end of their respective containers.
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
188 return m_iterator != it.m_iterator;
191 /*---------------------------------------------------------------------------*/
193 * \brief Constructor with an iterator on graph class data.
194 * \param it Iterator where scan starts.
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)
202 } // graph_vertex_iterator() [constructor on an iterator]
207 /*---------------------------------------------------------------------------*/
209 * \brief Constructor.
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)
216 } // edge::edge [constructor]
218 /*---------------------------------------------------------------------------*/
220 * \brief Gets edge's label.
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
226 assert(m_label != NULL);
230 /*---------------------------------------------------------------------------*/
232 * \brief Gets edge's source.
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
238 assert(m_source != NULL);
242 /*---------------------------------------------------------------------------*/
244 * \brief Gets edge's target.
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
250 assert(m_target != NULL);
254 /*---------------------------------------------------------------------------*/
256 * \brief Sets label, source and taget.
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 )
270 /*---------------------------------------------------------------------------*/
272 * \brief Constructor of the graph_edge_iterator class.
274 template <class S, class A, class Comp>
275 claw::graph<S, A, Comp>::graph_edge_iterator::graph_edge_iterator()
278 } // graph_edge_iterator() [constructor]
280 /*---------------------------------------------------------------------------*/
282 * \brief Preincrement.
283 * \pre Iterator is not at the end of the container.
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++()
290 ++m_neighbours_iterator;
292 // end of a neighbourhood
293 if ( m_neighbours_iterator == m_vertex_iterator->second.end() )
295 // find next edge or end.
299 while ( (m_vertex_iterator != m_vertex_end) && !ok )
300 if ( !m_vertex_iterator->second.empty() )
303 m_neighbours_iterator = m_vertex_iterator->second.begin();
310 m_edge.set( m_neighbours_iterator->second, m_vertex_iterator->first,
311 m_neighbours_iterator->first );
314 } // operator++() [preincrement]
316 /*---------------------------------------------------------------------------*/
318 * \brief Postincrement.
319 * \pre Iterator is not at the end of the container.
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)
325 graph_edge_iterator it_tmp(*this);
328 } // operator++() [postincrement]
330 /*---------------------------------------------------------------------------*/
332 * \brief Predecrement.
333 * \pre Iterator is not at the begining of the container.
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--()
341 if (m_vertex_iterator == m_vertex_end)
344 m_neighbours_iterator = m_vertex_iterator->second.end();
347 // begining of a neighbourhood
348 if ( m_neighbours_iterator == m_vertex_iterator->second.begin() )
351 // find previous edge or begining.
352 while ( (m_vertex_iterator != m_vertex_begin) && !ok )
355 if ( !m_vertex_iterator->second.empty() )
358 m_neighbours_iterator = --m_vertex_iterator->second.end();
363 --m_neighbours_iterator;
366 m_vertex_iterator == m_vertex_end;
368 m_edge.set( m_neighbours_iterator->second, m_vertex_iterator->first,
369 m_neighbours_iterator->first );
372 } // operator--() [predecrement]
374 /*---------------------------------------------------------------------------*/
376 * \brief postdecrement.
377 * \pre Iterator is not at the begining of the container.
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)
383 graph_edge_iterator it_tmp(*this);
386 } // operator--() [postdecrement]
388 /*---------------------------------------------------------------------------*/
391 * \pre Iterator is not at the end of the container.
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
400 /*---------------------------------------------------------------------------*/
403 * \pre Iterator is not at the end of the container.
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
412 /*---------------------------------------------------------------------------*/
415 * \param it Iterator to compare to.
416 * \pre Iterator and it are not at the end of their respective containers.
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
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);
427 if ( it.m_vertex_begin == it.m_vertex_end ) // -it- is empty
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);
435 if (it.m_vertex_iterator == it.m_vertex_end)
438 return m_neighbours_iterator == it.m_neighbours_iterator;
441 /*---------------------------------------------------------------------------*/
444 * \param it Iterator to compare to.
445 * \pre Iterator and it are not at the end of their respective containers.
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
451 return !(*this == it);
454 /*---------------------------------------------------------------------------*/
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.
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)
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]
479 /*---------------------------------------------------------------------------*/
481 * \brief Constructor.
483 template <class S, class A, class Comp>
484 claw::graph<S, A, Comp>::graph()
488 } // graph::graph() [constructor]
490 /*---------------------------------------------------------------------------*/
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.
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 )
501 if ( !edge_exists(s1, s2) )
503 // s2 is not a neighbor of s1
509 // in all cases, s2 as one more inner edge
510 ++m_inner_degrees[s2];
514 } // graph::add_edge()
516 /*---------------------------------------------------------------------------*/
518 * \brief Add a vertex.
519 * \param s The vertex to add.
521 template <class S, class A, class Comp>
522 void claw::graph<S, A, Comp>::add_vertex( const vertex_type& s )
524 std::pair<S, neighbours_list> p;
526 if (m_edges.find(s) == m_edges.end())
528 // Add the vertex in the adjacency list.
531 m_inner_degrees[s] = 0;
533 } // graph::add_vertex()
535 /*---------------------------------------------------------------------------*/
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.
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
545 typename graph_content::const_iterator it = m_edges.find(s);
547 if ( it == m_edges.end() )
550 return it->second.find(r) != it->second.end();
551 } // graph::edge_exists()
553 /*---------------------------------------------------------------------------*/
555 * \brief Get the neighbors of a vertex.
556 * \param s The vertex.
557 * \param v (out) The neighbors.
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
563 typename graph_content::const_iterator it_s = m_edges.find(s);
566 if ( it_s != m_edges.end() )
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>() );
572 } // graph::neighbours()
574 /*---------------------------------------------------------------------------*/
576 * \brief Get all the vertices.
577 * \param v (out) The vertices.
579 template <class S, class A, class Comp>
580 void claw::graph<S, A, Comp>::vertices(std::vector<vertex_type>& v) const
583 v.resize(m_edges.size());
585 std::transform( m_edges.begin(), m_edges.end(), v.begin(),
586 const_first<S,neighbours_list>() );
587 } // graph::vertices()
589 /*---------------------------------------------------------------------------*/
591 * \brief Get a node iterator on the first node.
592 * \remark Returns vertex_end() if graph is empty.
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
598 return vertex_iterator( m_edges.begin() );
599 } // graph::vertex_begin()
601 /*---------------------------------------------------------------------------*/
603 * \brief Get a node iterator past the last node.
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
609 return vertex_iterator( m_edges.end() );
610 } // graph::vertex_end()
612 /*---------------------------------------------------------------------------*/
614 * \brief Get a node iterator on a particular node.
615 * \remark Returns vertex_end() if S is not found.
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
621 return vertex_iterator( m_edges.find(s) );
622 } // graph::vertex_begin()
624 /*---------------------------------------------------------------------------*/
626 * \brief Get a reverse node iterator on the first node.
627 * \remark Returns vertex_rend() if graph is empty.
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
633 return reverse_vertex_iterator( vertex_end() );
634 } // graph::vertex_rbegin()
636 /*---------------------------------------------------------------------------*/
638 * \brief Get a reverse node iterator past the last node.
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
644 return reverse_vertex_iterator( vertex_begin() );
645 } // graph::vertex_rend()
647 /*---------------------------------------------------------------------------*/
649 * \brief Get a reverse node iterator just after a particular node.
650 * \remark Returns vertex_rend() if s is not found.
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
656 vertex_iterator it = vertex_begin(s);
658 if (it != vertex_end())
661 return reverse_vertex_iterator( it );
662 } // graph::vertex_rbegin()
664 /*---------------------------------------------------------------------------*/
666 * \brief Get an edge iterator on the first edge.
667 * \remark Returns edge_end() if there's no edge in the graph.
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
674 typename graph_content::const_iterator it_s;
675 it_s = m_edges.begin();
677 while ( (it_s != m_edges.end()) && !ok )
678 if ( it_s->second.empty() )
684 return edge_iterator( m_edges.begin(), m_edges.end(), it_s,
685 it_s->second.begin() );
689 } // graph::edge_begin()
691 /*---------------------------------------------------------------------------*/
693 * \brief Get an edge iterator after the last edge.
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
699 return edge_iterator( m_edges.begin(), m_edges.end(), m_edges.end(),
700 typename neighbours_list::const_iterator() );
701 } // graph::edge_end()
703 /*---------------------------------------------------------------------------*/
705 * \brief Get en iterator on a particular edge .
706 * \remark Returns edge_end() if edge (s1,s2) is not found.
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
713 if ( edge_exists(s1, s2) )
715 typename graph_content::const_iterator it_s1;
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) );
725 /*---------------------------------------------------------------------------*/
727 * \brief Get a reverse edge iterator on the first edge.
728 * \remark Returns redge_end() if there's no edge in the graph.
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
734 return reverse_edge_iterator( edge_end() );
735 } // graph::edge_rbegin()
737 /*---------------------------------------------------------------------------*/
739 * \brief Get a reverse edge iterator after the last edge.
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
745 return reverse_edge_iterator( edge_begin() );
746 } // graph::edge_rend()
748 /*---------------------------------------------------------------------------*/
750 * \brief Get a reverse edge iterator on a particular edge.
751 * \remark Returns redge_end() if edge (s1,s2) is not found.
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
758 reverse_edge_iterator it = edge_begin(s1, s2);
760 if ( it != edge_end() )
763 return reverse_edge_iterator( it );
764 } // graph::edge_rbegin()
766 /*---------------------------------------------------------------------------*/
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.
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
777 typename graph_content::const_iterator it_s = m_edges.find(s);
779 if ( it_s == m_edges.end() )
780 throw graph_exception
781 ("claw::graph::label(): unkonwn source vertex.");
784 typename neighbours_list::const_iterator it_r = it_s->second.find(r);
786 if ( it_r == it_s->second.end() )
787 throw graph_exception
788 ("claw::graph::label(): destination is not a neighbor.");
794 /*---------------------------------------------------------------------------*/
796 * \brief Get the outter degree of a vertex.
797 * \param s The vertex.
799 template <class S, class A, class Comp>
800 std::size_t claw::graph<S, A, Comp>::outer_degree( const vertex_type& s ) const
802 typename graph_content::const_iterator it = m_edges.find(s);
804 if (it == m_edges.end())
805 throw graph_exception("claw::graph::outer_degree(): unknown vertex.");
807 return it->second.size();
808 } // graph::outer_degree()
810 /*---------------------------------------------------------------------------*/
812 * \brief Get the inner degree of a vertex.
813 * \param s The vertex
815 template <class S, class A, class Comp>
816 std::size_t claw::graph<S, A, Comp>::inner_degree( const vertex_type& s ) const
818 typename std::map<S, std::size_t, Comp>::const_iterator it;
819 it = m_inner_degrees.find(s);
821 if (it == m_inner_degrees.end())
822 throw graph_exception
823 ("claw::graph::inner_degree(): unkown vertex.");
826 } // graph::inner_degree()
828 /*---------------------------------------------------------------------------*/
830 * \brief Get the number of vertices.
832 template <class S, class A, class Comp>
833 std::size_t claw::graph<S, A, Comp>::vertices_count() const
835 return m_edges.size();
836 } // graph::vertices_count()
838 /*---------------------------------------------------------------------------*/
840 * \brief Get the number of edges.
842 template <class S, class A, class Comp>
843 std::size_t claw::graph<S, A, Comp>::edges_count() const
845 return m_edges_count;
846 } // graph::edges_count()