A class to represent a graph. More...
#include <graph.hpp>
Classes | |
class | graph_edge_iterator |
Iterator on the graph's edges. More... | |
class | graph_vertex_iterator |
Iterator on the graph's vertices. More... | |
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 |
The adjacency list of a vertex. vertex_type is the target vertex, edge_type is the label on the edge. | |
typedef std::map< vertex_type, neighbours_list, vertex_compare > | graph_content |
The whole graph: an adjacency list for each vertex. | |
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=edge_type()) |
Add an edge in the graph. | |
void | add_vertex (const vertex_type &s) |
Add a vertex. | |
bool | edge_exists (const vertex_type &s, const vertex_type &r) const |
Check if there is an edge linking to vertices. | |
void | neighbours (const vertex_type &s, std::vector< vertex_type > &v) const |
Get the neighbors of a vertex. | |
void | vertices (std::vector< vertex_type > &v) const |
Get all the vertices. | |
vertex_iterator | vertex_begin () const |
Get a node iterator on the first node. | |
vertex_iterator | vertex_end () const |
Get a node iterator past the last node. | |
vertex_iterator | vertex_begin (const vertex_type &s) const |
Get a node iterator on a particular node. | |
reverse_vertex_iterator | vertex_rbegin () const |
Get a reverse node iterator on the first node. | |
reverse_vertex_iterator | vertex_rend () const |
Get a reverse node iterator past the last node. | |
reverse_vertex_iterator | vertex_rbegin (const vertex_type &s) const |
Get a reverse node iterator just after a particular node. | |
edge_iterator | edge_begin () const |
Get an edge iterator on the first edge. | |
edge_iterator | edge_end () const |
Get an edge iterator after the last edge. | |
edge_iterator | edge_begin (const vertex_type &s1, const vertex_type &s2) const |
Get en iterator on a particular edge . | |
reverse_edge_iterator | edge_rbegin () const |
Get a reverse edge iterator on the first edge. | |
reverse_edge_iterator | edge_rend () const |
Get a reverse edge iterator after the last edge. | |
reverse_edge_iterator | edge_rbegin (const vertex_type &s1, const vertex_type &s2) const |
Get a reverse edge iterator on a particular edge. | |
const edge_type & | label (const vertex_type &s, const vertex_type &r) const |
Get the label of an edge. | |
std::size_t | outer_degree (const vertex_type &s) const |
Get the outter degree of a vertex. | |
std::size_t | inner_degree (const vertex_type &s) const |
Get the inner degree of a vertex. | |
std::size_t | vertices_count () const |
Get the number of vertices. | |
std::size_t | edges_count () const |
Get the number of edges. | |
Private Attributes | |
graph_content | m_edges |
The content of the graph (edges and vertices. | |
std::map< vertex_type, std::size_t, vertex_compare > | m_inner_degrees |
Inner degree of the vertices. | |
std::size_t | m_edges_count |
Number of edges. |
A class to represent a graph.
Constraints on the template parameters:
Definition at line 77 of file graph.hpp.
typedef graph_edge_iterator claw::graph< S, A, Comp >::edge_iterator |
typedef A claw::graph< S, A, Comp >::edge_type |
typedef std::map<vertex_type, neighbours_list, vertex_compare> claw::graph< S, A, Comp >::graph_content |
typedef std::map<vertex_type, edge_type, vertex_compare> claw::graph< S, A, Comp >::neighbours_list |
typedef std::reverse_iterator<edge_iterator> claw::graph< S, A, Comp >::reverse_edge_iterator |
typedef std::reverse_iterator<vertex_iterator> claw::graph< S, A, Comp >::reverse_vertex_iterator |
typedef claw::graph<vertex_type, edge_type, vertex_compare> claw::graph< S, A, Comp >::self_type |
typedef Comp claw::graph< S, A, Comp >::vertex_compare |
typedef graph_vertex_iterator claw::graph< S, A, Comp >::vertex_iterator |
typedef S claw::graph< S, A, Comp >::vertex_type |
claw::graph< S, A, Comp >::graph | ( | ) | [inline] |
Constructor.
Definition at line 484 of file graph.tpp.
00485 : m_edges_count(0) 00486 { 00487 00488 } // graph::graph() [constructor]
void claw::graph< S, A, Comp >::add_edge | ( | const vertex_type & | s1, | |
const vertex_type & | s2, | |||
const edge_type & | e = edge_type() | |||
) | [inline] |
Add an edge in the graph.
s1 | Tail of the edge. | |
s2 | Head of the edgre. | |
e | The label on the edge. |
Definition at line 499 of file graph.tpp.
00500 { 00501 if ( !edge_exists(s1, s2) ) 00502 { 00503 // s2 is not a neighbor of s1 00504 ++m_edges_count; 00505 00506 add_vertex(s1); 00507 add_vertex(s2); 00508 00509 // in all cases, s2 as one more inner edge 00510 ++m_inner_degrees[s2]; 00511 } 00512 00513 m_edges[s1][s2] = e; 00514 } // graph::add_edge()
void claw::graph< S, A, Comp >::add_vertex | ( | const vertex_type & | s | ) | [inline] |
Add a vertex.
s | The vertex to add. |
Definition at line 522 of file graph.tpp.
References claw::graph< S, A, Comp >::m_edges, and claw::graph< S, A, Comp >::m_inner_degrees.
00523 { 00524 std::pair<S, neighbours_list> p; 00525 00526 if (m_edges.find(s) == m_edges.end()) 00527 { 00528 // Add the vertex in the adjacency list. 00529 p.first = s; 00530 m_edges.insert(p); 00531 m_inner_degrees[s] = 0; 00532 } 00533 } // graph::add_vertex()
claw::graph< S, A, Comp >::edge_iterator claw::graph< S, A, Comp >::edge_begin | ( | const vertex_type & | s1, | |
const vertex_type & | s2 | |||
) | const [inline] |
Get en iterator on a particular edge .
Definition at line 711 of file graph.tpp.
00712 { 00713 if ( edge_exists(s1, s2) ) 00714 { 00715 typename graph_content::const_iterator it_s1; 00716 00717 it_s1 = m_edges.find(s1); 00718 return edge_iterator( m_edges.begin(), m_edges.end(), it_s1, 00719 it_s1->second.find(s2) ); 00720 } 00721 else 00722 return edge_end(); 00723 } // graph::edge_()
claw::graph< S, A, Comp >::edge_iterator claw::graph< S, A, Comp >::edge_begin | ( | ) | const [inline] |
Get an edge iterator on the first edge.
Definition at line 671 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_rend().
00672 { 00673 bool ok = false; 00674 typename graph_content::const_iterator it_s; 00675 it_s = m_edges.begin(); 00676 00677 while ( (it_s != m_edges.end()) && !ok ) 00678 if ( it_s->second.empty() ) 00679 ++it_s; 00680 else 00681 ok = true; 00682 00683 if (ok) 00684 return edge_iterator( m_edges.begin(), m_edges.end(), it_s, 00685 it_s->second.begin() ); 00686 else 00687 return edge_end(); 00688 00689 } // graph::edge_begin()
claw::graph< S, A, Comp >::edge_iterator claw::graph< S, A, Comp >::edge_end | ( | ) | const [inline] |
Get an edge iterator after the last edge.
Definition at line 697 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().
00698 { 00699 return edge_iterator( m_edges.begin(), m_edges.end(), m_edges.end(), 00700 typename neighbours_list::const_iterator() ); 00701 } // graph::edge_end()
bool claw::graph< S, A, Comp >::edge_exists | ( | const vertex_type & | s, | |
const vertex_type & | r | |||
) | const [inline] |
Check if there is an edge linking to vertices.
s | Vertex at the tail of the edge. | |
r | Vertex at the head of the edge. |
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] |
Get a reverse edge iterator on a particular edge.
Definition at line 756 of file graph.tpp.
00757 { 00758 reverse_edge_iterator it = edge_begin(s1, s2); 00759 00760 if ( it != edge_end() ) 00761 ++it; 00762 00763 return reverse_edge_iterator( it ); 00764 } // graph::edge_rbegin()
claw::graph< S, A, Comp >::reverse_edge_iterator claw::graph< S, A, Comp >::edge_rbegin | ( | ) | const [inline] |
Get a reverse edge iterator on the first edge.
Definition at line 732 of file graph.tpp.
References claw::graph< S, A, Comp >::edge_end().
00733 { 00734 return reverse_edge_iterator( edge_end() ); 00735 } // graph::edge_rbegin()
claw::graph< S, A, Comp >::reverse_edge_iterator claw::graph< S, A, Comp >::edge_rend | ( | ) | const [inline] |
Get a reverse edge iterator after the last edge.
Definition at line 743 of file graph.tpp.
References claw::graph< S, A, Comp >::edge_begin().
00744 { 00745 return reverse_edge_iterator( edge_begin() ); 00746 } // graph::edge_rend()
std::size_t claw::graph< S, A, Comp >::edges_count | ( | ) | const [inline] |
Get the number of edges.
Definition at line 843 of file graph.tpp.
References claw::graph< S, A, Comp >::m_edges_count.
00844 { 00845 return m_edges_count; 00846 } // graph::edges_count()
std::size_t claw::graph< S, A, Comp >::inner_degree | ( | const vertex_type & | s | ) | const [inline] |
Get the inner degree of a vertex.
s | The vertex |
Definition at line 816 of file graph.tpp.
References claw::graph< S, A, Comp >::m_inner_degrees.
00817 { 00818 typename std::map<S, std::size_t, Comp>::const_iterator it; 00819 it = m_inner_degrees.find(s); 00820 00821 if (it == m_inner_degrees.end()) 00822 throw graph_exception 00823 ("claw::graph::inner_degree(): unkown vertex."); 00824 else 00825 return it->second; 00826 } // graph::inner_degree()
const claw::graph< S, A, Comp >::edge_type & claw::graph< S, A, Comp >::label | ( | const vertex_type & | s, | |
const vertex_type & | r | |||
) | const [inline] |
Get the label of an edge.
s | The vertex at the tail of the edge. | |
r | The vertex at the head of the edge. |
Definition at line 775 of file graph.tpp.
00776 { 00777 typename graph_content::const_iterator it_s = m_edges.find(s); 00778 00779 if ( it_s == m_edges.end() ) 00780 throw graph_exception 00781 ("claw::graph::label(): unkonwn source vertex."); 00782 else 00783 { 00784 typename neighbours_list::const_iterator it_r = it_s->second.find(r); 00785 00786 if ( it_r == it_s->second.end() ) 00787 throw graph_exception 00788 ("claw::graph::label(): destination is not a neighbor."); 00789 else 00790 return it_r->second; 00791 } 00792 } // graph::label()
void claw::graph< S, A, Comp >::neighbours | ( | const vertex_type & | s, | |
std::vector< vertex_type > & | v | |||
) | const [inline] |
Get the neighbors of a vertex.
s | The vertex. | |
v | (out) The neighbors. |
Definition at line 561 of file graph.tpp.
00562 { 00563 typename graph_content::const_iterator it_s = m_edges.find(s); 00564 v.clear(); 00565 00566 if ( it_s != m_edges.end() ) 00567 { 00568 v.resize( it_s->second.size() ); 00569 std::transform( it_s->second.begin(), it_s->second.end(), v.begin(), 00570 const_first<S,A>() ); 00571 } 00572 } // graph::neighbours()
std::size_t claw::graph< S, A, Comp >::outer_degree | ( | const vertex_type & | s | ) | const [inline] |
Get the outter degree of a vertex.
s | The vertex. |
Definition at line 800 of file graph.tpp.
References claw::graph< S, A, Comp >::m_edges.
claw::graph< S, A, Comp >::vertex_iterator claw::graph< S, A, Comp >::vertex_begin | ( | const vertex_type & | s | ) | const [inline] |
Get a node iterator on a particular node.
Definition at line 619 of file graph.tpp.
References claw::graph< S, A, Comp >::m_edges.
00620 { 00621 return vertex_iterator( m_edges.find(s) ); 00622 } // graph::vertex_begin()
claw::graph< S, A, Comp >::vertex_iterator claw::graph< S, A, Comp >::vertex_begin | ( | ) | const [inline] |
Get a node iterator on the first node.
Definition at line 596 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().
00597 { 00598 return vertex_iterator( m_edges.begin() ); 00599 } // graph::vertex_begin()
claw::graph< S, A, Comp >::vertex_iterator claw::graph< S, A, Comp >::vertex_end | ( | ) | const [inline] |
Get a node iterator past the last node.
Definition at line 607 of file graph.tpp.
References claw::graph< S, A, Comp >::m_edges.
Referenced by claw::graph< S, A, Comp >::vertex_rbegin().
00608 { 00609 return vertex_iterator( m_edges.end() ); 00610 } // graph::vertex_end()
claw::graph< S, A, Comp >::reverse_vertex_iterator claw::graph< S, A, Comp >::vertex_rbegin | ( | const vertex_type & | s | ) | const [inline] |
Get a reverse node iterator just after a particular node.
Definition at line 654 of file graph.tpp.
References claw::graph< S, A, Comp >::vertex_begin(), and claw::graph< S, A, Comp >::vertex_end().
00655 { 00656 vertex_iterator it = vertex_begin(s); 00657 00658 if (it != vertex_end()) 00659 ++it; 00660 00661 return reverse_vertex_iterator( it ); 00662 } // graph::vertex_rbegin()
claw::graph< S, A, Comp >::reverse_vertex_iterator claw::graph< S, A, Comp >::vertex_rbegin | ( | ) | const [inline] |
Get a reverse node iterator on the first node.
Definition at line 631 of file graph.tpp.
References claw::graph< S, A, Comp >::vertex_end().
00632 { 00633 return reverse_vertex_iterator( vertex_end() ); 00634 } // graph::vertex_rbegin()
claw::graph< S, A, Comp >::reverse_vertex_iterator claw::graph< S, A, Comp >::vertex_rend | ( | ) | const [inline] |
Get a reverse node iterator past the last node.
Definition at line 642 of file graph.tpp.
References claw::graph< S, A, Comp >::vertex_begin().
00643 { 00644 return reverse_vertex_iterator( vertex_begin() ); 00645 } // graph::vertex_rend()
void claw::graph< S, A, Comp >::vertices | ( | std::vector< vertex_type > & | v | ) | const [inline] |
Get all the vertices.
v | (out) The vertices. |
Definition at line 580 of file graph.tpp.
References claw::graph< S, A, Comp >::m_edges.
std::size_t claw::graph< S, A, Comp >::vertices_count | ( | ) | const [inline] |
Get the number of vertices.
Definition at line 833 of file graph.tpp.
References claw::graph< S, A, Comp >::m_edges.
00834 { 00835 return m_edges.size(); 00836 } // graph::vertices_count()
graph_content claw::graph< S, A, Comp >::m_edges [private] |
The content of the graph (edges and vertices.
Definition at line 261 of file graph.hpp.
Referenced by 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 >::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::size_t claw::graph< S, A, Comp >::m_edges_count [private] |
Number of edges.
Definition at line 267 of file graph.hpp.
Referenced by claw::graph< S, A, Comp >::edges_count().
std::map<vertex_type, std::size_t, vertex_compare> claw::graph< S, A, Comp >::m_inner_degrees [private] |
Inner degree of the vertices.
Definition at line 264 of file graph.hpp.
Referenced by claw::graph< S, A, Comp >::add_vertex(), and claw::graph< S, A, Comp >::inner_degree().