CLAW Library (a C++ Library Absolutely Wonderful) 1.5.5
|
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:
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 | ( | ) |
Constructor.
Definition at line 484 of file graph.tpp.
: m_edges_count(0) { } // 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() |
||
) |
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.
{ if ( !edge_exists(s1, s2) ) { // s2 is not a neighbor of s1 ++m_edges_count; add_vertex(s1); add_vertex(s2); // in all cases, s2 as one more inner edge ++m_inner_degrees[s2]; } m_edges[s1][s2] = e; } // graph::add_edge()
void claw::graph< S, A, Comp >::add_vertex | ( | const vertex_type & | s | ) |
claw::graph< S, A, Comp >::edge_iterator claw::graph< S, A, Comp >::edge_begin | ( | ) | const |
Get an edge iterator on the first edge.
Definition at line 671 of file graph.tpp.
{ bool ok = false; typename graph_content::const_iterator it_s; it_s = m_edges.begin(); while ( (it_s != m_edges.end()) && !ok ) if ( it_s->second.empty() ) ++it_s; else ok = true; if (ok) return edge_iterator( m_edges.begin(), m_edges.end(), it_s, it_s->second.begin() ); else return edge_end(); } // graph::edge_begin()
claw::graph< S, A, Comp >::edge_iterator claw::graph< S, A, Comp >::edge_begin | ( | const vertex_type & | s1, |
const vertex_type & | s2 | ||
) | const |
Get en iterator on a particular edge .
Definition at line 711 of file graph.tpp.
{ if ( edge_exists(s1, s2) ) { typename graph_content::const_iterator it_s1; it_s1 = m_edges.find(s1); return edge_iterator( m_edges.begin(), m_edges.end(), it_s1, it_s1->second.find(s2) ); } else return edge_end(); } // graph::edge_()
claw::graph< S, A, Comp >::edge_iterator claw::graph< S, A, Comp >::edge_end | ( | ) | const |
bool claw::graph< S, A, Comp >::edge_exists | ( | const vertex_type & | s, |
const vertex_type & | r | ||
) | const |
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 |
Get a reverse edge iterator on a particular edge.
Definition at line 756 of file graph.tpp.
{ reverse_edge_iterator it = edge_begin(s1, s2); if ( it != edge_end() ) ++it; return reverse_edge_iterator( it ); } // graph::edge_rbegin()
claw::graph< S, A, Comp >::reverse_edge_iterator claw::graph< S, A, Comp >::edge_rbegin | ( | ) | const |
Get a reverse edge iterator on the first edge.
Definition at line 732 of file graph.tpp.
{ return reverse_edge_iterator( edge_end() ); } // graph::edge_rbegin()
claw::graph< S, A, Comp >::reverse_edge_iterator claw::graph< S, A, Comp >::edge_rend | ( | ) | const |
Get a reverse edge iterator after the last edge.
Definition at line 743 of file graph.tpp.
{ return reverse_edge_iterator( edge_begin() ); } // graph::edge_rend()
std::size_t claw::graph< S, A, Comp >::edges_count | ( | ) | const |
Get the number of edges.
Definition at line 843 of file graph.tpp.
{ return m_edges_count; } // graph::edges_count()
std::size_t claw::graph< S, A, Comp >::inner_degree | ( | const vertex_type & | s | ) | const |
Get the inner degree of a vertex.
s | The vertex |
Definition at line 816 of file graph.tpp.
{ typename std::map<S, std::size_t, Comp>::const_iterator it; it = m_inner_degrees.find(s); if (it == m_inner_degrees.end()) throw graph_exception ("claw::graph::inner_degree(): unkown vertex."); else return it->second; } // 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 |
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.
{ typename graph_content::const_iterator it_s = m_edges.find(s); if ( it_s == m_edges.end() ) throw graph_exception ("claw::graph::label(): unkonwn source vertex."); else { typename neighbours_list::const_iterator it_r = it_s->second.find(r); if ( it_r == it_s->second.end() ) throw graph_exception ("claw::graph::label(): destination is not a neighbor."); else return it_r->second; } } // graph::label()
void claw::graph< S, A, Comp >::neighbours | ( | const vertex_type & | s, |
std::vector< vertex_type > & | v | ||
) | const |
Get the neighbors of a vertex.
s | The vertex. |
v | (out) The neighbors. |
std::size_t claw::graph< S, A, Comp >::outer_degree | ( | const vertex_type & | s | ) | const |
Get the outter degree of a vertex.
s | The vertex. |
claw::graph< S, A, Comp >::vertex_iterator claw::graph< S, A, Comp >::vertex_begin | ( | ) | const |
Get a node iterator on the first node.
Definition at line 596 of file graph.tpp.
{ return vertex_iterator( m_edges.begin() ); } // graph::vertex_begin()
claw::graph< S, A, Comp >::vertex_iterator claw::graph< S, A, Comp >::vertex_begin | ( | const vertex_type & | s | ) | const |
Get a node iterator on a particular node.
Definition at line 619 of file graph.tpp.
{ return vertex_iterator( m_edges.find(s) ); } // graph::vertex_begin()
claw::graph< S, A, Comp >::vertex_iterator claw::graph< S, A, Comp >::vertex_end | ( | ) | const |
Get a node iterator past the last node.
Definition at line 607 of file graph.tpp.
{ return vertex_iterator( m_edges.end() ); } // graph::vertex_end()
claw::graph< S, A, Comp >::reverse_vertex_iterator claw::graph< S, A, Comp >::vertex_rbegin | ( | ) | const |
Get a reverse node iterator on the first node.
Definition at line 631 of file graph.tpp.
{ return reverse_vertex_iterator( vertex_end() ); } // graph::vertex_rbegin()
claw::graph< S, A, Comp >::reverse_vertex_iterator claw::graph< S, A, Comp >::vertex_rbegin | ( | const vertex_type & | s | ) | const |
Get a reverse node iterator just after a particular node.
Definition at line 654 of file graph.tpp.
{ vertex_iterator it = vertex_begin(s); if (it != vertex_end()) ++it; return reverse_vertex_iterator( it ); } // graph::vertex_rbegin()
claw::graph< S, A, Comp >::reverse_vertex_iterator claw::graph< S, A, Comp >::vertex_rend | ( | ) | const |
Get a reverse node iterator past the last node.
Definition at line 642 of file graph.tpp.
{ return reverse_vertex_iterator( vertex_begin() ); } // graph::vertex_rend()
void claw::graph< S, A, Comp >::vertices | ( | std::vector< vertex_type > & | v | ) | const |
std::size_t claw::graph< S, A, Comp >::vertices_count | ( | ) | const |
graph_content claw::graph< S, A, Comp >::m_edges [private] |
std::size_t claw::graph< S, A, Comp >::m_edges_count [private] |
std::map<vertex_type, std::size_t, vertex_compare> claw::graph< S, A, Comp >::m_inner_degrees [private] |