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.
39claw::graph_exception::graph_exception() throw()
45/*---------------------------------------------------------------------------*/
48 * \param s An explanation of the problem.
50claw::graph_exception::graph_exception( const std::string& s) throw()
56/*---------------------------------------------------------------------------*/
60claw::graph_exception::~graph_exception() throw()
63} // ~graph_exception()
65/*---------------------------------------------------------------------------*/
67 * \brief Get an explanation of the problem.
69const char* claw::graph_exception::what() const throw()
77/*---------------------------------------------------------------------------*/
79 * \brief Constructor of the graph_vertex_iterator class.
81template <class S, class A, class Comp>
82claw::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.
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++()
98} // operator++() [preincrement]
100/*---------------------------------------------------------------------------*/
102 * \brief Postincrement.
103 * \pre Iterator is not at the end of the container.
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)
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.
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--()
125} // operator--() [predecrement]
127/*---------------------------------------------------------------------------*/
129 * \brief Postdecrement.
130 * \pre Iterator is not at the begining of the container.
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)
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.
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
150 return m_iterator->first;
153/*---------------------------------------------------------------------------*/
156 * \pre Iterator is not at the end of the container.
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
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.
171template <class S, class A, class Comp>
172bool 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.
184template <class S, class A, class Comp>
185bool 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.
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)
202} // graph_vertex_iterator() [constructor on an iterator]
207/*---------------------------------------------------------------------------*/
209 * \brief Constructor.
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)
216} // edge::edge [constructor]
218/*---------------------------------------------------------------------------*/
220 * \brief Gets edge's label.
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
226 assert(m_label != NULL);
230/*---------------------------------------------------------------------------*/
232 * \brief Gets edge's source.
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
238 assert(m_source != NULL);
242/*---------------------------------------------------------------------------*/
244 * \brief Gets edge's target.
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
250 assert(m_target != NULL);
254/*---------------------------------------------------------------------------*/
256 * \brief Sets label, source and taget.
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 )
270/*---------------------------------------------------------------------------*/
272 * \brief Constructor of the graph_edge_iterator class.
274template <class S, class A, class Comp>
275claw::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.
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++()
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.
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)
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.
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--()
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.
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)
383 graph_edge_iterator it_tmp(*this);
386} // operator--() [postdecrement]
388/*---------------------------------------------------------------------------*/
391 * \pre Iterator is not at the end of the container.
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
400/*---------------------------------------------------------------------------*/
403 * \pre Iterator is not at the end of the container.
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
412/*---------------------------------------------------------------------------*/
415 * \param it Iterator to compare to.
416 * \pre Iterator and it are not at the end of their respective containers.
418template <class S, class A, class Comp>
419bool 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.
447template <class S, class A, class Comp>
448bool 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.
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)
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.
483template <class S, class A, class Comp>
484claw::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.
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 )
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.
521template <class S, class A, class Comp>
522void 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.
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
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.
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
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.
579template <class S, class A, class Comp>
580void 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.
594template <class S, class A, class Comp>
595typename claw::graph<S, A, Comp>::vertex_iterator
596claw::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.
605template <class S, class A, class Comp>
606typename claw::graph<S, A, Comp>::vertex_iterator
607claw::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.
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
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.
629template <class S, class A, class Comp>
630typename claw::graph<S, A, Comp>::reverse_vertex_iterator
631claw::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.
640template <class S, class A, class Comp>
641typename claw::graph<S, A, Comp>::reverse_vertex_iterator
642claw::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.
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
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.
669template <class S, class A, class Comp>
670typename claw::graph<S, A, Comp>::edge_iterator
671claw::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.
695template <class S, class A, class Comp>
696typename claw::graph<S, A, Comp>::edge_iterator
697claw::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.
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
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.
730template <class S, class A, class Comp>
731typename claw::graph<S, A, Comp>::reverse_edge_iterator
732claw::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.
741template <class S, class A, class Comp>
742typename claw::graph<S, A, Comp>::reverse_edge_iterator
743claw::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.
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
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.
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
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.
799template <class S, class A, class Comp>
800std::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
815template <class S, class A, class Comp>
816std::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.
832template <class S, class A, class Comp>
833std::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.
842template <class S, class A, class Comp>
843std::size_t claw::graph<S, A, Comp>::edges_count() const
845 return m_edges_count;
846} // graph::edges_count()