#include <graph.hpp>
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_type & | label (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... |
typedef S claw::graph< S, A, Comp >::vertex_type |
typedef A claw::graph< S, A, Comp >::edge_type |
typedef Comp claw::graph< S, A, Comp >::vertex_compare |
typedef std::map<vertex_type, edge_type, vertex_compare> claw::graph< S, A, Comp >::neighbours_list |
typedef std::map<vertex_type, neighbours_list, vertex_compare> claw::graph< S, A, Comp >::graph_content |
typedef claw::graph<vertex_type, edge_type, vertex_compare> claw::graph< S, A, Comp >::self_type |
typedef graph_vertex_iterator claw::graph< S, A, Comp >::vertex_iterator |
typedef graph_edge_iterator claw::graph< S, A, Comp >::edge_iterator |
typedef std::reverse_iterator<vertex_iterator> claw::graph< S, A, Comp >::reverse_vertex_iterator |
typedef std::reverse_iterator<edge_iterator> claw::graph< S, A, Comp >::reverse_edge_iterator |
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]
void claw::graph< S, A, Comp >::add_edge | ( | const vertex_type & | s1, | |
const vertex_type & | s2, | |||
const edge_type & | e | |||
) | [inline] |
Ajoute un arc.
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()
void claw::graph< S, A, Comp >::add_vertex | ( | const vertex_type & | s | ) | [inline] |
Ajoute un sommet.
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()
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.
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()
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.
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()
void claw::graph< S, A, Comp >::vertices | ( | std::vector< vertex_type > & | v | ) | const [inline] |
Récupère la liste d'adjacence.
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()
claw::graph< S, A, Comp >::vertex_iterator claw::graph< S, A, Comp >::vertex_begin | ( | ) | const [inline] |
Gets a node iterator on the first node.
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()
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()
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.
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()
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.
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()
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()
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.
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()
claw::graph< S, A, Comp >::edge_iterator claw::graph< S, A, Comp >::edge_begin | ( | ) | const [inline] |
Gets an edge iterator on the first edge.
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()
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()
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 .
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_()
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.
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()
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()
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.
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()
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.
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()
unsigned int claw::graph< S, A, Comp >::outer_degree | ( | const vertex_type & | s | ) | const [inline] |
Récupère le degré sortant d'un sommet.
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()
unsigned int claw::graph< S, A, Comp >::inner_degree | ( | const vertex_type & | s | ) | const [inline] |
Récupère le degré entrant d'un sommet.
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()
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()
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()
graph_content claw::graph< S, A, Comp >::m_edges [private] |
edge_typedjacency list.
Definition at line 272 of file graph.hpp.
Referenced by claw::graph< S, A, Comp >::add_edge(), claw::graph< S, A, Comp >::add_vertex(), claw::graph< S, A, Comp >::edge_begin(), claw::graph< S, A, Comp >::edge_end(), claw::graph< S, A, Comp >::edge_exists(), claw::graph< S, A, Comp >::label(), claw::graph< S, A, Comp >::neighbours(), claw::graph< S, A, Comp >::outer_degree(), claw::graph< S, A, Comp >::vertex_begin(), claw::graph< S, A, Comp >::vertex_end(), claw::graph< S, A, Comp >::vertices(), and claw::graph< S, A, Comp >::vertices_count().
std::map<vertex_type, unsigned int, vertex_compare> claw::graph< S, A, Comp >::m_inner_degrees [private] |
Degré entrants des sommets.
Definition at line 275 of file graph.hpp.
Referenced by claw::graph< S, A, Comp >::add_edge(), claw::graph< S, A, Comp >::add_vertex(), and claw::graph< S, A, Comp >::inner_degree().
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().