claw::graph< S, A, Comp > Class Template Reference

#include <graph.hpp>

List of all members.


Detailed Description

template<class S, class A, class Comp = std::less<S>>
class claw::graph< S, A, Comp >

Une classe pour gérer les graphs.

Remarks:
Contraintes sur les types :
  • S est LessThanComparable ;
  • A est n'importe quel type assignable et constructible ;
  • Comp est un prédicat binaire tel que Comp(S a, S b) == vrai si a < b.
Author:
Julien Jorge

Definition at line 76 of file graph.hpp.


Public Types

typedef S vertex_type
 Type of the vertices.
typedef A edge_type
 Type of the edges.
typedef Comp vertex_compare
 Binary predicate to compare vertices.
typedef std::map< vertex_type,
edge_type, vertex_compare
neighbours_list
 La liste d'adjacence d'un sommet. vertex_type est le sommet destination, edge_type est l'étiquette de l'arc qui y mène.
typedef std::map< vertex_type,
neighbours_list,
vertex_compare
graph_content
 La liste d'adjacence, représente tout le graph.
typedef claw::graph
< vertex_type, edge_type,
vertex_compare
self_type
 Type of the current structure.
typedef graph_vertex_iterator vertex_iterator
typedef graph_edge_iterator edge_iterator
typedef std::reverse_iterator
< vertex_iterator
reverse_vertex_iterator
typedef std::reverse_iterator
< edge_iterator
reverse_edge_iterator

Public Member Functions

 graph ()
 Constructor.
void add_edge (const vertex_type &s1, const vertex_type &s2, const edge_type &e)
 Ajoute un arc.
void add_vertex (const vertex_type &s)
 Ajoute un sommet.
bool edge_exists (const vertex_type &s, const vertex_type &r) const
 Teste l'existence d'une arête entre deux sommet.
void neighbours (const vertex_type &s, std::vector< vertex_type > &v) const
 Récupère les voisins d'un sommet.
void vertices (std::vector< vertex_type > &v) const
 Récupère la liste d'adjacence.
vertex_iterator vertex_begin () const
 Gets a node iterator on the first node.
vertex_iterator vertex_end () const
 Gets a node iterator past the last node.
vertex_iterator vertex_begin (const vertex_type &s) const
 Gets a node iterator on a particular node.
reverse_vertex_iterator vertex_rbegin () const
 Gets a reverse node iterator on the first node.
reverse_vertex_iterator vertex_rend () const
 Gets a reverse node iterator past the last node.
reverse_vertex_iterator vertex_rbegin (const vertex_type &s) const
 Gets a reverse node iterator just after a particular node.
edge_iterator edge_begin () const
 Gets an edge iterator on the first edge.
edge_iterator edge_end () const
 Gets an edge iterator after the last edge.
edge_iterator edge_begin (const vertex_type &s1, const vertex_type &s2) const
 Gets en iterator on a particular edge .
reverse_edge_iterator edge_rbegin () const
 Gets a reverse edge iterator on the first edge.
reverse_edge_iterator edge_rend () const
 Gets a reverse edge iterator after the last edge.
reverse_edge_iterator edge_rbegin (const vertex_type &s1, const vertex_type &s2) const
 Gets a reverse edge iterator on a particular edge.
const edge_typelabel (const vertex_type &s, const vertex_type &r) const
 Récupère l'étiquette d'une arête.
unsigned int outer_degree (const vertex_type &s) const
 Récupère le degré sortant d'un sommet.
unsigned int inner_degree (const vertex_type &s) const
 Récupère le degré entrant d'un sommet.
unsigned int vertices_count () const
 Gets the number of vertices.
unsigned int edges_count () const
 Gets the number of edges.

Private Attributes

graph_content m_edges
 edge_typedjacency list.
std::map< vertex_type,
unsigned int, vertex_compare
m_inner_degrees
 Degré entrants des sommets.
unsigned int m_edges_count
 Number of edges.

Classes

class  graph_edge_iterator
 Iterator on the graph's edges. More...
class  graph_vertex_iterator
 Iterator on the graph's vertices. More...

Member Typedef Documentation

template<class S, class A, class Comp = std::less<S>>
typedef S claw::graph< S, A, Comp >::vertex_type

Type of the vertices.

Definition at line 80 of file graph.hpp.

template<class S, class A, class Comp = std::less<S>>
typedef A claw::graph< S, A, Comp >::edge_type

Type of the edges.

Definition at line 83 of file graph.hpp.

template<class S, class A, class Comp = std::less<S>>
typedef Comp claw::graph< S, A, Comp >::vertex_compare

Binary predicate to compare vertices.

Definition at line 86 of file graph.hpp.

template<class S, class A, class Comp = std::less<S>>
typedef std::map<vertex_type, edge_type, vertex_compare> claw::graph< S, A, Comp >::neighbours_list

La liste d'adjacence d'un sommet. vertex_type est le sommet destination, edge_type est l'étiquette de l'arc qui y mène.

Definition at line 91 of file graph.hpp.

template<class S, class A, class Comp = std::less<S>>
typedef std::map<vertex_type, neighbours_list, vertex_compare> claw::graph< S, A, Comp >::graph_content

La liste d'adjacence, représente tout le graph.

Definition at line 95 of file graph.hpp.

template<class S, class A, class Comp = std::less<S>>
typedef claw::graph<vertex_type, edge_type, vertex_compare> claw::graph< S, A, Comp >::self_type

Type of the current structure.

Definition at line 98 of file graph.hpp.

template<class S, class A, class Comp = std::less<S>>
typedef graph_vertex_iterator claw::graph< S, A, Comp >::vertex_iterator

Definition at line 227 of file graph.hpp.

template<class S, class A, class Comp = std::less<S>>
typedef graph_edge_iterator claw::graph< S, A, Comp >::edge_iterator

Definition at line 228 of file graph.hpp.

template<class S, class A, class Comp = std::less<S>>
typedef std::reverse_iterator<vertex_iterator> claw::graph< S, A, Comp >::reverse_vertex_iterator

Definition at line 229 of file graph.hpp.

template<class S, class A, class Comp = std::less<S>>
typedef std::reverse_iterator<edge_iterator> claw::graph< S, A, Comp >::reverse_edge_iterator

Definition at line 230 of file graph.hpp.


Constructor & Destructor Documentation

template<class S, class A, class Comp>
claw::graph< S, A, Comp >::graph (  )  [inline]

Constructor.

Definition at line 515 of file graph.tpp.

00516   : m_edges_count(0)
00517 {
00518 
00519 } // graph::graph() [constructor]


Member Function Documentation

template<class S, class A, class Comp>
void claw::graph< S, A, Comp >::add_edge ( const vertex_type s1,
const vertex_type s2,
const edge_type e 
) [inline]

Ajoute un arc.

Parameters:
s1 sommet de départ.
s2 sommet d'arrivée.
e l'étiquête de l'arc.

Definition at line 529 of file graph.tpp.

References claw::graph< S, A, Comp >::add_vertex(), claw::graph< S, A, Comp >::edge_exists(), claw::graph< S, A, Comp >::m_edges, claw::graph< S, A, Comp >::m_edges_count, and claw::graph< S, A, Comp >::m_inner_degrees.

00532 {
00533   if ( !edge_exists(s1, s2) )
00534     {
00535       // s2 n'est pas un voisin de s1
00536       ++m_edges_count;
00537 
00538       add_vertex(s1);
00539       add_vertex(s2); 
00540 
00541       // dans tous les cas s2 a un arc entrant supplémentaire
00542       ++m_inner_degrees[s2]; 
00543     }
00544 
00545   m_edges[s1][s2] = e;
00546 } // graph::add_edge()

template<class S, class A, class Comp>
void claw::graph< S, A, Comp >::add_vertex ( const vertex_type s  )  [inline]

Ajoute un sommet.

Parameters:
s sommet à ajouter.

Definition at line 554 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges, and claw::graph< S, A, Comp >::m_inner_degrees.

Referenced by claw::graph< S, A, Comp >::add_edge().

00555 {
00556   std::pair<S, neighbours_list> p;
00557 
00558   if (m_edges.find(s) == m_edges.end())
00559     {
00560       // ajout dans la liste d'adjacence
00561       p.first = s;
00562       m_edges.insert(p);
00563       m_inner_degrees[s] = 0;
00564     }
00565 } // graph::add_vertex()

template<class S, class A, class Comp>
bool claw::graph< S, A, Comp >::edge_exists ( const vertex_type s,
const vertex_type r 
) const [inline]

Teste l'existence d'une arête entre deux sommet.

Parameters:
s sommet de depart.
r sommet d'arrivée.

Definition at line 574 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

Referenced by claw::graph< S, A, Comp >::add_edge(), and claw::graph< S, A, Comp >::edge_begin().

00576 { 
00577   typename graph_content::const_iterator it = m_edges.find(s);
00578 
00579   if ( it == m_edges.end() )
00580     return false;
00581   else
00582     return it->second.find(r) != it->second.end(); 
00583 } // graph::edge_exists()

template<class S, class A, class Comp>
void claw::graph< S, A, Comp >::neighbours ( const vertex_type s,
std::vector< vertex_type > &  v 
) const [inline]

Récupère les voisins d'un sommet.

Parameters:
s sommet à considérer.
v (out) Les voisins de s.

Definition at line 592 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

00594 { 
00595   typename graph_content::const_iterator it_s = m_edges.find(s);
00596   v.clear();
00597 
00598   if ( it_s != m_edges.end() )
00599     {
00600       v.resize( it_s->second.size() );
00601       std::transform( it_s->second.begin(), it_s->second.end(), v.begin(),
00602                       const_first<S,A>() );
00603     }
00604 } // graph::neighbours()

template<class S, class A, class Comp>
void claw::graph< S, A, Comp >::vertices ( std::vector< vertex_type > &  v  )  const [inline]

Récupère la liste d'adjacence.

Parameters:
v (out) Les sommets du graph.

Definition at line 612 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

00613 { 
00614   v.clear();
00615   v.resize(m_edges.size());
00616 
00617   std::transform( m_edges.begin(), m_edges.end(), v.begin(), 
00618                   const_first<S,neighbours_list>() );
00619 } // graph::vertices()

template<class S, class A, class Comp>
claw::graph< S, A, Comp >::vertex_iterator claw::graph< S, A, Comp >::vertex_begin (  )  const [inline]

Gets a node iterator on the first node.

Remarks:
Returns vertex_end() if graph is empty.

Definition at line 628 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

Referenced by claw::graph< S, A, Comp >::vertex_rbegin(), and claw::graph< S, A, Comp >::vertex_rend().

00629 {
00630   return vertex_iterator( m_edges.begin() );
00631 } // graph::vertex_begin()

template<class S, class A, class Comp>
claw::graph< S, A, Comp >::vertex_iterator claw::graph< S, A, Comp >::vertex_end (  )  const [inline]

Gets a node iterator past the last node.

Definition at line 639 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

Referenced by claw::graph< S, A, Comp >::vertex_rbegin().

00640 {
00641   return vertex_iterator( m_edges.end() );
00642 } // graph::vertex_end()

template<class S, class A, class Comp>
claw::graph< S, A, Comp >::vertex_iterator claw::graph< S, A, Comp >::vertex_begin ( const vertex_type s  )  const [inline]

Gets a node iterator on a particular node.

Remarks:
Returns vertex_end() if S is not found.

Definition at line 651 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

00652 {
00653   return vertex_iterator( m_edges.find(s) );
00654 } // graph::vertex_begin()

template<class S, class A, class Comp>
claw::graph< S, A, Comp >::reverse_vertex_iterator claw::graph< S, A, Comp >::vertex_rbegin (  )  const [inline]

Gets a reverse node iterator on the first node.

Remarks:
Returns vertex_rend() if graph is empty.

Definition at line 663 of file graph.tpp.

References claw::graph< S, A, Comp >::vertex_end().

00664 {
00665   return reverse_vertex_iterator( vertex_end() );
00666 } // graph::vertex_rbegin()

template<class S, class A, class Comp>
claw::graph< S, A, Comp >::reverse_vertex_iterator claw::graph< S, A, Comp >::vertex_rend (  )  const [inline]

Gets a reverse node iterator past the last node.

Definition at line 674 of file graph.tpp.

References claw::graph< S, A, Comp >::vertex_begin().

00675 {
00676   return reverse_vertex_iterator( vertex_begin() );
00677 } // graph::vertex_rend()

template<class S, class A, class Comp>
claw::graph< S, A, Comp >::reverse_vertex_iterator claw::graph< S, A, Comp >::vertex_rbegin ( const vertex_type s  )  const [inline]

Gets a reverse node iterator just after a particular node.

Remarks:
Returns vertex_rend() if s is not found.

Definition at line 686 of file graph.tpp.

References claw::graph< S, A, Comp >::vertex_begin(), and claw::graph< S, A, Comp >::vertex_end().

00687 {
00688   vertex_iterator it = vertex_begin(s);
00689 
00690   if (it != vertex_end())
00691     ++it;
00692 
00693   return reverse_vertex_iterator( it );
00694 } // graph::vertex_rbegin()

template<class S, class A, class Comp>
claw::graph< S, A, Comp >::edge_iterator claw::graph< S, A, Comp >::edge_begin (  )  const [inline]

Gets an edge iterator on the first edge.

Remarks:
Return edge_end() if there's no edge in the graph.

Definition at line 703 of file graph.tpp.

References claw::graph< S, A, Comp >::edge_end(), and claw::graph< S, A, Comp >::m_edges.

Referenced by claw::graph< S, A, Comp >::edge_rbegin(), and claw::graph< S, A, Comp >::edge_rend().

00704 {
00705   bool ok = false;
00706   typename graph_content::const_iterator it_s;
00707   it_s = m_edges.begin();
00708 
00709   while ( (it_s != m_edges.end()) && !ok )
00710     if ( it_s->second.empty() )
00711       ++it_s;
00712     else
00713       ok = true;
00714 
00715   if (ok)
00716     return edge_iterator( m_edges.begin(), m_edges.end(), it_s, 
00717                           it_s->second.begin() );
00718   else
00719     return edge_end();
00720                                                  
00721 } // graph::edge_begin()

template<class S, class A, class Comp>
claw::graph< S, A, Comp >::edge_iterator claw::graph< S, A, Comp >::edge_end (  )  const [inline]

Gets an edge iterator after the last edge.

Definition at line 729 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

Referenced by claw::graph< S, A, Comp >::edge_begin(), and claw::graph< S, A, Comp >::edge_rbegin().

00730 {
00731   return edge_iterator( m_edges.begin(), m_edges.end(), m_edges.end(),
00732                         typename neighbours_list::const_iterator() );
00733 } // graph::edge_end()

template<class S, class A, class Comp>
claw::graph< S, A, Comp >::edge_iterator claw::graph< S, A, Comp >::edge_begin ( const vertex_type s1,
const vertex_type s2 
) const [inline]

Gets en iterator on a particular edge .

Remarks:
Return edge_end() if edge (s1,s2) is not found.

Definition at line 742 of file graph.tpp.

References claw::graph< S, A, Comp >::edge_end(), claw::graph< S, A, Comp >::edge_exists(), and claw::graph< S, A, Comp >::m_edges.

00744 {
00745   if ( edge_exists(s1, s2) )
00746     {
00747       typename graph_content::const_iterator it_s1;
00748 
00749       it_s1 = m_edges.find(s1);
00750       return edge_iterator( m_edges.begin(), m_edges.end(), it_s1, 
00751                             it_s1->second.find(s2) );
00752     }
00753   else
00754     return edge_end();
00755 } // graph::edge_()

template<class S, class A, class Comp>
claw::graph< S, A, Comp >::reverse_edge_iterator claw::graph< S, A, Comp >::edge_rbegin (  )  const [inline]

Gets a reverse edge iterator on the first edge.

Remarks:
Returns redge_end() if there's no edge in the graph.

Definition at line 764 of file graph.tpp.

References claw::graph< S, A, Comp >::edge_end().

00765 {
00766   return reverse_edge_iterator( edge_end() );
00767 } // graph::edge_rbegin()

template<class S, class A, class Comp>
claw::graph< S, A, Comp >::reverse_edge_iterator claw::graph< S, A, Comp >::edge_rend (  )  const [inline]

Gets a reverse edge iterator after the last edge.

Definition at line 775 of file graph.tpp.

References claw::graph< S, A, Comp >::edge_begin().

00776 {
00777   return reverse_edge_iterator( edge_begin() );
00778 } // graph::edge_rend()

template<class S, class A, class Comp>
claw::graph< S, A, Comp >::reverse_edge_iterator claw::graph< S, A, Comp >::edge_rbegin ( const vertex_type s1,
const vertex_type s2 
) const [inline]

Gets a reverse edge iterator on a particular edge.

Remarks:
Returns redge_end() if edge (s1,s2) is not found.

Definition at line 788 of file graph.tpp.

References claw::graph< S, A, Comp >::edge_begin(), and claw::graph< S, A, Comp >::edge_end().

00789 {
00790   reverse_edge_iterator it = edge_begin(s1, s2);
00791 
00792   if ( it != edge_end() )
00793     ++it;
00794 
00795   return reverse_edge_iterator( it );
00796 } // graph::edge_rbegin()

template<class S, class A, class Comp>
const claw::graph< S, A, Comp >::edge_type & claw::graph< S, A, Comp >::label ( const vertex_type s,
const vertex_type r 
) const [inline]

Récupère l'étiquette d'une arête.

Parameters:
s sommet de départ.
r sommet d'arrivée.

Definition at line 806 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

00808 { 
00809   typename graph_content::const_iterator it_s = m_edges.find(s);
00810 
00811   if ( it_s == m_edges.end() )
00812     throw graph_exception
00813       ("claw::graph::label(): unkonwn source vertex.");
00814   else 
00815     {
00816       typename neighbours_list::const_iterator it_r = it_s->second.find(r);
00817 
00818       if ( it_r == it_s->second.end() )
00819         throw graph_exception
00820           ("claw::graph::label(): destination is not a neighbor.");
00821       else
00822         return it_r->second; 
00823     }
00824 } // graph::label()

template<class S, class A, class Comp>
unsigned int claw::graph< S, A, Comp >::outer_degree ( const vertex_type s  )  const [inline]

Récupère le degré sortant d'un sommet.

Parameters:
s sommet à consider.

Definition at line 833 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

00834 { 
00835   typename graph_content::const_iterator it = m_edges.find(s);
00836   
00837   if (it == m_edges.end())
00838     throw graph_exception("claw::graph::outer_degree(): unknown vertex.");
00839   else
00840     return it->second.size(); 
00841 } // graph::outer_degree()

template<class S, class A, class Comp>
unsigned int claw::graph< S, A, Comp >::inner_degree ( const vertex_type s  )  const [inline]

Récupère le degré entrant d'un sommet.

Parameters:
s sommet à consider.

Definition at line 850 of file graph.tpp.

References claw::graph< S, A, Comp >::m_inner_degrees.

00851 { 
00852   typename std::map<S, unsigned int, Comp>::const_iterator it;
00853   it = m_inner_degrees.find(s);
00854   
00855   if (it == m_inner_degrees.end())
00856     throw graph_exception
00857       ("claw::graph::inner_degree(): unkown vertex.");
00858   else
00859     return it->second; 
00860 } // graph::inner_degree()

template<class S, class A, class Comp>
unsigned int claw::graph< S, A, Comp >::vertices_count (  )  const [inline]

Gets the number of vertices.

Definition at line 867 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

00868 {
00869   return m_edges.size(); 
00870 } // graph::vertices_count()

template<class S, class A, class Comp>
unsigned int claw::graph< S, A, Comp >::edges_count (  )  const [inline]

Gets the number of edges.

Definition at line 877 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges_count.

00878 {
00879   return m_edges_count; 
00880 } // graph::edges_count()


Member Data Documentation

template<class S, class A, class Comp = std::less<S>>
graph_content claw::graph< S, A, Comp >::m_edges [private]

template<class S, class A, class Comp = std::less<S>>
std::map<vertex_type, unsigned int, vertex_compare> claw::graph< S, A, Comp >::m_inner_degrees [private]

template<class S, class A, class Comp = std::less<S>>
unsigned int claw::graph< S, A, Comp >::m_edges_count [private]

Number of edges.

Definition at line 278 of file graph.hpp.

Referenced by claw::graph< S, A, Comp >::add_edge(), and claw::graph< S, A, Comp >::edges_count().


The documentation for this class was generated from the following files:

Generated on Thu May 22 21:07:37 2008 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.5.5